# 量子态制备详解：从门电路到结构化加速

量子态制备（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$，使得

$$U|0\rangle^{\otimes n} = |\psi\rangle = \frac{1}{\|\mathbf{v}\|} \sum_{j=0}^{N-1} v_j |j\rangle .$$

我们强调这一问题的三重挑战：

- 经典数据有 $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 分别给出并优化。

**记号**。设目标态为

$$|\psi\rangle = \sum_{j=0}^{N-1} \alpha_j |j\rangle, \qquad \alpha_j = \sqrt{p_j}\, e^{i\varphi_j}, \qquad \sum_j p_j = 1,$$

其中 $p_j = |\alpha_j|^2$。对长度为 $\ell$ 的比特串 $w \in \{0,1\}^\ell$，我们用 $j \prec w$ 表示基矢指标 $j$ 的二进制展开以 $w$ 为前缀，并定义**子树概率**

$$p_w \;=\; \sum_{j \prec w} p_j, \qquad p_\varnothing = 1 .$$

由定义，前缀为 $w$ 的指标集合恰好被 $w0$、$w1$ 二等分，因此 $p_{w0} + p_{w1} = p_w$。

**第一步：单比特旋转的作用**。我们采用约定

$$R_y(\theta) = \exp\!\left(-i\frac{\theta}{2}Y\right) = \begin{pmatrix} \cos(\theta/2) & -\sin(\theta/2) \\ \sin(\theta/2) & \cos(\theta/2) \end{pmatrix},$$

直接读出矩阵的第一列便得基本恒等式

$$R_y(\theta)|0\rangle = \cos\frac{\theta}{2}\,|0\rangle + \sin\frac{\theta}{2}\,|1\rangle .$$

**第二步：旋转角度的推导**。我们对层号 $\ell = 0, 1, \ldots, n$ 归纳证明：在处理完前 $\ell$ 层之后，电路将初态变为

$$|\Phi_\ell\rangle = \sum_{w \in \{0,1\}^\ell} \sqrt{p_w}\; |w\rangle \otimes |0\rangle^{\otimes (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)$，并选取

$$\cos\frac{\theta_w}{2} = \sqrt{\frac{p_{w0}}{p_w}}, \qquad \sin\frac{\theta_w}{2} = \sqrt{\frac{p_{w1}}{p_w}}
\qquad\Longleftrightarrow\qquad
\theta_w = 2\arcsin\sqrt{\frac{p_{w1}}{p_w}} = 2\arccos\sqrt{\frac{p_{w0}}{p_w}} .$$

由 $p_{w0}+p_{w1}=p_w$ 知两个平方根的平方和为 $1$，故该角度良定义。该旋转只作用于振幅为 $\sqrt{p_w}$ 的分支，得到

$$\sqrt{p_w}\;|w\rangle|0\rangle \;\longmapsto\; \sqrt{p_w}\left(\sqrt{\frac{p_{w0}}{p_w}}\,|w0\rangle + \sqrt{\frac{p_{w1}}{p_w}}\,|w1\rangle\right) = \sqrt{p_{w0}}\,|w0\rangle + \sqrt{p_{w1}}\,|w1\rangle .$$

不同前缀 $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)$ 个两比特门，故朴素实现的门数为

$$\sum_{\ell=1}^{n} 2^{\ell-1}\, O(\ell) = O(n\,2^n) = O(N \log N).$$

**门数计数（合并版，达到 $2^n - 2$ 个 CNOT）**。关键观察是：同一层的所有旋转作用在**同一个目标比特**上、只以控制取值区分。这种"以 $\ell-1$ 个比特为控制、对每个控制取值施加一个独立角度"的算子称为**均匀受控旋转**（uniformly controlled rotation）。我们先对 $\ell = 2$（单控制、双角度 $\theta_0, \theta_1$）给出显式分解并验证：断言

$$\begin{pmatrix} R_y(\theta_0) & 0 \\ 0 & R_y(\theta_1) \end{pmatrix} = \bigl(R_y(a)\otimes I\bigr)\cdot \mathrm{CNOT}\cdot\bigl(R_y(b)\otimes I\bigr)\cdot \mathrm{CNOT},$$

