01021nas a2200169 4500008004100000245009300041210006900134260001500203300001200218490000700230520048600237100002400723700002400747700001800771700002500789856003700814 2012 eng d00aAchieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems0 aAchieving perfect completeness in classicalwitness quantum Merli c2012/05/01 a461-4710 v123 a 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.
1 aJordan, Stephen, P.1 aKobayashi, Hirotada1 aNagaj, Daniel1 aNishimura, Harumichi uhttp://arxiv.org/abs/1111.5306v2