Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

以下是关于 Guan 与 Katiyar 的论文《Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms》（无条件的非均匀量子傅里叶与切比雪夫变换）的技术摘要翻译：

问题陈述

本文旨在解决在量子计算机上高效计算**非均匀切比雪夫变换（NUCT）**的挑战。NUCT 将定义在等间距节点 $x_k \in [-1, 1]$ 上的函数 $f$ 映射到其在切比雪夫多项式 $T_j(x)$ 上的投影。

• 难点： 虽然在切比雪夫节点（在角度 $\theta = \arccos x$ 下是均匀的，但在 $x$ 上是非均匀的）上的经典离散切比雪夫变换可以简化为标准的离散傅里叶变换（DFT），但等间距 $x$ 节点上的 NUCT 对应于在非均匀角度 $\theta_k = \arccos(x_k)$ 下的 DFT。
• 先前的局限性： 现有的量子方法（如 [AKY26] 中的非均匀量子傅里叶变换 NUQFT）依赖于变换矩阵的低秩分解。然而，这些现有方法的误差界限取决于一个与几何相关的参数 $\kappa$，该参数定义为应用 $\arccos$ 函数的平均值定理时的 $1/\sqrt{1-(y^*)^2}$ 的最大值。对于靠近网格边界的节点（其中 $y^* \to \pm 1$），$\kappa$ 会变得任意大，从而可能破坏算法的效率保证。此外，先前的研究通常假设存在底层稀疏矩阵的“行访问预言机（row-access oracles）”，而没有进行显式构造。

方法论

作者提出了一种无条件的 NUQFT，并通过以下方法论步骤将其应用于 NUCT：

1. 精确定点处理： 该算法并非将存储的节点值视为实数的带噪声近似，而是将 $m$ 位定点表示 $\tau_k$ 视为变换的精确输入节点。变换矩阵 $F_\tau$ 是根据这些精确存储的数值构造的。
2. 误差分解： 总误差被分为两个独立的组成部分：
   • 实现误差： 实现的电路与在存储节点（$F_\tau$）上的变换之间的差异。
   • 节点误差： 在存储节点（$F_\tau$）上的变换与目标实数节点（$F_t$）之间的差异。
3. 消除 $\kappa$：
   • 在实现误差分析中，算法在精确存储的偏移量 $z_j$ 上计算 $\arccos$。由于 $\arccos$ 的输入是精确的，误差仅源于输出角度的舍入。这避免了 $\arccos$ 在 $\pm 1$ 处无界的导数作用于输入误差，从而消除了对 $\kappa$ 的依赖。
   • 节点误差通过分析傅里叶相位对节点扰动的敏感性来单独进行界定，其结果是一个与 $\|t - \tau\|_\infty$ 成比例的界限，且不存在几何奇异性。
4. 低秩分解与 LCU： NUCT 矩阵被简化为两个 II 型非均匀离散傅里叶变换（NUDFT）的平均值。每个 NUDFT 通过低秩切比雪夫-贝塞尔展开（秩为 $K$）进行近似。作者使用带有加权外态的**线性组合酉算符（LCU）**来实现这一点，与均匀 LCU 方法相比，这改善了归一化因子。
5. 显式预言机构造： 论文提供了以下方面的显式量子电路：
   • 节点预言机 ($O_\tau$)： 可逆地计算 $\arccos(x_k)$ 的 $m$ 位近似值。
   • 行访问预言机 ($O_r$)： 利用 NUCT 节点的特定结构（即最多有 5 个节点映射到同一个网格点，且索引是连续的），在无需查找表的情况下提供稀疏行访问。
   • 系数准备： 在经典端构造贝塞尔函数系数并将其加载到量子态中，证明这些系数是与实例无关的。

核心贡献

1. 无条件的 NUQFT： 主要的理论贡献是一个改进的 NUQFT 算法（定理 4.7），其中误差界限和资源需求独立于几何参数 $\kappa$。误差仅取决于每个节点的位数 ($m$)、目标精度 ($\epsilon$) 和行稀疏度 ($d_r$)。
2. 改进的归一化： 通过利用加权外 LCU 和对总贝塞尔权重（$\Lambda < 24$）更紧凑的界限，作者实现了 $O(\sqrt{d_r})$ 的块编码归一化。对于 $d_r \le 5$ 的 NUCT，这导致了 $O(1)$ 归一化，相比于先前方法的 $O(K^2\sqrt{d_r})$ 或 $O(K\sqrt{d_r})$ 标度，这是一个显著的改进。
3. 显式预言机构造： 论文通过提供专门为等间距切比雪夫设置定制的、高效的节点生成和行访问量子电路，消除了对预存预言机的假设。
4. 端到端 NUCT 算法： 作者提出了一个完整的 NUCT 量子电路（算法 2），包括涵盖量子比特数、门深度和成功概率的严格复杂度分析。

结果

论文确定了具有 $N=2^q$ 个节点和目标精度 $\epsilon$ 的 NUCT 的以下复杂度结果：

• 量子比特复杂度： $O(L)$ 个量子比特，其中 $L = q + \log(1/\epsilon)$。
• 门复杂度： $\tilde{O}(L^2)$ 个逻辑门（可逆算术、Clifford、Toffoli、受控旋转）。当合成到 Clifford+T 门时，复杂度为 $\tilde{O}(L^3)$。
• 归一化： $O(1)$（具体限定为 $24\sqrt{5}$）。
• 精度： 算法产生一个 $\epsilon$-精确的 NUCT 矩阵块编码。
• 输出态： 给定输入态 $|f\rangle$，算法准备一个近似归一化输出 $C_N|f\rangle / \|C_N|f\rangle\|$ 的态，其误差为 $O(\epsilon / (r-\epsilon))$，其中 $r = \|C_N|f\rangle\|$。所需的振幅放大轮数为 $O(1/(r-\epsilon))$。

意义与主张

作者声称这项工作提供了第一个针对等间距节点上的非均匀切比雪夫变换的高效、无条件的量子算法。

• 指数级加速： 该变换的经典算法（由 Driscoll, Healy, and Rockmere [DHR97] 提出）需要 $O(N \log^2 N)$ 次操作。所提出的量子算法在 $N$ 上是多项式对数级的（$\tilde{O}(\log^2 N)$），在变换本身提供了指数级加速。
• 通用变换的基础： 作者将 NUCT 定位为实现完整 [DHR97] 流程的关键构建模块，该流程通过基于三项递推关系的分治法，计算用于一般正交多项式族的离散多项式变换。
• 鲁棒性： 通过消除对 $\kappa$ 的依赖，该算法对于任何节点分布都是鲁棒的，包括那些节点任意接近网格边界的情况，而在这种情况下，以往的方法将会失效或需要未经验证的节点放置假设。

论文最后指出，虽然变换本身具有指数级的加速，但对于实际应用的端到端加速取决于输入态准备的成本、输出的范数以及所需输出系数的数量。未来的工作旨在将这些技术扩展到一般的正交多项式族。