为什么Shor的分解算法中使用的量子位数如此之多？

Question

当准备算法的初始状态因子$n$时，他计算$q = 2^l$，使得$n^2 \leq q< 2n^2$。

然后，第一个寄存器包含$l$量子位。为什么要这么高。如果我们取$q=2^m$，使得$n \leq q< 2n$，我们有$m$量子位，它可以表示到$n$为止的所有整数。

为什么他把$l$量子位元大约是其中的一半($m$量子位元)就足够了？

Answer 1

最初存在一种状态叠加，并且电路中必须有足够的量子位，这样迭代后函数$f(X)=a^x$的正确周期就可以找到$a$是随机的，并且可以找到$N=pq$，也就是说，由于我们工作在一个循环群中，并且环绕可以通过积累引入假警报，所以应该在没有环绕效应的情况下进行收敛。

引用维基百科的话：

Shor的算法由两部分组成：

1. 在经典计算机上，将分解问题简化为求序问题。
2. 一种求解定序问题的量子算法。

该算法使用的量子电路是为$N$的每一种选择而设计的，$f(x) = a^x .$给定$N，$ find $Q = 2q$中所使用的随机量子寄存器的每一种选择都使得$$N^{2}leq Q<2N^{2}，$$，这意味着$Q /r>N，输入和输出量子位寄存器需要保持从$0$到$Q−1$的值的叠加，因此每一个都有$q$量子位元。使用所需的量子位数可能是所需的两倍，保证至少有$N$不同的$x$产生相同的$f(x)，$即使在$r$接近$N/2.$的周期内也是如此。