SCIENCE@home

Quantum versus Classical Proofs and Advice

S. Aaronson,G. Kuperberg

Published 2006 in Cybersecurity and Cyberforensics Conference

ABSTRACT

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCM A. More concretely, we show that any quantum algorithm needs Omega (radic2n-m+1) queries to find an n-qubit "marked state" \Psi rang, even if given an m-bit classical description of \Psi rang together with a quantum black box that recognizes \Psi rang. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Wa- trous gave a QM IK protocol for verifying non-membership infinite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only poly-nomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-37 of 37 references · Page 1 of 1

CITED BY

Showing 1-100 of 114 citing papers · Page 1 of 2

12
Next