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.02130

Quantum impurity models: easy at equilibrium, universal in motion

Srinivasan Arunachalam, Sergey Bravyi, Anirban Chowdhury, Arkopal Dutt, Alexandru Gheorghiu, Zhi Li

quant-phSubmitted Oct 1, 2026• Announced Oct 2, 2026• 3 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks whether a constant-size interacting fermionic impurity coupled to a free bath admits efficient classical equilibrium algorithms, and whether its time-independent dynamics can nevertheless realize universal quantum computation. It answers both questions affirmatively for general quadratic baths, including pairing terms, and parity-preserving impurity interactions. For $n$ modes and impurity size $m$ counted in Majorana modes, the global ground energy is approximated to additive error $\varepsilon$ in time $\operatorname{poly}(n,1+\|V\|)\exp[O(m\log(m/\varepsilon))]$, replacing the previous quasi-polynomial accuracy dependence. The algorithm also returns a variational state as a short Gaussian superposition. At inverse temperature $\beta$, an interaction-independent Gaussian spanning set of size $(2+\beta)^{O(m)}/\delta$ approximates the thermofield double to norm error $O(\delta)$. With $\|V\|\le1$, its coefficients and the Helmholtz free energy are classically computable in time polynomial in $n,\beta$ and inverse accuracy for fixed $m$. The equilibrium proofs organize bath modes into energy shells and Krylov layers, establish product bounds suppressing simultaneous bath excitations, and truncate configurations by weighted occupation. Thermal-state reconstruction uses a global least-squares fit to imaginary-time evolution to control error amplification. For dynamics, a fixed number-conserving quartic interaction on 24 fermionic modes implements circuits through sequential scattering of program and data wave packets. A Slater-determinant input and $n,T=O((k+g)^4)$ reproduce a $k$-qubit, $g$-gate circuit’s output probability within $1/12$, yielding BQP-completeness. This is worst-case dynamical hardness, not specifically hardness of equilibrium response functions. Efficiency requires fixed impurity size; constructive thermal results assume bounded interaction strength.

Little sign of AI-generated textAI use disclosed
The key ideas and technical work behind the main classical algorithms, as well as the BQP-hardness result, were generated by GPT-5.6 Sol and Astra.

Central claim may not hold: The abstract omits the interaction-strength dependence in the ground-energy runtime, whereas the theorem establishes polynomial time in n and 1/ε for constant impurity size only with an additional polynomial bound on ||V||. The abstract omits the bounded-interaction assumption used to compute the TFD coefficients and free energy, and rescaling stronger interactions introduces additional runtime dependence on their strength.

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

Comments
81 pages, 2 figures

Related papers

Polynomial-time classical and quantum simulation of quantum impurity models

Jiaqing Jiang, Nathan Ju, Ojas Parekh +2 more

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.

quant-pharXiv:2610.02167•Oct 2, 2026•2 citations

Time evolution of impurity models and their universality for quantum computation

N. C. Mai Pham, Raul A. Santos

Impurity Hamiltonians are systems of $N$ fermionic modes where $O(1)$ of them interact among themselves via quartic (or higher order) fermion terms, while coupling quadratically with $O(N)$ bath modes. Without the quartic interactions, these systems are classically simulable with $O(N^3)$ resources. It was proved that the time-dependent evolution of these systems can perform universal quantum computation. The question of whether or not this remains true for time-independent evolution remains open. Here, we prove that the time evolution of generic time-independent impurity Hamiltonians on $O(N)$ qubits is universal on $N$ qubits if the input state is a product state of fermions in any single particle basis. In our proof we find that for a computation of depth $S$, the size of the impurity scales as $O(S\log S)$.

quant-pharXiv:2604.08466•Apr 10, 2026•1 citation

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•21 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

Variational principle for quantum impurity systems in and out of equilibrium: Application to Kondo problems

Yuto Ashida, Tao Shi, Mari Carmen Bañuls +2 more

We provide a detailed formulation of the recently proposed variational approach [Y. Ashida, T. Shi, M.-C. Ba\~nuls, J. I. Cirac, and E. Demler, Phys. Rev. Lett. 121, 026805 (2018)] to study ground-state properties and out-of-equilibrium dynamics for generic quantum spin-impurity systems. Motivated by the original ideas of Tomonaga, Lee, Low, and Pines, we construct a canonical transformation that completely decouples the impurity from the bath degrees of freedom. By combining this transformation with a Gaussian ansatz for the fermionic bath, we obtain a family of variational many-body states that can efficiently encode the strong entanglement between the impurity and fermions of the bath. We give a detailed derivation of equations of motions in the imaginary- and real-time evolutions on the variational manifold. We benchmark our approach by applying it to investigate ground-state and dynamical properties of the anisotropic Kondo model and compare results with those obtained using the matrix-product state (MPS) ansatz. We show that our approach can achieve an accuracy comparable to MPS-based methods with several orders of magnitude fewer variational parameters than the corresponding MPS ansatz. Comparisons to the Yosida ansatz and the exact solution from the Bethe ansatz are also discussed. We use our approach to investigate the two-lead Kondo model and analyze its long-time spatiotemporal behavior and the conductance behavior at finite bias and magnetic fields. The obtained results are consistent with the previous findings in the Anderson model and the exact solutions at the Toulouse point.

arXiv:1802.03861•Physical review. B./Physical review. B•Jul 11, 2018•36 citations

Quantum Monte Carlo algorithm for out-of-equilibrium Green's functions at long times

Corentin Bertrand, Olivier Parcollet, Antoine Maillard +1 more

We present a quantum Monte Carlo algorithm for computing the perturbative expansion in power of the coupling constant $U$ of the out-of-equilibrium Green's functions of interacting Hamiltonians of fermions. The algorithm extends the one presented in Profumo et al. [Phys. Rev. B 91, 245154 (2015)], and inherits its main property: it can reach the infinite time (steady state) limit since the computational cost to compute order ${U}^{n}$ is uniform versus time; the computing time increases as ${2}^{n}$. The algorithm is based on the Schwinger-Keldysh formalism and can be used for both equilibrium and out-of-equilibrium calculations. It is stable at both small and long real times including in the stationary regime, because of its automatic cancellation of the disconnected Feynman diagrams. We apply this technique to the Anderson quantum impurity model in the quantum dot geometry to obtain the Green's function and self-energy expansion up to order ${U}^{10}$ at very low temperature. We benchmark our results at weak and intermediate coupling with high precision numerical renormalization-group computations as well as analytical results.

