Introduction To Commuting Local Hamiltonian Problems
summary
Claims that commuting local Hamiltonian instances sit between classical and full quantum complexity and gives concrete results: structure lemma proves all 2-local (and many 3-local) commuting Hamiltonians have constant-depth trivial ground states, so the decision problem lies in NP; a separate trace-of-product reduction shows qubit 2D plaquette instances are in NP by expanding Tr(Pgray Pwhite) into nonnegative summands and using an index as an NP witness; recent work extends NP membership to qutrits via a self-reduction to lower local dimension and shows factorized cases reduce to stabilizer form.
AI-written summary · about
chapters (9)
- 0:00Introduction to commuting
- 3:38Defining the problem
- 5:58Complexity and entanglement
- 10:28Motivation for the study
- 12:28Summary of current results
- 16:45Structural lemma technique
- 23:51Limitations of the lemma
- 30:21Norbert's proof technique
- 37:46New techniques and outlook
related talks
50mMaking the Leap to Quantum PCPs
58mLimitations for Quantum PCPs
12mShort Proof of a Spectral Chernoff Bound for Local Hamiltonians
01h 09mGap Amplification for Local Hamiltonians with Combinatorial Soundness
01h 06mHow Hamiltonian complexity differs from quantum chemistry
43mStrongly Universal Hamiltonian Simulators
45mHamiltonian Complexity in the Thermodynamic Limit
01h 10mQuantum Advantage with Shallow Clifford Circuits