⚛️ quantum physics

Sparse Quantum State Preparation with Sublinear T-Count

本文提出了一种容错量子算法，用于制备具有 $s$ -稀疏性的 $n$ -比特量子态，其 $T$ -计数为亚线性的 $\widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(1/\epsilon)}+\log(1/\epsilon))$ ，同时建立了一个匹配的下界 $\Omega(\min\{s,\sqrt{ns}\})$ ，证明了对于较小的支撑集大小而言，对 $s$ 的线性依赖是不可避免的。

原作者： Jingquan Luo, Lvzhou Li

发布于 2026-08-04

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Jingquan Luo, Lvzhou Li

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

想象一下，你正试图用乐高积木搭建一座宏大而精巧的城堡。在量子计算的世界里，这座城堡就是一个“量子态”——即量子计算机需要用来解决问题的特定且复杂的各种信息排列。但问题在于，我们用来建造这些城堡的工具非常挑剔。有些工具被称为“Clifford 门”，它们便宜、快速且易于使用，不会损坏任何东西。而另一些工具，被称为“T 门”，就像是稀有的、闪闪发光的、极其昂贵的宝石。它们是建造城堡中真正神奇部分的唯一途径，但如果使用过多的 T 门，整个项目的进度会变得太慢，成本也会高到在实际应用中无法实现。

现在，想象一下，你并不需要用到盒子里所有的积木。也许你只需要建造一座只使用其中一小部分特定积木的城堡，让剩下的盒子保持空置。用论文中的术语来说，这被称为“稀疏”态。长期以来，科学家们一直认为，即使你只需要很少的积木，T 门的成本仍会随着你使用的积木数量呈线性增长。如果你把积木数量增加一倍，成本也会随之翻倍。但有没有可能找到一种捷径？如果你的城堡变得足够大，你是否可以不再为每一块积木付费，而是只支付其中一小部分的费用？这就是这篇论文要解决的核心问题：我们能否比之前认为的更节省那些昂贵的宝石（T 门）来构建这些稀疏的量子城堡？

作者景泉（Jingquan Luo）和李路舟（Lvzhou Li）说：“是的，但有一个转折。”他们发现，对于小型城堡，旧的规则仍然适用：你必须为每一块积木付费。但一旦城堡变得足够大（具体来说，当积木数量大于一个涉及计算机规模的数学阈值时），成本就不再呈线性增长。相反，它的增长速度会慢得多，遵循一个结合了计算机规模和积木数量平方根的公式（大约与 $n^{3/4}\sqrt{s}$ 成比例）。这意味着，对于非常大的稀疏量子态，我们可以节省大量的 T 门，尽管这种节省遵循一个比简单平方根更复杂一点的特定曲线。

为了理解他们是如何做到的，请把这个问题想象成一场带有转折的“捉迷藏”游戏。量子态是一份关于信息所在秘密位置（“支撑集”）的列表。以前的方法准备这种状态就像是一个个检查所有可能的隐藏地点，这既慢又贵。作者提出了一种基于布尔函数（即一种将输入转化为输出的巧妙数学规则）的“合成定理”的新策略。

他们的方法分为两个主要阶段。首先，他们为这些秘密位置创建一个“标签”。他们不再处理所有可能位置的庞大且混乱的列表，而是将这些秘密位置压缩成一个更小、更易于管理的标签列表。然后，他们使用一个特殊的、高效的电路，根据这些标签来“加载”实际的位置。真正的魔力发生在最后一步：擦除标签，以免计算机产生混淆。这是最困难的部分，也是他们发现捷径的地方。

他们意识到，如果秘密位置的列表非常庞大，他们并不需要逐一检查每一个。相反，他们可以观察位置的“前缀”（即起始部分）。如果许多位置拥有相同的开头，他们就可以将它们归为一组并同时处理；如果只有少数位置共享同一个开头，他们可以将这些开头压缩成一段更短的代码。通过不断地在“分组”与“压缩”之间切换，他们可以比以前更快地剥离问题的层级。这使得他们构建出的状态所使用的 T 门数量是“亚线性”的——这意味着成本的增长远慢于状态本身的大小。

