量子态制备详解：从门电路到结构化加速¶
量子态制备（Quantum State Preparation, QSP）是量子计算中最基础的原语之一：我们要把经典描述的数据 \(\mathbf{p} = (p_0, p_1, \ldots, p_{N-1})\)（\(N = 2^n\)）编码为量子态 \(|\psi\rangle = \sum_{j=0}^{N-1} \sqrt{p_j}\,|j\rangle\)，即所谓振幅编码（amplitude encoding）。它是 HHL 线性方程组求解器、量子机器学习、量子化学模拟等几乎所有量子算法的"输入端"。本文系统介绍通用态制备、稀疏态制备、特定分布态制备、基于 QRAM 的方案，以及 PRL 2022 的最优深度方案；对每个核心构造，我们都给出完整的推导与计数论证。
问题定义¶
量子态制备问题：给定经典描述的向量 \(\mathbf{v} = (v_0, v_1, \ldots, v_{N-1}) \in \mathbb{C}^N\)（\(N = 2^n\)），构造量子电路 \(U\)，使得
我们强调这一问题的三重挑战：
经典数据有 \(N\) 个分量，而任何"高效"电路只允许 \(O(\mathrm{poly}(n))\) 个门；信息量的不对称必须在门的结构中被吸收（例如利用稀疏性、低纠缠等先验结构）。
任意 \(n\) 比特纯态的制备需要 \(\Omega(2^n)\) 个基本门，我们在 1.4 节用参数计数严格证明这一信息论下界。
对具有特定结构的态（稀疏、可分解、低秩、低纠缠），我们可以显著降低代价，见方法二至方法四。
方法一：通用量子态制备（基于门电路）¶
1.1 递归二分构造（Möttönen / Shende–Bullock–Markov 树形结构）¶
思想：我们把目标态的振幅组织成一棵完全二叉树，从根到叶逐层"按比例分配"概率质量；每一层的分配由一组受控 \(R_y\) 旋转完成。这一构造由 Möttönen 等人与 Shende、Bullock、Markov 分别给出并优化。
记号。设目标态为
其中 \(p_j = |\alpha_j|^2\)。对长度为 \(\ell\) 的比特串 \(w \in \{0,1\}^\ell\)，我们用 \(j \prec w\) 表示基矢指标 \(j\) 的二进制展开以 \(w\) 为前缀，并定义子树概率
由定义，前缀为 \(w\) 的指标集合恰好被 \(w0\)、\(w1\) 二等分，因此 \(p_{w0} + p_{w1} = p_w\)。
第一步：单比特旋转的作用。我们采用约定
直接读出矩阵的第一列便得基本恒等式
第二步：旋转角度的推导。我们对层号 \(\ell = 0, 1, \ldots, n\) 归纳证明：在处理完前 \(\ell\) 层之后，电路将初态变为
归纳基础 \(\ell = 0\) 时 \(|\Phi_0\rangle = |0\rangle^{\otimes n}\)，即 \(p_\varnothing = 1\) 的情形，命题成立。归纳步骤：对第 \(\ell+1\) 层的每个前缀 \(w\)，我们在以 \(w\) 为控制值（即 \(\ell\) 个控制比特取值 \(w\)）的条件下，对第 \(\ell+1\) 个量子比特施加旋转 \(R_y(\theta_w)\)，并选取
由 \(p_{w0}+p_{w1}=p_w\) 知两个平方根的平方和为 \(1\)，故该角度良定义。该旋转只作用于振幅为 \(\sqrt{p_w}\) 的分支，得到
不同前缀 \(w\) 对应的旋转作用在相互正交的子空间上，因此彼此对易、可任意排序。对所有 \(w \in \{0,1\}^{\ell}\) 完成上述操作后即得 \(|\Phi_{\ell+1}\rangle\)，归纳完成。取 \(\ell = n\)，我们得到所有振幅均为非负实数的态 \(\sum_j \sqrt{p_j}|j\rangle\)。
第三步：相位修正。若目标振幅是复数，我们在振幅树之后追加一个相位树：对每个 \(j\) 施加多控相位门，把 \(|j\rangle\) 的相位从 \(0\) 旋到 \(\varphi_j\)；等价地，Möttönen 等人在每一层交错使用均匀受控的 \(R_z\) 旋转。由于全局相位无物理意义，我们可固定 \(\varphi_0 = 0\)，因此相位树至多包含 \(2^n - 1\) 个受控相位门。
数值例子。我们取 \(N = 4\)、\(p = (0.4,\ 0.1,\ 0.25,\ 0.25)\)（复算每个角度）：
第 1 层：左子树概率 \(p_0 = 0.4 + 0.1 = 0.5\)，故 \(\theta_\varnothing = 2\arcsin\sqrt{0.5} = 2 \times \frac{\pi}{4} = \frac{\pi}{2} \approx 1.5708\)；
第 2 层左分支：\(p_{00} = 0.4\)，\(p_{01} = 0.1\)，条件概率 \(p_{01}/p_0 = 0.2\)，故 \(\theta_0 = 2\arcsin\sqrt{0.2} \approx 2 \times 0.4636 = 0.9273\)，且 \(\cos(\theta_0/2) = \sqrt{0.8} \approx 0.8944\)、\(\sin(\theta_0/2) = \sqrt{0.2} \approx 0.4472\)；
第 2 层右分支：\(p_{10} = p_{11} = 0.25\)，条件概率各为 \(0.5\)，故 \(\theta_1 = \frac{\pi}{2}\)。
最终态为 \(\sqrt{0.5}\bigl(\sqrt{0.8}\,|00\rangle + \sqrt{0.2}\,|01\rangle\bigr) + \sqrt{0.5}\bigl(\sqrt{0.5}\,|10\rangle + \sqrt{0.5}\,|11\rangle\bigr)\)，即四个振幅分别为 \(\sqrt{0.5 \times 0.8} = \sqrt{0.4}\)、\(\sqrt{0.5 \times 0.2} = \sqrt{0.1}\)、\(\sqrt{0.5 \times 0.5} = \sqrt{0.25}\)、\(\sqrt{0.25}\)，其平方恰为 \((0.4,\ 0.1,\ 0.25,\ 0.25)\)，验证无误。
门数计数（朴素版）。完全二叉树的内部节点数为 \(\sum_{\ell=1}^{n} 2^{\ell-1} = 2^n - 1\)，每个节点对应一个多控 \(R_y\)；第 \(\ell\) 层的旋转带 \(\ell - 1\) 个控制比特，用 Barenco 等人的无辅助比特构造展开需要 \(O(\ell)\) 个两比特门，故朴素实现的门数为
门数计数（合并版，达到 \(2^n - 2\) 个 CNOT）。关键观察是：同一层的所有旋转作用在同一个目标比特上、只以控制取值区分。这种"以 \(\ell-1\) 个比特为控制、对每个控制取值施加一个独立角度"的算子称为均匀受控旋转（uniformly controlled rotation）。我们先对 \(\ell = 2\)（单控制、双角度 \(\theta_0, \theta_1\)）给出显式分解并验证：断言
其中 \(a = \frac{\theta_0 + \theta_1}{2}\)，\(b = \frac{\theta_0 - \theta_1}{2}\)。验证如下：控制比特为 \(|0\rangle\) 时两个 CNOT 均不作用，目标比特上剩 \(R_y(a)R_y(b) = R_y(a+b) = R_y(\theta_0)\)；控制比特为 \(|1\rangle\) 时，中间的旋转被两侧的 CNOT 共轭为 \(X R_y(b) X = R_y(-b)\)（因为 \(X Y X = -Y\)，故 \(X e^{-ibY/2} X = e^{+ibY/2}\)），目标比特上剩 \(R_y(a)R_y(-b) = R_y(\theta_1)\)。两个方程解出 \(a, b\) 即得断言。这一分解用了 \(2\) 个 CNOT 和 \(2\) 个单比特旋转。Möttönen 等人将该分解沿 Gray 码推广到 \(\ell\) 个比特：双角度情形换成 \(2^{\ell-1}\) 个角度后，恰好需要 \(2^{\ell-1}\) 个 CNOT 与 \(2^{\ell-1}\) 个 \(R_y\)。
于是对每一层使用均匀受控分解（第 1 层无控制比特，不需要 CNOT），CNOT 总数为
振幅树的 \(R_y\) 总数为 \(\sum_{\ell=1}^n 2^{\ell-1} = 2^n - 1\)；相位树（均匀受控 \(R_z\)）复用同一套 CNOT 骨架，再增加至多 \(2^n - 1\) 个旋转。因此该构造共需 \(2^n - 2\) 个 CNOT 与至多 \(2^{n+1} - 2\) 个单比特旋转；利用相邻同比特旋转可合并的性质，文献中的精确计数为 \(2^{n+1} - 2n\) 个单比特旋转。
深度。串行执行时，第 \(\ell\) 层的均匀受控旋转深度为 \(O(2^{\ell-1})\)，总深度为 \(O(2^n)\)。若把多控旋转视为基本门，则树只有 \(n\) 层、深度为 \(O(n)\)；但一旦把这些多控门展开为基本门，深度回到 \(O(N)\) 量级。要真正实现 \(O(n)\) 深度，需要 Zhang、Li、Yuan 的辅助比特并行技术（见方法五）。
优点与缺点。该构造完全显式、无需辅助比特、达到最优门数 \(O(N)\)；其缺点是门数对大 \(N\) 仍是指数级，深度也为 \(O(N)\)。
1.2 基于 Gray 码的方案（Shende–Bullock–Markov, 2006）¶
Shende、Bullock 与 Markov 给出了更系统的电路综合视角，并得到相同的紧门数。
定理：任意 \(n\) 量子比特纯态可以用 \(2^n - 2\) 个 CNOT 与 \(2^{n+1} - 2n\) 个单比特旋转精确制备，且通用构造需要 \(\Omega(2^n)\) 个门（见 1.4 节）。
构造：电路从 \(|0\cdots 0\rangle\) 出发，按 Gray 码顺序遍历非零基矢——相邻两个基矢恰好相差一个比特翻转，因此每步只需一个作用于该比特的多控门。在第 \(k\) 步，我们施加一个多控 \(R_y\)，把"当前驻留分支"的振幅的一部分搬运到下一个基矢，使已遍历基矢的振幅达到终值；随后施加多控相位门设置该基矢的相对相位。把振幅从第一个基矢搬运到最后一个基矢共需 \(2^n - 2\) 次转移，这正是 CNOT 数的来源。Gray 码调度的好处是：相邻步共享大部分控制比特，多控门展开时的 CNOT 序列可以大量复用。
1.3 基于 QR 分解的方案（Plesch–Brukner, 2011）¶
Plesch 与 Brukner 把制备问题视为酉矩阵综合的特例，只综合 \(U\) 的第一列。
推导：我们要找一列两维平面旋转（Givens 旋转）把 \(|\psi\rangle\) 化为 \(|0\cdots 0\rangle\)。对坐标 \((N-2, N-1)\) 施加 Givens 旋转 \(G(N\!-\!2, N\!-\!1)\)，把坐标 \(N-1\) 的振幅旋转归零，其质量并入坐标 \(N-2\)；再对 \((N-3, N-2)\) 施加 Givens 旋转归零坐标 \(N-2\)；依此类推，最后一步 \((0,1)\) 把全部振幅集中到坐标 \(0\)（每次旋转附带一个相位自由度，用来把留存振幅转成实正数）。总共需要 \(N - 1\) 个 Givens 旋转，且
每个 Givens 旋转只混合两个计算基矢 \(|i\rangle, |j\rangle\)，是一个两阶酉（two-level unitary），可用 \(O(n)\) 个两比特门实现；用 Gray 码把整列旋转一起调度后，总门数为 \(O(N)\) 个两比特门，与 1.1、1.2 的构造同阶（理论最优）。
1.4 门数下界：参数计数¶
我们证明任何通用构造都需要 \(\Omega(2^n)\) 个单比特门，从而 \(O(N)\) 门数不可改进。
\(n\) 比特纯态全体（模去全局相位）是复射影空间 \(\mathbb{CP}^{2^n - 1}\)，其实维数为 \(2 \cdot 2^n - 2 = 2^{n+1} - 2\)。考虑由 \(G_1\) 个任意单比特门（每个 \(3\) 个实参数）和任意数量的固定两比特门（如 CNOT，\(0\) 个实参数）组成的电路族：该族可实现的态集合由至多 \(3G_1\) 个实参数描述。若该族能制备所有 \(n\) 比特纯态，则参数化映射必须是到 \(2^{n+1}-2\) 维流形的满射，因此
结合 \(2^n - 2\) 个 CNOT 的可达构造（1.1–1.3 节），我们得出结论：通用态制备的门数为 \(\Theta(2^n)\)，无法避免。
复杂度总结¶
方法 |
CNOT 门数 |
深度 |
辅助比特 |
|---|---|---|---|
递归二分（朴素展开） |
\(O(nN)\) |
\(O(N)\) |
0 |
递归二分（均匀受控合并） |
\(2^n - 2\) |
\(O(N)\) |
0 |
Shende–Bullock–Markov |
\(2^n - 2\) |
\(O(N)\) |
0 |
QR 分解（Givens） |
\(O(N)\) |
\(O(N)\) |
0 |
理论下界 |
\(\Omega(N)\) |
\(\Omega(n)\) |
0 |
关键结论：通用态制备的门数下界是 \(\Omega(N)\)（1.4 节），深度的平凡下界是 \(\Omega(n)\)（每个数据比特至少要被一个门作用）。以下方法针对特定结构的态降低代价。
方法二：稀疏量子态制备¶
2.1 定义¶
\(s\)-稀疏量子态指只有 \(s\) 个非零振幅的态：\(|\psi\rangle = \sum_{j \in S} \alpha_j |j\rangle\)，\(|S| = s \ll N = 2^n\)。
我们的目标是以 \(O(s \cdot \mathrm{poly}(n))\) 个门制备 \(|\psi\rangle\)，即把门数从关于 \(N\) 指数级降为关于稀疏度多项式级。
2.2 Grover–Rudolph 方法（2002）¶
Grover 与 Rudolph 在 2002 年提出了用于概率分布制备的递归方法，是稀疏态制备的经典方案；其思想与 1.1 节的二叉树完全一致。
算法（对 \(s\)-稀疏态）：
我们在经典侧计算支撑集 \(S\) 中各元素二进制表示的前缀结构，即二叉树上从根到每个 \(j \in S\) 的路径；
对每个"分支点"（路径上度数不为 \(1\) 的内部节点），按 1.1 节公式计算条件概率 \(p_{w0}/p_w\) 与旋转角 \(\theta_w = 2\arcsin\sqrt{p_{w1}/p_w}\)；
用受控 \(R_y\) 旋转实现按比例分配，递归处理各子空间。
门数论证：\(s\) 条根到叶路径每条长度为 \(n\)，其并集（即所有需要放置旋转的节点）的大小至多为 \(sn\)；路径共享前缀时节点数更少。每个节点恰好对应一个受控旋转，故多控旋转数为 \(O(sn)\)。朴素地把第 \(\ell\) 层的多控旋转展开需要 \(O(\ell)\) 个基本门，总计 \(O(sn^2)\)；Ramacciotti 与 Turco（2024）证明对 Grover–Rudolph 做一个简单修改后可把依赖降到线性，总门数为 \(O(sn)\)（见 2.5 节）。
辅助比特：\(0\)。
优点：不需要辅助比特，构造简单，且与通用方案共享同一棵树。
缺点：需要经典预处理（计算 \(O(sn)\) 个条件概率），对动态更新的数据不友好。
2.3 基于 Oracle 的稀疏态制备¶
思想：我们假设存在量子预言机 \(O_S\) 能高效识别稀疏支撑 \(S\)（即 \(O_S|j\rangle = (-1)^{[j \in S]}|j\rangle\)），然后用量子搜索找到 \(S\) 中的元素。
算法：
我们以 \(O_S\) 为标记预言机，在均匀叠加态中做 Grover 搜索，逐一提取 \(S\) 中的元素；找到全部 \(s\) 个标记项的总代价为 \(O(\sqrt{Ns})\) 次 Grover 迭代；
对每个找到的 \(|j\rangle \in S\)，我们用受控旋转把振幅设定为 \(\alpha_j\)；
最后合并所有分支。
门数：\(O(\sqrt{Ns}\cdot n)\)（Grover 搜索）加上 \(O(sn)\)（振幅设定）。该方案适合 \(S\) 未知但可被高效判定的情形；代价是深度中有 \(\sqrt{N}\) 因子，劣于 2.2 节的树形方案。
2.4 最新进展：PRL 上的最优稀疏态制备¶
Zhang, Li, Yuan（PRL 129, 230504, 2022） 对任意 \(n\) 量子比特态给出了最优深度的制备方案。
核心思想：他们将态制备转化为"并行多控门"的调度问题，通过 Gray 码遍历和门合并技术，把深度从 \(O(N)\) 压缩到 \(\Theta(n)\)。
精确陈述（按原文摘要）：任意 \(n\) 比特态可以用只含单、两比特门的 \(\Theta(n)\) 深度电路制备，代价是指数多个辅助比特（\(O(2^n)\) 个）；对具有 \(d\) 个非零分量的稀疏态，深度可降为 \(\Theta(\log(nd))\)，辅助比特数为 \(O(nd\log d)\)。这一辅助比特数随系统规模仅多项式增长，接近最优。
门数：\(O(N)\)（受 1.4 节下界约束）；深度：\(\Theta(n)\)（匹配平凡下界——每个比特至少要被一个门作用）。
应用：
HHL 算法中 \(|b\rangle\) 的制备：\(\Theta(n)\) 深度；
量子化学初态制备：对 \(s\)-稀疏初态，\(O(sn)\) 门。
2.5 PRA 2024：简化稀疏态制备¶
Ramacciotti 与 Turco（PRA 110, 032609, 2024） 分析了 Grover–Rudolph 算法在稀疏目标态上的表现：
原始 Grover–Rudolph 用于稀疏态时门数关于非零振幅数 \(s\) 线性、关于比特数 \(n\) 二次，即 \(O(sn^2)\)；
他们提出一个简单修改（合并相邻层中控制比特相同的旋转），把对比特数的依赖也降为线性，总门数为 \(O(sn)\)；
该方案不需要辅助比特，并利用稀疏支撑的树形结构在经典侧高效计算条件概率。
方法三：特定分布的量子态制备¶
3.1 均匀分布态¶
我们只需 \(n\) 个 Hadamard 门。验证：\(H|0\rangle = (|0\rangle + |1\rangle)/\sqrt 2 = |+\rangle\)，张量积展开即得 \(N = 2^n\) 项等幅叠加。
3.2 正态分布态¶
目标态为
方法一（余弦幂近似）。我们先证明恒等式 \(e^{-x^2/2} = \lim_{M\to\infty} \cos(x/\sqrt M)^M\)。利用泰勒展开 \(\log\cos y = -\frac{y^2}{2} + O(y^4)\)（\(y \to 0\)），取 \(y = x/\sqrt M\) 得
故 \(\cos(x/\sqrt M)^M \to e^{-x^2/2}\)，误差为 \(O(x^4/M)\) 量级。于是我们把高斯核写成 \(M\) 个余弦因子的乘积，每个因子对应一层"把分支 \(|j\rangle\) 的振幅乘以 \(\cos\theta_j\)"的受控旋转（\(\theta_j = (j-\mu)/(\sigma\sqrt M)\)），共 \(M\) 层，每层是一个有 \(2^n\) 个角度的均匀受控旋转、\(O(2^n)\) 个门。该方案的总门数为 \(O(M\cdot 2^n)\)，精度由 \(M\) 控制；它适合 \(x_j = (j-\mu)/\sigma\) 取值范围不太大的场景。
方法二（截断 + 稀疏态制备）。高斯核衰减极快，超出若干个标准差的部分可以直接截断。我们验证截断误差：对 \(t > 0\)，
其中第一格用了单调递减函数的求和不超过积分，第二格是标准的高斯尾界（分部积分可得）。取 \(t = \sigma\sqrt{2\ln(2/\varepsilon)}\) 即可把尾部总质量压到 \(\varepsilon\) 以下。因此对 \(\sigma = O(n)\) 的离散高斯，有效支撑只有 \(s = O(\sigma\sqrt{\log(1/\varepsilon)}) = O(n\,\mathrm{polylog})\) 个点；再用 2.2 节的稀疏态制备，门数为 \(O(sn) = O(n^2\,\mathrm{polylog})\)，避免了指数代价。
3.3 幂律分布态¶
目标态为
方法：我们用 Grover–Rudolph 递归，在每一层计算条件概率 \(p_{w0}/p_w\)。前缀和 \(j^{-\alpha}\) 没有初等闭式，但可以在经典侧以 \(O(N)\) 时间预算预处理并存储，从而满足 Grover–Rudolph 对"条件概率可高效计算"的要求；此时通用门数为 \(O(2^n)\)。
稀疏化论证：对 \(\alpha > 1\)，幂律尾部可以截断。与 3.2 节同理，
要使尾部不超过 \(\varepsilon\)，只需 \(t \ge \bigl((\alpha-1)\varepsilon\bigr)^{-1/(\alpha-1)}\)。这个截断点与 \(N\) 无关，因此有效支撑 \(s = O\bigl(\varepsilon^{-1/(\alpha-1)}\bigr)\) 对固定的 \(\varepsilon\)、\(\alpha\) 是常数，稀疏态制备给出门数 \(O(sn) = O(n)\)。
3.4 Qiskit/MPS 方法¶
对低纠缠态，我们利用矩阵乘积态（Matrix Product State, MPS）分解
其中 \(\chi\) 为键维度（bond dimension）。Schön 等人的顺序生成结果表明：MPS 与"阶梯形"两比特门电路等价，把 MPS 转换为电路需要 \(n-1\) 个阶梯排列的多比特门，每个可分解为 \(O(\chi^2)\) 个两比特门。
门数：\(O(n\chi^2)\)；对低纠缠态 \(\chi = O(1)\)，门数为 \(O(n)\)——相对通用方案是指数级改进。
方法四：基于 QRAM 的量子态制备¶
4.1 标准 QRAM 方案¶
若经典数据 \(\mathbf{v}\) 存储在量子随机存取存储器（QRAM）中，则查询操作实现 \(|j\rangle|0\rangle \mapsto |j\rangle|v_j\rangle\)；QRAM 的结构与代价详见本教程的 QRAM 一文。我们给出完整的振幅编码流程（这是 Sanders 等人 2019 年"无算术黑盒态制备"的框架）。
步骤一（叠加 + 查询）：我们先制备均匀叠加并查询 QRAM，使值寄存器写入与 \(j\) 配对的数据：
其中我们让 QRAM 在地址 \(j\) 处存储数对 \((c_j, s_j)\)，满足 \(c_j^2 + s_j^2 = 1\) 且 \(s_j = \gamma v_j\)，\(\gamma \le 1/\max_j |v_j|\) 为缩放因子。直接存储 \((c_j, s_j)\) 而非 \(v_j\) 本身，是为了避免在量子侧计算 \(\arcsin\)。
步骤二（受控旋转）：我们以值寄存器为控制，对辅助比特施加旋转 \(|0\rangle \mapsto c_j|0\rangle + s_j|1\rangle\)，得到
步骤三（后选择与幅度放大）：测得辅助比特为 \(|1\rangle\) 的概率为
成功时地址寄存器坍缩为 \(\sum_j v_j |j\rangle / \|\mathbf v\|\)，即目标态（值寄存器随后用一次反向 QRAM 查询擦除）。用 \(O(1/\sqrt q)\) 轮幅度放大可以把成功概率提升到 \(\Theta(1)\)，因此总查询次数为 \(O\bigl(\sqrt N / (\gamma\|\mathbf v\|)\bigr)\)。
代价：每轮查询的深度为 \(O(\log N)\)，但 QRAM 硬件需要 \(O(N)\) 个存储单元。QRAM 方案把门数换成硬件开销，这正是其争议所在。
4.2 CVO-QRAM（Conditional Value Oracle）¶
思想：我们不存储完整数据，只存储"值是否非零"的稀疏标志位，结合受控旋转实现振幅设定。
算法：
我们用条件值预言机（CVO）标识非零振幅的位置 \(j \in S\)；
对每个 \(j \in S\)，用受控旋转把振幅设为 \(\alpha_j = v_j / \|\mathbf v\|\)；
用幅度放大（Grover 型）放大所有非零分量。
门数：\(O(sn)\)，\(s\) 为非零分量数。
优点：避免了 QRAM 的 \(O(N)\) 存储要求，只需要 \(O(sn)\) 量级的量子比特和门。
4.3 QRAM 在量子化学中的应用¶
Sparse Quantum State Preparation for Strongly Correlated Systems（J. Phys. Chem. Lett., 2024） 将 CVO-QRAM 方法应用于强关联化学体系的基态制备，并实验验证到 28 量子比特：
该工作使用高效保对称变分拟设（Efficient Symmetry-Preserving, ESP Ansatz）；
通过 CVO-QRAM 加速初态制备；
在 GPU 上模拟了含 \(O(10^6)\) 参数的量子电路。
方法五：PRL 2022 的最优深度方案（Zhang, Li, Yuan）¶
核心结果¶
定理（Zhang, Li, Yuan, PRL 129, 230504, 2022）：任意 \(n\) 量子比特纯态 \(|\psi\rangle = \sum_{j=0}^{2^n-1} \alpha_j |j\rangle\) 可以用深度 \(\Theta(n)\)、仅含单比特与两比特门的电路制备，代价是 \(O(2^n)\) 个辅助比特。
门数：\(O(2^n)\)（受 1.4 节参数计数下界约束）。深度：\(\Theta(n)\)（理论最优；下界是平凡的——每个数据比特至少要被一个门触碰）。
需要澄清一点：\(\Theta(n)\) 深度与"零辅助比特"不可兼得。无辅助比特时，已知构造（1.1–1.3 节）的深度为 \(\Theta(N)\)；Zhang 等人用指数级辅助比特换取并行化，这也是原文摘要中"用辅助比特换深度"的主旨。
技术要点¶
1. Gray 码并行化。传统方法按 Gray 码序逐个处理基矢，深度 \(O(N)\)。Zhang 等人观察到：多个"独立的"多控门（控制与目标比特集合不相交）可以并行执行。
2. 门合并。相邻的两个多控门若控制条件只差一个比特，可以合并为一个更深的门，而不增加总深度。
3. 分层调度。我们把所有门按"作用的量子比特层"分组，每组内的门并行执行；辅助比特用来承载扇出（fan-out）与中间结果，使得每个目标比特的依赖链长度为 \(O(1)\)，总深度等于层数 \(\Theta(n)\)。
对稀疏态的改进¶
对 \(s\)-稀疏态（\(s\) 个非零振幅），Zhang 等人的方案给出：深度 \(\Theta(\log(ns))\)、辅助比特 \(O(ns\log s)\)、门数 \(O(sn)\)（串行调度）至 \(O(ns\log s)\)（完全并行调度）。在 \(s \ll N\) 时，这是相对通用方案的指数级改进。
方法六：变分量子态制备（VQSP）¶
思想¶
我们把态制备转化为变分优化问题：
我们先把这个目标与保真度等价起来。利用 \(\||a\rangle - |b\rangle\|^2 = \langle a|a\rangle + \langle b|b\rangle - 2\,\mathrm{Re}\langle a|b\rangle = 2 - 2\,\mathrm{Re}\langle a|b\rangle\)，记保真度 \(F = |\langle\psi(\vec\theta)|\psi_{\text{target}}\rangle|^2\)，则
即最小化距离等价于最大化保真度；实践中常用代价函数 \(C(\vec\theta) = 1 - F\)。我们用参数化量子电路 \(U(\vec{\theta})\) 作用于 \(|0\rangle^{\otimes n}\) 得到 \(|\psi(\vec\theta)\rangle\)，并用交换测试或"逆向电路 + 测量"估计 \(F\)。
优势¶
门数由参数化电路结构决定，不依赖于 \(N\)；
适用于 NISQ 设备。
局限¶
优化可能陷入局部极小；
参数化电路存在贫瘠高原（Barren Plateaus）问题，梯度随规模指数衰减；
不保证精确制备。
方法七：基于 QSVT 的态制备¶
思想¶
若目标态可以写成 \(|\psi\rangle \propto f(A)|0\rangle\)（\(A\) 为某厄米算符或酉算符，\(f\) 为某函数），我们用量子奇异值变换（Quantum Singular Value Transformation, QSVT）实现 \(f(A)\) 的块编码，然后作用于 \(|0\rangle\)。
应用¶
Gibbs 态制备：\(|\psi_\beta\rangle \propto e^{-\beta H/2}|0\rangle\)，取 \(f(x) = e^{-\beta x/2}\)；
基态制备：取滤子函数 \(f(x) = (x - \tilde E)^{-1}\)，其中 \(\tilde E = E_0 - \Delta\) 是低于基态能量的偏移量。由于 \(f\) 在谱上单调递减，\(f(H)|0\rangle\) 中基态分量的相对权重最大；\(\Delta\) 越大滤子越平缓、多项式近似越容易。
门数¶
\(O(\mathrm{deg}(f_{\text{approx}}) \cdot C_{U_A})\)，其中 \(C_{U_A}\) 为块编码代价、\(\mathrm{deg}(f_{\text{approx}})\) 为 \(f\) 的多项式近似次数。
复杂度总结¶
方法 |
门数 |
深度 |
辅助比特 |
适用场景 |
|---|---|---|---|---|
递归二分（合并） |
\(O(N)\) |
\(O(N)\) |
0 |
通用 |
Shende–Bullock–Markov |
\(O(N)\) |
\(O(N)\) |
0 |
通用 |
Zhang（PRL 2022） |
\(O(N)\) |
\(\Theta(n)\) |
\(O(2^n)\) |
通用（最优深度） |
Grover–Rudolph（稀疏） |
\(O(sn)\) |
\(O(sn)\) |
0 |
稀疏态 |
Ramacciotti–Turco（PRA 2024） |
\(O(sn)\) |
\(O(sn)\) |
0 |
稀疏态（简化） |
Zhang（稀疏版） |
\(O(ns\log s)\) |
\(\Theta(\log(ns))\) |
\(O(ns\log s)\) |
稀疏态（最优深度） |
CVO-QRAM |
\(O(sn)\) |
\(O(sn)\) |
\(O(\log s)\) |
稀疏态 + QRAM |
MPS 分解 |
\(O(n\chi^2)\) |
\(O(n)\) |
0 |
低纠缠态 |
变分方法 |
\(O(pn)\) |
\(O(Dn)\) |
0 |
近似制备 |
实验实现¶
年份 |
平台 |
规模 |
方法 |
|---|---|---|---|
2020 |
IBM |
5 量子比特 |
递归二分 |
2022 |
超导 |
12 量子比特 |
Zhang 最优深度方案 |
2023 |
光量子 |
100+ 模式 |
压缩态制备 |
2024 |
GPU 模拟 |
28 量子比特 |
CVO-QRAM + ESP Ansatz |
局限性¶
通用态制备不可避免 \(O(N)\) 门：这是 1.4 节参数计数给出的信息论下界，任何方案都无法突破。
稀疏态需要已知支撑：若不知道哪些振幅非零，需要额外的搜索代价（2.3 节）。
QRAM 的物理可行性存疑：\(O(N)\) 硬件与精度要求是主要障碍，参见本教程的 QRAM 一文。
变分方法无法保证精度：对需要高保真的下游算法（如量子相位估计）不适用。
噪声累积：\(O(N)\) 个门的噪声累积可能使结果不可用；最优深度方案以 \(O(2^n)\) 辅助比特缓解深度问题，但硬件代价同样巨大。
总结¶
量子态制备的代价高度依赖目标态的结构：通用态需要 \(\Theta(2^n)\) 个门（我们用参数计数证明了下界，用均匀受控旋转构造达到了 \(2^n - 2\) 个 CNOT），稀疏态只需 \(O(sn)\) 个门，低纠缠态可用 \(O(n\chi^2)\) 个门。Zhang 等人（PRL 2022）用指数级辅助比特把任意态制备的深度压缩到 \(\Theta(n)\)，是近年理论上的重要突破。在实际应用中，我们应根据目标态的结构（稀疏性、纠缠、分布形状）选择合适的制备方案。
参考文献：
Grover, L., & Rudolph, T. (2002). Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph/0208112.
Sanders, Y. R., et al. (2019). Black-box quantum state preparation without arithmetic. Physical Review Letters, 122(2), 020502.
Zhang, X.-M., Li, T., & Yuan, X. (2022). Quantum state preparation with optimal circuit depth: Implementations and applications. Physical Review Letters, 129(23), 230504.
Ramacciotti, D., & Turco, A. (2024). A simple quantum algorithm to efficiently prepare sparse states. Physical Review A, 110, 032609.
Shende, V. V., Bullock, S. S., & Markov, I. L. (2006). Synthesis of quantum-logic circuits. IEEE TCAD, 25(6), 1000-1010.
返回目录：量子计算算法教程系列