A slightly improved upper bound for quantum statistical zero-knowledge
By: François Le Gall, Yupan Liu, Qisheng Wang
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 \textit{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. A similar improvement also applies to the upper bound for the non-interactive variant $\mathsf{NIQSZK}$. Our main techniques are an algorithmic version 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).
Similar Papers
QIP $ \subseteq $ AM(2QCFA)
Quantum Physics
Makes computers solve harder problems with quantum help.
Quantum Statistical Witness Indistinguishability
Quantum Physics
Keeps secrets safe even with quantum computers.
NISQ Security and Complexity via Simple Classical Reasoning
Quantum Physics
Makes quantum computers more secure and reliable.