1. 课程导入

在量子计算算法体系中，量子傅里叶变换（Quantum Fourier Transform, QFT）与相位估计（Quantum Phase Estimation, QPE）处于一个非常特殊的位置：它们本身是独立算法，同时又作为子程序被大量上层算法反复调用。理解这两者的关系，是进入量子算法世界的必经入口。

本课程的目标不是让读者记住若干公式，而是建立一条清晰的能力链：能写出 QFT 的电路、能推导 QPE 的精度与成功概率、能把 QPE 嵌入 Shor 分解、HHL 线性方程求解、量子模拟等场景，并能在真实噪声条件下判断结果是否可信。

一、为什么 QFT 与 QPE 是核心

经典傅里叶变换把时域信号映射到频域，量子傅里叶变换则把计算基态 |x⟩ 映射为相位叠加态。对 n 位输入，其定义为：

QFT|x⟩ = (1/√N) Σ_{y=0}^{N-1} e^{2πi·x·y/N} |y⟩,  N = 2^n

它的关键价值在于：经典 FFT 需要 O(N log N) 次运算，而 QFT 电路只需 O(n²) 个门，即对 N=2^n 呈指数级加速。但要注意，QFT 的输出是量子态，不能直接读出全部频谱——这正是它必须与相位估计、振幅放大等技巧配合的原因。

相位估计解决的正是"读出相位"的问题。给定酉算子 U 及其本征态 |u⟩，满足 U|u⟩ = e^{2πiφ}|u⟩，QPE 用 t 个辅助比特估计出 φ 的二进制近似。它的核心结构是：辅助寄存器制备均匀叠加 → 受控-U 幂次作用 → 逆 QFT → 测量。

二、从 QFT 到 QPE 的逻辑链

QFT 的电路实现依赖两个基本构件：Hadamard 门和受控相位门 R_k。对 n 位输入，标准分解为：先对每个比特施加 H 门，再插入受控相位旋转，最后用交换门反转比特顺序。以 n=3 为例，输入 |x₂x₁x₀⟩，输出为：

QFT|x₂x₁x₀⟩ = (|0⟩+e^{2πi·0.x₀}|1⟩)(|0⟩+e^{2πi·0.x₁x₀}|1⟩)(|0⟩+e^{2πi·0.x₂x₁x₀}|1⟩)/√8

这里 0.x₀ 表示二进制小数。这个乘积形式说明：QFT 把输入比特的每一位"编码"到输出态的相位中，且相位随比特位置逐级累积。这正是 QPE 能够从相位反推本征值的信息基础。

QPE 的完整流程可以概括为三步。第一步，t 个辅助比特全部置为 |0⟩，施加 H 门得到均匀叠加态。第二步，以辅助比特为控制位，对目标寄存器施加受控 U^{2^k}，把本征相位 φ 逐位"写入"辅助寄存器的相对相位。第三步，对辅助寄存器施加逆 QFT，把相位信息转换为计算基下的可测比特串。测量得到 t 位整数 y，则 φ ≈ y/2^t。

三、精度、成功概率与工程约束

QPE 的精度由辅助比特数 t 决定。若 φ 恰好是 t 位二进制小数，测量以概率 1 得到精确结果；若 φ 不能精确表示，则测量结果以高概率落在最近的两个 t 位近似值之一，误差上界约为 1/2^t。要保证误差小于 ε，需要 t ≥ log₂(1/ε)。

成功概率方面，若 φ 可精确表示，成功概率为 1；一般情况下，取 t = n + ⌈log₂(2 + 1/(2δ))⌉ 可使成功概率至少为 1-δ。例如要求 δ = 0.1，则需额外约 4 个辅助比特。这些参数关系直接决定了电路深度和资源开销，是工程实现中必须权衡的核心。

四、典型应用场景与学习路径

QPE 最经典的应用是 Shor 算法中的周期求解：把待分解整数 N 的因数问题转化为求模幂函数 f(x)=a^x mod N 的周期 r，再用 QPE 估计该周期对应的相位。另一个重要场景是量子化学中的分子能级计算：把哈密顿量 H 编码为酉算子 U=e^{-iHt}，用 QPE 估计其本征值，从而得到基态能量。HHL 算法则用 QPE 求矩阵本征值，再结合受控旋转实现线性方程组的量子求解。

本课程后续将按以下路径展开：先补齐量子门与线路基础，再逐步推导 QFT 的电路与数学形式，然后完整构建 QPE 并分析其精度与成功概率，最后进入 Shor、HHL、量子模拟等应用，并讨论噪声、纠错与当前硬件的现实约束。每一章都会给出可复现的电路结构、参数取值和结果判读方法，帮助读者从"看懂"走向"能算、能验、能判断"。