Polynomial-time classical and quantum simulation of quantum impurity models
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 poly(n,δ−1), and (2) estimate the partition function at inverse temperature β to relative precision δ in time 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.
Related
- Reinforcement Learning Assisted Quantum Simulation of Many-Body Excited States and Real-Time Dynamics
- Real-time simulation of charge migration within the time-dependent Kohn-Sham DFT
- GPU implementation of mixed quantum-classical Liouville molecular dynamics without momentum jump
- Mixed quantum-classical evolution in open molecular systems
- Grow, Compress, and Perturb: A Hybrid Quantum-Classical Pathway to Scalable Quantum Chemistry on Quantum Computers
BibTeX
@misc{jiang2026polynomialtime,
title = {{Polynomial-time classical and quantum simulation of quantum impurity models}},
author = {Jiaqing Jiang and Nathan Ju and Ojas Parekh and Chaithanya Rayudu and Andrew Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02167},
eprint = {2610.02167},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02167},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polynomial-time classical and quantum simulation of quantum impurity models
AU - Jiaqing Jiang
AU - Nathan Ju
AU - Ojas Parekh
AU - Chaithanya Rayudu
AU - Andrew Zhao
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.02167
UR - https://arxiv.org/abs/2610.02167
AB - 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 poly(n,δ^−1), and (2) estimate the partition function at inverse temperature β to relative precision δ in time 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.
ER -