arXiv · Oct 1, 2026
Quantum impurity models: easy at equilibrium, universal in motion
By Srinivasan Arunachalam, Sergey Bravyi, Anirban Chowdhury et al.
A quantum impurity model describes a small interacting subsystem embedded into a large bath of free fermions. Here we study the computational complexity of calculating the ground energy, thermal equilibrium, and dynamical properties of these models. Our work reveals a sharp contrast: equilibrium properties can be efficiently approximated by classical means, whereas time evolution can implement a universal quantum computation. More precisely, let H be the Hamiltonian of an impurity model with n fermionic modes and a constant-size impurity. We show that: (1) the ground energy of H can be approximated to additive error ε by a classical algorithm with runtime poly(n,1/ε), improving on the quasi-polynomial runtime of the best previously known algorithm; (2) at inverse temperature β, the Helmholtz free energy and a classical description of the thermofield double state can be computed to precision ε in time poly(n,β,1/ε); (3) simulating the time evolution e^(-iHt) is BQP-complete, for H that is time-independent and has a fixed, constant impurity size. Our algorithms exploit exponential suppression of multi-particle bath excitations in a basis organized by energy scale and Krylov depth. Our universality construction realizes a stationary quantum processor whose program arrives in a stream of freely propagating fermions.