📚 课程目录第4章量子傅里叶变换线路深度与执行时间基准

4. 量子傅里叶变换线路深度与执行时间基准

QFT 线路的构造与规模参数

量子傅里叶变换（QFT）作用在 n 个量子比特上，把计算基态 |j⟩ 映射为等幅叠加态，其相位由二进制小数决定。标准教科书线路由两类门构成：

Hadamard 门：每个量子比特上 1 个，共 n 个。
受控相位门：比特 k 与比特 j（j > k）之间一个 CP(2π/2^(j-k+1))，数量为 n(n−1)/2。
SWAP 门：线路末尾用于恢复比特顺序，共 ⌊n/2⌋ 个（每个可分解为 3 个 CNOT）。

因此总门数约为 n + n(n−1)/2 + 3⌊n/2⌋，呈 O(n²) 增长。线路深度则取决于调度策略：若允许任意两比特门并行，深度约为 2n−1 量级；若按线性链拓扑只允许相邻比特耦合，深度会显著上升。下面的结构图给出 n=4 时的门排布与依赖关系，这是后续深度统计与执行时间测量的直接对象。

基准脚本：规模扫描与双后端计时

下面用 Qiskit 构造 QFT 线路并做规模扫描。关键点有三处：一是用 QFT 门或 qft 线路构造器生成线路后必须 decompose() 到基础门集，否则深度统计会把整个 QFT 当成一个黑盒门；二是计时必须区分线路构建时间与模拟执行时间，前者反映编译开销，后者才是后端性能；三是两种后端要喂同一份线路对象，保证可比性。

import time
import numpy as np
from qiskit import QuantumCircuit, transpile
from qiskit.circuit.library import QFT
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

def build_qft(n, do_swaps=True):
    """构造 n 比特 QFT 并分解到基础门集，返回可统计的线路。"""
    qc = QuantumCircuit(n)
    qc.append(QFT(num_qubits=n, do_swaps=do_swaps), range(n))
    qc = qc.decompose(reps=3)          # 展开到 H / CP / SWAP 级别
    qc = transpile(qc, basis_gates=['h', 'cx', 'u1', 'swap'],
                   optimization_level=0)  # 关闭优化，保留原始结构
    return qc

def benchmark(n_list, shots=1024, repeats=5):
    # 后端 A：状态向量模拟器（无噪声）
    sv = AerSimulator(method='statevector')
    # 后端 B：含退相干噪声的密度矩阵模拟器
    noise = NoiseModel()
    from qiskit_aer.noise import depolarizing_error
    noise.add_all_qubit_quantum_error(depolarizing_error(0.001, 1), ['u1', 'h'])
    noise.add_all_qubit_quantum_error(depolarizing_error(0.01, 2), ['cx'])
    dm = AerSimulator(method='density_matrix', noise_model=noise)

    rows = []
    for n in n_list:
        t0 = time.perf_counter()
        qc = build_qft(n)
        t_build = time.perf_counter() - t0

        depth = qc.depth()
        n_gates = qc.size()
        n_cx = qc.count_ops().get('cx', 0)

        # 加测量以触发采样路径
        qc_m = qc.copy()
        qc_m.measure_all()

        t_sim = {}
        for name, backend in [('statevector', sv), ('density_matrix', dm)]:
            t0 = time.perf_counter()
            backend.run(transpile(qc_m, backend), shots=shots).result()
            t_sim[name] = time.perf_counter() - t0

        rows.append(dict(n=n, depth=depth, gates=n_gates, cx=n_cx,
                         build_ms=t_build*1e3,
                         sv_ms=t_sim['statevector']*1e3,
                         dm_ms=t_sim['density_matrix']*1e3))
    return rows

if __name__ == '__main__':
    for r in benchmark([3, 4, 5, 6, 7, 8]):
        print(f"n={r['n']:2d} depth={r['depth']:3d} gates={r['gates']:3d} "
              f"cx={r['cx']:3d} build={r['build_ms']:7.2f}ms "
              f"sv={r['sv_ms']:8.2f}ms dm={r['dm_ms']:9.2f}ms")

若使用 do_swaps=False，门数会减少约 3⌊n/2⌋，但输出比特顺序为逆序。做深度基准时建议固定 do_swaps=True，否则不同规模间的深度对比会混入顺序修正的差异。

结果判读：三条增长曲线

运行上述脚本后，应重点观察三类量随 n 的变化形态，而不是只看单个数值：

门数与深度：门数应严格符合 n + n(n−1)/2 + 3⌊n/2⌋ 的解析值，可作为线路构造正确性的自检。深度在 optimization_level=0 下通常接近门数，因为受控相位门之间存在数据依赖，并行度有限。
状态向量后端耗时：随 n 近似按 2ⁿ 增长（态矢量维度翻倍），在 n=8 时约 256 维，仍很快；到 n≥20 会迅速变得不可接受。
密度矩阵后端耗时：维度为 4ⁿ，增长速率约为状态向量的平方，因此两条曲线在对数坐标下斜率不同。这正是双后端对比的核心结论。

判读时建议把耗时画在对数纵轴上，用线性拟合斜率验证：状态向量斜率应接近 log₂ 底的增长，密度矩阵斜率约为其两倍。若实测斜率明显偏离，先检查是否误开了 optimization_level 导致线路被大幅化简，或是否把首次调用的编译开销计入了执行时间。

计时结果对机器负载敏感。每次测量前应丢弃一次预热运行，并对同一 n 重复 5 次取中位数；不要用单次测量值下结论。示例中的噪声参数 0.001/0.01 仅为演示密度矩阵路径的可用性，不代表任何真实硬件指标。

可复用的基准记录表

把每次扫描的结果填入下表，便于跨机器、跨版本对比。字段只保留与 QFT 规模基准直接相关的量：

量子比特数 n	线路深度	总门数	CX 数	构建耗时 (ms)	状态向量耗时 (ms)	密度矩阵耗时 (ms)	备注
3	—	—	—	—	—	—	基线
4	—	—	—	—	—	—
5	—	—	—	—	—	—
6	—	—	—	—	—	—
7	—	—	—	—	—	—
8	—	—	—	—	—	—	规模上限

填写时把“—”替换为实测值，并在备注列记录后端版本、是否启用噪声模型、是否开启优化。完成一轮后，用门数列与解析公式对照，即可确认线路构造无误；用两列耗时的比值随 n 的变化，即可量化两种后端的性能差距。