arXiv:1903.11636•Physical review. B./Physical review. B•Sep 12, 2019•53 citations
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 paper asks whether a constant-size interacting fermionic impurity coupled to a free bath admits efficient classical equilibrium algorithms, and whether its time-independent dynamics can nevertheless realize universal quantum computation. It answers both questions affirmatively for general quadratic baths, including pairing terms, and parity-preserving impurity interactions.
For nnn modes and impurity size mmm counted in Majorana modes, the global ground energy is approximated to additive error ε\varepsilonε in time poly⁡(n,1+∥V∥)exp⁡[O(mlog⁡(m/ε))]\operatorname{poly}(n,1+\|V\|)\exp[O(m\log(m/\varepsilon))]poly(n,1+∥V∥)exp[O(mlog(m/ε))], replacing the previous quasi-polynomial accuracy dependence. The algorithm also returns a variational state as a short Gaussian superposition. At inverse temperature β\betaβ, an interaction-independent Gaussian spanning set of size (2+β)O(m)/δ(2+\beta)^{O(m)}/\delta(2+β)O(m)/δ approximates the thermofield double to norm error O(δ)O(\delta)O(δ). With ∥V∥≤1\|V\|\le1∥V∥≤1, its coefficients and the Helmholtz free energy are classically computable in time polynomial in n,βn,\betan,β and inverse accuracy for fixed mmm.
The equilibrium proofs organize bath modes into energy shells and Krylov layers, establish product bounds suppressing simultaneous bath excitations, and truncate configurations by weighted occupation. Thermal-state reconstruction uses a global least-squares fit to imaginary-time evolution to control error amplification.
For dynamics, a fixed number-conserving quartic interaction on 24 fermionic modes implements circuits through sequential scattering of program and data wave packets. A Slater-determinant input and n,T=O((k+g)4)n,T=O((k+g)^4)n,T=O((k+g)4) reproduce a kkk-qubit, ggg-gate circuit’s output probability within 1/121/121/12, yielding BQP-completeness. This is worst-case dynamical hardness, not specifically hardness of equilibrium response functions. Efficiency requires fixed impurity size; constructive thermal results assume bounded interaction strength.
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.
Impurity Hamiltonians are systems of NNN fermionic modes where O(1)O(1)O(1) of them interact among themselves via quartic (or higher order) fermion terms, while coupling quadratically with O(N)O(N)O(N) bath modes. Without the quartic interactions, these systems are classically simulable with O(N3)O(N^3)O(N3) resources. It was proved that the time-dependent evolution of these systems can perform universal quantum computation. The question of whether or not this remains true for time-independent evolution remains open. Here, we prove that the time evolution of generic time-independent impurity Hamiltonians on O(N)O(N)O(N) qubits is universal on NNN qubits if the input state is a product state of fermions in any single particle basis. In our proof we find that for a computation of depth SSS, the size of the impurity scales as O(Slog⁡S)O(S\log S)O(SlogS).
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.
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.
We provide a detailed formulation of the recently proposed variational approach [Y. Ashida, T. Shi, M.-C. Ba\~nuls, J. I. Cirac, and E. Demler, Phys. Rev. Lett. 121, 026805 (2018)] to study ground-state properties and out-of-equilibrium dynamics for generic quantum spin-impurity systems. Motivated by the original ideas of Tomonaga, Lee, Low, and Pines, we construct a canonical transformation that completely decouples the impurity from the bath degrees of freedom. By combining this transformation with a Gaussian ansatz for the fermionic bath, we obtain a family of variational many-body states that can efficiently encode the strong entanglement between the impurity and fermions of the bath. We give a detailed derivation of equations of motions in the imaginary- and real-time evolutions on the variational manifold. We benchmark our approach by applying it to investigate ground-state and dynamical properties of the anisotropic Kondo model and compare results with those obtained using the matrix-product state (MPS) ansatz. We show that our approach can achieve an accuracy comparable to MPS-based methods with several orders of magnitude fewer variational parameters than the corresponding MPS ansatz. Comparisons to the Yosida ansatz and the exact solution from the Bethe ansatz are also discussed. We use our approach to investigate the two-lead Kondo model and analyze its long-time spatiotemporal behavior and the conductance behavior at finite bias and magnetic fields. The obtained results are consistent with the previous findings in the Anderson model and the exact solutions at the Toulouse point.
We present a quantum Monte Carlo algorithm for computing the perturbative expansion in power of the coupling constant UUU of the out-of-equilibrium Green's functions of interacting Hamiltonians of fermions. The algorithm extends the one presented in Profumo et al. [Phys. Rev. B 91, 245154 (2015)], and inherits its main property: it can reach the infinite time (steady state) limit since the computational cost to compute order Un{U}^{n}Un is uniform versus time; the computing time increases as 2n{2}^{n}2n. The algorithm is based on the Schwinger-Keldysh formalism and can be used for both equilibrium and out-of-equilibrium calculations. It is stable at both small and long real times including in the stationary regime, because of its automatic cancellation of the disconnected Feynman diagrams. We apply this technique to the Anderson quantum impurity model in the quantum dot geometry to obtain the Green's function and self-energy expansion up to order U10{U}^{10}U10 at very low temperature. We benchmark our results at weak and intermediate coupling with high precision numerical renormalization-group computations as well as analytical results.