Achieving perfect completeness for one- and two-message quantum proof systems
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), qq−sf QAM, sf QAM, and sf QMA can achieve perfect completeness. Here qq−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. This also yields an alternative proof of sf QCMA=sf QCMA1. 2. For sf QIP(2) (and implicitly qq−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.
Related
- Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials
- QMA has perfect completeness
- Simultaneously achieving Heisenberg- and Landau-limited precision in equilibrium quantum thermometry
- On the Completeness of Quantum Mechanics: Sources, Records and Probabilities
- Learning to Decode Concatenated Quantum Codes with Hierarchical Message Passing
BibTeX
@misc{liu2026achieving,
title = {{Achieving perfect completeness for one- and two-message quantum proof systems}},
author = {Yupan Liu and Thomas Vidick},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.15926},
eprint = {2609.15926},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15926},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Achieving perfect completeness for one- and two-message quantum proof systems
AU - Yupan Liu
AU - Thomas Vidick
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2609.15926
UR - https://arxiv.org/abs/2609.15926
AB - 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), qq−sf QAM, sf QAM, and sf QMA can achieve perfect completeness. Here qq−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. This also yields an alternative proof of sf QCMA=sf QCMA_1. 2. For sf QIP(2) (and implicitly qq−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.
ER -