Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura · Quantum Information and Computation · 2012
This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, ${\QCMA = \QCMA_1}$. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, \emph{e.g.}, ${\{\textrm{Hadamard, Toffoli, NOT}\}}$. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that \emph{additively} adjusts the success probability, which may be of independent interest.