Abstract
This article surveys quantum computational complexity, with a focus on three fundamental notions: polynomial-time quantum computations, the efficient verification of quantum proofs, and quantum interactive proof systems. Properties of quantum complexity classes based on these notions, such as BQP, QMA, and QIP, are presented. Other topics in quantum complexity, including quantum advice, space-bounded quantum computation, and bounded-depth quantum circuits, are also discussed.
📄 Full Paper Available as PDF
This paper is available as a downloadable PDF.
📄 Download PDF
Comments (0)
No comments yet. Be the first to comment.
Research
