← 研踪 PaperTrailarXiv: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
摘要
The complexity class Quantum Statistical Zero-Knowledge (), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound , which was simplified following the inclusion established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and denotes the complement of . We slightly improve this upper bound to with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original proof system. A similar improvement also applies to the upper bound for the non-interactive variant . 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-18 21:13 · 最新观测版本
A slightly improved upper bound for quantum statistical zero-knowledge
The complexity class Quantum Statistical Zero-Knowledge (), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound , which was simplified following the inclusion established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and denotes the complement of . We slightly improve this upper bound to with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original proof system. A similar improvement also applies to the upper bound for the non-interactive variant . 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).
查看此版本解读 →查看此版本原文 ↗