Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles

技术摘要：无辅助比特的随机化 Toffoli 门与布尔预言机的 $T$ 计数

问题陈述
在利用 Clifford+$T$ 门集的容错量子计算中，实现布尔预言机（特别是 Toffoli 门和一般的多控制非门）存在资源成本之间的权衡：即 $T$ 门数量（消耗蒸馏魔术态的资源）与辅助比特数量之间的权衡。

• 精确实现： 对于 $n \ge 4$ 个量子比特，精确的 Toffoli 门 ($\text{Toff}_n$) 无法在其自身的量子比特上不使用额外量子比特来实现（受行列式约束限制）。精确电路通常需要一个干净的辅助比特（成本约为 $8n$ 个 $T$ 门）或借用一个量子比特（成本约为 $16n$ 个 $T$ 门）。
• 随机化方法： Gosset, Kothari, 和 Zhang (GKZ) 证明了通过电路的随机混合可以近似实现 $\text{Toff}_n$，且其 $T$ 计数与 $n$ 无关（具体为 $O(\log(1/\varepsilon))$）。然而，他们直接实现的采样器将采样的奇偶性计算到新的辅助比特中，这大约需要每个精度位一个辅助比特（$\ell \approx \log(1/\varepsilon)$）。

本文解决的核心问题是：是否可以在实现 $O(\log(1/\varepsilon))$ 的 $T$ 计数优势的同时，完全消除对额外辅助比特的需求，即使对于较大的 $n$ 也是如此。

方法论
本文采用了一种“混合模型”，其中电路是一个由酉 Clifford+$T$ 分支组成的概率分布。误差定义为目标酉算子与平均通道之间的钻石距离（diamond distance）。该方法论包括：

1. 原地奇偶性计算： 与 GKZ 的直接采样器将采样奇偶性计算到新的辅助比特中不同，作者提出将这些奇偶性“原地”计算在门自身的控制量子比特上，使用 CNOT 电路 ($\Gamma$)。
2. 借用空闲控制位： 用于检查这些奇偶性的多控制非门（MCNOT）被构造为通过借用门自身的空闲控制量子比特作为工作量子比特，而不是需要干净的辅助比特。
3. 仿射分解： 该方法被推广到任意布尔函数，通过将函数分解为仿射子空间指示函数的异或（XOR）和来实现。每一项要么通过精确实现（如果子空间余维数较小），要么通过随机分支实现。
4. 下界分析： 本文利用随机奇偶决策树（RPDT）和计数论证来建立 $T$ 计数的下界。文中区分了结构化集合（仿射子空间）与非结构化集合（随机集合），以表明仅仅依靠“与仿射性的距离”并不能决定成本。

核心贡献与结果

1. 无辅助比特的随机化 Toffoli 门（定理 1）：

   • 作者构造了一种混合方案，用于实现 $\text{Toff}_n$，该方案不需要辅助比特，也不需要中途测量。
   • 成本： 每个分支使用 $8\ell - 8$ 个 $T$ 门，其中 $\ell = \lceil \log(4/\varepsilon) \rceil$。
   • 条件： 当 $n \ge \lceil 3\ell/2 \rceil$ 时，可实现此最优成本。在此机制下，$n-1-\ell$ 个空闲控制量子比特足以作为 MCNOT 构造（基于 Maslov 的相对相位 Toffoli 门）的借用工作量子比特。
   • 中间机制： 对于 $\ell + 2 \le n < \lceil 3\ell/2 \rceil$ 的情况，该构造仍不使用辅助比特，但需要高达 $16\ell - 32$ 个 $T$ 门，使用的是借用较少量子比特的构造（基于 Zindorf 和 Bose 的构造）。
   • 对比： 与保留一个干净辅助比特的最佳无测量变体相比，该方法每个电路仅多出一个 $T$ 门，但它完全消除了对辅助比特的需求。

2. 向结构化预言机的扩展（定理 2）：

   • 该技术可推广到任何可以分解为 $J$ 个仿射子空间指示函数之异或的布尔函数 $f$（例如：相等性测试、线性方程检查、决策树）。
   • 如果量子比特数 $n$ 相对于子空间的余维数足够大，则该预言机可以用无辅助比特且每个分支 $T$ 计数最多为 $8J\ell_J$ 来实现，且该计数与 $n$ 无关。

3. 下界与最优性（定理 3 & 4）：

   • 本文证明，任何以钻石距离 $\varepsilon$ 近似 $\text{Toff}_n$ 的混合方案，在某些分支中至少需要 $\min\{n-1, \log((1-\varepsilon)/\varepsilon)\} - 2$ 个 $T$ 门。
   • 所提出的构造在常数因子内处于该下界的 8 倍以内（忽略加性常数）。
   • 至关重要的是，对于每个分支都实现精确布尔预言机的混合方案，缩小上界（$8\ell$）与下界（$\approx \ell$）之间的差距，等同于寻找每个控制位使用少于 8 个 $T$ 门的精确多控制非门。

4. 结构与随机性（定理 5）：

   • 本文证明了 $T$ 计数并不完全由函数与最近仿射函数的距离决定。
   • 仿射子空间： 余维数为 $k$ 的仿射子空间的指示函数成本为 $O(1)$ $T$ 门（具体而言，对于恒定误差 $\le 24$）。
   • 随机集合： 具有相同密度（$2^{-k}$）的随机集合需要指数级的 $T$ 门：使用干净辅助比特时约为 $2^{(n-k)/2}$，不使用辅助比特时约为 $2^{n-k}$。
   • 这强调了非结构化预言机即使在有额外量子比特的情况下，也无法通过随机化变得廉价，而结构化预言机（仿射子空间）则能从所提出的无辅助比特随机化方法中显著获益。

意义与主张
作者指出，对于受限于逻辑量子比特数量的计算（这是早期容错设备的常见约束），所提出的无辅助比特随机化电路提供了一种可行的替代方案。

• 资源效率： 它消除了以往随机采样器中“每个精度位需要一个额外量子比特”的开销，使得电路可以完全在自身的量子比特上运行。
• 可扩展性： 一旦 $n$ 相对于期望精度 $\varepsilon$ 足够大，其 $T$ 计数将与控制数 $n$ 无关。
• 理论洞察： 它建立了随机化预言机分支的成本与优化精确多控制非门这一开放问题之间的紧密联系。同时，它阐明了虽然随机化可以消除结构化函数的 $n$ 的线性依赖，但无法克服非结构化函数的指数级成本。

作者指出，目前尚不知道随机化 Toffoli 门的最优常数因子（目前为 8，而下界约为 1），并且缩小这一差距取决于未来对精确多控制非门合成技术的改进。此外，作者也承认尚未对特定架构上的时空体积进行估算。