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• 2 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.

AI Summary

The paper asks which simulation tasks for quantum impurity models are classically tractable when an arbitrarily interacting, constant-size impurity is coupled to a noninteracting fermionic bath. It assumes polynomially bounded Hamiltonian norm, but imposes no geometry or spectral-gap assumptions. It gives a classical algorithm estimating ground-state energy to additive error $\delta$ in $\mathrm{poly}(n,\delta^{-1})$ time, improving the previous quasipolynomial guarantee. Randomized classical algorithms estimate the partition function to relative error $\delta$ and bounded Hermitian Gaussian thermal observables to additive error $\delta$ in $\mathrm{poly}(n,\beta,\delta^{-1})$ time. A quantum algorithm also prepares Gibbs states with polynomial dependence on inverse temperature and inverse trace-distance error. The central construction partitions bath energies into logarithmic bands and builds a Krylov basis within each band. Weighted joint-occupation bounds identify efficiently enumerable, polynomial-dimensional subspaces supporting ground states and thermally gapped sectors. For general thermal states, a soft–hard decomposition leaves a compressed interacting sector, a free sector, and a perturbation satisfying $\beta\|V\|=O(\log n)$. This controls the exponential cost of continuous-time Monte Carlo and quantum belief propagation. For bounded, time-dependent impurity Hamiltonians and polynomial evolution times, estimating nonequilibrium Majorana two-point functions is $\mathrm{DQC}_1$-complete at infinite temperature and $\mathrm{BQP}$-complete for $\Omega(1)\leq\beta\leq\mathrm{poly}(n)$. Hardness uses a universal encoding with one extra fermionic mode and, at finite temperature, algorithmic cooling. These results concern driven dynamics, not general time-independent models. Runtime dependence on impurity size is exponential; practical efficiency, excited-state extensions, and possible polynomial quantum speedups remain unresolved.

No sign of AI-generated textAI use disclosed
After several initially unsuccessful approaches with GPT 5.6 Sol Ultra, it eventually proposed, based on the Krylov-basis idea, a candidate proof of an efficient classical algorithm for the ground-state energy.

Error found: The abstract’s polynomial runtime claims require the body’s assumptions of constant impurity size and polynomially bounded Hamiltonian norm. The abstract does not disclose that its dynamical hardness results concern time-dependent impurity Hamiltonians, rather than establishing hardness for time-independent evolution. The blanket exclusion of superpolynomial quantum speedups for static properties exceeds the proved tasks, which do not include arbitrary ground-state observables.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

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•3 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•4 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•33 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•15 citations

The complexity of simulating quantum physics: dynamics and equilibrium

Abhinav Deshpande

Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind. We apply tools from computer science and mathematical physics to study the complexity of simulating quantum systems. In general, our goal is to identify parameter regimes under which simulating quantum systems is easy (efficiently solvable) or hard (not efficiently solvable). This study leads to an understanding of the features that make certain problems easy or hard to solve. We also get physical insight into the behavior of the system being simulated. In the first part of this dissertation, we study the classical complexity of simulating quantum dynamics. In general, the systems we study transition from being easy to simulate at short times to being harder to simulate at later times. We argue that the transition timescale is a useful measure for various Hamiltonians and is indicative of the physics behind the change in complexity. We illustrate this idea for a specific bosonic system, obtaining a complexity phase diagram that delineates the system into easy or hard for simulation. We also prove that the phase diagram is robust, supporting our statement that the phase diagram is indicative of the underlying physics. In the next part, we study open quantum systems from the point of view of their potential to encode hard computational problems. We study a class of fermionic Hamiltonians subject to Markovian noise described by Lindblad jump operators and illustrate how, sometimes, certain Lindblad operators can induce computational complexity into the problem. Specifically, we show that these operators can implement entangling gates, which can be used for universal quantum computation. We also study a system of bosons with Gaussian initial states subject to photon loss and detected using photon-number-resolving measurements. We show that such systems can remain hard to simulate exactly and retain a relic of the "quantumness" present in the lossless system. Finally, in the last part of this dissertation, we study the complexity of simulating a class of equilibrium states, namely ground states. We give complexity-theoretic evidence to identify two structural properties that can make ground states easier to simulate. These are the existence of a spectral gap and the existence of a classical description of the ground state. Our findings complement and guide efforts in the search for efficient algorithms.

