Achieving perfect completeness for one- and two-message quantum proof systems
Quantum computers can now verify proofs with perfect accuracy in just one or two messages
Researchers solved a 20-year-old puzzle about quantum proof systems by showing that even single-message and two-message quantum proofs can achieve perfect completeness—meaning a quantum computer can verify correct solutions without ever mistakenly rejecting them. The breakthrough uses new mathematical techniques to construct quantum certifications that work flawlessly, closing gaps that persisted even as three-message systems were cracked decades ago.
This advances our understanding of the limits of quantum computing and verification. Proof systems are fundamental to quantum cryptography and computational theory; knowing exactly what quantum computers can verify with perfect accuracy reshapes what's theoretically possible in quantum information processing and helps engineers design more efficient quantum verification protocols for real systems.