跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2512.11597 · v3

A slightly improved upper bound for quantum statistical zero-knowledge

首次提交 2025-12-12 22:33
版本更新 2026-11-18 21:13
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

The complexity class Quantum Statistical Zero-Knowledge (QSZK\mathsf{QSZK}), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}, which was simplified following the inclusion QIP(2)⊆PSPACE\mathsf{QIP(2)} \subseteq \mathsf{PSPACE} established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, QIP(2)\mathsf{QIP(2)} denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-QIP(2)\text{co-}\mathsf{QIP(2)} denotes the complement of QIP(2)\mathsf{QIP(2)}. We slightly improve this upper bound to QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)} with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original QSZK\mathsf{QSZK} proof system. A similar improvement also applies to the upper bound for the non-interactive variant NIQSZK\mathsf{NIQSZK}. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, 2026). We also establish that our linear-space bounds for these two tasks are near-optimal under the counting version of the Satisfiability Hypothesis (#SH).

作者备注:37 pages, 2 figures, 3 protocols. v3: Added near-optimality results for our linear-space bounds under #SH, along with minor changes. v2: Minor changes, including revisions to the proofs of Theorems 3.4, 4.5, and Corollary 4.9. This work supersedes Section 5 of arXiv:2308.05079v2

期刊信息:Proceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026), pp. 12:1-12:20, 2026

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-18 21:13 · 最新观测版本

A slightly improved upper bound for quantum statistical zero-knowledge

The complexity class Quantum Statistical Zero-Knowledge (QSZK\mathsf{QSZK}), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}, which was simplified following the inclusion QIP(2)⊆PSPACE\mathsf{QIP(2)} \subseteq \mathsf{PSPACE} established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, QIP(2)\mathsf{QIP(2)} denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-QIP(2)\text{co-}\mathsf{QIP(2)} denotes the complement of QIP(2)\mathsf{QIP(2)}. We slightly improve this upper bound to QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)} with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original QSZK\mathsf{QSZK} proof system. A similar improvement also applies to the upper bound for the non-interactive variant NIQSZK\mathsf{NIQSZK}. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, 2026). We also establish that our linear-space bounds for these two tasks are near-optimal under the counting version of the Satisfiability Hypothesis (#SH).

查看此版本解读 →查看此版本原文 ↗