2025/12/12 by Gall, François Le, Liu, Yupan, Wang, Qisheng
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2512.11597
openalex publication_date 2025/12/12 · openalex created_date 2025/12/16 · openalex updated_date 2026/07/28
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).