Quantum impurity models can be efficiently simulated classically and quantumly
Polynomial-time classical and quantum simulation of quantum impurity models
Computational ComplexityData Structures and Algorithms
Summary
Quantum impurity models describe a small interacting system linked to a large environment. The authors show that key static properties of these models, like energy, can be calculated efficiently using regular computers. However, calculating how these systems change over time requires a quantum computer and cannot be done quickly on classical ones. This work clarifies what parts of simulating these models are easy or hard for classical and quantum computers.
What this means in practice
- •For electronic structure teams: Calculate equilibrium properties of quantum impurity models efficiently on classical computers to improve materials simulations.
- •For quantum computing engineers: Use quantum computers to simulate time-dependent behavior of impurity models that classical computers find intractable.
Authors
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.