•Jan 1, 2021•0 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•4 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.
The paper asks which simulation tasks for quantum impurity models are classically tractable when an arbitrarily interacting, constant-size impurity is coupled to a noninteracting fermionic bath. It assumes polynomially bounded Hamiltonian norm, but imposes no geometry or spectral-gap assumptions.
It gives a classical algorithm estimating ground-state energy to additive error δ\deltaδ in poly(n,δ−1)\mathrm{poly}(n,\delta^{-1})poly(n,δ−1) time, improving the previous quasipolynomial guarantee. Randomized classical algorithms estimate the partition function to relative error δ\deltaδ and bounded Hermitian Gaussian thermal observables to additive error δ\deltaδ in poly(n,β,δ−1)\mathrm{poly}(n,\beta,\delta^{-1})poly(n,β,δ−1) time. A quantum algorithm also prepares Gibbs states with polynomial dependence on inverse temperature and inverse trace-distance error.
The central construction partitions bath energies into logarithmic bands and builds a Krylov basis within each band. Weighted joint-occupation bounds identify efficiently enumerable, polynomial-dimensional subspaces supporting ground states and thermally gapped sectors. For general thermal states, a soft–hard decomposition leaves a compressed interacting sector, a free sector, and a perturbation satisfying β∥V∥=O(log⁡n)\beta\|V\|=O(\log n)β∥V∥=O(logn). This controls the exponential cost of continuous-time Monte Carlo and quantum belief propagation.
For bounded, time-dependent impurity Hamiltonians and polynomial evolution times, estimating nonequilibrium Majorana two-point functions is DQC1\mathrm{DQC}_1DQC1​-complete at infinite temperature and BQP\mathrm{BQP}BQP-complete for Ω(1)≤β≤poly(n)\Omega(1)\leq\beta\leq\mathrm{poly}(n)Ω(1)≤β≤poly(n). Hardness uses a universal encoding with one extra fermionic mode and, at finite temperature, algorithmic cooling. These results concern driven dynamics, not general time-independent models. Runtime dependence on impurity size is exponential; practical efficiency, excited-state extensions, and possible polynomial quantum speedups remain unresolved.
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.
Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind. We apply tools from computer science and mathematical physics to study the complexity of simulating quantum systems. In general, our goal is to identify parameter regimes under which simulating quantum systems is easy (efficiently solvable) or hard (not efficiently solvable). This study leads to an understanding of the features that make certain problems easy or hard to solve. We also get physical insight into the behavior of the system being simulated. In the first part of this dissertation, we study the classical complexity of simulating quantum dynamics. In general, the systems we study transition from being easy to simulate at short times to being harder to simulate at later times. We argue that the transition timescale is a useful measure for various Hamiltonians and is indicative of the physics behind the change in complexity. We illustrate this idea for a specific bosonic system, obtaining a complexity phase diagram that delineates the system into easy or hard for simulation. We also prove that the phase diagram is robust, supporting our statement that the phase diagram is indicative of the underlying physics. In the next part, we study open quantum systems from the point of view of their potential to encode hard computational problems. We study a class of fermionic Hamiltonians subject to Markovian noise described by Lindblad jump operators and illustrate how, sometimes, certain Lindblad operators can induce computational complexity into the problem. Specifically, we show that these operators can implement entangling gates, which can be used for universal quantum computation. We also study a system of bosons with Gaussian initial states subject to photon loss and detected using photon-number-resolving measurements. We show that such systems can remain hard to simulate exactly and retain a relic of the "quantumness" present in the lossless system. Finally, in the last part of this dissertation, we study the complexity of simulating a class of equilibrium states, namely ground states. We give complexity-theoretic evidence to identify two structural properties that can make ground states easier to simulate. These are the existence of a spectral gap and the existence of a classical description of the ground state. Our findings complement and guide efforts in the search for efficient algorithms.
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