其中 $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 总数为

$$\sum_{\ell=2}^{n} 2^{\ell-1} = (2^n - 1) - 1 = 2^n - 2 .$$

振幅树的 $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 旋转，且

$$|\psi\rangle = G(0,1)^\dagger\, G(1,2)^\dagger \cdots G(N\!-\!2, N\!-\!1)^\dagger\, |0\cdots 0\rangle .$$

每个 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$ 维流形的满射，因此

$$3 G_1 \;\ge\; 2^{n+1} - 2 \qquad\Longrightarrow\qquad G_1 \;\ge\; \frac{2^{n+1} - 2}{3} = \Omega(2^n).$$

结合 $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$-稀疏态）：

1. 我们在经典侧计算支撑集 $S$ 中各元素二进制表示的前缀结构，即二叉树上从根到每个 $j \in S$ 的路径；
2. 对每个"分支点"（路径上度数不为 $1$ 的内部节点），按 1.1 节公式计算条件概率 $p_{w0}/p_w$ 与旋转角 $\theta_w = 2\arcsin\sqrt{p_{w1}/p_w}$；
3. 用受控 $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$ 中的元素。

**算法**：

1. 我们以 $O_S$ 为标记预言机，在均匀叠加态中做 Grover 搜索，逐一提取 $S$ 中的元素；找到全部 $s$ 个标记项的总代价为 $O(\sqrt{Ns})$ 次 Grover 迭代；
2. 对每个找到的 $|j\rangle \in S$，我们用受控旋转把振幅设定为 $\alpha_j$；
3. 最后合并所有分支。

**门数**：$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 均匀分布态

$$|U_N\rangle = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} |j\rangle = |+\rangle^{\otimes n}$$

我们只需 $n$ 个 Hadamard 门。验证：$H|0\rangle = (|0\rangle + |1\rangle)/\sqrt 2 = |+\rangle$，张量积展开即得 $N = 2^n$ 项等幅叠加。

### 3.2 正态分布态

目标态为

$$|\mathcal{N}\rangle \propto \sum_j e^{-(j-\mu)^2/2\sigma^2}\, |j\rangle .$$

**方法一（余弦幂近似）**。我们先证明恒等式 $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$ 得

$$M \log\cos\frac{x}{\sqrt M} = M\left(-\frac{x^2}{2M} + O\!\left(\frac{x^4}{M^2}\right)\right) = -\frac{x^2}{2} + O\!\left(\frac{x^4}{M}\right) \xrightarrow{M\to\infty} -\frac{x^2}{2},$$

故 $\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$，

$$\sum_{k > t} e^{-k^2/2\sigma^2} \;\le\; \int_t^\infty e^{-x^2/2\sigma^2}\,dx \;\le\; \frac{\sigma^2}{t}\, e^{-t^2/2\sigma^2},$$

其中第一格用了单调递减函数的求和不超过积分，第二格是标准的高斯尾界（分部积分可得）。取 $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 幂律分布态

目标态为

$$|\mathrm{pow}\rangle \propto \sum_j j^{-\alpha}\, |j\rangle .$$

**方法**：我们用 Grover–Rudolph 递归，在每一层计算条件概率 $p_{w0}/p_w$。前缀和 $j^{-\alpha}$ 没有初等闭式，但可以在经典侧以 $O(N)$ 时间预算预处理并存储，从而满足 Grover–Rudolph 对"条件概率可高效计算"的要求；此时通用门数为 $O(2^n)$。

**稀疏化论证**：对 $\alpha > 1$，幂律尾部可以截断。与 3.2 节同理，

$$\sum_{j > t} j^{-\alpha} \;\le\; \int_t^\infty x^{-\alpha}\, dx \;=\; \frac{t^{1-\alpha}}{\alpha - 1},$$

要使尾部不超过 $\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）分解

$$|\psi\rangle = \sum_{i_1,\ldots,i_n} \mathrm{tr}\!\left[A_1^{i_1} A_2^{i_2} \cdots A_n^{i_n}\right] |i_1 i_2 \cdots i_n\rangle,$$

