How Hamiltonian complexity differs from quantum chemistry
summary
Worst-case ground-energy estimation is QMA-complete, but chemistry-relevant models like the translation-invariant Fermi–Hubbard lattice lack proven worst-case hardness; phase-estimation from a 1/poly-overlap guided state yields the claimed quantum advantage for very high precision, yet stronger notions (entrywise strong guided state) allow classical strategies. Fixed-node and projection Monte Carlo variants convert H to a stochastic matrix and, with classical amplitude access, produce Markov-chain algorithms; the decision problem with a succinct ground state is shown MA-complete, leaving dequantization for general Hamiltonians open.
AI-written summary · about
chapters (5)
- 0:00Introduction to GEE
- 11:33Worst-case hardness
- 25:39Guided states and complexity
- 35:50Classical simulation strategies
- 52:57Heuristics and future directions
related talks
01h 03mGround Energy estimation of Quantum Impurity model is in BQP
45mHamiltonian Complexity in the Thermodynamic Limit
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
44mOptimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
43mStrongly Universal Hamiltonian Simulators
20mMarQSim: Reconciling Determinism and Randomness in Compiler Optimization for Quantum(…)
48mIntroduction To Commuting Local Hamiltonian Problems
48mThe Quantum Games PCP: Results and Confessions