# 数据 QRAM 详解：量子随机存取存储器的原理与前沿

QRAM（Quantum Random Access Memory，量子随机存取存储器）是量子计算中最具变革性但也最具争议的基础设施。它允许以量子叠加的方式并行访问经典数据库，是实现多项式加速的关键假设之一。本文详细分析 QRAM 的两种主要架构——桶链式（bucket brigade）架构与基于预制备资源态的方案——给出查询复杂度 $O(\log N)$ 的完整论证、交换测试等关键子例程的推导，澄清 QRAM 与量子态制备的区别，并讨论其物理可行性争议。

## 问题背景：为什么需要 QRAM

### 数据访问的瓶颈

大量量子算法的加速依赖于对经典数据的高效量子访问：

| 算法 | QRAM 需求 |
|------|-----------|
| HHL 线性方程组 | 制备 $|b\rangle$（需访问 $\vec{b}$ 的所有分量） |
| 量子推荐系统 | 访问用户-商品评分矩阵 |
| 量子主成分分析 | 访问密度矩阵的经典描述 |
| 量子机器学习 | 访问训练数据 |
| Grover 搜索 | 访问数据库 $f(x)$ |

没有 QRAM 时，我们把 $N$ 个经典数据加载到量子态需要 $O(N)$ 步——这会抵消许多量子加速。

### QRAM 的定义

**定义**：QRAM 是一个实现如下酉嵌入（unitary embedding）的量子设备：给定地址寄存器 $|a\rangle$ 和初始为 $|0\rangle$ 的数据寄存器，它实现

$$|a\rangle|0\rangle \;\longmapsto\; |a\rangle|D_a\rangle ,$$

其中 $D_a$ 是存储在地址 $a$ 的数据。

**关键要求**：由线性性，该操作对叠加态也必须成立：

$$\sum_{a} \alpha_a |a\rangle|0\rangle \;\longmapsto\; \sum_{a} \alpha_a |a\rangle|D_a\rangle .$$

即所有地址被相干地并行访问——这是 QRAM 的量子优势来源。我们要强调：这要求操作是**可逆的酉演化**，而不是"读出再写入"；因此查询结束后必须能够反计算（uncompute），把设备内部的辅助系统还原，否则连续两次查询会引入不可控的纠缠。

## 架构一：Bucket Brigade QRAM

### 基本思想

Bucket Brigade QRAM 由 Giovannetti、Lloyd 与 Maccone 于 2008 年提出，是目前讨论最广泛的 QRAM 架构。

**核心结构**：一棵深度为 $d = \lceil\log_2 N\rceil$ 的二叉树，叶节点存储数据，内部节点为"路由器"（router）。

### 架构细节

**树结构**：

- 深度 $d = \lceil\log_2 N\rceil$（$N$ 个数据项）；满二叉树的路由器（内部节点）总数为 $1 + 2 + \cdots + 2^{d-1} = N - 1$；
- 每个路由器是一个三能级系统（qutrit）：$|w\rangle$（等待/wait）、$|0\rangle$（向左子树路由）、$|1\rangle$（向右子树路由）；
- 叶节点存储数据 $D_k$。

**路由操作**。地址比特逐个由一条量子总线（bus，例如光子）携带进入树。当一个处于等待态的路由器遇到总线上的地址比特 $a \in \{0,1\}$ 时，发生一次"吸收"酉操作：路由器记录该比特，总线归零并继续前进：

$$|a\rangle_{\text{总线}}\,|w\rangle_{\text{路由器}} \;\longmapsto\; |0\rangle_{\text{总线}}\,|a\rangle_{\text{路由器}}, \qquad a \in \{0, 1\};$$

（对叠加的地址比特，线性性保证 $\bigl(\alpha|0\rangle + \beta|1\rangle\bigr)|w\rangle \mapsto |0\rangle\bigl(\alpha|0\rangle + \beta|1\rangle\bigr)$，即地址的量子信息被完整地搬进路由器。）已激活的路由器（处于 $|0\rangle$ 或 $|1\rangle$）对后续总线执行**经典**开关行为：把总线向左或向右子树转发，不再发生任何量子相互作用。物理上，吸收操作可以用受控交换（Fredkin 门、量子光开关或离子阱的条件转移）实现。