其中 $\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$ 配对的数据：

$$\frac{1}{\sqrt N}\sum_j |j\rangle|0\rangle \;\longmapsto\; \frac{1}{\sqrt N}\sum_j |j\rangle\,|c_j\rangle|s_j\rangle,$$

其中我们让 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$，得到

$$\frac{1}{\sqrt N}\sum_j |j\rangle\,|c_j\rangle|s_j\rangle\,\bigl(c_j|0\rangle + s_j|1\rangle\bigr).$$

**步骤三（后选择与幅度放大）**：测得辅助比特为 $|1\rangle$ 的概率为

$$q = \frac{1}{N}\sum_j s_j^2 = \frac{\gamma^2 \|\mathbf v\|^2}{N},$$

成功时地址寄存器坍缩为 $\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）

**思想**：我们不存储完整数据，只存储"值是否非零"的稀疏标志位，结合受控旋转实现振幅设定。

**算法**：

1. 我们用条件值预言机（CVO）标识非零振幅的位置 $j \in S$；
2. 对每个 $j \in S$，用受控旋转把振幅设为 $\alpha_j = v_j / \|\mathbf v\|$；
3. 用幅度放大（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）

### 思想

我们把态制备转化为变分优化问题：

$$\min_{\vec{\theta}} \left\| |\psi(\vec{\theta})\rangle - |\psi_{\text{target}}\rangle \right\|^2 .$$

我们先把这个目标与保真度等价起来。利用 $\||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$，则

$$\left\| |\psi(\vec{\theta})\rangle - |\psi_{\text{target}}\rangle \right\|^2 = 2 - 2\sqrt{F} = 2\bigl(1 - \sqrt{F}\bigr),$$

即最小化距离等价于最大化保真度；实践中常用代价函数 $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 |

## 局限性

1. **通用态制备不可避免 $O(N)$ 门**：这是 1.4 节参数计数给出的信息论下界，任何方案都无法突破。
2. **稀疏态需要已知支撑**：若不知道哪些振幅非零，需要额外的搜索代价（2.3 节）。
3. **QRAM 的物理可行性存疑**：$O(N)$ 硬件与精度要求是主要障碍，参见本教程的 QRAM 一文。
4. **变分方法无法保证精度**：对需要高保真的下游算法（如量子相位估计）不适用。
5. **噪声累积**：$O(N)$ 个门的噪声累积可能使结果不可用；最优深度方案以 $O(2^n)$ 辅助比特缓解深度问题，但硬件代价同样巨大。

## 总结

量子态制备的代价高度依赖目标态的结构：通用态需要 $\Theta(2^n)$ 个门（我们用参数计数证明了下界，用均匀受控旋转构造达到了 $2^n - 2$ 个 CNOT），稀疏态只需 $O(sn)$ 个门，低纠缠态可用 $O(n\chi^2)$ 个门。Zhang 等人（PRL 2022）用指数级辅助比特把任意态制备的深度压缩到 $\Theta(n)$，是近年理论上的重要突破。在实际应用中，我们应根据目标态的结构（稀疏性、纠缠、分布形状）选择合适的制备方案。

---

**参考文献：**

1. Grover, L., & Rudolph, T. (2002). *Creating superpositions that correspond to efficiently integrable probability distributions.* arXiv:quant-ph/0208112.
2. Sanders, Y. R., et al. (2019). *Black-box quantum state preparation without arithmetic.* Physical Review Letters, 122(2), 020502.
3. Zhang, X.-M., Li, T., & Yuan, X. (2022). *Quantum state preparation with optimal circuit depth: Implementations and applications.* Physical Review Letters, 129(23), 230504.
4. Ramacciotti, D., & Turco, A. (2024). *A simple quantum algorithm to efficiently prepare sparse states.* Physical Review A, 110, 032609.
5. Shende, V. V., Bullock, S. S., & Markov, I. L. (2006). *Synthesis of quantum-logic circuits.* IEEE TCAD, 25(6), 1000-1010.
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)