📚 课程目录第1章课程导入与问题定义

1. 课程导入与问题定义

在计算科学中，“抽样”几乎无处不在：估算一个概率分布下的期望值、判断一个集合中满足条件的元素比例、在蒙特卡洛模拟中近似积分。经典抽样依赖随机数发生器，通过重复采样把统计误差按 \(1/\sqrt{N}\) 的速度压低——想让精度提高 10 倍，就要多采 100 倍的样本。量子振幅估计（Quantum Amplitude Estimation, QAE）正是针对这类“估计某个概率/振幅”的问题，给出二次加速的量子算法框架：在理想条件下，达到精度 \(\epsilon\) 所需的量子采样次数约为 \(O(1/\epsilon)\)，而经典方法需要 \(O(1/\epsilon^2)\)。

要理解 QAE，先要把“经典抽样问题”翻译成“量子态形式”。设有一个布尔函数 \(f:\{0,1\}^n\to\{0,1\}\)，我们关心满足 \(f(x)=1\) 的元素比例 \(a\)。经典做法是均匀随机取 \(x\)，统计 \(f(x)=1\) 的频率。量子做法则构造一个算子 \(\mathcal{A}\)，作用在 \(n\) 个量子比特的零态上，产生

𝒜|0⟩_n = √(1-a)|Ψ₀⟩ + √a|Ψ₁⟩

其中 \(|Ψ₀⟩\) 与 \(|Ψ₁⟩\) 分别是“不满足”和“满足”两个子空间中的归一化状态，\(a\) 就是我们要估计的振幅平方（也就是概率）。QAE 的目标不是直接测量得到 0 或 1，而是通过相位估计的手段，把 \(\sqrt{a}\) 编码进一个可测量的相位角 \(\theta\)，其中 \(\sin^2\theta = a\)，再以高精度读出 \(\theta\)。

核心转换：经典抽样估计“频率”，量子振幅估计估计“角度”。一旦把目标量写成 \(\sin^2\theta\)，问题就从统计计数变成了相位估计，Grover 迭代带来的振幅放大正是加速的来源。

下图给出从经典抽样到量子振幅估计的整体问题映射与算法主干。左侧是经典蒙特卡洛的“采样—计数—频率”链路，右侧是 QAE 的“态制备—振幅放大—相位估计—反演”链路，中间用同一个目标量 \(a\) 连接，说明两者求解的是同一个问题，只是信息载体不同。

从图中可以看到，QAE 并不是“另一种随机抽样”，而是把抽样问题重构成相位估计问题。具体来说，算法需要两个关键组件：一是态制备算子 \(\mathcal{A}\)，它把目标函数 \(f\) 的判定逻辑（通常是一个布尔预言机）与均匀叠加态结合起来；二是 Grover 算子 \(Q = \mathcal{A} S_0 \mathcal{A}^{\dagger} S_\chi\)，其中 \(S_0\) 对零态施加相位翻转，\(S_\chi\) 对“满足”子空间施加相位翻转。反复施加 \(Q\) 会让状态在二维子空间内旋转，旋转角为 \(2\theta\)，于是 \(Q^k\mathcal{A}|0\rangle\) 中“满足”分量的概率变为 \(\sin^2((2k+1)\theta)\)。

接下来的问题就是：如何从这些旋转后的状态中把 \(\theta\) 读出来？这正是量子相位估计（QPE）的任务。标准 QAE 使用一个辅助寄存器，通过受控 \(Q^{2^j}\) 操作把相位信息写入辅助比特的相对相位，再做逆量子傅里叶变换，最后测量得到一个整数 \(y\)，满足 \(\theta \approx \pi y / 2^m\)（\(m\) 为辅助比特数）。由此得到 \(\tilde{a} = \sin^2(\pi y/2^m)\)。需要强调的是，测量结果是离散的，且存在以一定概率出现的偏差，因此实际实现中还要考虑置信区间与重复次数。

学习路径建议：先掌握“振幅编码”和“Grover 旋转”这两个几何图像，再进入 QPE 的电路细节，最后比较标准 QAE、最大似然 QAE（MLAE）与迭代 QAE（IQAE）在查询次数、辅助比特数和置信区间上的差异。本课程后续章节会按这条主线逐步展开。

为了让“问题定义”落到可操作的层面，可以用一个具体的小例子来校准理解。假设 \(n=4\)，共有 16 个候选元素，其中恰好 4 个满足 \(f(x)=1\)，于是真实 \(a=0.25\)，对应 \(\theta=\arcsin(0.5)=\pi/6\)。若辅助寄存器取 \(m=4\) 比特，则相位被量化为 \(2^4=16\) 个格点，理想测量结果应落在 \(y\approx 16\times(\pi/6)/(2\pi)=16/12\approx1.33\)，即最可能读到 \(y=1\) 或 \(y=2\)，反演得到 \(\sin^2(\pi/16)\approx0.038\) 或 \(\sin^2(2\pi/16)=0.146\)，与 0.25 有明显偏差。这说明：辅助比特数不足时，QAE 的估计分辨率受限；要分辨更细的 \(\theta\)，必须增加 \(m\)，或采用不需要大量辅助比特的迭代式变体。这个例子中的数值仅用于说明量化误差的量级，并非某次真实运行的测量记录。

由此可以归纳出本课程要解决的三个层次的问题。第一层是建模：给定一个计数/比例/期望值问题，如何写出对应的 \(f\)、构造 \(\mathcal{A}\)，并确认 \(a\) 与目标量之间的换算关系。第二层是算法：选择标准 QAE、MLAE 还是 IQAE，确定辅助比特数、重复次数与置信水平，估算查询复杂度。第三层是验证：在模拟器或真实设备上，如何从测量分布反演 \(\tilde{a}\)，如何构造置信区间，以及如何判断结果是否落在可接受误差内。这三层分别对应“写得出、算得准、验得了”，也是后续章节反复使用的分析框架。

最后需要建立正确的期望管理。QAE 的二次加速成立的前提包括：\(\mathcal{A}\) 可以被高效实现、\(Q\) 的受控版本可被干净地构造、噪声与退相干不占主导。在实际含噪设备上，深电路的 QPE 往往难以直接运行，这也是迭代式 QAE 与误差缓解技术受到关注的原因。学习本章时，先把“经典抽样—振幅编码—相位估计—反演”这条链路在概念上打通，再逐步加入电路级与工程级的细节，会比一上来就记忆公式更有效。