第十二章：量子计算

量子计算改变状态空间和允许的转移，但复杂度分析仍遵循相同框架：规定输入、uniform circuit、gate 集合、测量、错误概率和资源上界。

Qubit 与状态

一个 qubit 状态为

$$|\psi\rangle=\alpha|0\rangle+\beta|1\rangle, \qquad |\alpha|^2+|\beta|^2=1.$$

$n$ 个 qubit 的联合状态位于 $2^n$ 维复向量空间：

$$|\psi\rangle=\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle.$$

指数维描述不表示可以读出全部 $\alpha_x$。测量只得到一个经典结果 $x$，概率为 $|\alpha_x|^2$。

Unitary gate

封闭量子演化由 unitary 矩阵 $U$ 描述：

$$U^\dagger U=I.$$

Hadamard、phase、CNOT 等有限 gate 集可近似任意所需 unitary。complexity 需要规定近似精度；Solovay–Kitaev 类型结论说明有限 universal gate set 可用 polylog 开销近似一般 gate。

unitarity 意味着演化可逆。不可逆经典计算可通过保存中间信息嵌入可逆线路，再使用 uncomputation 清除辅助状态。

Measurement 与 no-cloning

标准基测量将状态投影到某个 $|x\rangle$，并改变后续状态。未知量子态不能被通用线路完美复制，即 no-cloning theorem。

因此经典算法中的调试、备份和多数投票不能原样应用。量子 error amplification 需要重新运行制备过程，而不能复制一次中间态。

BQP

$\mathsf{BQP}$ 包含由 polynomial-time uniform quantum circuit family 以有界错误判定的 language：

$$\begin{aligned} x\in L&\Rightarrow \Pr[C_x\text{ accepts}]\ge 2/3,\\ x\notin L&\Rightarrow \Pr[C_x\text{ accepts}]\le 1/3. \end{aligned}$$

错误可通过独立重复放大。已知关系包括

$$\mathsf P\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}.$$

这些包含是否严格大多未知。没有已知证据表明 NP-complete 问题属于 BQP。

Interference

量子算法的资源来自振幅干涉，不是枚举所有答案后一次读出。设计通常包含：

1. 制备多个计算路径的叠加；
2. 通过 phase 编码目标性质；
3. 使错误路径相消、目标路径相长；
4. 测量得到具有较高概率的经典信息。

若路径只形成叠加而未产生有用干涉，测量通常只得到一个近似随机样本。

Grover search

给定 oracle $f:[N]\to\{0,1\}$，寻找 marked item。经典随机查询需要 $\Theta(N)$ 次；Grover amplitude amplification 使用

$$O(\sqrt N)$$

次量子查询。

该界是最优的：quantum adversary 或 polynomial method 可证明 $\Omega(\sqrt N)$ lower bound。Grover 提供平方加速，不会把一般指数搜索自动变为多项式时间；若 $N=2^n$，复杂度仍为 $2^{n/2}$。

Shor algorithm

Shor 算法在量子多项式时间内完成整数分解和离散对数。核心是将问题归约到 period finding，再用 quantum Fourier transform 提取周期。

它对基于 factoring/discrete-log 的密码体系具有直接影响，但不适用于所有公钥密码。lattice-based 等后量子方案基于不同困难性假设。

Shor 给出 BQP 中的重要 function problem，却没有证明 factoring 不在经典 P；经典最优复杂度仍是算法研究结果而非无条件 lower bound。

Quantum query 与 communication

量子 query model 允许对 oracle 做 coherent query，可直接比较

$$D(f),\quad R(f),\quad Q(f).$$

某些 promise problem 存在更大分离；对 total Boolean function，这些 measure 之间受到多项式关系约束。

量子通信允许发送 qubit 和预共享 entanglement。entanglement 本身不能传递经典信息，但可改变通信协议，例如 superdense coding 和 teleportation 展示 classical bit、qubit 与 entanglement 的资源交换。

Noise 与 fault tolerance

复杂度类通常假设理想 gate。现实量子设备存在退相干、控制误差和测量错误。threshold theorem 表明：若物理错误率低于阈值，使用量子纠错可将长计算的逻辑错误压低，开销为可控的 polylog 因子。

完整资源估算需要区分：

• logical qubit 与 physical qubit；
• circuit depth 与受纠错后的时钟周期；
• gate count、connectivity 和 magic-state cost；
• 成功概率与重复次数。

渐进 BQP membership 不等于近期设备上可行。

本章自测

1. $n$ qubit 状态有 $2^n$ 个振幅，为什么不能一次读出全部振幅？
2. unitarity 为什么要求对经典不可逆计算进行可逆嵌入？
3. Grover 对 $2^n$ 大小搜索空间提供何种复杂度？
4. Shor 算法为什么没有证明 factoring 不在经典 P？
5. BQP upper bound 与容错量子机上的实际资源估算有何区别？

上一章：查询复杂度 · 下一章：Lower bound 与证明障碍 →