Table of contents

单振幅模拟器（Single-Amplitude Simulator）实现原理详解 ¶

单振幅模拟器（Single-Amplitude Simulator）是量子计算经典模拟器中的一种重要类型，其核心目标是高效计算量子电路输出状态中某个特定计算基态的振幅（或概率），而无需存储或计算整个巨大的状态向量。这在验证量子算法、调试量子电路或研究特定量子态性质时非常有用。

一、核心思想：路径求和（Path Summation）¶

单振幅模拟器的核心原理基于量子力学的路径积分表述。它将量子电路的计算过程分解为所有可能的“计算路径”，并将目标振幅表示为这些路径贡献的复数之和。

量子态与振幅 ¶

一个 n 量子比特系统的状态可以表示为 2^n 维复向量：$$|\psi\rangle = \sum_{x \in \{0,1\}^n} \alpha_x |x\rangle$$
目标是计算某个特定基态 |z⟩（例如 |101...0⟩）的振幅 $\alpha_z = \langle z|\psi\rangle$。

量子电路的分解 ¶

量子电路由一系列量子门 $U_1, U_2, ..., U_m$ 组成，作用在初始态 $|0\rangle^{\otimes n}$ 上：$$|\psi\rangle = U_m \dots U_2 U_1 |0\rangle^{\otimes n}$$
每个量子门 $U_k$ 可以看作是一个酉矩阵，作用在部分或全部量子比特上。

路径的概念 ¶

从初始态 $|0\rangle^{\otimes n}$ 到最终态 $|z\rangle$ 的演化过程，可以看作是在电路的每个“时间步”（即每个量子门作用前后）中，系统经历的一系列中间基态 $|x_0\rangle, |x_1\rangle, ..., |x_m\rangle$。
路径 $P$ 定义为这样一个序列：$$P = (|x_0\rangle = |0\rangle^{\otimes n}, |x_1\rangle, |x_2\rangle, ..., |x_m\rangle = |z\rangle)$$
其中，$|x_k\rangle$ 是第 k 个门 $U_k$ 作用前的状态，$|x_{k+1}\rangle$ 是作用后的状态。$|x_{k+1}\rangle$ 必须是 $U_k$ 作用在 $|x_k\rangle$ 上可能产生的基态之一（即 $\langle x_{k+1}| U_k |x_k\rangle \neq 0$）。

对于一条特定的路径 $P$，其对最终振幅 $\alpha_z$ 的贡献 $C(P)$ 是路径上所有相邻基态之间转移振幅的乘积：$$C(P) = \langle x_1| U_1 |x_0\rangle \times \langle x_2| U_2 |x_1\rangle \times \dots \times \langle x_m| U_m |x_{m-1}\rangle$$ 每个因子 $\langle x_{k+1}| U_k |x_k\rangle$ 就是量子门 $U_k$ 从基态 $|x_k\rangle$ 转移到基态 $|x_{k+1}\rangle$ 的矩阵元。

振幅求和 ¶

最终的振幅 $\alpha_z$ 等于所有从 $|0\rangle^{\otimes n}$ 到 $|z\rangle$ 的有效路径 $P$ 的贡献 $C(P)$ 之和：$$\alpha_z = \sum_{P: |0\rangle^{\otimes n} \to |z\rangle} C(P)$$

二、实现算法：基于递归/动态规划的路径枚举与求和 ¶

直接枚举所有路径的数量是指数级的（最坏情况下 $O(2^{n \cdot m})$），无法实用。单振幅模拟器通过动态规划（Dynamic Programming, DP） 或 记忆化递归（Memoized Recursion） 来高效计算这个求和。

状态表示 ¶

定义一个函数 $A(k, s)$：表示在第 k 个门作用后，系统处于基态 |s⟩ 的振幅。
目标是计算 $A(m, z)$（即 $\alpha_z$）。

初始条件 ¶

$A(0, s) = 1$ 如果 $s = |0\rangle^{\otimes n}$（初始态）。
$A(0, s) = 0$ 如果 $s \neq |0\rangle^{\otimes n}$。

递推关系（核心）¶

