Name
Title | ||
|---|---|---|
Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems |
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. |
Year | Venue | Keywords |
|---|---|---|
2012 | Quantum Information & Computation | novel quantum technique,independent interest,classical-witness quantum merlin-arthur proof,arbitrary classical reversible transformation,success probability,quantumly nonrelativizing,proof system,perfect completeness |
Field | DocType | Volume |
Quantum,Discrete mathematics,Witness,Completeness (statistics),Hadamard transform,Mathematics,Toffoli gate | Journal | 12 |
Issue | ISSN | Citations |
5-6 | Quantum Information and Computation Vol. 12 No. 5/6 pg. 461-471
(2012) | 11 |
PageRank | References | Authors |
0.70 | 20 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephen P. Jordan | 1 | 79 | 10.76 |
| Hirotada Kobayashi | 2 | 260 | 19.98 |
| Daniel Nagaj | 3 | 57 | 5.84 |
| harumichi nishimura | 4 | 229 | 23.82 |