Quantum proof systems with fewer messages achieve perfect correctness
Achieving perfect completeness for one- and two-message quantum proof systems
Computational Complexity
Summary
Quantum proof systems help verify complex problems by exchanging messages between a prover and a verifier. Until now, it was unknown if systems with only one or two messages could always be perfectly certain when accepting correct answers. The authors show that these simpler systems can indeed achieve perfect correctness, meaning they never wrongly reject true cases. They use new mathematical constructions and transformations to prove this for several classes of quantum proof systems.
What this means in practice
- •For quantum algorithm developers: Design verification protocols that guarantee perfect acceptance for correct quantum proofs using fewer message exchanges.
- •For quantum cryptography engineers: Implement quantum proof systems with guaranteed perfect completeness to increase protocol reliability under message constraints.
A theory result. No direct application yet.
Authors
Yupan Liu, Thomas Vidick
Abstract
While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether perfect completeness is achievable for one- and two-message quantum proof systems has remained open. For the one-message case, whether $\sf QMA$ can achieve perfect completeness was posed as an open problem in Watrous (FOCS 2000) and Aharonov and Naveh (2002); for the two-message case, the corresponding problems were (implicitly) posed in Jain, Upadhyay, and Watrous~(FOCS 2009) and Kobayashi, Le Gall, and Nishimura (SICOMP, 2019). In this work, we establish that ${\sf QIP}(2)$, ${\rm qq}\text{-}{\sf QAM}$, $\sf QAM$, and $\sf QMA$ can achieve perfect completeness. Here ${\rm qq}\text{-}{\sf QAM}$ denotes the class of promise problems admitting two-message quantum-public-coin quantum interactive proof systems in which the verifier's only message consists of half-EPR pairs. Our main technical contributions are the follows: 1. For $\sf QMA$ (and directly for $\sf QAM$), an exactly constructible block-encoded matrix whose kernel certifies yes instances, constructed from the acceptance operator induced by the verification circuit. 2. For ${\sf QIP}(2)$ (and implicitly ${\rm qq}\text{-}{\sf QAM}$), a new turn-halving transformation that preserves completeness and ensures that the resulting proof system retains at least two messages, provided that the terminal state before the final measurement is efficiently preparable.