要计算 $A(k, s)$（第 k 个门作用后处于 |s⟩ 的振幅），需要考虑第 k 个门 $U_k$ 作用前的所有可能状态 |t⟩，以及 $U_k$ 从 |t⟩ 转移到 |s⟩ 的振幅：$$A(k, s) = \sum_{t \in \{0,1\}^n} \langle s| U_k |t\rangle \times A(k-1, t)$$ 这个公式是动态规划的关键。它表明当前状态 |s⟩ 的振幅，是前一个状态 |t⟩ 的振幅乘以门 $U_k$ 的转移矩阵元 $\langle s| U_k |t\rangle$，然后对所有可能的 |t⟩ 求和。

计算过程 ¶

顺序计算：从 $k=0$（初始态）开始，依次计算 $k=1, 2, ..., m$ 时所有基态 s 的振幅 $A(k, s)$。
空间优化（关键！）：
- 计算第 k 层的 $A(k, s)$ 只需要第 k-1 层的 $A(k-1, t)$。
- 因此，不需要存储所有 $2^n$ 个 $A(k, s)$！ 只需要存储当前层 k 和前一层 k-1 的振幅值。
- 更进一步，由于我们只关心最终 $A(m, z)$，在计算第 k 层时，可以只计算那些可能最终贡献到 |z⟩ 的状态 s 的振幅。这通过剪枝（Pruning）实现。

剪枝（Pruning）- 效率提升的核心 ¶

观察 ¶

并非所有基态 s 在每一层 k 都需要计算。只有那些存在一条路径从 |s⟩（在 k 层）最终到达 |z⟩（在 m 层）的状态 s 才对 $\alpha_z$ 有贡献。

反向传播（Backward Propagation）¶

在开始正向计算（从 $k=0$ 到 $k=m$）之前，先进行一次反向计算（从 $k=m$ 到 $k=0$）。
定义一个函数 $B(k, s)$：表示从第 k 个门作用后的状态 |s⟩ 出发，最终到达目标态 |z⟩ 的振幅（即剩余电路的转移振幅）。
反向初始条件：$B(m, s) = 1$ 如果 $s = z$；$B(m, s) = 0$ 如果 $s \neq z$。
反向递推：$$B(k-1, t) = \sum_{s \in \{0,1\}^n} \langle s| U_k |t\rangle \times B(k, s)$$
剪枝规则：在正向计算 $A(k, s)$ 时，只计算那些 $B(k, s) \neq 0$ 的状态 s。因为如果 $B(k, s) = 0$，意味着从 |s⟩ 出发不可能到达 |z⟩，那么 $A(k, s)$ 对最终 $\alpha_z$ 的贡献必然为零，无需计算。

效果 ¶

剪枝极大地减少了需要计算和存储的状态数量。在最理想情况下（如电路结构简单、目标态 z 特定），需要计算的状态数可能远小于 $2^n$。

最终计算 ¶

正向计算（带剪枝）完成后，$A(m, z)$ 就是所求的目标振幅 $\alpha_z$。

三、时间复杂度分析 ¶

无剪枝（最坏情况）¶

需要计算每一层 k 的所有 $2^n$ 个状态。每个状态 s 的计算需要遍历前一层所有 $2^n$ 个状态 t（计算 $\sum_t \langle s|U_k|t\rangle \times A(k-1, t)$）。总复杂度为：$$O(m \times 2^n \times 2^n) = O(m \times 4^n)$$ 这比全状态模拟的 $O(m \times 2^n)$ 差，所以剪枝至关重要。

带剪枝（实际运行）¶

复杂度取决于电路结构和目标态 z。设 $S_k$ 是第 k 层需要计算的状态数（即 $B(k, s) \neq 0$ 的 s 的数量）。则复杂度为：$$O\left(\sum_{k=1}^m |S_k| \times |S_{k-1}|\right)$$

$|S_k|$ 通常远小于 $2^n$。例如，如果电路是局部作用的（门只作用于少量量子比特），且目标态 z 是计算基态，$|S_k|$ 可能是 $O(\text{poly}(n))$ 或 $O(2^{c n})$（$c < 1$）。
在理想情况下（如电路是树状结构或目标态有特定模式），复杂度可以显著低于 $O(4^n)$，甚至达到 $O(\text{poly}(n) \times 2^n)$ 或更好。但对于通用随机电路和任意 z，最坏情况仍可能是指数级。

四、优点与缺点 ¶

优点 ¶

