Quantum NP and Beyond
summary
Defines QMA as NP with a quantum witness and highlights the 5-local Hamiltonian result showing local Hamiltonian is QMA-complete, an eigenvalue decision problem with a 1/poly promise gap. Shows hardness persists under physically constrained layouts: reductions to nearest-neighbor 2D, gadgetized qubit 2D, and even engineered 1D chains; translationally invariant encodings push complexity to exponentially succinct inputs. Describes a quantum Metropolis implementation that makes rejection reversible and converges to the Gibbs state, but no general polynomial mixing bounds are known.
AI-written summary · about
chapters (7)
- 0:00Intro
- 3:12Local Hamiltonian Problem
- 5:38Constraint Satisfaction Problem
- 10:42A key problen in searching for spin liquids in 2D models is that there are no exact or nearly exact analytical or computational methods to solve infinite 2D quantum lattice systems.
- 12:29Clock State of the Quantum
- 19:32Quantum Simulation
- 21:30Quantum Metropolis Sampling
related talks
47mOracle Separations Between QMA and QCMA
22mQuantum space, ground space traversal, and how to embed multi-prover...
01h 20mVerifiable Quantum Supremacy: What I Hope Will Be Done
41mQuantum Computing deep dive
57mA Simple Quantum Sketch With Applications to Graph Algorithms
49mQuantum Cryptanalysis
41mState of Quantum Computing in programming
59mDiving Into Q#