A log-depth in-place quantum Fourier transform that rarely needs ancillas

技术摘要：一种极少需要辅助量子的对数深度原地量子傅里叶变换

问题陈述
为特定幺正变换设计量子电路时，通常需要在资源约束（深度、量子比特数、局部性）与近似误差之间进行权衡。传统方法要求电路在所有可能的输入状态下都能以低误差近似一个幺正变换。然而，实现这种“最坏情况”保证往往需要大量的资源，例如大量的辅助量子比特、长程门或深层电路。例如，先前的对数深度量子傅里叶变换（QFT）构造需要 $O(n)$ 个辅助量子比特、长程连通性或基于测量的反馈控制。作者提出，对于大型量子算法中的许多应用而言，只要能对大多数输入实现良好的近似，即便是“坏”输入（其中误差较高）是稀有的或可以通过规约来处理，也是足够的。

方法论
本文引入了一个“乐观量子电路”的框架，并将其应用于 QFT，随后使用了一种处理最坏情况输入的规约技术。

1. 乐观量子电路：
   作者定义了一个针对目标幺正变换 $U$ 的乐观量子电路 $C$（诱导幺正变换为 $\tilde{U}$），其中在任何正交基上的平均平方误差被限制在 $\epsilon$ 以内。形式上，$\frac{1}{\dim \mathcal{H}} \sum_i \|\tilde{U}|\phi_i\rangle - U|\phi_i\rangle\|^2 < \epsilon$。这个定义是与基无关的，且等价于限制误差算子的 Frobenius 范数。至关重要的是，这允许存在一个极小的“坏”输入子空间，其中误差为 $O(1)$，只要该子空间仅占据希尔伯特空间的 $O(\epsilon)$ 分数。

2. 乐观 QFT 构造：
   作者构造了一个针对 $n$ 个量子比特、误差参数为 $\epsilon$ 的乐观 QFT ($\widetilde{\text{QFT}}$)。

   • 分块方法： 将输入寄存器划分为大小为 $m = O(\log(n/\epsilon))$ 的块。
   • 相位估计技巧： 该电路利用了这样一个事实：对一个块应用逆 QFT 可以近似对该块的相位因子进行相位估计。通过对一个块应用 $\text{QFT}^\dagger$，电路可以估计相邻块的相位贡献。
   • 交换律： 构造中插入了形式为 $\text{QFT}^\dagger \text{QFT}$ 的恒等变换，并将交换的块相互移动。这打破了标准近似 QFT 的线性依赖链。
   • 失效模式： 当块上的输入状态接近 $0$或$2^m$（即由长串的 0 或 1 组成）时，相位估计会失效（模$2^m$ 绕回）。这些构成了“坏”子空间。
   • 资源： 所得电路深度为 $O(\log(n/\epsilon))$，使用恰好 $n$ 个量子比特（无辅助量子比特），对于 1D 量子比特排列是局部的（范围为 $O(\log(n/\epsilon))$），且无需测量。

3. 从平均情况到最坏情况的规约：
   为了应对输入可能集中在“坏”子空间的情况，作者提出了一种规约技术，将乐观电路转化为通用近似电路。

   • 随机化规约： 在应用乐观电路之前，先应用一个来自幺正 1-设计（unitary 1-design）的随机幺正变换 $V$。之后，应用 $\hat{V}^\dagger = U V^\dagger U^\dagger$。这会对输入状态进行随机化，确保落在高误差子空间的概率很低。
   • 去随机化规约： 通过将 $V$ 的选择编码进一个控制寄存器，可以将随机化过程纯化为一个幺正操作。
   • 特定 1-设计： 对于 QFT，作者利用 Weyl-Heisenberg 群（对 Pauli 类平移和相位梯度进行均匀采样）作为 1-设计。这种选择确保了所需的随机化和去随机化操作是高效的。

核心贡献与结果

• 乐观 QFT： 本文提出了第一个同时实现以下特征的 QFT 构造：
  • 深度：$O(\log(n/\epsilon))$。
  • 量子比特数：$n$（无辅助量子比特）。
  • 局部性：$O(\log(n/\epsilon))$ 范围（对于 1D 是局部的）。
  • 无需测量。
  • 误差：在除 $O(\epsilon)$ 比例的希尔伯特空间之外的所有状态上均受限于 $\epsilon$。
• 乐观乘法与因数分解： 作者展示了可以将乐观 QFT 直接用于 Shor 算法进行整数分解。通过将乐观 QFT 集成到近期的基于 QFT 的快速算术构造中（具体而言是一个乐观乘法器），他们实现了深度为 $O(n^{1+\delta})$（对于可调的 $\delta > 0$）的分解电路，且总共仅使用 $2n + O(n/\log n)$ 个量子比特。与以往需要 $O(n)$ 个辅助量子比特或更深电路的方法相比，这在深度和量子比特效率上都有显著提升。
• 通用近似 QFT： 通过应用规约技术，作者推导出了一个在任意输入上均具有低误差的近似 QFT。
  • 随机化版本： 使用 $n + O(n/\log(n/\epsilon))$ 个总量子比特实现 $O(\log(n/\epsilon))$ 的深度。
  • 去随机化（幺正）版本： 使用 $3n + O(n/\log(n/\epsilon))$ 个总量子比特实现 $O(\log(n/\epsilon))$ 的深度。
  • 这些被认为是首个实现渐近最优对数深度且具有亚线性辅助量子比特数（随机化版本）或无需测量/反馈控制（去随机化版本）的构造。

意义
本文声称，“乐观量子电路”为量子算法设计提供了一种实用的范式转变。通过接受在典型算法语境下（如 Shor 算法）统计上极不可能发生的罕见失效模式，人们可以大幅减少资源开销（深度和辅助量子比特数）。特定的乐观 QFT 构造消除了分解电路中 QFT 的瓶颈，从而实现了近线性深度的分解，且仅需极少的量子比特开销。此外，所提供的规约技术提供了一种通用的方法，可将此类乐观电路转化为鲁棒的最坏情况保证，从而在启发式效率与严格正确性之间架起桥梁。这项工作表明，随着量子硬件的成熟，时空体积与深度的权衡将变得至关重要，而这些构造为优化两者提供了路径。