空间效率高：核心优势。存储需求是 $O(|S_k| + |S_{k-1}|)$，通常远小于全状态模拟的 $O(2^n)$。这使得模拟更大规模的量子电路（在特定条件下）成为可能。
目标明确：当只关心特定输出态的概率/振幅时（如验证量子算法的特定输出、研究特定量子态），效率远高于计算整个状态向量。
可并行化：不同状态 s 的计算 $A(k, s)$ 在同一层 k 内是相互独立的，易于并行化。

缺点 ¶

时间复杂度：最坏情况下时间复杂度仍为指数级（$O(4^n)$），且常数因子较大。对于通用随机电路，剪枝效果有限，效率可能不如其他模拟方法（如张量网络）。
依赖电路结构：效率高度依赖于量子电路的结构和目标态的选择。局部性强的电路（门作用在少量比特上）和结构化的目标态剪枝效果好；全局门或高度纠缠电路剪枝效果差。
单点信息：只能得到一个振幅/概率。如果需要多个振幅或整个状态分布，需要多次运行模拟器（每次针对不同的 z），总开销可能超过全状态模拟。

五、与其他模拟方法的对比 ¶

模拟方法	核心逻辑	时间复杂度	空间复杂度	适用场景
单振幅模拟器	路径求和+动态规划+剪枝	$O(\sum \vert S_k \vert \times \vert S_{k-1}\vert)$	$O(\vert S_k\vert + \vert S_{k-1}\vert)$	仅需特定基态振幅、电路局部性强的场景
全状态模拟器	存储并更新完整状态向量	$O(m \times 2^n)$	$O(2^n)$	需要完整状态分布、量子比特数较少（$n \leq 30$）
张量网络模拟器	量子电路→张量网络→张量收缩	取决于张量收缩顺序	取决于张量收缩顺序	通用场景，尤其适合局部电路、大规模量子比特
Feynman路径积分模拟器	显式枚举路径+并行化	指数级（依赖路径数）	取决于路径存储需求	路径可并行枚举、特定结构化电路

关键差异：单振幅模拟器可视为一种特殊的、基于路径求和的张量收缩方法，但其优化策略（反向剪枝）更聚焦于“单点振幅计算”；张量网络模拟器则是更通用的框架，通过张量收缩顺序优化适配更广泛的电路类型。

六、总结 ¶

单振幅模拟器的核心原理是将目标振幅分解为所有可能计算路径的贡献之和，并通过动态规划结合反向传播剪枝来高效计算这个求和。其关键优势在于显著降低了空间复杂度（只需存储少量相关状态），使其在只需要特定输出态信息且电路结构有利于剪枝的场景下非常实用。

然而，其时间复杂度在最坏情况下仍为指数级，且效率受电路结构和目标态选择影响较大。它是量子计算经典模拟工具箱中一种重要的、针对特定需求的优化方法，与全状态模拟器、张量网络模拟器等形成互补，共同支撑量子算法验证与量子电路调试工作。

单振幅模拟器中剪枝过程的实例解析与数学原理 ¶

剪枝是单振幅模拟器突破“指数级状态存储”瓶颈的核心优化手段。本文通过2量子比特贝尔态制备电路的具体案例，直观展示剪枝的执行过程，并从数学层面推导其通用性原理，明确“为何能剪枝”“如何剪枝”及“剪枝效率的关键影响因素”。

一、核心概念回顾 ¶

在深入实例前，先明确剪枝的底层逻辑：
单振幅模拟器的目标是计算特定目标态 |z⟩ 的振幅 ⟨z|U|0ⁿ⟩（U 为电路总酉算子，|0ⁿ⟩ 为初始态）。它通过动态规划（DP） 将电路按“量子门时间步”分解，计算从 |0ⁿ⟩ 到 |z⟩ 的所有路径贡献之和。

剪枝的核心思想是：丢弃“注定对最终结果无贡献”的中间状态——若某时间步 k 的中间状态 |x⟩ 振幅为 0，则后续所有从 |x⟩ 出发的路径贡献均为 0，无需存储该状态或计算其后续演化。

二、实例：2量子比特贝尔态电路的剪枝过程 ¶

实验设定 ¶

目标：计算最终态 |11⟩ 的振幅 ⟨11|U|00⟩（n=2 量子比特，初始态 |00⟩）。
电路结构：2个时间步（2个量子门）：
1. 门1（H₀）：对量子比特0施加Hadamard门（H ⊗ I，I 为比特1的单位门）。
2. 门2（CNOT₀₁）：以比特0为控制位、比特1为目标位的CNOT门。
已知理论结果：电路输出贝尔态 |Φ⁺⟩ = (|00⟩ + |11⟩)/√2，故 ⟨11|U|00⟩ = 1/√2。

