arXiv:2610.02167
Polynomial-time classical and quantum simulation of quantum impurity models
Jiaqing Jiang, Nathan Ju, Ojas Parekh, Chaithanya Rayudu, Andrew Zhao
Abstract
Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision $δ$ in time $\mathrm{poly}(n,δ^{-1})$, and (2) estimate the partition function at inverse temperature $β$ to relative precision $δ$ in time $\mathrm{poly}(n,β,δ^{-1})$, where $n$ is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.
AI Summary
The paper asks which simulation tasks for quantum impurity models are classically tractable when an arbitrarily interacting, constant-size impurity is coupled to a noninteracting fermionic bath. It assumes polynomially bounded Hamiltonian norm, but imposes no geometry or spectral-gap assumptions. It gives a classical algorithm estimating ground-state energy to additive error $\delta$ in $\mathrm{poly}(n,\delta^{-1})$ time, improving the previous quasipolynomial guarantee. Randomized classical algorithms estimate the partition function to relative error $\delta$ and bounded Hermitian Gaussian thermal observables to additive error $\delta$ in $\mathrm{poly}(n,\beta,\delta^{-1})$ time. A quantum algorithm also prepares Gibbs states with polynomial dependence on inverse temperature and inverse trace-distance error. The central construction partitions bath energies into logarithmic bands and builds a Krylov basis within each band. Weighted joint-occupation bounds identify efficiently enumerable, polynomial-dimensional subspaces supporting ground states and thermally gapped sectors. For general thermal states, a soft–hard decomposition leaves a compressed interacting sector, a free sector, and a perturbation satisfying $\beta\|V\|=O(\log n)$. This controls the exponential cost of continuous-time Monte Carlo and quantum belief propagation. For bounded, time-dependent impurity Hamiltonians and polynomial evolution times, estimating nonequilibrium Majorana two-point functions is $\mathrm{DQC}_1$-complete at infinite temperature and $\mathrm{BQP}$-complete for $\Omega(1)\leq\beta\leq\mathrm{poly}(n)$. Hardness uses a universal encoding with one extra fermionic mode and, at finite temperature, algorithmic cooling. These results concern driven dynamics, not general time-independent models. Runtime dependence on impurity size is exponential; practical efficiency, excited-state extensions, and possible polynomial quantum speedups remain unresolved.
After several initially unsuccessful approaches with GPT 5.6 Sol Ultra, it eventually proposed, based on the Krylov-basis idea, a candidate proof of an efficient classical algorithm for the ground-state energy.
Error found: The abstract’s polynomial runtime claims require the body’s assumptions of constant impurity size and polynomially bounded Hamiltonian norm. The abstract does not disclose that its dynamical hardness results concern time-dependent impurity Hamiltonians, rather than establishing hardness for time-independent evolution. The blanket exclusion of superpolynomial quantum speedups for static properties exceeds the proved tasks, which do not include arbitrary ground-state observables.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 73 pages, 1 figure. Updated bibliography and font, fixed typos