想象一下，你正在为量子计算机构建一个超高速图书馆。在这个图书馆中，你需要根据唯一的地址查找特定的信息（例如电话号码或化学式）。在量子世界中，这被称为QROM（量子只读存储器）。它是几乎每个量子算法的“主力”，承担着加载数据的繁重工作。

然而，在过去七年里，构建这个图书馆在“托佛利门”（Toffoli gates）方面的成本极其高昂。将托佛利门想象为构建图书馆所需的复杂且耗能的砖块。你需要的砖块越多，运行计算机就越困难、越昂贵。

以下是 Xanadu 的 Danial Motlagh 和 Matthew Pocrnic 这两位作者如何将构建这座图书馆的成本降低一半的方法。

旧方法：“交换”之舞

此前，加载这些数据（使用“脏”量子比特，即像借用工具那样可能有些混乱的量子比特）最高效的方法涉及一个称为SelectSwap的过程。

想象你有一排 100 个上锁的盒子（数据）和一个干净、空的盒子（输出）。你有一把魔法钥匙（地址），它能告诉你打开哪个盒子。

旧方法：为了将正确的物品放入你的干净盒子中，你必须：
1. 将脏盒子与干净盒子交换。
2. 复制物品。
3. 将脏盒子交换回其原始位置。
4. 对每个物品重复这一“舞蹈”。

这种“交换之舞”非常高效，但它仍然需要为每个你想要加载的物品进行两次复杂的移动（砖块）。

第一个突破：“复制”捷径

作者们意识到，“交换之舞”是不必要的。与其来回交换盒子，不如直接复制物品。

新方法：他们用**“SelectCopy"**技术取代了"SelectSwap"。
- 他们不再将脏盒子与干净盒子交换，而是根据地址直接将脏盒子的内容复制到干净盒子中。
- 结果：这立即将复制过程所需的复杂砖块数量减少了一半。这就像意识到你不需要移动家具来打扫房间；你可以直接擦拭表面。

第二个突破：“数据包”策略

虽然第一个改进很棒，但作者们发现了一种能获得更好结果的方法，特别是当你没有大量那些“脏”的借用工具（脏量子比特）时。

想象你正在用 1,000 个包裹装载一辆大卡车。

旧方法：你逐个或成小组地装载它们，需要大量的来回奔波。
新策略：他们意识到可以将数据视为一系列小数据包。与其一次性加载整个 1,000 项的列表，不如将其分解为更小的块（例如，每次 10 项），然后按顺序加载。

通过这样做，他们改变了所需“复杂砖块”的数学计算。

以前，成本约为每项2 块砖。
使用这种新的“数据包”策略，他们将成本降低到每项约1 块砖（具体为 $1 + 1/b$ 块砖，其中 $b$ 是数据的大小）。

全局视角：成本减半

通过将"SelectCopy"捷径与“数据包”策略相结合，作者们取得了巨大的改进：

他们将成本减半：在实际场景中，加载数据所需的昂贵“砖块”（托佛利门）数量下降了约50%。
他们达到了最佳性能：他们设法让“脏”（混乱）量子比特的表现与“干净”（完美）量子比特一样好，而此前人们认为如果不使用两倍的资源，这是不可能实现的。

为什么这很重要

在量子计算领域，每一块“砖”（托佛利门）都至关重要。这些门是系统中最困难且最容易出错的部分。通过将加载数据所需的砖块数量减半，这种新方法使量子算法更加高效，也更容易在现实世界的量子计算机上运行。

作者们并没有发明一种新型计算机；他们只是找到了一种更聪明的数据加载组织方式，将笨拙、昂贵的过程转变为 streamlined、高效的过程。

技术摘要：将 QROM 成本减半

问题陈述

量子只读存储器（QROM）是容错量子算法中的基本子程序，它能够将经典数据相干地加载到叠加态中。它是哈密顿量模拟、态制备、酉合成以及微分和线性方程量子求解器等应用中的主要算法开销来源。

QROM 的核心任务是实现以下变换：
$\sum_{x=0}^{N-1} \psi_x |x\rangle|0\rangle \to \sum_{x=0}^{N-1} \psi_x |x\rangle|f(x)\rangle$
其中 $N$ 是数据条目数量， $b$ 是每个条目的比特长度， $f(x)$ 是一个预计算的经典函数。

历史上，QROM 的非 Clifford 成本（特别是 Toffoli 门计数）一直是一个瓶颈。虽然早期使用一元迭代（unary iteration）的方法将成本降低到了 $N$ ，但利用辅助量子比特引入的"SelectSwap"技术允许了进一步的优化。在此项工作之前的最先进方法由 Berry 等人建立，利用 $b(\lambda-1)$ 个“脏”（非纯）辅助量子比特，实现了如下 Toffoli 成本：
$2\frac{N}{\lambda} + 4b(\lambda-1)$
其中 $\lambda$ 是一个参数，用于决定辅助量子比特数量与 Toffoli 计数之间的权衡。由于使用了脏辅助比特，该构造在主导项 $N/\lambda$ 上引入了 2 倍的乘数因子，这一局限性已持续了七年多。

