技术摘要：对量子统计零知识（QSZK）上界的微小改进

1. 问题陈述

本文研究了**量子统计零知识（QSZK）**这一复杂度类，该类由具有单证明者量子交互式证明系统且满足统计零知识属性的承诺问题组成。在此项工作之前，QSZK 最佳的已知上界由 Watrous (2002, 2009) 确立为：
$$\text{QSZK} \subseteq \text{QIP}(2) \cap \text{co-QIP}(2)$$
这里，$\text{QIP}(2)$ 表示由两条消息组成的量子交互式证明系统，其中诚实证明者通常被假设为计算能力不受限。

本文研究的核心问题是：能否通过限制诚实证明者的计算资源来收紧这一上界。具体而言，作者探讨了 QSZK 在 $\text{QIP}(2) \cap \text{co-QIP}(2)$ 证明系统中，其诚实证明者是否可以从计算能力不受限转变为使用量子线性空间（从而实现单指数时间复杂度）。

2. 研究方法

作者的方法依赖于为两个用于原始 QSZK 证明的基础信息论工具——Holevo–Helstrom 测量和 Uhlmann 变换——构建算法版本。其核心技术创新在于利用**空间高效的量子奇异值变换（QSVT）**来实现这些工具。

2.1 关键技术工具

• 空间高效的多项式逼近： 作者利用了 Le Gall, Liu, 和 Wang (LLW25) 关于符号函数 $P^{\text{sgn}}_{d'}(x)$ 空间高效多项式逼近的最新结果。与可能需要多项式空间的标准时间高效 QSVT 方法不同，这些逼近可以在 $O(\log d)$ 空间和 $poly(d)$ 时间内计算完成。
• 块编码（Block-Encodings）： 该方法涉及为来自承诺问题的特定线性算子构建精确的块编码。
  • 对于 Holevo–Helstrom 测量，算子为 $(\rho_0 - \rho_1)/2$。
  • 对于 Uhlmann 变换，算子为 $X_{\text{Uhl}} = \text{Tr}_A(|\psi_0\rangle\langle\psi_1|)$，其中 $|\psi_0\rangle$ 和 $|\psi_1\rangle$ 是状态的纯化。
• Hadamard 测试： 作者采用一比特精度相位估计（Hadamard 测试），将酉块编码的实现转换为二结果测量或信道应用。

2.2 实现策略

1. 算法化 Holevo–Helstrom 测量： 作者构建了一个量子电路，用于逼近最优测量 $\Pi_0 = \frac{I}{2} + \frac{1}{2}\text{sgn}(\text{SV})\left(\frac{\rho_0 - \rho_1}{2}\right)$。通过在 $(\rho_0 - \rho_1)/2$ 的块编码上使用空间高效的 QSVT，他们在 $O(n)$ 空间和 $2^{O(n)}$ 时间内实现了具有 $2^{-n}$ 加性误差的实现。
2. 算法化 Uhlmann 变换： 作者构建了一个信道 $\Phi_\star(\cdot) = U_\star(\cdot)U_\star^\dagger$，其中 $U_\star = \text{sgn}(\text{SV})(\text{Tr}_A(|\psi_0\rangle\langle\psi_1|))$。他们结合了近期关于偏迹算子的精确块编码技术（来自 UNWT25）以及空间高效的 QSVT 来实现该变换，并具有类似的空间和时间界限。

3. 主要贡献与结果

3.1 主要定理

本文确立了关于 QSZK 及其补集的完备问题的两个主要定理：

• 定理 3.5 (GapQSD)： 量子状态可区分性问题（GapQSD）是 QSZK 的完备问题，它属于 $\text{QIP}(2)$，其诚实证明者使用量子线性空间（具体而言，空间大小与原始证明系统的记录大小成线性关系）。证明者的策略实现的完备性概率至少为 $\frac{1}{2} + \frac{1}{2}(T(\rho_0, \rho_1) - 2^{-n})$。
• 定理 4.7 (GapF2Est)： 量子平方保真度估计问题（GapF2Est）与 QSZK 的补集相关，它也属于具有量子线性空间诚实证明者的 $\text{QIP}(2)$。证明者的策略实现的完备性概率至少为 $F^2(\rho_0, \rho_1) - 2^{-n}$。

3.2 对复杂度类的意义

结合这些结果，可以得出主要推论：

• 推论 1.4： $\text{QSZK} \subseteq \text{QIP}(2) \cap \text{co-QIP}(2)$，且具有量子线性空间诚实证明者。其空间复杂度相对于原始 QSZK 证明系统的记录大小是线性的。
• 推论 1.5： 非交互变体 NIQSZK 包含在 qq-QAM（$\text{QIP}(2)$ 的一个子类，具有量子公共硬币）中，且具有量子线性空间诚实证明者。

3.3 计算效率比较

本文强调了在空间复杂度上相对于前人工作的多项式级改进。以往实现一般量子交互式证明中诚实证明者的尝试（例如 Myers 和 Yuen, 2023）需要量子多项式空间。相比之下，这项工作针对构成 QSZK 的特定两条消息系统实现了量子线性空间。因此，时间复杂度从超多项式（在状态维度 $N=2^n$ 下）改进到了单指数级（$2^{O(n)} = \text{poly}(N)$）。

4. 重要性与主张

作者声称这项工作为 QSZK 提供了一个“略微改进”的上界。其重要性在于诚实证明者的计算效率：

• 空间效率： 此前认为实现一般量子交互式证明中的诚实证明者（例如 Myers 和 Yuen, 2023）可能需要多项式空间，而本文证明了对于刻画 QSZK 的特定证明系统，其可以在线性空间内实现。
• 根本区别： 本文指出这种区别似乎是根本性的且难以弥合。即使将先前工作的 SDP 方法与空间高效的 QSVT 结合，对于一般的两条消息系统仍需要二次空间。本文的成功依赖于 GapQSD 和 GapF2Est 问题的特定结构性质。
• 开放问题： 作者谦虚地表示，虽然他们改进了证明者的效率，但关于 QSZK 的上界是否可以改进到由“公共硬币”定义的 $\text{QIP}(2)$ 子类（例如 $\text{qq-QAM} \cap \text{co-qq-QAM}$），或者经典上界是否可以改进到 $\text{PSPACE}$ 以下，目前仍是一个开放问题。他们指出，在线性空间内构造更一般问题（如 Close Image to Totally Mixed Problem）的最优状态仍然是一个技术障碍。

总之，本文表明 QSZK 典型 $\text{QIP}(2) \cap \text{co-QIP}(2)$ 特征化中的诚实证明者并非计算能力不受限，而是可以在量子线性空间内高效模拟，从而精细化了我们对量子环境下零知识证明资源需求的理解。