Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.02167

Polynomial-time classical and quantum simulation of quantum impurity models

Jiaqing Jiang, Nathan Ju, Ojas Parekh, Chaithanya Rayudu, Andrew Zhao

quant-phcond-mat.str-elcs.CCcs.DSphysics.chem-phSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations• Revised Oct 5, 2026 (v2)
v1 · Oct 1, 2026v2 · Oct 5, 2026
arXivHTMLPDF

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.

Comments
73 pages, 1 figure. Updated bibliography and font, fixed typos

Related papers

Quantum impurity models: easy at equilibrium, universal in motion

Srinivasan Arunachalam, Sergey Bravyi, Anirban Chowdhury +3 more

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 $\varepsilon$ by a classical algorithm with runtime $\textsf{poly}(n,1/\varepsilon)$, 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 $\varepsilon$ in time $\textsf{poly}(n,β,1/\varepsilon)$; (3) simulating the time evolution $e^{-iHt}$ is $\textsf{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.

quant-pharXiv:2610.02130•Oct 2, 2026•0 citations

Polynomial-time classical algorithms for mean-field models up to the glass transition

Alexander Schmidhuber, Alexander Zlokapa

The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.

quant-pharXiv:2610.06807•Oct 6, 2026•0 citations

Hybrid quantum-classical algorithm for computing imaginary-time correlation functions

Rihito Sakurai, Wataru Mizukami, Hiroshi Shinaoka

Quantitative descriptions of strongly correlated materials pose a considerable challenge in condensed matter physics and chemistry. A promising approach to address this problem is quantum embedding methods. In particular, the dynamical mean-field theory (DMFT) maps the original system to an effective quantum impurity model comprising correlated orbitals embedded in an electron bath. The biggest bottleneck in DMFT calculations is numerically solving the quantum impurity model, i.e., computing the Green's function. Past studies have proposed theoretical methods to compute the Green's function of a quantum impurity model in polynomial time using a quantum computer. So far, however, efficient methods for computing the imaginary-time Green's functions have not been established despite the advantages of the imaginary-time formulation. We propose a quantum-classical hybrid algorithm for computing imaginary-time Green's functions on quantum devices with limited hardware resources by applying the variational quantum simulation. Using a quantum circuit simulator, we verified this algorithm by computing Green's functions for a dimer model as well as a four-site impurity model obtained by DMFT calculations of the single-band Hubbard model, although our method can be applied to general imaginary-time correlation functions.

arXiv:2112.02764•Physical Review Research•Jun 16, 2022•30 citations

Solving free fermion problems on a quantum computer

Maarten Stroeks, Daan Lenterman, Barbara M. Terhal +1 more

Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly ( N ) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log ( N ) . The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.

arXiv:2409.04550•Physical Review Research•Nov 18, 2025•5 citations

Comparative study on compact quantum circuits of hybrid quantum-classical algorithms for quantum impurity models

Rihito Sakurai, Oliver J. Backhouse, George H. Booth +2 more

Predicting the properties of strongly correlated materials is a significant challenge in condensed matter theory. The widely used dynamical mean-field theory faces difficulty in solving quantum impurity models numerically. Hybrid quantum-classical algorithms such as variational quantum eigensolvers emerge as a potential solution for quantum impurity models. A common challenge in these algorithms is the rapid growth of the number of variational parameters with the number of spin-orbitals in the impurity. In our approach to this problem, we develop compact using a combination of two different strategies. First, we employ a compact physics-inspired , k -unitary cluster Jastrow , developed in the field of quantum chemistry. Second, we eliminate largely redundant variational parameters of physics-inspired associated with bath sites based on physical intuition. This is based on the fact that a quantum impurity model with a star-like geometry has no direct hopping between bath sites. We benchmark the accuracy of these for both ground-state energy and dynamic quantities by solving typical quantum impurity models with and without shot noise. The results suggest that we can maintain the accuracy of ground-state energy while we drop the number of variational parameters associated with bath sites. Furthermore, we demonstrate that a moment expansion, when combined with the proposed , can calculate the imaginary-time Green's functions under the influence of shot noise. This study demonstrates the potential for addressing complex impurity models in large-scale quantum simulations with fewer variational parameters without sacrificing accuracy. Published by the American Physical Society 2024

arXiv:2312.04105•Physical Review Research•May 1, 2024•3 citations

Efficient pseudomode representation and complexity of quantum impurity models

Julian Thoenniss, Ilya Vilkoviskiy, Dmitry A. Abanin

Out-of-equilibrium fermionic quantum impurity models (QIM), describing a small interacting system coupled to a continuous fermionic bath, play an important role in condensed matter physics. Solving such models is a computationally demanding task, and a variety of computational approaches are based on finding approximate representations of the bath by a finite number of modes. In this paper, we formulate the problem of finding efficient bath representations as that of approximating a kernel of the bath's Feynman-Vernon influence functional by a sum of complex exponentials, with each term defining a fermionic pseudomode. Under mild assumptions on the analytic properties of the bath spectral density, we provide an analytic construction of pseudomodes, and prove that their number scales polylogarithmically with the maximum evolution time $T$ and the approximation error $\ensuremath{\varepsilon}$. We then demonstrate that the number of pseudomodes can be significantly reduced by an interpolative matrix decomposition (ID). Furthermore, we present a complementary approach, based on constructing rational approximations of the bath's spectral density using the ``AAA'' algorithm, followed by compression with ID. The combination of two approaches yields a pseudomode count scaling as ${N}_{\text{ID}}\ensuremath{\sim}ln(T)ln(1/\ensuremath{\varepsilon})$, and the agreement between the two approaches suggests that the result is close to optimal. Finally, to relate our findings to QIM, we derive an explicit Liouvillian that describes the time evolution of the combined impurity-pseudomodes system. These results establish bounds on the computational resources required for solving out-of-equilibrium QIMs, providing an efficient starting point for tensor-network methods for QIMs.

arXiv:2409.08816•Physical review. B./Physical review. B•Aug 13, 2025•5 citations
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)\mathrm{poly}(n,δ^{-1})poly(n,δ−1), and (2) estimate the partition function at inverse temperature βββ to relative precision δδδ in time poly(n,β,δ−1)\mathrm{poly}(n,β,δ^{-1})poly(n,β,δ−1), where nnn 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.
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 HHH be the Hamiltonian of an impurity model with nnn fermionic modes and a constant-size impurity. We show that: (1) the ground energy of HHH can be approximated to additive error ε\varepsilonε by a classical algorithm with runtime poly(n,1/ε)\textsf{poly}(n,1/\varepsilon)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 ε\varepsilonε in time poly(n,β,1/ε)\textsf{poly}(n,β,1/\varepsilon)poly(n,β,1/ε); (3) simulating the time evolution e−iHte^{-iHt}e−iHt is BQP\textsf{BQP}BQP-complete, for HHH 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.
The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.
Quantitative descriptions of strongly correlated materials pose a considerable challenge in condensed matter physics and chemistry. A promising approach to address this problem is quantum embedding methods. In particular, the dynamical mean-field theory (DMFT) maps the original system to an effective quantum impurity model comprising correlated orbitals embedded in an electron bath. The biggest bottleneck in DMFT calculations is numerically solving the quantum impurity model, i.e., computing the Green's function. Past studies have proposed theoretical methods to compute the Green's function of a quantum impurity model in polynomial time using a quantum computer. So far, however, efficient methods for computing the imaginary-time Green's functions have not been established despite the advantages of the imaginary-time formulation. We propose a quantum-classical hybrid algorithm for computing imaginary-time Green's functions on quantum devices with limited hardware resources by applying the variational quantum simulation. Using a quantum circuit simulator, we verified this algorithm by computing Green's functions for a dimer model as well as a four-site impurity model obtained by DMFT calculations of the single-band Hubbard model, although our method can be applied to general imaginary-time correlation functions.
Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly ( N ) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log ( N ) . The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.
Predicting the properties of strongly correlated materials is a significant challenge in condensed matter theory. The widely used dynamical mean-field theory faces difficulty in solving quantum impurity models numerically. Hybrid quantum-classical algorithms such as variational quantum eigensolvers emerge as a potential solution for quantum impurity models. A common challenge in these algorithms is the rapid growth of the number of variational parameters with the number of spin-orbitals in the impurity. In our approach to this problem, we develop compact using a combination of two different strategies. First, we employ a compact physics-inspired , k -unitary cluster Jastrow , developed in the field of quantum chemistry. Second, we eliminate largely redundant variational parameters of physics-inspired associated with bath sites based on physical intuition. This is based on the fact that a quantum impurity model with a star-like geometry has no direct hopping between bath sites. We benchmark the accuracy of these for both ground-state energy and dynamic quantities by solving typical quantum impurity models with and without shot noise. The results suggest that we can maintain the accuracy of ground-state energy while we drop the number of variational parameters associated with bath sites. Furthermore, we demonstrate that a moment expansion, when combined with the proposed , can calculate the imaginary-time Green's functions under the influence of shot noise. This study demonstrates the potential for addressing complex impurity models in large-scale quantum simulations with fewer variational parameters without sacrificing accuracy. Published by the American Physical Society 2024
Out-of-equilibrium fermionic quantum impurity models (QIM), describing a small interacting system coupled to a continuous fermionic bath, play an important role in condensed matter physics. Solving such models is a computationally demanding task, and a variety of computational approaches are based on finding approximate representations of the bath by a finite number of modes. In this paper, we formulate the problem of finding efficient bath representations as that of approximating a kernel of the bath's Feynman-Vernon influence functional by a sum of complex exponentials, with each term defining a fermionic pseudomode. Under mild assumptions on the analytic properties of the bath spectral density, we provide an analytic construction of pseudomodes, and prove that their number scales polylogarithmically with the maximum evolution time TTT and the approximation error $\ensuremath{\varepsilon}$. We then demonstrate that the number of pseudomodes can be significantly reduced by an interpolative matrix decomposition (ID). Furthermore, we present a complementary approach, based on constructing rational approximations of the bath's spectral density using the ``AAA'' algorithm, followed by compression with ID. The combination of two approaches yields a pseudomode count scaling as ${N}_{\text{ID}}\ensuremath{\sim}ln(T)ln(1/\ensuremath{\varepsilon})$, and the agreement between the two approaches suggests that the result is close to optimal. Finally, to relate our findings to QIM, we derive an explicit Liouvillian that describes the time evolution of the combined impurity-pseudomodes system. These results establish bounds on the computational resources required for solving out-of-equilibrium QIMs, providing an efficient starting point for tensor-network methods for QIMs.