方法论

作者提出了一种新的 QROM 构造方法，在实际参数范围内有效地将实现成本减半。该方法分为两个主要阶段：

1. 从 SelectSwap 到 SelectCopy

第一项优化用"SelectCopy"架构取代了"SelectSwap"架构。

先前方法（SelectSwap）： 为了使用脏辅助比特加载数据，算法根据地址态 $|r\rangle$ 将第 $r$ 个脏寄存器与零号寄存器交换，将零号寄存器复制到干净寄存器，然后再交换回来。这一序列需要多个多路复用的交换门和 CNOT 门。
新方法（SelectCopy）： 作者观察到，交换、复制再交换回来的序列，在数学上等价于根据 $|r\rangle$ $∣ r ⟩$ 直接将第 $r$ $r$ 个寄存器多路复制到干净寄存器中。
- 这种直接复制操作将多路复用操作的 Toffoli 成本相比基于交换的方法降低了一半。
- 此外，通过修改加载策略，将 $f(q, 0)$ 直接加载到干净寄存器中，并将 $f(q, r) \oplus f(q, 0)$ 加载到脏寄存器中（对于 $r > 0$ ），作者将脏辅助比特的需求从 $b\lambda$ 减少到了 $b(\lambda-1)$ ，同时进一步优化了常数项。
- 结果成本： $2\frac{N}{\lambda} + 2b(\lambda-1) + 2\lambda - 6$ 。

2. 顺序比特包（参数化优化）

第二项优化针对的是 $N/\lambda$ 项占主导的量子比特受限区域。作者提出了一种方法，将单个 $b$ 比特的 QROM 视为 $\alpha$ 个顺序 QROM，每个加载 $b/\alpha$ 比特。

顺序卸载： 通过串联 $m$ 个 QROM 应用，第 $j$ 个应用的卸载步骤可以与第 $(j+1)$ 个应用的加载步骤相结合。这减少了完整的加载/卸载循环次数。
成本降低： 对于 $m$ 个顺序 QROM， $N/\lambda$ 项的系数变为 $(m+1)$ 而不是 $2m$ 。
应用于单个 QROM： 作者将一个 $b$ 比特的 QROM 视为 $\alpha$ 个大小为 $b/\alpha$ 的顺序 QROM。这使得"SelectCopy"的深度从 $\lambda$ 增加到 $\alpha\lambda$ 。
参数化族： 这产生了一个依赖于可调参数 $\alpha$ 的成本函数：
$\left(1 + \frac{1}{\alpha}\right)\frac{N}{\lambda} + \left(b + \frac{b}{\alpha}\right)(\alpha\lambda - 1) + (\alpha + 1)(\alpha\lambda - 3)$
通过改变 $\alpha$ 从 1 到 $b$ ，主导项 $N/\lambda$ 的系数可以从 2 插值到 $(1 + 1/b)$ 。

关键结果

最优区域： 在 $N \gg b^2\lambda^2$ 且可用脏量子比特数量受限的极限情况下，设置 $\alpha = b$ （即一次顺序加载一个比特）是最优的。
成本降低： 在这些条件下，总 Toffoli 成本降低至约：
$\left(1 + \frac{1}{b}\right)\frac{N}{\lambda}$
性能提升： 与之前的最先进方法（ $2N/\lambda$ ）相比，这代表了约 50% 的成本降低。
干净量子比特等价性： 对于实际的 $b$ 值，这种脏量子比特构造的性能实际上与干净量子比特 QROM（通常实现系数为 1）的性能相匹配。
推广性： 该论文提供了一个参数化方法族，允许用户根据具体的量子比特可用性和问题规模约束，在标准 SelectCopy 方法的成本与完全顺序方法的成本之间进行插值。

意义与主张

该论文声称提供了半年来对 QROM 子程序的首次重大改进。其意义在于以下几点：

开销降低： 由于 QROM 构成了大多数实际量子应用（如化学、线性系统）中算法开销的大部分，将其成本减半直接转化为整个领域的显著资源节约。
实用性： 这些改进是使用“脏”辅助量子比特实现的，在容错架构中，“脏”辅助比特比“干净”（纯）辅助比特更容易实现，且没有牺牲通常与干净量子比特相关的效率提升。
灵活性： 该解决方案的参数化性质允许算法设计者通过调整参数 $\alpha$ ，针对特定的硬件约束（量子比特预算与门深度）进行优化。

作者指出，虽然当前的构造假设参数是 2 的幂，但未来的工作可以结合整数除法技术，以在可用脏量子比特预算不符合 $2^k$ 约束时充分利用它们，从而在特定区域提供进一步的降低。所提出的构造已在 PennyLane 库中实现。

Halving the cost of QROM