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.
37 pages, 5 figures. To appear as ACM SIGACT News guest column
References in corpus (15)
- Quantum algorithm for solving linear systems of equations
- Variational Quantum Algorithms
- Exponential algorithmic speedup by quantum walk
- Training variational quantum algorithms is NP-hard
- A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
- NLTS Hamiltonians from good quantum codes
- Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements
- Complexity of Supersymmetric Systems and the Cohomology Problem
- BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
- An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms
- A Computational Separation Between Quantum No-cloning and No-telegraphing
- The Complexity of Translationally Invariant Problems beyond Ground State Energies
- 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