技术摘要：估计量子态的 Schatten 范数与幂距离

问题陈述

本文研究了在给定状态制备电路的情况下，估计两个 $n$ 量子比特量子态 $\rho_0$ 和 $\rho_1$ 之间距离的计算复杂度。研究的核心重点是 量子 Schatten $\alpha$-范数距离（Quantum Schatten $\alpha$-norm distance），定义为 $T_\alpha(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\alpha = \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)^{1/\alpha}$，以及其幂版本——量子 Schatten $\alpha$-幂距离（Quantum Schatten $\alpha$-power distance），$\Lambda_\alpha(\rho_0, \rho_1) := \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)$。

本文探讨的核心问题是 具有 Schatten $\alpha$-范数的量子状态可区分性问题（QSD$_\alpha$）的计算复杂度：判定是否 $T_\alpha(\rho_0, \rho_1) \geq 2/5$ 或 $T_\alpha(\rho_0, \rho_1) \leq 1/5$。作者旨在解决 trace 距离（$\alpha=1$）与 $\ell_2$ 类度量（例如 Hilbert-Schmidt 距离，$\alpha=2$）之间的复杂度二分法。已知 trace 距离是 QSZK-完全的，而 $\ell_2$ 类度量属于 BQP。作者询问这种二分法是否对所有常数 $\alpha > 1$ 都成立，或者复杂度是否取决于 $\alpha$ 是偶数还是奇数。

此外，本文还研究了 $0 < \alpha < 1$ 的情形。在此范围内，$T_\alpha$ 不再是度量（违反三角不等式），而 $\Lambda_\alpha$ 仍然是一个有效的距离度量（准范数幂）。作者寻求在该范围内 $\Lambda_\alpha$ 的高效估计器。

方法论

1. 高效量子估计器

作者开发了基于 量子奇异值变换 (QSVT) 和 算子线性组合 (LCU) 的量子算法。

• 对于 $\alpha > 1$（与秩无关）：
  核心挑战在于如何高效逼近函数 $f(x) = \text{sgn}(x)|x|^{\alpha-1}$。作者利用了用于符号正幂的 最佳一致多项式逼近（受 Bernstein 工作及近期关于 Tsallis 熵结果的启发）。

  • 他们构造了一个多项式 $P(x)$，在 $[-1, 1]$ 上以均匀误差 $\epsilon$ 逼近 $\frac{1}{2}\text{sgn}(x)|x|^{\alpha-1}$。
  • 利用 QSVT，他们实现了 $\text{sgn}(\nu)|\nu|^{\alpha-1}$ 的块编码（block-encoding），其中 $\nu = \rho_0 - \rho_1$。
  • 通过 Hadamard 测试计算 $\text{tr}(\rho_0 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1}) - \text{tr}(\rho_1 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1})$ 来估计距离。
  • 关键创新： 不同于以往依赖于投影算子秩相关块编码的方法（如 [WGL+24]），该方法使用不依赖于状态秩的多项式逼近，实现了 秩无关（rank-independent） 的查询和采样复杂度。

• 对于 $0 < \alpha < 1$（与秩相关）：
  在此范围内，函数 $x^{\alpha-1}$ 在 $x=0$ 处存在奇异性。作者使用在远离零点（使用截断值 $\delta$）时有效的缩放符号幂的多项式逼近。

  • 算法通过使用一个有界但会在零点附近产生误差的多项式来逼近 $\text{sgn}(\nu)|\nu|^{\alpha-1}$。
  • 该方法导致了 秩相关（rank-dependent） 的复杂度，具体表现为关于秩 $r$ 的多项式级别，但优于先前的界限。

2. 硬度与下界

为了建立计算硬度，作者推导了联系 trace 距离 $T(\rho_0, \rho_1)$ 与 $T_\alpha$ 及 $\Lambda_\alpha$ 的新 秩相关不等式。