**完整查询的三阶段**。我们把一次对叠加地址 $\sum_a \alpha_a|a\rangle$ 的查询分解为三个阶段，并写出每阶段结束时的系统状态：

1. **路由**：地址比特逐位进入，第 $k$ 位决定第 $k$ 层路由器的指向。路由结束后，路由器树整体保存了地址，总线归零：

$$\sum_a \alpha_a |a\rangle_{\text{地址}}\,\bigl(|w\rangle^{\otimes(N-1)}\bigr)_{\text{路由器}} \;\longmapsto\; \sum_a \alpha_a\, |a\rangle_{\text{路由器树}}\,|0\rangle^{\otimes n}_{\text{总线}};$$

2. **读出**：一束读出脉冲（READ pulse）沿已激活的路径下行到叶节点，把数据 $D_a$ 相干地写入总线并原路返回：

$$\sum_a \alpha_a\, |a\rangle_{\text{路由器}}\,|0\rangle_{\text{总线}} \;\longmapsto\; \sum_a \alpha_a\, |a\rangle_{\text{路由器}}\,|D_a\rangle_{\text{总线}};$$

3. **反计算**：地址寄存器反向重放一遍（或等价地把路由阶段整体逆转），把路由器树还原到全等待态、并把地址恢复到地址寄存器：

$$\sum_a \alpha_a\, |a\rangle_{\text{路由器}}\,|D_a\rangle \;\longmapsto\; \bigl(|w\rangle^{\otimes(N-1)}\bigr)_{\text{路由器}} \sum_a \alpha_a\, |a\rangle_{\text{地址}}\,|D_a\rangle .$$

最终效果正是定义中的酉嵌入，且设备内部恢复原状、可供下一次查询使用。

### 查询复杂度 $O(\log N)$ 的论证

我们对深度与门数做完整计数。设 $N = 2^d$（一般情形取 $d = \lceil\log_2 N\rceil$）：

- **路由阶段**：地址有 $d$ 个比特、逐位进入，第 $k$ 步只与第 $k$ 层的路由器发生一次吸收操作，共 $d$ 步；
- **读出阶段**：读出脉冲沿长度为 $d$ 的路径下行并返回，共 $O(d)$ 步；
- **反计算阶段**：与路由阶段对称，$O(d)$ 步。

三阶段合计，单次查询的深度与门数均为

$$O(d) = O(\log N),$$

与数据规模仅对数相关。硬件方面，路由器树需要 $N - 1$ 个 qutrit 加上 $N$ 个存储单元，即 $O(N)$ 的物理资源。总结如下表：

| 资源 | 数量 |
|------|------|
| 路由器（qutrit） | $N - 1$ |
| 存储单元 | $N$ |
| 查询深度 | $O(\log N)$ |
| 单次查询门数 | $O(\log N)$ |

**看起来很高效**：$O(\log N)$ 深度实现 $N$ 个数据的并行相干访问。但这一账本的成立依赖于噪声论证，见下文。

### 激活路由器的数目：基态地址与叠加地址的区别

原始论文的直觉是"每次调用只有 $O(\log N)$ 个路由器改变状态"。我们需要区分两种情形：

- **基态地址**：只有从根到目标叶的一条长度为 $d$ 的路径上的路由器被激活，严格为 $O(\log N)$ 个；
- **叠加地址**：第 $k$ 层的路由器只要对应叠加中出现的某个前缀就会被激活。对均匀叠加 $\frac{1}{\sqrt N}\sum_a|a\rangle$，所有 $N - 1$ 个内部路由器都会被激活。

因此"同时只有一个路径被激活"的说法对叠加查询并不成立；bucket brigade 在叠加查询中原则上会触碰全部 $O(N)$ 个路由器。不过，纠缠结构仍然友好：路由器树的状态与地址一一对应（第 2 阶段结束时为 $\sum_a \alpha_a|a\rangle_{\text{路由器}}|D_a\rangle$），反计算后路由器解缠恢复原状。$O(\log N)$ 的深度论证不受影响——它来自"地址逐位串行进入、每层只操作一次"，而不是来自激活元件的数目。