然而，论文非常谨慎，并未声称这是一种解决一切问题的“魔杖”。作者证明了对于小型状态，原有的线性成本是不可避免的：当秘密列表很短时，你无法绕过这个系统。他们还表明，虽然他们的新方法是一个巨大的进步，但目前最好的成本与绝对的理论极限之间仍存在微小的差距。这就像是你发现了一条比旧路短了 90% 的路径，但还不是绝对意义上的最短路径。他们还不确定这最后的距离是因为他们的地图不够完美，还是因为地形本身就不允许有更短的路径。

简而言之，这篇论文证明了对于大型稀疏量子态，我们可以比之前认为的更高效地构建它们，从而节省宝贵的资源。但它也划定了一条明确的界限：对于小型状态，昂贵的成本依然存在。作者为更高效的量子计算未来打开了一扇门，但也向我们展示了墙壁依然矗立在哪里，邀请未来的探索者去看看是否能找到穿透的方法。

技术摘要：具有亚线性 T-计数（T-count）的稀疏量子态制备

问题陈述
本文研究了在 Clifford+T 模型下，制备稀疏量子态的容错成本。一个 $n$ 量子比特的状态被定义为 $s$ -稀疏，即其在计算基下的支撑集（support）包含至多 $s$ 个非零振幅。虽然对于一般的 $n$ 量子比特态制备，已知其最优 T-计数为 $\Theta(\sqrt{2^n} \log(1/\epsilon) + \log(1/\epsilon))$ ，但以往针对稀疏态的研究受限于对稀疏度 $s$ 的线性依赖。具体而言，近期的研究确立了对于 $s$ -稀疏态具有 $O(s)$ 个 T 门的上界。本研究探讨的核心问题是：当支持集大小 $s$ 相对于量子比特数 $n$ 较大时，制备 $s$ -稀疏态的 T-计数是否可以实现对 $s$ 的亚线性依赖。

方法论
作者通过将态制备分解为三个主要阶段来处理该问题：

标签态制备（Label State Preparation）： 在一个 $\lceil \log s \rceil$ 量子比特的索引寄存器上制备一个稠密叠加态。
相干加载（Coherent Loading）： 使用布尔函数将索引 $i$ 映射到 $n$ 量子比特数据寄存器中对应的基字符串 $x^{(i)}$ 。
标签擦除（Label Erasure）： 应用标签映射的逆过程来取消计算（uncompute）索引寄存器，从而使数据寄存器处于目标态。

其核心技术创新在于标签擦除步骤的合成，这涉及实现一个稀疏布尔函数 $L: \{0, 1\}^n \to \{0, 1\}^{\lceil \log s \rceil}$ ，该函数将受支持的输入 $x^{(i)}$ 映射回其索引 $i$ ，并将所有其他输入映射为零。作者开发了一个针对稀疏布尔函数的支持感知合成定理（support-aware synthesis theorem），该定理根据支持大小 $s$ 调整其策略：

小支持集区间（ $s \leq n^{3/2} \log n$ ）： 该方法通过一个单射（injection）将 $s$ 个受支持的输入压缩到一个对数大小的标签寄存器中。问题被简化为合成一个在 $O(\log s)$ 比特上的布尔函数，这可以通过 $O(s+n)$ 个 Toffoli 门完成。
大支持集区间（ $s > n^{3/2} \log n$ ）： 作者采用了一种递归算法，固定前缀长度 $r$ $r$ 。在每一步中，算法分析当前支持集中活跃的 $r$ $r$ -位前缀：
- 如果活跃的前缀较少，它执行前缀压缩（prefix compression），通过对活跃前缀进行单射重标记来缩短输入长度，而不改变支持集大小。
- 如果活跃的前缀较多，它执行支持剥离（support peeling），从每个活跃前缀中移除一个受支持的输入。这种“剥离”后的切片实现成本较低，而剩余的递归实例则会损失大量的支持点。
  通过平衡这两类操作，算法实现了以亚线性于 $s$ 的比例缩放的 Toffoli 计数。

