Ground Energy estimation of Quantum Impurity model is in BQP
summary
Shows that ground-energy estimation for quantum impurity Hamiltonians admits a polynomial-time quantum algorithm that outputs the ground energy to inverse-polynomial precision by constructing an explicit guiding state and running QPE, with runtime roughly 2^m · poly(n,1/ε) where m is impurity size (constant for the result). Previous unconditional bounds were quasi-polynomial classical time and QCMA containment; proof uses covariance-matrix SDP, Krylov/kernel-space decompositions, and an AI-found counterexample that shaped the final structural lemma.
AI-written summary · about
chapters (6)
- 0:00Introduction
- 10:21Quantum impurity model
- 22:19Impurity model in BQP
- 32:49Algorithm overview
- 48:18AI-guided state
- 57:01Summary
related talks
01h 06mHow Hamiltonian complexity differs from quantum chemistry
23mThe importance of the spectral gap in estimating ground-state energies
48mThe Quantum Games PCP: Results and Confessions
01h 15mDissipative State Preparation and the Dissipative Quantum Eigensolver
46mLocal Minima in Quantum Systems
30mQuantum Constant Propagation
46mQuantum Learning Algorithms Imply Circuit Lower Bounds
20mUnitary property testing lower bounds by polynomials