### 关键争议：物理可行性

**问题 1：退相干**。路由器必须在查询期间保持相干。对 $d = \log N$ 层的查询，相干时间需为门时间的 $O(\log N)$ 倍——目前技术可及。

**问题 2：存储稳定性**。数据必须长期存储在叶节点。对超导量子比特，相干时间约 $100\,\mu s$ 量级，限制了数据的存储时间。

**问题 3（核心争议）：操作精度**。我们的论证遵循以下层次：

1. **朴素上界（扇出型架构）**：若一次查询会触碰全部 $O(N)$ 个部件、每个部件以概率 $\varepsilon$ 出错，则总误差约为 $N\varepsilon$，要把总误差压到常数就需要 $\varepsilon = O(1/N)$——每部件精度必须随规模指数收紧，这不可行。
2. **Arunachalam 等人（2015）的严格分析**：他们为 bucket brigade 建立了电路模型并证明，在**局部非相干噪声**模型下，桶链式结构远好于朴素上界：只要每个部件的误差率为 $O(1/\log^2 N)$，整个 QRAM 的查询误差就保持为常数。这比扇出架构的 $O(1/N)$ 宽松得多，是 bucket brigade 的真实优势所在；但精度仍必须随 $N$（多项式地对数地）提升，与容错量子计算中"物理误差率只需低于一个常数阈值"形成对照。该工作同时指出：对路由器做标准量子纠错会引入多项式开销，抹平 $O(\log N)$ 深度的优势。
3. **后续争论**：Doriguello 与 Montanaro（2024）在更一般的噪声模型下（包括部件在未被激活时累积的误差、相干误差等）重新分析了 QRAM 的误差下界，其结论对大规模 bucket brigade 的实际可行性提出了更严格的约束；2024 年前后的争论正是围绕"局部非相干假设之外，稳健性是否仍然成立"展开。

**结论**：bucket brigade 的精度要求介于"常数阈值"（容错电路）与"$O(1/N)$"（扇出架构）之间；它是否实用，取决于真实器件的噪声以哪类模型为主。

## 架构二：基于预制备资源态的方案

（早期文献与科普材料有时把这一方案非正式地称为"magic state QRAM"；需要注意它与容错量子计算中的魔幻态（magic state）并无关系——这里的核心资源只是一个预先制备好的叠加态，我们据此改用"预制备资源态"这一更准确的名称。）

### 核心思想

另一类方案不依赖桶链式路由，而是把经典数据库 $D_0, D_1, \ldots, D_{N-1}$ 一次性编码为一个量子态：

$$|\mathcal{D}\rangle = \frac{1}{\sqrt{N}} \sum_{a=0}^{N-1} |a\rangle|D_a\rangle .$$

这个态就是资源态（resource state）。值得注意的是，$|\mathcal{D}\rangle$ 恰好等于"对均匀叠加地址做一次 QRAM 查询"的输出：把上一节的酉嵌入作用在 $\frac{1}{\sqrt N}\sum_a|a\rangle|0\rangle$ 上即得。一旦制备好 $|\mathcal{D}\rangle$，对数据库的许多操作就化为对该资源态的受控操作与测量。

### 资源态的制备

**方法一：门电路制备**。我们直接用量子门电路制备 $|\mathcal{D}\rangle$。对 $N = 2^n$ 个每项 $k$ 比特的数据，制备需要 $O(N\cdot k)$ 个门——本质上是线性操作，没有相对经典制备的加速。

**方法二：经典预处理 + 量子加载**。我们把经典数据预处理为一个可高效编译的制备序列（要求数据具有稀疏、低秩、低纠缠等结构，参见态制备教程），然后用 $O(\mathrm{poly}(n))$ 个门实现。

