2026-08-21T18:02:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27393 2026-08-21T14:42:38Z ddc:004 open_access

A Slightly Improved Upper Bound for Quantum Statistical Zero-Knowledge Le Gall, François Liu, Yupan Wang, Qisheng Quantum statistical zero-knowledge Algorithmic Holevo-Helstrom measurement Algorithmic Uhlmann transform The complexity class Quantum Statistical Zero-Knowledge (QSZK), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound QIP(2) ∩ co-QIP(2), which was simplified following the inclusion QIP(2) ⊆ PSPACE established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 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) denotes the complement of QIP(2). We slightly improve this upper bound to QIP(2) ∩ co-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 proof system. A similar improvement also applies to the upper bound for the non-interactive variant 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, to appear). Schloss Dagstuhl – Leibniz-Zentrum für Informatik François Le Gall and Yupan Liu and Qisheng Wang 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.12 urn:nbn:de:0030-drops-273933 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode