QMA quantum proofs can always be made perfectly complete
QMA has perfect completeness
Computational Complexity
Summary
Some computer problems can be checked using quantum proofs, but these checks sometimes have a small chance of rejecting a correct proof. The authors show that it is possible to design these quantum proof systems so that if the proof is correct, it will always be accepted. They achieve this using a specific set of basic quantum operations. This result also confirms that an important quantum logic problem remains one of the hardest in quantum computation.
What this means in practice
- •For quantum algorithm developers: Create quantum verification protocols where correct proofs are always accepted, improving reliability of quantum proof checking.
- •For quantum complexity analysts: Use the equivalence of QMA and QMA_1 to clarify relationships between complexity classes and oracles relevant for analysis of quantum computations.
A theory result. No direct application yet.
Authors
Sabee Grewal, Dorian Rudolph
Abstract
We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.