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:2604.08466

Time evolution of impurity models and their universality for quantum computation

N. C. Mai Pham, Raul A. Santos

quant-phSubmitted Apr 9, 2026• Announced Apr 10, 2026• 1 citation
arXivHTMLPDF

Abstract

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)$.

Comments
14 pages, 2 figures

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

Quantum dynamics of impurities coupled to a Fermi sea

Meera M. Parish, Jesper Levinsen

We consider the dynamics of an impurity atom immersed in an ideal Fermi gas at zero temperature. We focus on the coherent quantum evolution of the impurity following a quench to strong impurity-fermion interactions, where the interactions are assumed to be short range like in cold-atom experiments. To approximately model the many-body time evolution, we use a truncated basis method, where at most two particle-hole excitations of the Fermi sea are included. When the system is initially noninteracting, we show that our method exactly captures the short-time dynamics following the quench, and we find that the overlap between initial and final states displays a universal nonanalytic dependence on time in this limit. We further demonstrate how our method can be used to compute the impurity spectral function, as well as describe many-body phenomena involving coupled impurity spin states, such as Rabi oscillations in a medium or highly engineered quantum quenches.

arXiv:1608.00864•Physical review. B./Physical review. B•Nov 4, 2016•67 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•21 citations

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

Universal two-body-Hamiltonian quantum computing

Daniel Nagaj

We present a Hamiltonian quantum-computation scheme universal for quantum computation. Our Hamiltonian is a sum of a polynomial number (in the number of gates $L$ in the quantum circuit) of constant-norm, time-independent, two-body interaction terms. Furthermore, each qubit in the system interacts only with a constant number of other qubits in a three-layer, geometrically local layout. The computer runs in three steps---it starts in a simple initial product state, evolves according to a time-independent Hamiltonian for time of order ${L}^{2}$ (up to logarithmic factors), and finishes with a two-qubit measurement. Our model improves previous universal two-local-Hamiltonian constructions, as it avoids using perturbation gadgets and large energy-penalty terms in the Hamiltonian, which would result in a large required run time.

arXiv:1002.0420•Physical Review A•Mar 27, 2012•26 citations

Efficient method for quantum impurity problems out of equilibrium

Julian Thoenniss, Michael Sonner, Alessio Lerose +1 more

We introduce an efficient method to simulate the dynamics of an interacting quantum impurity coupled to noninteracting fermionic reservoirs. Viewing the impurity as an open quantum system, we describe the reservoirs by their Feynman-Vernon influence functionals (IFs). The IFs are represented as matrix-product states in the temporal domain, which enables an efficient computation of the dynamics for arbitrary interactions. We apply our method to study quantum quenches and transport in an Anderson impurity model, including highly nonequilibrium setups, and find a favorable performance compared to state-of-the-art methods. The computational resources required for an accurate computation of the dynamics scale polynomially with evolution time, indicating that a broad class of out-of-equilibrium quantum impurity problems are efficiently solvable. This approach will provide additional insights into the dynamical properties of mesoscopic devices and correlated materials.

arXiv:2211.10272•Physical review. B./Physical review. B•May 23, 2023•65 citations
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).
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.
We consider the dynamics of an impurity atom immersed in an ideal Fermi gas at zero temperature. We focus on the coherent quantum evolution of the impurity following a quench to strong impurity-fermion interactions, where the interactions are assumed to be short range like in cold-atom experiments. To approximately model the many-body time evolution, we use a truncated basis method, where at most two particle-hole excitations of the Fermi sea are included. When the system is initially noninteracting, we show that our method exactly captures the short-time dynamics following the quench, and we find that the overlap between initial and final states displays a universal nonanalytic dependence on time in this limit. We further demonstrate how our method can be used to compute the impurity spectral function, as well as describe many-body phenomena involving coupled impurity spin states, such as Rabi oscillations in a medium or highly engineered quantum quenches.
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.
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.
We present a Hamiltonian quantum-computation scheme universal for quantum computation. Our Hamiltonian is a sum of a polynomial number (in the number of gates LLL in the quantum circuit) of constant-norm, time-independent, two-body interaction terms. Furthermore, each qubit in the system interacts only with a constant number of other qubits in a three-layer, geometrically local layout. The computer runs in three steps---it starts in a simple initial product state, evolves according to a time-independent Hamiltonian for time of order L2{L}^{2}L2 (up to logarithmic factors), and finishes with a two-qubit measurement. Our model improves previous universal two-local-Hamiltonian constructions, as it avoids using perturbation gadgets and large energy-penalty terms in the Hamiltonian, which would result in a large required run time.
We introduce an efficient method to simulate the dynamics of an interacting quantum impurity coupled to noninteracting fermionic reservoirs. Viewing the impurity as an open quantum system, we describe the reservoirs by their Feynman-Vernon influence functionals (IFs). The IFs are represented as matrix-product states in the temporal domain, which enables an efficient computation of the dynamics for arbitrary interactions. We apply our method to study quantum quenches and transport in an Anderson impurity model, including highly nonequilibrium setups, and find a favorable performance compared to state-of-the-art methods. The computational resources required for an accurate computation of the dynamics scale polynomially with evolution time, indicating that a broad class of out-of-equilibrium quantum impurity problems are efficiently solvable. This approach will provide additional insights into the dynamical properties of mesoscopic devices and correlated materials.