Quantum NP - A Survey

Abstract

We describe Kitaev's result from 1999, in which he defines the complexity class QMA, the quantum analog of the class NP, and shows that a natural extension of 3-SAT, namely local Hamiltonians, is QMA complete. The result builds upon the classical Cook-Levin proof of the NP completeness of SAT, but differs from it in several fundamental ways, which we highlight. This result raises a rich array of open problems related to quantum complexity, algorithms and entanglement, which we state at the end of this survey. This survey is the extension of lecture notes taken by Naveh for Aharonov's quantum computation course, held in Tel Aviv University, 2001.

23 pages

Cited by in corpus (51)

• Adiabatic Quantum Computing
• Simulating chemistry using quantum computers
• Quantum Metropolis Sampling
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• Variational quantum eigensolver for the Heisenberg antiferromagnet on the kagome lattice
• Introduction to Quantum Algorithms for Physics and Chemistry
• QMA-complete problems for stoquastic Hamiltonians and Markov matrices
• Merlin-Arthur Games and Stoquastic Complexity
• An Application of Quantum Finite Automata to Interactive Proof Systems
• The Quantum PCP Conjecture
• Categorical Quantum Circuits
• Binary Constraint System Games and Locally Commutative Reductions
• Hardness of approximation for quantum problems
• A quantum primality test with order finding
• Robustness of QMA against witness noise
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Limits on Efficient Computation in the Physical World
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Ground state connectivity of local Hamiltonians
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• 3-Local Hamiltonian is QMA-complete
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Importance of the spectral gap in estimating ground-state energies
• Consistency of Local Density Matrices is QMA-complete
• Commutative version of the k-local Hamiltonian problem and common eigenspace problem
• Improved Soundness for QMA with Multiple Provers
• Hamiltonian sparsification and gap-simulations
• The Local Hamiltonian problem on a line with eight states is QMA-complete
• BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
• Non-Identity Check Remains QMA-Complete for Short Circuits
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• The commuting local Hamiltonian on locally-expanding graphs is in NP
• Turing-equivalent automata using a fixed-size quantum memory
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• On the Complexity of Two Dimensional Commuting Local Hamiltonians
• Constant-Soundness Interactive Proofs for Local Hamiltonians
• Quantum Versus Classical Proofs and Advice
• Oracle complexity classes and local measurements on physical Hamiltonians
• Approximation, Proof Systems, and Correlations in a Quantum World
• One-Sided Error QMA with Shared EPR Pairs -- A Simpler Proof
• Gibbs States and the Consistency of Local Density Matrices
• On Perfect Completeness for QMA
• Quantum State Isomorphism
• A Lattice Problem in Quantum NP
• Quantum Computing, Postselection, and Probabilistic Polynomial-Time
• Two QCMA-complete problems
• Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more
• Adiabatic Quantum Computation