Quantum Computational Complexity

Simple item page
dc.creatorWatrous, John
dc.date2008-04-21
dc.date.accessioned2026-07-07T09:33:57Z
dc.date.available2026-07-07T09:33:57Z
dc.descriptionThis 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.
dc.description44 pages, 14 figures. To appear in the Springer Encyclopedia of Complexity and Systems Science
dc.identifierhttps://arxiv.org/abs/0804.3401
dc.identifierhttp://arxiv.org/abs/0804.3401
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/159313
dc.subjectQuantum Physics
dc.titleQuantum Computational Complexity
dc.typetext

Files

Collections

arXiv