3. 量子计算基础回顾
振幅估计的所有公式都建立在同一套量子力学符号之上。如果这套符号不统一，后面推导 QAE 时就会出现“相位到底加在哪、概率幅到底归谁”的混乱。本节把后续反复使用的记号一次性固定下来：量子比特写成什么、门作用在哪个位置、线路按什么顺序读、测量给出什么、并行性究竟“并行”在哪里。
量子比特与计算基
一个量子比特的状态写成二维复向量：
|ψ⟩ = α|0⟩ + β|1⟩, α, β ∈ ℂ, |α|² + |β|² = 1其中 {|0⟩, |1⟩} 是计算基，α、β 称为概率幅。约定：测量前谈振幅，测量后谈概率。振幅是复数，可以相消、可以干涉；概率是非负实数，只由 |α|² 得到。后续 QAE 要估计的那个量，本质就是一个特定子空间上的概率幅平方，因此“振幅”这个词不是修辞，而是被估计的对象本身。
多比特系统用张量积拼接。两个量子比特的基为 |00⟩、|01⟩、|10⟩、|11⟩，一般 n 比特系统的状态是 2ⁿ 个基态的叠加：
|ψ⟩ = Σ_{x∈{0,1}ⁿ} α_x |x⟩, Σ_x |α_x|² = 1这里 α_x 是基态 |x⟩ 的振幅。把下标 x 看作二进制串，就得到后续常用的整数索引写法。约定：比特串从左到右对应从高位到低位，即 |b₁b₂…bₙ⟩ 中 b₁ 是最高位。这个约定在画线路和写矩阵时必须前后一致。
量子门：酉算子与作用位置
量子门是作用在态上的酉算子 U，满足 U†U = I。单比特门写成 2×2 矩阵，作用在某个比特上时，其余比特保持不变。几个后续必用的门：
- Pauli-X：把 |0⟩ 与 |1⟩ 互换，矩阵 [[0,1],[1,0]]，相当于经典取反。
- Hadamard H：H|0⟩ = (|0⟩+|1⟩)/√2，H|1⟩ = (|0⟩−|1⟩)/√2，是制造叠加与干涉的核心工具。
- 相位门 S、T：只改 |1⟩ 分支的相位，S|1⟩ = i|1⟩，T|1⟩ = e^{iπ/4}|1⟩。
- 受控门：以控制比特为条件作用目标比特，如 CNOT、受控相位门。控制位为 |1⟩ 时施加目标门，否则不变。
约定：矩阵按列作用在态向量上，U|ψ⟩ 表示先准备 |ψ⟩ 再施加 U。线路图中时间从左向右流动，因此最左边的门最先作用。若一个门作用在第 k 个比特上，写作 U_k = I⊗…⊗U⊗…⊗I，U 位于第 k 个张量位置。这个下标写法在推导受控门和相位反冲时会反复出现。
量子线路与测量假设
量子线路是把门按时间顺序排列的序列，读法固定为：从左到右依次作用，等价于从右到左的矩阵乘积。若线路依次施加 U₁、U₂、U₃，则整体算子为 U = U₃U₂U₁。线路末端通常接测量。
测量假设包含两条：其一，在计算基下测量态 Σ_x α_x|x⟩，得到结果 x 的概率为 |α_x|²；其二，测量后态坍缩到 |x⟩，原有叠加被破坏。因此测量是线路中不可逆的一步，不能放在需要继续干涉的位置。若只测量部分比特，则未测部分保留条件态，这一条在 QAE 的辅助比特读取中会用到。
量子并行性：并行的是振幅，不是答案
量子并行性的准确含义是：一个作用于 n 比特的酉算子 U_f 可以同时把函数 f 在所有 2ⁿ 个输入上的取值编码进叠加态的振幅中。典型形式是
U_f: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩当输入寄存器处于均匀叠加 (1/√2ⁿ)Σ_x|x⟩ 时，一次 U_f 调用就让所有 x 的 f(x) 同时出现在输出寄存器中。但必须强调：并行得到的是振幅分布，不是可直接读出的 2ⁿ 个答案。直接测量只会随机给出一个 x 及其 f(x)，概率为 1/2ⁿ。要利用并行性，必须再设计干涉步骤，让目标答案的振幅被放大、非目标答案的振幅相消。振幅估计正是这类干涉步骤的定量版本：它不直接读出所有 f(x)，而是估计某个标记子空间的总概率幅平方。
为振幅估计准备的符号体系
把上面的约定收拢成后续直接可用的形式。设算子 A 作用在 n 个量子比特上，把初始态 |0⟩ⁿ 映射为
A|0⟩ⁿ = √(1−a)|ψ₀⟩ + √a|ψ₁⟩其中 |ψ₀⟩ 与 |ψ₁⟩ 是两个正交归一子空间中的态，a ∈ [0,1] 是待估计的概率。这里 √a 就是“好”子空间的振幅，a 是它的概率幅平方。振幅估计的目标是给出 a 的估计值 ã，并控制误差 ε 与成功概率。后续所有推导都沿用这套记号：A 是态准备算子，|ψ₁⟩ 是标记子空间，a 是被估计量，Q 是振幅放大算子，m 是读取用的辅助比特数。
| 符号 | 含义 | 取值/约束 |
|---|---|---|
| n | 目标寄存器比特数 | 正整数，基态数 2ⁿ |
| A | 态准备酉算子 | A|0⟩ⁿ = √(1−a)|ψ₀⟩+√a|ψ₁⟩ |
| a | 待估计概率 | a ∈ [0,1] |
| |ψ₁⟩ | 标记（好）子空间 | 与 |ψ₀⟩ 正交归一 |
| Q | 振幅放大算子 | Q = −A S₀ A† S_χ |
| m | 辅助读取比特数 | 精度 ε ~ 1/2ᵐ 量级 |
最后强调线路读法与矩阵顺序的一致性：若线路从左到右依次是 H、U_f、H，则整体算子为 H·U_f·H，作用在初始态上写作 H U_f H|0⟩。在后续推导 Q = −A S₀ A† S_χ 时，S₀ 与 S_χ 的作用位置、控制条件、以及它们与 A、A† 的先后关系，都直接决定振幅是被放大还是被抵消。把本节这套符号固定下来，后面每一章的公式都能在同一坐标系里对齐。