$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation

技术摘要：通过块稀疏哈密顿量模拟实现 T-高效幺正变换合成

问题陈述
在容错量子计算中，非 Clifford 门（特别是 $T$ 门）是比 Clifford 门昂得多的资源，通常需要进行魔态蒸馏。一个核心挑战是确定合成任意 $n$ 量子比特幺正变换 $U \in U(N)$（其中 $N=2^n$ 到达目标算符范数误差 $\epsilon$）所需的最小 $T$ 门数量。虽然计数论证确立了 $\Omega(N)$ 的下界，但以往针对最坏情况合成的上限范围从 $\tilde{O}(N^{3/2})$ 下降到了 $\tilde{O}(N^{5/4})$。这些界限与理论下限之间的差距仍然显著，特别是在 $T$ 计数与辅助量子比特（ancilla）使用量之间的权衡方面。

方法论
作者提出了一种构造方法，通过将目标幺正变换编码为厄米对数（Hermitian logarithm）的演化 $U = e^{iH}$，并利用随机相似变换、块稀疏划分和随机乘积公式来模拟这一演化。

1. 厄米对数与平坦化（Flattening）： 目标幺正变换被分解为一个全局相位和一个无迹厄米生成元 $H_0$。为了控制矩阵块的范数，作者应用了一个两层随机相似变换 $P = F S_\tau F S_\sigma F$（其中 $F$ 是 Hadamard 变换，$S$ 是随机符号矩阵）。这种“平坦化”确保了变换后的生成元 $H'$ 的 $b \times b$ 块的算符范数以高概率保持在较小水平，具体为 $\tilde{O}(1/\sqrt{D})$，其中 $D = N/b$。

2. 块稀疏划分： 平坦化后的生成元 $H'$ 被随机划分为 $s$ 个厄米部分 $H_1, \dots, H_s$。每个部分仅保留原始块的一个子集，同时确保非对角伴随对被分配到同一个部分，以保持厄米性。这导致了块稀疏矩阵，每个部分相对于稠密矩阵而言，每列拥有的非零块数量显著减少。

3. 独立的块编码： 与以往处理包含所有 $N^2$ 个条目的单个查找表的稠密编码方法（例如 Yuan 等人的工作）不同，该方法为每个部分构建了单独的块编码。每个部分使用一个更小的查找表，其条目数为 $O(D^2/s)$。每次查询块编码的成本从 $\tilde{O}(N)$ 降低到 $\tilde{O}(N/\sqrt{s} + b^2)$。

4. 通过 qDRIFT 和 QSVT 进行哈密顿量模拟： 利用 qDRIFT 算法近似演化 $e^{iH'}$，该算法通过采样单个部分 $H_k$ 的短时间演化来进行。总演化是这些短段的乘积。每一段都使用应用于所选部分特定块编码的量子奇异值变换（QSVT）来实现。

5. 残差精化（Residual Refinement）： 为了提高精度依赖性，作者采用了残差精化策略。在初始近似之后，剩余的误差被视为一个新的目标幺正变换。这个过程重复进行，生成元的范数在每一步都会缩小，从而允许使用更少的块并减少后续迭代中的模拟成本。

主要贡献与结果

• 改进的上限： 本文建立了一个结论，即任何 $n$ 量子比特的幺正变换都可以使用 Clifford+T 电路以常数精度合成，其 $T$ 计数为 $\tilde{O}(N^{8/7})$。这改进了之前最优的 $5/4$ 指数。

  • 对于目标误差 $\epsilon$，满足 $L = n + \log_2(1/\epsilon) \leq N$ 时，精化后的构造实现的 $T$ 计数为 $\tilde{O}(N^{8/7}L^{3/7} + NL)$，并使用 $\tilde{O}(N)$ 个干净的辅助量子比特。
  • 在常数精度下，该构造使用 $\tilde{O}(N^{8/7})$ 个 $T$ 门和 $\tilde{O}(N^{6/7})$ 个干净的辅助量子比特。

• 受限模型内的最优性： 作者证明了在“顺序块-SELECT”（sequential block-SELECT）成本模型下的匹配下界 $\tilde{\Omega}(N^{8/7})$。该模型考虑了矩阵查找、块处理和模拟的成本，同时限制了存储在哈密顿量演化之间的幺正变换中的信息。这表明 $8/7$ 指数对于此类构造是优化的。

• 资源权衡： 该构造明确平衡了单次查询成本（通过更小的查找表降低）与所需查询次数（由于需要模拟许多部分的求和而增加）之间的关系。通过选择最优的块大小 $b$ 和部分数量 $s$ 来最小化总 $T$ 计数，从而得到 $N^{8/7}$ 的缩放比例。

意义
本文声称缩小了常数精度下最坏情况幺正变换合成的已知上限与下限之间的差距，将指数从 $5/4$ 降低到了 $8/7$。其意义在于证明了通过分别编码块稀疏部分而非使用稠密全局编码，可以显著降低主要的查找成本。此外，在顺序块-SELECT模型内证明的最优性为进一步改进该指数提供了有力证据，表明任何进一步的改进可能需要采用该模型之外的根本不同的方法。这项工作还强调了 $T$ 计数与辅助量子比特使用量之间的权衡，指出虽然其构造比以往的一些工作（如 Tan 的工作）使用更多的辅助量子比特，但它实现了更低的 $T$ 计数，使资源成本更接近于 $T \approx m_{anc} \approx N$ 的平衡规模。作者承认，对于不受限制电路的通用下界 $\Omega(N^{1+c})$ 仍是一个开放性问题。