**方法三：基于交换测试的渐进制备**。我们逐步把经典数据"注入"量子态：每一步用一次受控旋转与交换操作并入一个数据项，每步 $O(1)$ 个门，共需 $O(N\cdot k)$ 步。该途径与方法一同阶，但可以与误差缓解技术结合。

### 量子门 QRAM（Gate-based QRAM）

2023–2024 年的发展倾向于用标准量子门直接实现查询电路，而非依赖光学开关：

1. 用 $O(N\cdot k)$ 个量子比特存储数据；
2. 用 $O(N\cdot k)$ 个门把数据加载为 $|\mathcal{D}\rangle$；
3. 查询通过交换测试类子例程或直接测量完成。

**复杂度**：$O(N\cdot k)$ 个门与量子比特——与经典数据库的 $O(N\cdot k)$ 存储相同。

### 预制备资源态的优势与代价

**优势**：

- 门精度要求仅为 $O(1/\mathrm{poly}(n))$，没有指数精度问题；
- 可以用通用量子门实现；
- 与量子纠错兼容。

**代价**：

- 制备 $|\mathcal{D}\rangle$ 需要 $O(N\cdot k)$ 个门，失去了"每次查询 $O(\log N)$"的加速；
- 对无结构数据，QRAM 的量子优势消失。

## 关键子例程：交换测试（SWAP Test）

交换测试在 QRAM 相关算法中反复出现：它从量子态的副本中估计态的重叠，是把"量子数据"变成"经典统计"的标准接口。我们给出完整推导。

**电路**：给定两个处于 $|\phi\rangle$ 与 $|\psi\rangle$ 的寄存器和一个辅助比特，我们依次执行：(i) 对辅助比特施加 $H$；(ii) 以辅助比特为控制做受控交换（controlled-SWAP，即 Fredkin 门）;(iii) 再对辅助比特施加 $H$；(iv) 在计算基测量辅助比特。

**推导**。辅助比特经第一个 $H$ 后，系统处于

$$\frac{1}{\sqrt 2}\bigl(|0\rangle + |1\rangle\bigr)|\phi\rangle|\psi\rangle .$$

受控交换把 $|1\rangle$ 分支的两个寄存器互换：

$$\frac{1}{\sqrt 2}\bigl(|0\rangle|\phi\rangle|\psi\rangle + |1\rangle|\psi\rangle|\phi\rangle\bigr).$$

再对辅助比特施加 $H$（利用 $H|0\rangle = (|0\rangle+|1\rangle)/\sqrt 2$、$H|1\rangle = (|0\rangle-|1\rangle)/\sqrt 2$）：

$$\frac{1}{2}\Bigl[\,|0\rangle\bigl(|\phi\rangle|\psi\rangle + |\psi\rangle|\phi\rangle\bigr) + |1\rangle\bigl(|\phi\rangle|\psi\rangle - |\psi\rangle|\phi\rangle\bigr)\Bigr].$$

于是测得 $0$ 的概率为对称分支的范数平方：

$$\Pr(0) = \frac{1}{4}\Bigl(2 + \langle\phi|\psi\rangle\langle\psi|\phi\rangle + \langle\psi|\phi\rangle\langle\phi|\psi\rangle\Bigr) = \frac{1 + \bigl|\langle\phi|\psi\rangle\bigr|^2}{2} .$$

两个快速检验：$|\phi\rangle = |\psi\rangle$ 时 $\Pr(0) = 1$（对称分支唯一）；$\langle\phi|\psi\rangle = 0$ 时 $\Pr(0) = \frac 12$（对称与反对称分支等权），与推导一致。

**采样复杂度**：测量结果是伯努利变量，方差至多 $1/4$，由 Chebyshev/霍夫丁界，把 $|\langle\phi|\psi\rangle|^2$ 估计到精度 $\varepsilon$ 需要 $O(1/\varepsilon^2)$ 次重复。若需要带相位的重叠 $\langle\phi|\psi\rangle$ 而非其模方，我们改用 Hadamard 测试估计 $\mathrm{Re}\,\langle\phi|U|\phi\rangle$ 型量。光子系统中的破坏性交换测试（destructive SWAP test）直接在贝尔基测量两个寄存器，可省去辅助比特并给出相同统计。

