使用shor算法，我需要因数为15的量子比特有多少？

Question

根据this的说法，我知道我们需要4^n比特来模拟一个n量子比特的量子计算机。我想知道是否有可能在一台经典计算机上模拟shor的算法到因数15？使用shor算法因式15需要多少个量子比特？

Answer 1

就像经典的量子计算机一样，n比特可以表示2^n个不同的值。Shor在“周期查找子程序”中的算法使用两个寄存器，可能与2n + 1一样大，其中n是表示因数所需的位数。总的来说，你需要4n + 2量子比特来运行肖尔算法。

在lowering the qubit requirements上已经做了一些工作。该实现仅适用于一般数字的2n + 3量子比特。

要回答你的问题，你需要4个经典(或量子)比特来表示15，因此基本算法需要62个量子比特(你可能不会使用一些)。当然，在这个问题上有一些变通方法，而且由于预先已知的15的特殊性质，successfull experimental implementations只使用了7个量子比特，但这不能用于使用Shor算法分解的一般数字。

当你在经典的量子计算机上模拟量子计算机时，你通常希望用状态空间来表示它，其中每个基态对应于一个可能的输出。这需要虚数的2^n维向量，实际的位数取决于向量和虚数的实现。

Answer 2

你的问题的答案是-因数15 (5位数)，你需要两倍，即10个量子位。

有关shors算法如何工作的详细信息，请参阅此视频。如果你亲眼看到它在行动中，这应该会澄清你的疑虑。

截至2018年12月13日，使用Shor算法的纯/未稀释/参考实现破解的最大任意RSA模为2048位。RSA-2048支持破解。请参阅用于破解RSA - 2048 https://vimeo.com/306770425的实现演示。