The 7 faces of quantum NP
arXiv:2310.18010 · doi:10.1145/3639528.3639535
Abstract
When it comes to NP, its natural definition, its wide applicability across scientific disciplines, and its timeless relevance, the writing is on the wall: There can be only one. Quantum NP, on the other hand, is clearly the apple that fell far from the tree of NP. Two decades since the first definitions of quantum NP started rolling in, quantum complexity theorists face a stark reality: There's QMA, QCMA, QMA1, QMA(2), StoqMA, and NQP. In this article aimed at a general theoretical computer science audience, I survey these various definitions of quantum NP, their strengths and weaknesses, and why most of them, for better or worse, actually appear to fit naturally into the complexity zoo.
arXiv comment37 pages, 5 figures. To appear as ACM SIGACT News guest column
References in corpus (44)
- Quantum algorithm for solving linear systems of equations
- Variational Quantum Algorithms
- Improved Simulation of Stabilizer Circuits
- Quantum Amplitude Amplification and Estimation
- Quantum fingerprinting
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Exponential algorithmic speedup by quantum walk
- Schrieffer-Wolff transformation for quantum many-body systems
- Quantum measurements and the Abelian Stabilizer Problem
- Universal Quantum Estimator
- Direct estimations of linear and non-linear functionals of a quantum state
- Training variational quantum algorithms is NP-hard
- Improved classical simulation of quantum circuits dominated by Clifford gates
- A quantum-inspired classical algorithm for recommendation systems
- A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Universal Quantum Hamiltonians
- On the Computational Complexity of Curing the Sign Problem
- NLTS Hamiltonians from good quantum codes
- On product, generic and random generic quantum satisfiability
- Testing product states, quantum Merlin-Arthur games and tensor optimisation
- The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
- Hardness of approximation for quantum problems
- The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
- Ground state connectivity of local Hamiltonians
- Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements
- Analysis and limitations of modified circuit-to-Hamiltonian constructions
- Complete Characterization of the Ground Space Structure of Two-Body Frustration-Free Hamiltonians for Qubits
- Improved Soundness for QMA with Multiple Provers
- Complexity of Supersymmetric Systems and the Cohomology Problem
- 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
- The complexity of simulating local measurements on quantum systems
- Quantum 3-SAT is QMA1-complete
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- The Complexity of the Separable Hamiltonian Problem
- QCMA hardness of ground space connectivity for commuting Hamiltonians
- A Computational Separation Between Quantum No-cloning and No-telegraphing
- The Complexity of Translationally Invariant Problems beyond Ground State Energies
- An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms
- On the Complexity of Two Dimensional Commuting Local Hamiltonians
- Commuting Local Hamiltonian Problem on 2D beyond qubits
- Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
- Local Hamiltonians with no low-energy stabilizer states