⚛️ quantum physics

Sparse quantum state preparation with improved Toffoli cost

本文提出了一种用于制备 $n$ 个量子比特上的 $s$ -稀疏量子态的优化算法，该算法通过设计更高效的等距电路并联合优化稠密态制备步骤，显著降低了 Toffoli 门成本，实现了约 $2s$ 的最坏情况成本，并较现有最先进方法提升了 $\log(s)/2$ 。

原作者： Felix Rupprecht, Sabine Wölk

发布于 2026-01-15

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Felix Rupprecht, Sabine Wölk

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位试图整理一座拥有数十亿本书（量子态）的巨型图书馆的图书管理员。然而，你只关心其中一小部分特定的藏书——也许在数十亿本书中，你只想要几百本。在量子计算的世界中，寻找一种方法来设置计算机，使其仅持有这些特定的“书”（量子态），而不浪费时间或能量，是一个巨大的挑战。这个过程被称为稀疏量子态准备（Sparse Quantum State Preparation）。

Rupprecht 和 Wölk 的论文讲述了如何建造一个更快速、更高效的“机器人图书管理员”来完成这项工作。以下是他们实现这一目标的方式，通过简单的语言进行解释：

两步舞步

作者们使用了一种两步走的策略，其他研究人员也曾使用过这种策略，但他们让第二步变得更快了。

第一步：“稠密”准备（草稿阶段）： 首先，机器人准备一份包含你想要的那几本书所有信息的精简清单。这就像是在一个小笔记本上写一份草稿。
第二步：“等距变换”（最终誊抄）： 这是最棘手的部分。机器人必须将那个小笔记本里的信息神奇地扩展成庞大图书馆的正确格式，将正确的书放在正确的位置，同时忽略那些空置的架子。

问题所在： 在以前的方法中，第二步就像是一个缓慢且笨拙的过程。对于你想要的每一本书，机器人都要走过去，检查一个架子，然后执行一次复杂且昂贵的操作（称为“Toffoli 门”）来将书移到位。如果你有 1,000 本书，大约就需要付出 1,000 倍的努力。

新的创新：“分批处理”技巧

作者意识到，他们不需要一本书一本书地移动。相反，他们发明了一种以**批次（batches）**进行移动的新方法。

旧方法： 想象你要搬运 100 个箱子。你拿起一个箱子，走到架子旁放下，再走回来，拿起下一个。这太慢了。
新方法： 作者设计了一个特殊的传送带系统（称为部分一元迭代/Partial Unary Iteration电路）。与其来回走动，机器人可以一次抓取一组箱子（一个批次），并将它们同时滑动到各自正确的位置。

他们称之为“分批处理”的方法。通过对工作进行分组，他们大幅减少了机器人需要进行的昂贵操作（Toffoli 门）的数量。

“无限制”捷径

为了让这个分批系统更快，他们引入了一个聪明的捷径，称为**“无限制”（Unrestricted）**方法。

类比： 想象你正在给一排房子刷漆。严格的规则（受限/Restricted）规定：“你只能粉刷编号为 1 到 10 的房子，并且必须在第 10 号房子处停止。”
捷径： 作者说：“如果我们粉刷了 1 到 10 号房子，但不小心在 11 号房子上也滴了一点漆，那也没关系！只要我们知道在处理下一个批次时会正确粉刷 11 号房子，我们现在就可以忽略这个小滴漏。”

这种“无限制”的方法允许机器人的工作方式稍微“乱一点”但速度更快，从而节省了大量的时间和能量。他们从数学上证明，与之前最好的方法相比，这节省了大约一半的精力。

处理“实数”

论文还发现了一个针对特定类型数据（实数，即没有虚部的数字，如 5.0 或 -2.5）的特殊技巧。

在标准过程中，机器人在最后需要进行一次“符号检查”，以确保正负号正确。这就像是最后的质量控制检查。
作者意识到，他们可以完全跳过这个最后的检查步骤。相反，他们将“符号检查”直接构建到了分批移动的过程（第二步）之中。这为处理这些实数状态节省了更多时间。

核心结论

他们实现了什么： 他们构建了一种新的算法，能够以比以往更少的昂贵操作（Toffoli 门）来准备特定的量子态。
结果： 对于大型系统，他们的方法使用的资源大约是之前最好方法的的一半。在一些随机测试中，其表现甚至接近理论上的最小值。
为什么这很重要： 在量子计算中，这些“昂贵的操作”是拖慢一切速度的瓶颈。通过让这一步变得更快，他们正在帮助使量子模拟和求解器在未来变得更加实用。

作者还向其他科学家开放了他们的代码和设计，确保这个“更快的机器人图书管理员”能够立即投入使用。

技术摘要：具有改进 Toffoli 成本的稀疏量子态制备

问题陈述
量子态制备是量子计算中的一个基本原语，对于从线性系统求解器到量子机器学习及量子模拟等应用至关重要。虽然通用态制备已被广泛研究，但稀疏量子态——即在 $n$ 个量子比特上仅包含 $s \ll 2^n$ 个非零计算基态的状态——需要专门且高效的算法。

在容错量子计算中，主要的资源指标通常是 Toffoli 门（以及 T 门）的数量，因为这些非 Clifford 操作由于魔术态蒸馏（magic-state distillation）的开销，其实现成本显著高于 Clifford 门。现有的稀疏态制备方法通常分为两类：

