aiqbench analysis
This research delineates the computational boundary for quantum impurity models, proving that static properties like ground-state energy are efficiently solvable classically while dynamic processes retain full quantum advantage. The study significantly improves classical complexity bounds for thermal equilibrium simulations and establishes rigorous polynomial-time guarantees for this specific class of interacting fermion systems. These findings clarify where quantum computers offer genuine speedups over classical algorithms in simulating strongly correlated electron matter.
Polynomial-time classical and quantum simulation of quantum impurity models
arXiv:2610.02167v1 Announce Type: new 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 $\delta$ in time $\mathrm{poly}(n,\delta^{-1})$, and (2) estimate the partition function at inverse temperature $\beta$ to relative precision $\delta$ in time $\mathrm{poly}(n,\beta,\delta^{-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.
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 $\delta$ in time $\mathrm{poly}(n,\delta^{-1})$, and (2) estimate the partition function at inverse temperature $\beta$ to relative precision $\delta$ in time $\mathrm{poly}(n,\beta,\delta^{-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.
Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Chemical Physics (physics.chem-ph)
arXiv:2610.02167 [quant-ph]
(or arXiv:2610.02167v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2610.02167 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 259 words
Related coverage
Researchers Classically Compute Ground Energy with Polynomial Scaling
Quantum Zeitgeist · Oct 2, 2026
Quantum impurity models: easy at equilibrium, universal in motion
arXiv · Oct 2, 2026
On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
Quantum Journal · Aug 3, 2026
Quantum Simulation of Nuclear Dynamics in First Quantization
Quantum Journal · Sep 2, 2026