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

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

2011-11-22

arxiv.org/abs/1111.5306v2

Quantum Information and Computation Vol. 12 No. 5/6 pg. 461-471 (2012)

Physics

Quantum Physics

10 pages. Added two more authors and a new proof technique, which requires only a fixed finite gate set

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375390