迭代构建法： 通过 $s$ 个步骤构建状态，每一步准备单个基态。这通常会导致超过 $s \lceil \log(s) \rceil$ 的 Toffoli 成本。
两步法（稠密制备 + 等距映射）： 首先在 $\lceil \log(s) \rceil$ 个量子比特的子寄存器上准备一个稠密态，然后通过等距映射（isometry）将其映射到目标稀疏态。虽然稠密制备的成本已得到优化（例如通过 Grover-Rudolph 算法），但等距映射步骤在历史上一直是瓶颈。先前的研究（如 Malvetti 等人的方法）要求等距映射的 worst-case Toffoli 成本为 $s(\lceil \log(s) \rceil - 1)$ ，这主导了整个算法的成本。

方法论
作者提出了一个改进的两步框架（如图 1 所示），旨在优化等距映射步骤并将其与稠密态制备集成：

分批等距构造（Batched Isometry Construction）：
核心创新在于一种用于构建等距电路的新型经典算法。该算法不再像 Malvetti 等人那样，通过应用单个多受控-X 门来为每个 $s$ 个状态中的非子空间量子比特清零，而是将状态分为大小为 $m$ 的批次（batches），其中 $m$ 是能够放入可用非子空间寄存器的最大 2 的幂次（ $m \le n - \lceil \log(s) \rceil$ ）。
- 对于每个批次，算法将状态转换为一种形式，使得非子空间寄存器在不同位置包含单个 $|1\rangle$ （例如 $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$ ）。
- 随后应用一个**部分一元迭代（Partial Unary Iteration, PUI）**电路，同时为整个批次的非子空间寄存器清零。
部分一元迭代（PUI）电路：
作者引入了两种 PUI 电路变体，它们迭代的是地址寄存器中的特定区间 $[l, r]$ ，而非整个空间：
- 限制性 PUI（Restricted PUI）： 保证幺正变换仅应用于目标区间 $[l, r]$ 内的状态。
- 非限制性 PUI（Unrestricted PUI）： 允许电路对地址值大于 $r$ 的状态应用非平凡的幺正变换。这种放宽显著降低了 Toffoli 计数。对于“不希望”对更高地址值产生的影响，通过经典方式进行追踪，并在后续步骤或批次中进行修正。
与稠密态制备的联合优化：
作者分析了等距成本与稠密态制备成本之间的权衡。他们提出将某些子任务从稠密制备“外包”给等距电路：
- 符号修复（Sign Fixes）： 与在稠密制备后通过解算角度寄存器来处理符号（这需要额外的 Toffoli 进行符号修正）不同，符号信息被直接编码进使用限制性 PUI 的等距映射中。
- 实数态（Real States）： 对于系数为纯实数的靶态，稠密制备中的相位编码步骤被完全移除，并由等距映射内部处理，这可能使稠密制备的 Toffoli 成本降低高达三倍。

核心贡献

改进的等距算法： 一种新的经典算法（算法 1），其构建的等距电路的 worst-case Toffoli 成本界限为：
$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$
其中 $\tilde{s} = 2^{\lceil \log(s) \rceil}$ 。相比于 Malvetti 等人的最先进方法，这实现了约 $\log(s)/2$ 的改进。
PUI 变体： 定义并分析了限制性和非限制性部分一元迭代电路的成本。非限制性版本通过允许向更高地址值“泄漏”操作，从而实现了更低的 Toffoli 计数，而这种泄漏在分批等距构造的上下文中是可控的。
资源权衡分析： 对结合了 Toffoli 和量子比特成本的稀疏态制备进行了全面分析（表 1），展示了如何通过优化等距映射来更好地利用辅助量子比特以降低稠密制备成本，特别是在处理实值态时。
实现： 这些电路在 Qualtran 框架中实现，其经典等距查找算法使用经过 SIMD 加速的 Rust 代码进行了优化。

结果

理论界限： 当 $n$ 足够大时，等距映射的 worst-case Toffoli 成本从 $O(s \log s)$ 降低到约 $O(s)$ 。具体而言，在随机态的数值基准测试中，随着 $n$ 的增加，每个 $s$ 对应的 Toffoli 数量趋近于 1，而此前最优方法约为 $s \log s$ 。
数值基准测试：
- 对于随机 $s$ -稀疏态，随着 $n$ 的增加，每个 $s$ 的 Toffoli 数量趋近于 1（图 2，右）。
- 对于纯实数态，联合优化显著降低了总 Toffoli 计数（图 9）。
比较： 该方法在保持相当或更低量子比特开销的同时，在 Toffoli 计数方面优于现有文献（如 [4, 14, 20, 21]）。

意义与主张
本文声称提出了文献中最有效的稀疏态制备电路（就 Toffoli 计数和量子比特数量而言）。其意义在于：

消除瓶颈： 通过将等距成本从主导因素降低到与稠密制备相当的水平，使整体算法更加高效。
可扩展性： 该方法随量子比特数 $n$ 的增加而表现出良好的扩展性，适用于 $s$ 较大但 $s \ll 2^n$ 的大规模容错量子算法。
实用性： 该方法与现有的容错资源估算框架（侧重于 Toffoli 计数）兼容，并以模块化软件框架（Qualtran）的形式实现。

作者对未来的影响保持谨慎，指出虽然 Toffoli 计数是当前的衡量标准，但随着魔术态生成（培育/蒸馏）技术的进步，未来的关注点可能会转向运行时间指标。他们也提出了一个开放性问题：在辅助量子比特资源有限的情况下，是否可以实现亚线性的 $s$ 相关的 Toffoli 成本。