对于下界，论文利用了两种不同的技术：

小 $s$ 情况（ $s = O(n)$ ）： 稳定子零度（stabilizer nullity）论证的扩展。作者证明，对于接近 W 态 $|W_s\rangle \otimes |0^{n-s}\rangle$ 的状态，稳定子子群的秩是有界的，这意味着存在 $\Omega(s)$ 的线性下界。
大 $s$ 情况（ $s = \Omega(n)$ ）： 结合了 [GKW26] 中的计数引理进行的填充论证（packing argument）。通过构建一个大规模的相互良分离（pairwise well-separated）的 $s$ -稀疏态族，并对使用 $t$ 个 T 门可制备的态的数量进行计数，他们推导出了 $\Omega(\sqrt{ns})$ 的下界。

主要贡献与结果

亚线性上界： 本文确定，任何 $n$ 量子比特的 $s$ -稀疏态在误差 $\epsilon$ 下，可以使用以下数量的 T 门进行制备：
$\tilde{O}\left(\min\left\{s, n^{3/4}\sqrt{s}\right\} + \sqrt{s}\log(1/\epsilon) + \log(1/\epsilon)\right)$
这是第一个展示了在足够大的支持集（具体为 $s \gtrsim n^{3/2}$ ）情况下，对 $s$ 具有亚线性依赖关系的结果。辅助量子比特（ancilla）的需求量为 $\tilde{O}(\sqrt{ns})$ 。
紧致下界： 作者证明，对于 $0 < \epsilon \leq 1/6$ 且 $2 \leq s \leq 2^{n/2}$ ，T-计数下界为：
$\Omega(\min\{s, \sqrt{ns}\})$
该结果表明，在小支持集区间（ $s = O(n)$ ）内，线性依赖于 $s$ 是不可避免的，并且在大的支持集区间内，对 $n$ 的依赖关系无法被完全消除。
支持感知合成定理： 一个用于合成具有支持大小 $s$ 的稀疏布尔函数 $F: \{0, 1\}^n \to \{0, 1\}^b$ 的通用定理。其 Toffoli 复杂度在小 $s$ 时为 $O(s+n)$ ，在大 $s$ 时为 $\tilde{O}(n^{3/4}\sqrt{s} + n^{1/4}\sqrt{bs})$ 。作者指出，该结果除了态制备之外，可能具有独立的学术价值。

意义与主张
本文声称解决了关于稀疏态制备是否可以实现对 $s$ 亚线性的问题。结果表明，对于较大的支持集（具体为 $s \gtrsim n^{3/2}$ ），此前已知的线性 $O(s)$ 并非固有属性；其成本可以降低至 $\tilde{O}(n^{3/4}\sqrt{s})$ 。然而，作者对自身上界的优越性持谨慎态度。他们强调，在上支持集区间内，上界 $\tilde{O}(n^{3/4}\sqrt{s})$ 与下界 $\Omega(\sqrt{ns})$ 之间仍存在差距。

论文明确指出，目前尚不清楚 $s \approx n^{3/2}$ 处的交叉点以及 $n^{3/4}$ 因子是其特定算法的产物，还是反映了容错稀疏量子态制备的固有限制。此外，虽然在小支持集区间内构造利用了布尔函数的局部性（partial nature），但作者指出，将这种松弛引入大支持集构造中目前并不能改善渐近界，这使得进一步利用偏函数结构（partial-function structure）成为一个开放性问题。

技术摘要：具有亚线性 T-计数（T-count）的稀疏量子态制备

类似论文