{"id":"arxiv/2609.13032","url":"https://arxiv.org/abs/2609.13032","tags":["quant-ph","cs.CC"],"score":0,"title":"QMA has perfect completeness","domain":"quant-ph","source":"arxiv","authors":["Sabee Grewal","Dorian Rudolph"],"reviews":0,"subject":"quant-ph","summary":"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}$.","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-11","reactions":{}}