Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems (pp0461-0471)
          Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura
          doi: https://doi.org/10.26421/QIC12.5-6-7
Abstracts: This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, QCMA = QCMA1 . This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, e.g., {Hadamard, Toffoli, NOT}. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that additively adjusts the success probability, which may be of independent interest.
Key words: quantum Merlin-Arthur proof systems, perfect completeness