动态规划（DP）表定义 ¶

用字典 DP_k 存储时间步 k 下所有非零振幅的中间状态，格式为 DP_k = { |x⟩: A_k(x) }，其中 A_k(x) 表示时间步 k 后系统处于 |x⟩ 的振幅。

步骤1：时间步0（k=0，初始态）¶

初始态仅 |00⟩，振幅为 1（无其他初始状态）。
DP_0 = { |00⟩: 1 }
无剪枝：仅1个状态，无需丢弃。

步骤2：时间步1（k=1，应用H₀门）¶

首先明确 H₀ 的转移振幅：
Hadamard门 H 的矩阵为 H = 1/√2 * [[1,1],[1,-1]]，作用于比特0时，H₀ = H ⊗ I，其对2量子比特基态的转移振幅满足：
⟨a b|H₀|c d⟩ = ⟨a|H|c⟩ * ⟨b|I|d⟩（a,b,c,d ∈ {0,1}，|a b⟩ 表示比特0为 a、比特1为 b 的基态）。

根据动态规划递推公式：
A₁(x) = Σ_{y ∈ DP_0} [ A₀(y) * ⟨x|H₀|y⟩ ]（仅遍历 DP_0 中的非零状态 y）。

逐一计算所有可能 x 的振幅：

x = |00⟩：
A₁(|00⟩) = A₀(|00⟩) * ⟨00|H₀|00⟩ = 1 * [⟨0|H|0⟩ * ⟨0|I|0⟩] = 1 * (1/√2 * 1) = 1/√2
x = |01⟩：
A₁(|01⟩) = 1 * [⟨0|H|0⟩ * ⟨1|I|0⟩] = 1 * (1/√2 * 0) = 0
x = |10⟩：
A₁(|10⟩) = 1 * [⟨1|H|0⟩ * ⟨0|I|0⟩] = 1 * (1/√2 * 1) = 1/√2
x = |11⟩：
A₁(|11⟩) = 1 * [⟨1|H|0⟩ * ⟨1|I|0⟩] = 1 * (1/√2 * 0) = 0

剪枝操作：

振幅为 0 的状态 |01⟩ 和 |11⟩ 对后续计算无贡献，直接丢弃。
更新 DP_1 = { |00⟩: 1/√2, |10⟩: 1/√2 }
剪枝效果：从4个潜在状态减少到2个，存储和后续计算量减半。

步骤3：时间步2（k=2，应用CNOT₀₁门，最终态）¶

首先明确 CNOT₀₁ 的转移规则：控制位（比特0）为 1 时翻转目标位（比特1），否则保持不变。其矩阵（基态顺序 |00⟩,|01⟩,|10⟩,|11⟩）为：
CNOT = [[1,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,1,0]]
核心转移振幅：⟨a b|CNOT|c d⟩ = 1 当且仅当：

若 c=0，则 a=c=0 且 b=d；
若 c=1，则 a=c=1 且 b=1-d；
否则 ⟨a b|CNOT|c d⟩ = 0。

递推公式：A₂(x) = Σ_{y ∈ DP_1} [ A₁(y) * ⟨x|CNOT|y⟩ ]（仅遍历 DP_1 的2个状态）。

我们重点计算目标态 |11⟩ 的振幅，同时验证其他状态：

x = |00⟩：
A₂(|00⟩) = [A₁(|00⟩)*⟨00|CNOT|00⟩] + [A₁(|10⟩)*⟨00|CNOT|10⟩] = (1/√2 * 1) + (1/√2 * 0) = 1/√2
x = |01⟩：
A₂(|01⟩) = (1/√2 * 0) + (1/√2 * 0) = 0（剪枝）
x = |10⟩：
A₂(|10⟩) = (1/√2 * 0) + (1/√2 * 0) = 0（剪枝）
x = |11⟩（目标态）：
A₂(|11⟩) = [A₁(|00⟩)*⟨11|CNOT|00⟩] + [A₁(|10⟩)*⟨11|CNOT|10⟩] = (1/√2 * 0) + (1/√2 * 1) = 1/√2

剪枝操作：