• 不等式： 他们证明了对于纯态，$T_\alpha$ 与 $T$ 满足常数因子关系；但对于混合态，这种关系取决于状态的秩。具体而言，$T(\rho_0, \rho_1) \leq 2(\text{rank}(\rho_0)^{1-\alpha} + \text{rank}(\rho_1)^{1-\alpha})^{-1/\alpha} T_\alpha(\rho_0, \rho_1)$。
• 归约：
  • BQP-硬度： 通过限制在纯态情形，作者表明通过 $T_\alpha$（对于 $\alpha \geq 1$）或 $\Lambda_\alpha$（对于 $0 < \alpha < 1$）区分状态与标准的 BQP 完全问题（PureQSD）一样困难。
  • QSZK-硬度： 对于 $\alpha$ 极度接近 1 的情况（具体为 $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$），他们利用了 $T_\alpha$ 的 部分极化引理（partial polarization lemma）。该引理允许他们像 trace 距离的极化过程一样放大 $T_\alpha$ 的间隙，从而证明在此情形下 QSD$_\alpha$ 是 QSZK-完全的。
  • 对于常数 $0 < \alpha < 1$，他们通过对 trace 距离应用极化并利用 $\Lambda_\alpha$ 关于 $T^\alpha$ 和秩的上界，证明了 PoweredQSD$_\alpha$ 是 QSZK-硬的。

核心贡献与结果

1. 高效量子算法

• 对于常数 $\alpha > 1$： 作者提出了一个高效的量子算法，使用 $O(1)$ 次查询（秩无关）以加性误差 $\epsilon$ 估计 $T_\alpha(\rho_0, \rho_1)$。如果状态制备电路是多项式大小，则时间复杂度为 $\text{poly}(n)$。
  • 这相对于之前的最优结果 [WGL+24] 实现了 指数级加速，后者具有依赖于秩 $r$ 的查询复杂度 $\tilde{O}(r^{3+1/\{\alpha/2\}}/\epsilon^{4\alpha+\dots})$。
  • 采样复杂度也得到了改进，变为 $\tilde{O}(1/\epsilon^{3\alpha+2+\dots})$（秩无关）。
• 对于常数 $0 < \alpha < 1$： 一个高效算法以 $\tilde{O}(r^{2/(\alpha-1)}/\epsilon^{2/\alpha})$ 的查询复杂度估计 $\Lambda_\alpha(\rho_0, \rho_1)$。这改进了之前 $\tilde{O}(r^{5/\alpha}/\epsilon^{5/\alpha+1})$ 的最优界限，但仍依赖于秩 $r$。

2. 计算复杂度二分法

本文确立了 QSD$_\alpha$ 复杂度中的剧烈相变：

• 情况 $\alpha > 1$（固定常数）： QSD$_\alpha$ 是 BQP-完全的。该问题在量子计算机上是可解的，且估计器与秩无关。
• 情况 $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$： QSD$_\alpha$ 是 QSZK-完全的。除非 BQP = QSZK，否则不存在高效的量子估计器。
• 情况 $0 < \alpha < 1$（固定常数）： PoweredQSD$_\alpha$ 是 QSZK-硬的。

3. 新的不等式

作者提供了连接 trace 距离、Schatten 范数和幂距离的新型秩相关不等式。这些不等式具有独立的学术价值，并且对于硬度归约至关重要，特别是展示了“容易”的情形（纯态）如何随着 $\alpha$ 趋向 1 而过渡到“困难”的情形（高秩混合态）。

重要性

本文解决了引言中提出的 问题 1，即关于使用一般 Schatten $\alpha$-范数进行接近度测试的计算复杂度问题。

• 它证明了 $\ell_1$-类度量（QSZK-硬）与 $\ell_2$-类度量（BQP-包含）之间的二分法不仅仅是偶数与奇数之间的区别，而是在 $\alpha=1$ 与任何常数 $\alpha > 1$ 之间发生的剧烈转变。
• 开发针对 $\alpha > 1$ 的 秩无关估计器 是一项重要的技术进步，消除了此前量子状态属性测试中的主要瓶颈（即需要预知或依赖于状态的秩）。
• 这些结果澄清了量子状态可区分性的图景，表明虽然对于 $\alpha > 1$ 的 $T_\alpha$ 是 trace 距离的一个自然下界，但它对于任何固定的 $\alpha > 1$ 都是可高效计算的，这与 trace 距离本身不同。

作者指出，$\alpha = \infty$ 的情况仍是一个开放问题，相关的承诺问题 QSD$_\infty$ 是 BQP-硬的且包含在 QMA 中，但目前尚不确定其是否包含在 BQP 中。此外，作者也留下了关于表 1 中的定量界限是否能进一步收紧的问题。