前沿物理学

量子算法（Shor、Grover）

量子算法利用干涉与纠缠加速特定问题，但并非让所有计算都更快。

量子算法由幺正门、测量和经典处理组成。其目标是在指定复杂度模型下，比已知最佳经典方法用更少资源得到有用输出分布。

T_{\mathrm{Grover}}=O(\sqrt{N}),\qquad T_{\mathrm{classique}}=O(N);\quad T_{\mathrm{Shor}}=\operatorname{poly}(n)\ (\text{portes quantiques})

定义: 量子加速

相对于明确的经典模型减少计算资源。加速主张须计入数据访问、输出抽样、误差及经典预处理和后处理成本。

态矢量在二维平面内旋转；这是理想Grover示意，不模拟含噪硬件。

Grover与Shor

Grover交替使用预言机与关于平均值的反演来放大标记态振幅；无结构搜索约需 $\sqrt N$ 次查询。Shor用量子傅里叶变换和周期寻找，在含纠错的门模型下以输入比特数的多项式时间分解整数。

例题: Grover查询次数

对 $N=10^4$ 项，估算经典预言机查询数与Grover查询量级。

解答

经典搜索量级为 $N=10^4$ 次；Grover为 $\sqrt N=10^2$ 次。常数因子取决于成功概率与预言机计数约定。

量子算法并不能让所有候选答案都可读出：测量只返回一个样本，因此必须通过干涉放大目标振幅。Grover搜索中，预言机标记目标，振幅放大每轮约将状态向目标旋转 $\pi/4$ ，查询次数为 $\sqrt N$ 量级。Shor算法利用模乘的周期性实现量子多项式时间因数分解，但实际优势取决于纠错和硬件。

查询复杂度并不等同于总运行时间：实际应用还要计入状态制备、纠错和读出成本。算法分析须明确预言机模型与输入分布；渐近优势可能在小数据或预处理成本高时消失。一个关键研究问题是，从理想电路转向容错机器后，哪些问题类别仍保有优势。

Grover对N个无结构项搜索需要多少量级查询？

关于Shor算法优势，哪项表述最准确？

Michael A. Nielsen, Isaac L. Chuang (2010). Quantum Computation and Quantum Information