技术摘要：通过空间高效的量子奇异值变换进行空间受限量子态测试

1. 问题陈述

本文研究了受限于对数个量子比特（空间受限量子计算）的量子计算计算能力。具体而言，它研究了空间受限量子态测试问题，即给定两个量子设备（电路）$Q_0$ 和 $Q_1$，它们分别作用于 $O(\log n)$ 个量子比特并制备量子态 $\rho_0$ 和 $\rho_1$。目标是在给定这些电路“源代码”的情况下，判定根据特定的距离度量，$\rho_0$ 与 $\rho_1$ 是 $\epsilon_1$-接近还是 $\epsilon_2$-远离。

作者关注两种不同的错误场景：

1. 单侧错误（认证）： 判定 $\rho_0 = \rho_1$ 还是距离至少为 $\alpha(n)$。
2. 双侧错误（测试）： 判定距离 $\ge \alpha(n)$ 还是 $\le \beta(n)$，其中 $\alpha(n) - \beta(n) \ge 1/\text{poly}(n)$。

本文考虑了三种主要的类距离度量：

• 迹距离 (Trace Distance, $T$)： 与 $\ell_1$ 范数相关。
• 平方希尔伯特-施密特距离 (Squared Hilbert–Schmidt Distance, $HS^2$)： 与 $\ell_2$ 范数相关。
• 量子熵差 ($S(\rho_0) - S(\rho_1)$) 以及 量子詹森-香农散度 (Quantum Jensen–Shannon Divergence, $QJS$)。

2. 方法论：空间高效的量子奇异值变换 (QSVT)

其核心技术贡献是空间高效变体的量子奇异值变换 (QSVT)。虽然标准的 QSVT (Gilyén et al., STOC 2019) 为时间高效的量子算法提供了一个统一框架，但其预处理步骤（特别是寻找多项式逼近的旋转角）并非空间高效的，这可能导致指数级的空间开销。

作者通过以下方式解决了这一问题：

• 平均切比雪夫截断 (Averaged Chebyshev Truncation)： 作者没有求解旋转角，而是利用 de La Vallée Poussin 部分和（切比雪夫截断的平均值）来逼近目标函数（例如符号函数、对数函数）。这种方法产生的多项式逼近误差界与次数 $d$ 无关，且预处理仅需 $O(s(n))$ 空间。
• 处理函数类：
  • 对于连续有界函数（如符号函数），他们使用确定性数值积分（复合梯形法则）以 $O(\log d)$ 空间计算系数。
  • 对于分段光滑函数（如归一化对数函数），他们采用基于空间高效随机游走的随机算法来估计低权重傅里叶逼近的系数，从而避免了超出对数空间的、需要高精度经典预处理的需求。
• 实现： 他们将这些多项式逼近与线性组合酉算子 (LCU) 技术以及鲁棒无备忘录振幅放大 (robust oblivious amplitude amplification) 相结合，在仅使用 $O(s(n))$ 个量子比特的情况下，在位串索引编码上实现该变换。

3. 核心贡献与结果

A. 空间受限复杂度类的完全刻画

本文确立了第一类自然的单侧酉误差 ($coRQUL$) 和**双侧误差** ($BQL$) 空间受限量子计算完全问题。

1. $coRQUL$-完全性（单侧错误）：

   • 问题： 迹距离下的空间受限量子态认证 ($CertQSD_{log}$) 和平方希尔伯特-施密特距离 ($CertQHS_{log}$)。
   • 结果： 这些问题是 $coRQUL$-完全的。该算法实现了完美完备性（若$\rho_0 = \rho_1$ 则以概率 1 接受），并在距离较大时，利用精确振幅放大使接受概率偏离 1 的程度呈多项式级。

2. $BQL$-完全性（双侧错误）：

   • 问题： 迹距离下的空间受限量子态测试 ($GapQSD_{log}$)、平方希尔伯特-施密特距离下的测试 ($GapQHS_{log}$)、量子熵差测试 ($GapQED_{log}$) 以及量子詹森-香农散度测试 ($GapQJS_{log}$)。
   • 结果： 所有四个问题均为 $BQL$-完全。
   • 意义： 与时间受限的状态测试不同（在时间受限设定下，复杂度取决于度量标准，例如迹距离是 $QSZK$-完全，而 $HS^2$ 是 $BQP$-完全），作者表明所有这些空间受限测试问题在计算上都与制备这些状态本身一样简单（即处于 $BQL$ 中）。

B. 算法框架

作者提出了一个通用的空间受限量子态测试框架：

1. 构建感兴趣算子的块编码 (block-encoding)（例如，对于迹距离，使用 $\frac{\rho_0 - \rho_1}{2}$；对于熵，使用 $\rho_i$）。
2. 使用空间高效的 QSVT，利用目标函数（如迹距离对应的符号函数，或熵对应的对数函数）的多项式逼近。
3. 使用 Hadamard 测试（或相位估计）来估计 $\text{Tr}(P(A)\rho)$，该值与距离度量相关。
4. 通过顺序重复该过程，在加性误差范围内估计该值，从而保持在 $BQL$ 内。

C. 硬度结果

论文通过将已知的硬问题（如良态矩阵幂或迭代矩阵乘积）归约为这些状态测试问题，证明了这些问题的硬度。

• $GapQSD_{log}$ 和 $GapQHS_{log}$ 被证明是 $BQUL$-硬的（因此也是 $BQL$-硬的）。
• $CertQSD_{log}$ 和 $CertQHS_{log}$ 被证明是 $coRQUL$-硬的。
• 对于 $GapQED_{log}$ 和 $GapQJS_{log}$ 的硬度是通过对 $GapQSD_{log}$ 的归约得出的。

4. 重要性与主张

本文声称取得了若干重要的概念和技术进展：

• 空间受限算法的统一框架： 空间高效的 QSVT 为设计量子对数空间算法提供了一个统一的方法，类似于标准 QSVT 统一了时间高效算法。这为发现 $BQL$ 及其变体的完全问题提供了新的方向。
• 空间受限测试的统一性： 研究结果揭示了时间受限与空间受限量子态测试之间的根本区别。在时间受限设定下，复杂度随距离度量的不同而显著变化（范围从 $SZK$-完全到 $BPP$-完全）；相比之下，空间受限设定展现出一种统一的复杂度景观，即所有考虑到的度量均为 $BQL$-完全。这意味着，在受限空间内制备量子态的测试在计算上等价于制备它们本身。
• 新的完全问题： 本工作引入了首批自然的 $coRQUL$-完全问题（填补了自 Watrous 在 2001 年提出 $RQUL$ 以来的空白），并将自然 $BQL$-完全问题的家族从线性代数任务（如矩阵求逆）扩展到了量子属性测试。
• 技术独立性： 空间高效的 QSVT 技术本身具有独立的价值，它提供了一种实现奇异值变换的方法，对于投影后的酉编码，其空间开销仅为常数级，且与多项式次数（在指数界限内）无关。

作者对未来的应用保持谦逊，指出虽然该框架暗示了在 $BQL$ 中求解半正定规划 (SDP) 的潜力，但由于迭代应用空间高效 QSVT 目前面临着辅助量子比特增长的问题，这仍然是一个悬而未决的挑战。