A slightly improved upper bound for quantum statistical zero-knowledge

Abstract

The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound $\mathsf{QIP}(2)\cap \text{co-}\mathsf{QIP}(2)$, which was simplified following the inclusion $\mathsf{QIP}(2)\subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, $\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 $\text{co-}\mathsf{QIP}(2)$ denotes the complement of $\mathsf{QIP}(2)$. We slightly improve this upper bound to $\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 $\mathsf{QSZK}$ proof system. A similar improvement also applies to the upper bound for the non-interactive variant $\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, to appear).

31 pages, 2 figures, 3 protocols. v2: To appear in MFCS 2026. 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