A Slightly Improved Upper Bound for Quantum Statistical Zero-Knowledge
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).
Cite this item
Le Gall, F., Liu, Y., & Wang, Q. (2026). A Slightly Improved Upper Bound for Quantum Statistical Zero-Knowledge. In M. Koucky & D. Petrisan (Editors), 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) (No. 12). 51 International Symposium on Mathematical Foundations of Computer Science, Paris, France, August 24, 2026. https://doi.org/10.4230/LIPIcs.MFCS.2026.12
Click Copy to copy the citation, or select the text manually.
LIPIcs.MFCS.2026.12.pdf
Main Document
openaccess
CC BY
951.22 KB
Adobe PDF
707c1c537c12b7bab5434bb231e69dd4