丢弃 |01⟩ 和 |10⟩，DP_2 = { |00⟩: 1/√2, |11⟩: 1/√2 }
最终结果：⟨11|U|00⟩ = A₂(|11⟩) = 1/√2，与理论一致。

剪枝效果总结：
整个过程仅处理了 DP_0（1个）、DP_1（2个）、DP_2（2个）状态，累计处理5个状态；若不剪枝，需处理 1+4+4=9 个状态，计算量减少约45%。

三、剪枝的一般性数学解释 ¶

动态规划核心公式 ¶

设电路有 m 个门 U₁, U₂, ..., U_m，定义：

A_k(x)：应用前 k 个门后，系统处于基态 |x⟩ 的振幅，即 A_k(x) = ⟨x|U_k U_{k-1}...U₁|0ⁿ⟩。
递推关系（线性叠加原理）：
$$A_k(x) = \sum_{y \in \{0,1\}^n} \left[ A_{k-1}(y) \cdot \langle x|U_k|y \rangle \right]$$
其中 ⟨x|U_k|y⟩ 是门 U_k 从 |y⟩ 到 |x⟩ 的转移振幅（酉矩阵元）。

剪枝的数学基础（关键定理）¶

定理：若 A_{k-1}(y) = 0，则对任意 x 和 U_k，A_{k-1}(y) · ⟨x|U_k|y⟩ = 0，即 y 对 A_k(x) 的贡献为 0。

证明：
根据乘法零元性质，0 与任意复数（⟨x|U_k|y⟩ 是复数）相乘结果仍为 0。因此，A_{k-1}(y) = 0 时，该项在求和中可忽略，无需计算或存储 A_{k-1}(y)。

剪枝的算法实现（通用流程）¶

剪枝通过“稀疏数据结构+选择性遍历”实现，具体步骤如下：

初始化：DP_0 = { |0ⁿ⟩: 1 }（仅初始态非零）。
迭代计算（k=1到m）：
a. 初始化空字典 DP_k（存储当前时间步非零状态）。
b. 遍历 DP_{k-1} 中的所有状态 y（仅非零振幅状态）。
c. 对每个 y，计算 U_k 能将 y 转移到的所有 x（即 ⟨x|U_k|y⟩ ≠ 0 的 x，利用门的稀疏性减少计算）。
d. 对每个 x，计算贡献 contribution = A_{k-1}(y) · ⟨x|U_k|y⟩，并累加到 DP_k[x]（若 x 未在 DP_k 中，则初始化为该贡献）。
e. 隐式剪枝：未进入 DP_k 的状态（振幅为 0）自动被丢弃，无需存储。
结果提取：目标振幅 ⟨z|U|0ⁿ⟩ = DP_m.get(|z⟩, 0)（若 |z⟩ 不在 DP_m 中，振幅为 0）。

剪枝效率的关键影响因素 ¶

剪枝效果并非恒定，取决于以下3个核心因素：

电路的稀疏性：
- 单量子比特门（如H、X、T）的转移矩阵是稀疏的（每个 y 仅连接2个 x），能保持 DP_k 规模较小；
- 多量子比特门（如Toffoli、SWAP）若导致强纠缠，会使 DP_k 中状态数接近 2ⁿ，剪枝效果骤降。
门的局部性：
- 仅作用于少数比特的门（如2比特CNOT）对其他比特无影响，DP_k 中状态的“无关比特位”可共享，减少状态数；
- 全局门（如多比特Hadamard）会作用于所有比特，易导致 DP_k 爆炸。
目标态的结构：
- 若目标态 |z⟩ 具有特殊结构（如稀疏二进制表示），反向剪枝（先从 |z⟩ 反向推导需保留的中间状态）可进一步减少 DP_k 规模（见附录）。

四、附录：反向剪枝（进阶优化）¶

上述实例使用“正向剪枝”（从初始态向前计算，丢弃零振幅状态），而反向剪枝是更高效的优化手段，尤其适用于复杂电路：

定义反向振幅：B_k(x) = ⟨z|U_m...U_{k+1}|x⟩（从时间步 k 的 x 到目标态 z 的振幅）。
反向递推：B_{k-1}(y) = Σ_x [ ⟨x|U_k|y⟩ · B_k(x) ]，初始条件 B_m(x) = 1（若 x=z），否则 0。
双向剪枝：正向计算 A_k(x) 时，仅保留 B_k(x) ≠ 0 的 x（即“能到达 z 的状态”），进一步减少 DP_k 规模。

