几个月前，我写了一篇博文《量子计算机奈何不了公钥加密术》，要旨在于，大数分解的Shor算法利用量子傅里叶变换，但是量子傅里叶变换对角度的精度要求太高了。在数学讨论的时候，当然无所谓；但是在物理实现的时候，就会有问题。 

后来我在知乎上看到一个问题与此有关，“如何看待北大物院雷奕安 2019 年 6 月刊于《大学物理》的文章《数学量子位与物理量子位的差别》？”就回答了一下。主要论点还在博文《数学和物理的差别》里重复了一遍。

最近有位“子璇”网友就此问题与我进行了几次交流，他说Nielsen&Chuang《量子计算与量子信息》这本书里，已经明确讲述了误差的问题，还说：

我们这里讨论的核心问题在于，完全精确的2^N点DFT实现需要N位精度，那么输出误差存在常数上界的2^N点DFT实现也需要O(N)位精度吗？这个问题本质上和是否用量子方式实现无关。

要给输出误差构造一个上界的话，只需要计算“精确DFT算符”和“近似DFT算符”之差的范数。剩下的就只是简单的计算问题了。

所以，我又去翻了翻那本书，第五章《量子傅里叶变换及其应用》的前两个小节《5.1 量子傅里叶变换》和《5.2 相位估计》都是讲这个问题的。关于误差影响的叙述是5.1节的一道习题，具体如下：

练习5.6（量子傅里叶变换的近似） 量子傅里叶变换的量子线路结构，表面上需要量子门的精度达到量子比特数目的指数量级。然而，多项式规模的量子线路永远也不需要这样的指数精度。例如，令U是n量子比特上的理想傅里叶变换，而V是以精度$\Delta =1/p(n)$完成受控$R_k$门得到的结果，$p(n)$是某个多项式。证明：$E(U,V)=max_{|\psi \rangle} \left | \left | (U-V)|\psi \rangle  \right | \right|$ 的大小是 $\Theta (n^2/p(n))$，因此，每个门的多项式精度对保证输出状态的多项式精度是足够了。

第5.2节的相位估计更是重点讨论了误差问题。

我想了想，觉得这仍然不能解决“量子傅里叶变换需要很小的角度”这个问题。原因大致如下。

这本书中给出的结论是：假设$\phi$的精确值是$n$位，由量子傅里叶变换及其相位估计得到的误差为$\epsilon$，那么通过量子测量得到的输出$\phi$将精确到$n-\ln (2+\frac{1}{2\epsilon})\sim n -\ln 2 -  \ln \frac{1}{\epsilon}$，其成功的概率至少是$1-\epsilon$。

由此可知，如果有了误差$\epsilon$，那么对于$n$位的$\phi$来说，最后的$ n- \ln2 - \ln \frac{1}{\epsilon}$位仍然是不准确的，需要进行搜索才行。换句话说，量子方法将搜索范围减小到原来的$2^k$分之一，$k=n-\ln 2 - \ln \frac{1}{\epsilon}$。所以，$\epsilon$越小，缩减的效率越大；反过来说，如果$\epsilon$是个确定值，缩减的倍数也就是一个常数（虽然可能是一个挺大的常数），对于大数分解来说，仍然是没有太大帮助的。因为一个指数困难的问题，消减了常数倍以后，仍然是指数困难的。

换句话说，如果我有个1000位的密码，你有个方法能够快速地得到前500位，但是这个方法仍然不能让你打开我的保险箱。

所以，我认为这本书并没有解决“量子傅里叶变换需要很小的角度”这个问题，量子计算机仍然奈何不了公钥加密术。

附录1：子璇与我的对话

子璇回复姬扬 (作者) 

您的这个理解可能确实有点问题。Nielsen的书上明确写了不需要无限精度，因为QFT的输出态并不要求无限精度，从而较小的旋转角度对应的controlled-rotation gate可以忽略。详见219页（或新版的Exercise 5.6）。

子璇回复姬扬 (作者)

我又想了一个更容易理解的说法。只考虑精度的话，1000位的QFT和2^1000位的经典DFT是一样的。那么假设存在一个能存下如此巨量数据的经典计算机，难道它没法计算DFT了吗？这个经典DFT矩阵里面同样有2pi/2^1000的相位因子呀。

姬扬 (作者) 回复子璇

没有理解你这个说法。

我去翻看了原著，也不是很理解他的说法。

经典DFT是可以处理2pi/2^1000这个相位因子的，可以精确地处理。这个我们都同意。

量子QFT不能处理2pi/2^1000这个相位因子，因为这个值太小了，没法做。如果说，相位足够小就可以忽略，那么就意味着（这是我猜的）：无论多少位的QFT，都只需要比如说100位的算法来近似。这个听起来太怪了。

进行“相位估计”的时候，必须做2^k乘法，非常微小的差别也会被迅速放大的，那怎么能够在前面忽略呢？

子璇回复姬扬 (作者)

我们这里讨论的核心问题在于，完全精确的2^N点DFT实现需要N位精度，那么输出误差存在常数上界的2^N点DFT实现也需要O(N)位精度吗？这个问题本质上和是否用量子方式实现无关。

要给输出误差构造一个上界的话，只需要计算“精确DFT算符”和“近似DFT算符”之差的范数。剩下的就只是简单的计算问题了。

姬扬 (作者) 回复子璇

你这个问题，我没有想过。

完全精确的2^N点DFT实现需要N位精度，那么输出误差存在常数上界的2^N点DFT实现也需要O(N)位精度吗？

你的意思是说：为了实现这个目的，不需要N位精度，而是只需要比如说sqrt{N}的精度吗？只是比如啊，也许是N^{\alpha}，其中\alpha <1。

是这个意思吗？如果是，这个命题好像很强啊。

我没有想过这个问题。也许应该想一想。

另外，你这个误差上界是什么意思？可不可以举个具体些的例子。比如说M=a*b，用这个算法，可以得到 |a-a'|/a<1%。是这个意思吗？

子璇回复姬扬 (作者) 

误差上界差不多就是这个意思。这个命题对于做工程的人来说是很自然的，如定点FFT和低相位量化精度的波束赋形之类的应用都是用了类似的思想。

附录2：原著和中译本的叙述

原著，第221页

中译本，第203页

注意：中译本的说法“表面上需要用到的门的个数为量子比特数目指数的量级”是不对的，这里说的不是“门的个数”，而是“门的精度”需要达到指数量级。

我把这道练习题重新翻译如下：

练习5.6（量子傅里叶变换的近似） 量子傅里叶变换的量子线路结构，表面上需要量子门的精度达到量子比特数目的指数量级。然而，多项式规模的量子线路根本不需要这样的指数精度。例如，令$U$是$n$量子比特上的理想傅里叶变换，而$V$是以精度$\Delta =1/p(n)$完成受控$R_k$门得到的结果，$p(n)$是某个多项式。证明：$E(U,V)=max_{|\psi \rangle} \left | \left | (U-V)|\psi \rangle  \right | \right|$ 的大小是 $\Theta (n^2/p(n))$，因此，每个门的多项式精度就足以保证输出状态的多项式精度。