



@article {1398,
	title = {Achieving perfect completeness in classical-witness quantum  Merlin-Arthur proof systems},
	journal = {Quantum Information and Computation},
	volume = {12},
	year = {2012},
	month = {2012/05/01},
	pages = {461-471},
	abstract = {  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.
},
	url = {http://arxiv.org/abs/1111.5306v2},
	author = {Stephen P. Jordan and Hirotada Kobayashi and Daniel Nagaj and Harumichi Nishimura}
}