五、总结 ¶

剪枝的本质是利用振幅计算的线性性和量子门的稀疏性，丢弃无贡献的中间状态。通过2量子比特贝尔态实例可见，剪枝能显著减少存储和计算量，使单振幅模拟器在中等规模电路（n≈20-30）上比全状态模拟器更高效。

需注意的是，剪枝并非“万能优化”——当电路存在强纠缠或全局门时，DP_k 仍可能指数增长。因此，单振幅模拟器通常与张量网络、蒙特卡洛等方法结合，形成互补的量子模拟工具箱。

在单振幅模拟器中，反向传播（Backward Propagation） 是一种与正向动态规划（Forward Propagation）协同工作的关键优化技术，它通过从目标态倒推必要条件来进一步剪枝无效路径，显著提升计算效率。以下是详细解释：

反向传播的核心思想¶

正向动态规划（Forward DP）从初始态出发，逐层计算中间状态振幅，并剪枝振幅为零的路径。但正向剪枝可能仍保留大量最终无法到达目标态的中间状态。反向传播则从目标态倒推，标记出对最终结果有贡献的必要中间状态，从而在正向计算中提前丢弃无关状态。

反向传播的数学原理¶

设目标态为 $ z $，量子门序列为 $ U = U_m U_{m-1} \cdots U_1 $。
反向传播的目标是：找到所有可能到达 $ z $ 的中间状态集合。
定义反向传播的“影响集” $ \mathcal{B}_k $：

$ \mathcal{B}_m = \{ z \} $（最终目标态）
对于时间步 $ k $（从 $ m-1 $ 到 $ 0 $）：
$$ \mathcal{B}_k = \left\{ x \mid \exists y \in \mathcal{B}_{k+1}, \langle y | U_{k+1} | x \rangle \neq 0 \right\} $$ 即：$ \mathcal{B}_k $ 包含所有能通过 $ U_{k+1} $ 演化到 $ \mathcal{B}_{k+1} $ 中某状态 $ y $ 的 $ x $。 剪枝规则：
在正向动态规划中，若当前状态 $ x \notin \mathcal{B}_k $，则直接丢弃 $ x $（因其无法到达目标态 $ z $）。

举例说明：贝尔态电路的反向传播¶

电路与目标 ¶

电路：$ U = \text{CNOT} \cdot (H \otimes I) $
初始态：$ |00\rangle $
目标态：$ z = |11\rangle $

反向传播步骤 ¶

初始化：
$ \mathcal{B}_2 = \{ |11\rangle \} $（最终目标态）
时间步 $ k=1 $（CNOT门）：
- CNOT门作用规则：
  $ \text{CNOT} |ab\rangle = |a, a \oplus b\rangle $
  逆操作（因CNOT是自逆门）：
  $ \text{CNOT} |cd\rangle = |c, c \oplus d\rangle $
- 找到所有能演化到 $ |11\rangle $ 的前驱态：
  $$ \text{CNOT} |x\rangle = |11\rangle \implies |x\rangle = \text{CNOT} |11\rangle = |1, 1 \oplus 1\rangle = |10\rangle $$
- 因此：$ \mathcal{B}_1 = \{ |10\rangle \} $
时间步 $ k=0 $（Hadamard门）：
- Hadamard门作用规则：
  $ H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}, \quad H|1\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}} $
- 找到所有能演化到 $ |10\rangle $ 的前驱态：
  设前驱态为 $ |ab\rangle $，则：
  $$ (H \otimes I) |ab\rangle = \left( H|a\rangle \right) \otimes |b\rangle = |10\rangle $$ 两边同时左乘 $ H \otimes I $： $$ |ab\rangle = H \otimes I |10\rangle = \frac{|00\rangle + |10\rangle}{\sqrt{2}} $$
- 因此：$ \mathcal{B}_0 = \{ |10\rangle , |00\rangle \} $

正向计算中的剪枝 ¶

初始态：$ |00\rangle \in \mathcal{B}_0 = \{ |10\rangle \} $
继续下一步
时间步 $ k=0 $（Hadamard门）：
- 计算 $ (H \otimes I)|00\rangle = \frac{|00\rangle + |10\rangle}{\sqrt{2}} $
- 保留状态：$ |00\rangle \notin \mathcal{B}_1 $（丢弃），$ |10\rangle \in \mathcal{B}_1 $（保留）。
时间步 $ k=1 $（CNOT门）：
- 仅处理 $ |10\rangle $：
  $ \text{CNOT} |10\rangle = |11\rangle $
