Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems

TitleAchieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
Publication TypeJournal Article
Year of Publication2012
AuthorsJordan, SP, Kobayashi, H, Nagaj, D, Nishimura, H
JournalQuantum Information and Computation
Volume12
Issue5-6
Pages461-471
Date Published2012/05/01
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.
URLhttp://arxiv.org/abs/1111.5306v2
Short TitleQuantum Information and Computation Vol. 12 No. 5/6 pg. 461-471 (2012)