**与 QRAM 的配合**：我们把 QRAM 加载出的数据叠加态 $|\psi_D\rangle = \frac{1}{\sqrt N}\sum_j|j\rangle|D_j\rangle$ 与参考态 $|\phi\rangle = \frac{1}{\sqrt N}\sum_j \beta_j|j\rangle|\mathrm{ref}\rangle$ 一起送入交换测试，其重叠 $\langle\phi|\psi_D\rangle = \frac{1}{N}\sum_j \beta_j^{\ast}\langle \mathrm{ref}|D_j\rangle$ 正是量子推荐系统与量子主成分分析里需要的内积型统计量；交换测试把它化为 $O(1/\varepsilon^2)$ 次重复的频率估计，每次重复只需 $O(\log N)$ 深度的查询。

## QRAM 与量子态制备的区别

这两个概念经常被混为一谈，我们把区别逐条写清楚：

1. **任务性质不同**。QRAM 实现的是可逆的酉嵌入 $|a\rangle|0\rangle \mapsto |a\rangle|D_a\rangle$，地址寄存器被保留、与数据寄存器相干纠缠；量子态制备输出的是一个固定态 $|\psi\rangle = \sum_j \sqrt{p_j}|j\rangle$，通常由测量后选择得到，是不可逆的操作。
2. **可重复性不同**。QRAM 查询结束后设备被反计算还原，可以在算法的任何中间步骤被再次调用；态制备一般只在算法开始时执行一次，其输出若被测量即坍缩，无法"再查一次"。
3. **信息形态不同**。QRAM 把数据写入寄存器（值编码）：数据以比特串形式相干存在，可继续被门操作处理、也可被反计算擦除；态制备把数据编码进振幅（振幅编码）：经典信息隐藏在概率幅中，按 Holevo 界读出 $N$ 个振幅需要 $\Omega(N)$ 份副本。
4. **代价结构不同**。QRAM 的账本是"$O(N)$ 硬件 + 每次查询 $O(\log N)$ 深度"；纯电路态制备的账本是"$O(N)$ 个门的一次性成本"。前者把开销从时间转移到空间。
5. **组合关系**。振幅编码的态制备可以用 QRAM 实现：均匀叠加上做一次查询，再做受控旋转与幅度放大（其成功概率与放大轮数已在态制备教程 4.1 节推导）；反过来，资源态 $|\mathcal{D}\rangle$ 本身就是一次 QRAM 查询的输出。两者是"基础设施"与"应用层"的关系，而非同一事物的两个名字。

## QRAM 的根本限制：下界结果

### Troyansky 与 Tishby 的下界（1996）

**命题**：从 $N$ 个经典数据项中读取 $k$ 项，无论使用何种量子算法，都至少需要 $\Omega(k)$ 次（测量-）查询。

**证明思路**：输出 $k$ 个数据项需要 $\Omega(k)$ 比特的经典输出；而每次查询后立即测量数据寄存器只能产生一个固定的比特串，信息量不超过寄存器长度。更严格地，把"读取 $k$ 项"建模为区分 $D^k$ 上所有取值组合的查询问题：单次查询的可访问信息不足以同时确定两个以上互不相交地址的内容（这是量子查询复杂度中关于多目标读取的标准论证），因此需要 $\lceil k \rceil$ 次查询。

**含义**：如果目标是读取所有 $N$ 个数据（如 HHL 需要 $\vec b$ 的全部分量），任何量子算法都需要 $\Omega(N)$ 次操作——与经典相同。QRAM 的价值不在于"把数据全部读出来"。

### QRAM 的量子优势在哪里

QRAM 的加速不在于批量读出，而在于以下场景：

1. **叠加查询**：制备 $\sum_a \alpha_a|a\rangle|D_a\rangle$ 型相干叠加，供需要同时访问多个数据的算法（如量子推荐系统）使用；
2. **数据结构操作**：对数据库的结构化操作（量子索引、量子搜索、重要性采样）；
3. **内积与范数估计**：$\langle a|D|b\rangle$、$\|D v\|$ 型量的量子估计——借助交换测试等子例程，仅需 $O(\mathrm{poly}(n)\cdot 1/\varepsilon)$ 次查询即可达到精度 $\varepsilon$。