- 结果：$ |11\rangle \in \mathcal{B}_2 $（命中目标）。

最终振幅：
$ \langle 11| U |00\rangle = \langle 11| \text{CNOT} \cdot (H \otimes I) |00\rangle = \frac{1}{\sqrt{2}} \langle 11| \text{CNOT} |10\rangle = \frac{1}{\sqrt{2}} \langle 11|11\rangle = \frac{1}{\sqrt{2}} $

反向传播的优化效果¶

方法	存储状态数（本例）	剪枝能力
纯正向动态规划	4（全状态空间）	仅剪枝振幅为零的路径
正向 + 反向传播	2（$ \vert 10\rangle, \vert 11\rangle $）	额外剪枝无法到达目标的路径

关键优势：

状态空间压缩：
反向传播将状态空间从 $ O(2^n) $ 压缩到仅保留必要路径上的状态（本例从 4 → 2）。
避免无效计算：
在正向计算中，直接跳过 $ x \notin \mathcal{B}_k $ 的状态，减少计算量。
协同剪枝：
- 正向剪枝：丢弃振幅为零的路径（如 $ |00\rangle \to |01\rangle $）。
- 反向剪枝：丢弃无法到达目标的路径（如 $ |00\rangle \to |00\rangle $）。

若 $ A_k(x) = 0 $ → 正向剪枝（振幅为零）。
若 $ x \notin \mathcal{B}_k $ → 反向剪枝（无法到达目标）。

复杂度分析¶

时间复杂度：
正向与反向传播各需 $ O(m \cdot 2^n) $，但实际因剪枝，状态数远小于 $ 2^n $。
空间复杂度：
仅存储 $ \mathcal{B}_k $ 和当前层非零状态，通常 $ O(2^{n/2}) $（对浅层电路）。

适用场景¶

高效剪枝条件：
电路中存在稀疏门（如CNOT、Toffoli）或局部纠缠，使 $ \mathcal{B}_k $ 较小。
低效场景：
高度纠缠电路（如量子傅里叶变换）导致 $ \mathcal{B}_k $ 接近全空间，剪枝效果减弱。

总结 ¶

反向传播通过从目标态倒推必要路径，与正向动态规划形成双向剪枝机制：

正向剪枝：丢弃振幅为零的路径（动态规划自然特性）。
反向剪枝：丢弃无法到达目标的路径（依赖 $ \mathcal{B}_k $ 预计算）。
协同效果：大幅减少需存储和计算的中间状态，使单振幅模拟器在中等规模电路（如50+量子比特）中仍可行。其本质是利用量子演化的局部性和可逆性，将指数级问题压缩为多项式级（对特定电路）。

核心思想：阈值控制的混合传播¶

策略流程¶

初始化：从目标态 $ z $ 开始反向传播，计算每层的 $ \mathcal{B}_k $（对目标态有贡献的前驱态集合）。
阈值检查：在每层 $ k $ 检查 $ |\mathcal{B}_k| $（集合大小）：
- 若 $ |\mathcal{B}_k| \leq \text{阈值} $（如 $ 2^{20} $）：继续反向传播。
- 若 $ |\mathcal{B}_k| > \text{阈值} $：终止反向传播，切换到前向传播。
前向传播阶段：
- 从初始态 $ |0\rangle^{\otimes n} $ 开始正向计算。
- 利用已计算的 $ \mathcal{B}_k $ 剪枝：只保留与反向传播中 $ \mathcal{B}_k $ 有交集的中间状态。
- 最终计算目标态 $ z $ 的振幅。

阈值的作用¶

避免指数爆炸：当电路高度纠缠（如随机电路）时，$ \mathcal{B}_k $ 可能指数增长（接近 $ 2^n $）。阈值强制提前终止反向传播，防止内存耗尽。
保留部分剪枝收益：即使提前切换，已计算的 $ \mathcal{B}_k $ 仍可作为前向传播的“过滤器”，大幅减少需计算的状态数。

示例说明¶

假设模拟一个 50 量子比特 的电路，目标态为 $ |0\rangle^{\otimes 50} $，阈值设为 $ 2^{25} $（约 3300 万状态）。

场景 1：电路局部性强（如 QFT）¶

