Quantum Computational Complexity
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.
Forward citations
Cited by 3 Pith papers
-
The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
The Guided Local Hamiltonian problem for stoquastic Hamiltonians is promise BPP-hard (even 2-local on lattices), BQP-hard under fixed local constraints, and admits a deterministic classical approximation algorithm whe...
-
Hierarchical entanglement transitions and hidden area-law sectors in quantum many-body dynamics
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...
-
On the Complexity of the Succinct State Local Hamiltonian Problem
The succinct state 2-local Hamiltonian problem for qubit Hamiltonians is promise-MA-complete.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.