pith. machine review for the scientific record. sign in

arxiv: 0804.3401 · v1 · submitted 2008-04-21 · 🪐 quant-ph

Recognition: unknown

Quantum Computational Complexity

John Watrous
Authors on Pith no claims yet
classification 🪐 quant-ph
keywords quantumcomplexitycomputationalnotionsadvicearticlebounded-depthcircuits
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Hierarchical entanglement transitions and hidden area-law sectors in quantum many-body dynamics

    quant-ph 2026-05 unverdicted novelty 7.0

    Local quenches in chaotic quantum systems produce a Renyi-index-tuned hierarchy of entanglement transitions, with S_alpha>1 obeying area law while S_alpha<=1 is volume-law, carried by an O(1)-dimensional dominant Schm...