## QRAM 在量子算法中的角色

### HHL 和量子线性代数

原始 HHL 论文假设 $\vec b$ 已经以量子态 $|b\rangle$ 形式存在。若 $\vec b$ 来自经典数据，需要 QRAM 将其加载：

- 有 QRAM：$O(\log N)$ 深度完成加载与后续访问；
- 无 QRAM：$O(N)$ 门加载，抵消量子加速。

### 量子推荐系统

Kerenidis 与 Prakash（2017）的量子推荐算法假设 QRAM 存储用户-商品评分矩阵，实现 $O(\mathrm{poly}(n))$ 的推荐。Tang（2019）的"去量子化"（dequantization）经典算法表明，该推荐问题没有真正的亚指数量子加速——部分原因正是 QRAM 假设过强：经典算法在同样的采样访问模型下也能匹配量子表现。

### 量子主成分分析

Lloyd、Mohseni 与 Rebentrost（2014）的量子 PCA 算法假设密度矩阵以 QRAM 形式可访问。对大密度矩阵（$N \times N$），这需要 $O(N^2)$ 存储——与经典相同。

## 当前实验进展

| 年份 | 平台 | 规模 | 方法 |
|------|------|------|------|
| 2019 | 光量子 | 8 项数据 | Bucket Brigade 原型 |
| 2021 | 超导 | 4 地址 | 受控路由 |
| 2023 | 离子阱 | $O(10)$ 项 | 门制备资源态 |
| 2024 | 多平台 | $O(100)$ 项 | 经典辅助量子加载 |

## QRAM 的争议与展望

### 支持方论点

- QRAM 对多个量子算法的多项式加速是必要的输入假设；
- 小规模 QRAM 已在实验上实现；
- 量子纠错与硬件技术的进步将改善 QRAM 的可行性。

### 质疑方论点

- Bucket brigade 的精度要求随 $N$ 按 $1/\mathrm{polylog}\,N$ 收紧（非相干噪声下为 $O(1/\log^2 N)$），最坏噪声模型下更严；
- 门制备资源态需要 $O(N)$ 个门，失去每次查询的加速；
- Tang 的去量子化结果表明，许多"需要 QRAM"的算法可以被经典采样算法匹配；
- QRAM 的物理实现面临根本性的退相干与可扩展性挑战。

### 当前共识

**谨慎乐观**：QRAM 可能在小规模、特定结构的数据上实用，但作为通用的量子数据库基础设施，其物理可行性仍存重大疑问。算法设计者应尽量减少对 QRAM 的依赖，或在结论中明确标注 QRAM 假设。

## 总结

QRAM 是量子计算中最具变革性潜力但也最具争议的基础设施。Bucket brigade 架构以 $O(\log N)$ 深度实现相干查询（论证来自"地址逐位进入、每层一次路由"），但在叠加查询中会激活 $O(N)$ 个路由器，其噪声稳健性介于常数阈值与 $O(1/N)$ 之间；基于预制备资源态的方案规避了精度问题，但代价是 $O(N)$ 的一次性制备成本。QRAM 提供的是可重复的酉嵌入，与一次性的振幅态制备有本质区别。理解 QRAM 的原理、局限和争议，对于正确评估量子算法的实际加速潜力至关重要。

---

**参考文献：**

1. Giovannetti, V., Lloyd, S., & Maccone, L. (2008). *Quantum random access memory.* Physical Review Letters, 100(16), 160501.
2. Arunachalam, S., Gheorghiu, V., Jochym-O'Connor, T., Mosca, M., & Srinivasan, P. V. (2015). *On the robustness of bucket brigade quantum RAM.* New Journal of Physics, 17(12), 123010.
3. Tang, E. (2019). *A quantum-inspired classical algorithm for recommendation systems.* STOC 2019.
4. Doriguello, J. F., & Montanaro, D. (2024). *Errors in quantum random access memory.*
---

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