%0 Journal Article
%J Quantum Information and Computation
%D 2012
%T Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
%A Stephen P. Jordan
%A Hirotada Kobayashi
%A Daniel Nagaj
%A Harumichi Nishimura
%X 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.
%B Quantum Information and Computation
%V 12
%P 461-471
%8 2012/05/01
%G eng
%U http://arxiv.org/abs/1111.5306v2
%N 5-6
%! Quantum Information and Computation Vol. 12 No. 5/6 pg. 461-471 (2012)