TY - JOUR
T1 - Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
JF - Quantum Information and Computation
Y1 - 2012
A1 - Stephen P. Jordan
A1 - Hirotada Kobayashi
A1 - Daniel Nagaj
A1 - Harumichi Nishimura
AB - 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.
VL - 12
U4 - 461-471
UR - http://arxiv.org/abs/1111.5306v2
CP - 5-6
J1 - Quantum Information and Computation Vol. 12 No. 5/6 pg. 461-471 (2012)
ER -