QMA has perfect completeness

Abstract

We prove $\mathsf{QMA}=\mathsf{QM}{\mathsf{A}}_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{QM}{\mathsf{A}}_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{QM}{\mathsf{A}}_1$.

13 pages