技术摘要：具有最优 T-计数（T-Count）的量子态制备

问题陈述

本文探讨了量化实现任意量子态和操作所需的“魔力”（非 Clifford 性）这一基本问题，特别是在容错量子计算中。具体而言，研究了在 $\ell_2$ 范数下（针对量子态）或算子范数下（针对幺正算符），以误差 $\varepsilon$ 近似实现任意 $n$ 比特量子态或任意对角 $n$ 比特幺正算符所需的最小 $T$ 门数量（即 $T$-计数）。

此前由 Low、Kliuchnikov 和 Schaeffer (LKS) 完成的工作确立了一个使用辅助量子比特进行态制备的上限 $O(\sqrt{2^n n \log(n/\varepsilon)} + \log^2(n/\varepsilon))$。作者旨在探究该缩放比例是否是最优的，以及与量子比特数 $n$ 相关的开销以及与误差 $\log(n/\varepsilon)$ 相关的开销是否可以降低。

方法论

本文结合了构造性合成算法和信息论下界论证。

1. 对角幺正算符合成

核心技术创新在于一种合成对角幺正算符的新方法。作者将一个 $n$ 比特对角幺正算符 $D$ 视为受 $n-1$ 个比特控制的单比特幺正算符 $G_y$。

• 近似： 每个单比特幺正算符 $G_y$ 通过一系列 $O(\log(1/\varepsilon))$ 个 Hadamard 门和 $T$ 门进行近似（使用现有的最优单比特合成技术，如 Ross-Selinger）。
• 算符实现： 构建一个布尔算符 $B$，根据控制比特 $y$ 计算该门序列的描述（一个位串 $s_y$）。该算符使用 LKS 的布尔函数技术实现，其 $T$-计数为 $O(\sqrt{2^n \log(1/\varepsilon)})$。
• 受控应用： 实际的门由计算出的位串 $s_y$ 控制并作用于目标比特。这一步产生的代价与 $s_y$ 的长度成正比，即 $O(\log(1/\varepsilon))$。
• 反计算（Uncomputation）： 对算符进行反计算，以使辅助比特返回零态。

2. 量子态制备

态制备算法改进了 Grover-Rudolph 方法和 LKS 构造：

• 粗略近似： 不同于需要 $O(n)$ 个受控旋转的标准 Grover-Rudolph 方法，作者使用一种近期方法（Rosenthal, INN+22）的变体，将问题简化为仅需合成 $O(1)$ 个对角幺正算符。他们利用两个布尔对角幺正算符（$B_1, B_2$）和 Hadamard 层构造一个与目标态 $|\psi\rangle$ 具有常数重叠的态 $|\phi\rangle$。
• 迭代细化： 为了将误差从常数降低到 $\varepsilon$，作者采用了一种迭代方法。使用相同的粗略近似技术来近似差分态 $|\psi\rangle - |\phi\rangle$。这生成了一系列状态 $|\phi_k\rangle$。
• 幺正算符线性组合 (LCU)： 最终的态通过 LCU 方法作为这些粗略近似的加权和进行制备。
• 振幅放大： 使用精确振幅放大来滤除叠加态中的“垃圾”成分，从而确保最终态在 $\varepsilon$ 范围内接近目标态。这需要将“标记”态的振幅调节至特定值（$\sin(\pi/10)$），以便在常数轮次内实现精确放大。

3. 下界

下界是在一个强大的 自适应 Clifford+T 电路 模型中建立的，该模型允许中途测量和经典前馈。

• 归约为态制备： 对于幺正算符合成，通过考虑电路对极大纠缠态（Choi 态）的作用，将问题归约为态制备。
• 计数论证： 作者使用了球填充（sphere-packing）论证。他们证明了在误差 $\varepsilon$ 内可区分的状态（或幺正算符）的数量按 $(1/\varepsilon)^{\Theta(2^n)}$ 缩放。
• 规范形式： 他们利用带有 Pauli 后选择的 Clifford 电路的规范形式（推广了 Beverland 等人的工作）来限制给定 $T$-计数 $t$ 下可实现的不同电路的数量。通过将可用电路的数量与可区分的目标数量等同，他们推导出了下界 $t = \Omega(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon))$。

主要贡献与结果

主要定理

1. 最优态制备 (定理 1.1)：
   任何 $n$ 比特态都可以使用 $T$-计数为以下值的 Clifford+T 电路制备，误差为 $\varepsilon$：
   $$\Theta\left(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon)\right)$$
   即使在带有测量的自适应模型中，该界限也是最优的。

2. 最优对角幺正算符合成 (定理 1.2)：
   任何 $n$ 比特的对角幺正算符可以用相同的最优 $T$-计数实现，误差为 $\varepsilon$：
   $$\Theta\left(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon)\right)$$

3. 批量合成 (定理 1.3)：
   $m = O(\log \log(1/\varepsilon))$ 个单比特幺正算符的张量积可以用 $T$-计数 $O(\log(1/\varepsilon))$ 实现。这意味着合成少量幺正算符不会增加超过单个幺正算符的渐近成本。

4. 大规模生产 (定理 1.4)：
   实现 $m$ 个单比特幺正算符 $U^{\otimes m}$ 需要 $T$-计数 $O(m + \log(1/\varepsilon))$。这是最优的，改进了以往会产生 $\log(m)$ 因子的策略。

对前人工作的改进

• 本文消除了 LKS 态制备界限中存在的 $O(\sqrt{n})$ 和 $O(\log n)$ 开销，达到了信息论下界。
• 对角幺正算符的 $T$-计数从 $O(\sqrt{2^n} \log(n/\varepsilon))$ 改进为 $O(\sqrt{2^n \log(1/\varepsilon)})$。

重要性与主张

作者声称他们已经表征了量子态制备和对角幺正算符合成的最坏情况 $T$-计数，并确定了先前已知的上界由于不必要的开销而非紧致的。

• 最优性： 这些结果代表了“两全其美”，既提供了弱（幺正）模型中的上界，也提供了匹配的强（自适应）模型中的下界。
• 资源权衡： 该构造实现了在辅助量子比特数量与 $T$-计数之间近乎最优的权衡，尽管确切的最优权衡仍是一个开放性问题。
• 应用： 改进的界限导致了对魔态（magic states）的稳定器秩（stabilizer rank）以及布尔函数分解下界的轻微提升。文中强调了“大规模生产”这一结果是一个特定的应用，即合成相同的幺正算符比合成不同的幺正算符要便宜得多。

论文明确指出，虽然 $T$-计数现在是最优的，但 Clifford 门的数量仍为 $O(2^n \log(1/\varepsilon))$，这非常接近最优的 $\Omega(2^n/n)$ 但尚未达到。此外，对于一般（非对角）$n$ 比特幺正算符的最优 $T$-计数仍然是一个开放问题，其下界 $\tilde{\Omega}(2^n)$ 与目前已知的最佳上界 $\tilde{O}(2^{1.5n})$ 之间存在差距。