反向传播：
- 前 20 层：$ |\mathcal{B}_k| $ 增长缓慢（如 $ 2^{10} \rightarrow 2^{15} $）。
- 第 21 层：$ |\mathcal{B}_{21}| = 2^{24} < 2^{25} $ → 继续反向传播。
- 最终：$ \mathcal{B}_k $ 始终低于阈值，完成反向传播，高效计算振幅。

场景 2：电路高度纠缠（如随机电路）¶

反向传播：
- 前 10 层：$ |\mathcal{B}_k| $ 指数增长（如 $ 2^{10} \rightarrow 2^{20} $）。
- 第 11 层：$ |\mathcal{B}_{11}| = 2^{26} > 2^{25} $ → 触发阈值，切换前向传播。
前向传播：
- 初始态：$ |0\rangle^{\otimes 50} $（振幅=1）。
- 利用 $ \mathcal{B}_{11} $ 剪枝：只计算与 $ \mathcal{B}_{11} $ 中状态有重叠的路径。
- 效果：前向传播只需处理 $ \approx 2^{26} $ 个状态（而非 $ 2^{50} $），内存可控。

数学解释：混合传播的复杂度分析¶

设 $ n $ 为量子比特数，$ m $ 为门层数，阈值 $ T = 2^t $（$ t \ll n $）。

反向传播阶段¶

时间复杂度：$ O(m \cdot T \cdot 2^s) $
（$ s $ 为门的局部宽度，通常 $ s \leq 3 $）。
空间复杂度：$ O(T) $（存储 $ \mathcal{B}_k $）。

前向传播阶段¶

时间复杂度：$ O(m \cdot \min(|\mathcal{B}_k|, 2^n)) $
实际被剪枝为 $ O(m \cdot T) $（因 $ |\mathcal{B}_k| \leq T $）。
空间复杂度：$ O(T) $（存储中间状态）。

整体复杂度¶

最坏情况（反向传播提前终止）：
$$ \text{Time} = O(m \cdot T \cdot 2^s) + O(m \cdot T) = O(m \cdot T \cdot 2^s) $$
对比纯反向传播（无阈值）：
最坏时间 $ O(m \cdot 2^n) $，空间 $ O(n \cdot 2^n) $ → 指数级改进。

优化技巧¶

动态阈值调整：
- 根据可用内存动态调整 $ T $（如 $ T = \text{可用内存}/10 $）。
- 监测 $ \mathcal{B}_k $ 增长率：若增长率 $ > 2^{\text{layer}} $，提前切换。
前向传播的进一步剪枝：
- 在正向计算中，结合反向传播的 $ \mathcal{B}_k $ 和正向振幅稀疏性：
  只保留满足 $ \langle x | \psi_k \rangle \neq 0 $ 且 $ x \in \mathcal{B}_k $ 的状态。
并行化加速：
- 反向传播的 $ \mathcal{B}_k $ 计算可并行（各层独立）。
- 前向传播的路径计算可分块并行。

适用场景与局限性¶

场景	效果
局部性强的电路	反向传播极少触发阈值，高效完成剪枝（如 QFT、VQE 电路）。
中等纠缠电路	混合策略平衡开销，显著优于纯前向/反向传播。
高度纠缠电路	反向传播提前终止，前向传播在 $ O(T) $ 空间内完成（避免 $ 2^n $ 爆炸）。
目标态概率极低	若 $ \vert\langle z \vert U \vert 0 \rangle\vert^2 \approx 0 $，混合策略仍能快速返回 0。

局限性¶

阈值选择敏感：$ T $ 过小 → 损失剪枝收益；$ T $ 过大 → 内存风险。
电路结构依赖：对全连接电路（如量子化学模拟），剪枝效果可能有限。

总结 ¶

阈值控制的混合传播策略 是单振幅模拟器的核心工程优化：

反向传播：在 $ \mathcal{B}_k $ 较小时高效剪枝。
阈值触发：防止 $ \mathcal{B}_k $ 指数增长导致内存崩溃。
前向传播：利用已计算的 $ \mathcal{B}_k $ 继续剪枝，控制计算规模。这种策略在保证正确性的前提下，将最坏情况复杂度从指数级 $ O(2^n) $ 降至亚指数级 $ O(\text{poly}(n) \cdot T) $，是模拟中等规模量子电路（30–60 量子比特）的实用方案。