🔬 physics

Polynomial-time classical and quantum simulation of quantum impurity models

This paper establishes that static properties of quantum impurity models can be efficiently simulated on classical computers with polynomial-time guarantees, while demonstrating that simulating their dynamical, nonequilibrium properties remains classically hard but is efficiently achievable on quantum computers.

Original authors: Jiaqing Jiang, Nathan Ju, Ojas Parekh, Chaithanya Rayudu, Andrew Zhao

Published 2026-10-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jiaqing Jiang, Nathan Ju, Ojas Parekh, Chaithanya Rayudu, Andrew Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the microscopic world of materials science, scientists often study how electrons behave when they are trapped in a small, crowded region while surrounded by a vast, quiet sea of other electrons. This setup, known as a quantum impurity model, is like a single, highly interactive person standing in the middle of a massive, silent crowd. The person at the center represents a "defect" or a specific atom where complex interactions happen, while the surrounding crowd represents a "bath" of non-interacting particles that simply flow around the center. These models are fundamental to understanding everything from why certain metals conduct electricity poorly at low temperatures to how electrons move through tiny molecular transistors. For decades, simulating these systems has been a major challenge for computers because the interactions at the center create a web of possibilities that grows too fast for standard machines to track.

For a long time, the scientific community wondered if these models were fundamentally too difficult for classical computers to solve, or if they required the power of a quantum computer to crack. The question was particularly pressing because these models are the building blocks for modern methods used to design new drugs and materials. If the underlying math was too hard, it would mean that our ability to predict the behavior of new materials was hitting a hard ceiling. However, a new study has settled this debate with a surprising twist. The researchers found that while the static, unchanging properties of these systems—such as their energy levels or their state at a specific temperature—can be calculated efficiently on a regular, classical computer, the story changes completely when the system is in motion.

The team demonstrated that the static properties of these quantum impurity models are not as hard as previously thought. They developed a new mathematical approach that allows a classical computer to compress the massive amount of information needed to describe the system into a much smaller, manageable size. Imagine trying to describe the position of every person in a stadium; it would take an enormous amount of data. But if you realize that the people in the stands are mostly still and only a few are moving, you can describe the whole scene by focusing only on the active few and the general state of the crowd. The researchers proved that for these quantum systems, the "active" part of the information is surprisingly small. They created algorithms that can calculate the ground-state energy—the lowest possible energy the system can have—and the thermal properties at any temperature with high precision, all in a time that grows reasonably with the size of the system. This result improves upon previous estimates that suggested these calculations would take an impractically long time, effectively proving that a super-polynomial speedup from a quantum computer is not needed for these specific static tasks.

However, the researchers also discovered a clear boundary where classical computers hit a wall. When the system is not in a steady state but is instead evolving over time, such as when electrons are moving through the material in a non-equilibrium situation, the problem becomes incredibly difficult for classical machines. In these dynamic scenarios, the researchers showed that simulating the system is as hard as the most difficult problems a universal quantum computer can solve. They proved that calculating how the system changes over time, specifically looking at how particles correlate with each other at different moments, captures the full power of quantum computation. This means that while a regular computer can easily tell you what the system looks like when it is sitting still, it will struggle immensely to predict how the system behaves when it is being pushed and pulled, a task that a quantum computer could handle with ease.

This distinction is crucial for the future of materials science and computing. It suggests that for applications like designing new materials where scientists are mostly interested in the stable, final properties of a system, classical computers are sufficient and will remain the primary tool. The promise of a massive quantum advantage lies not in solving these static puzzles, but in simulating the complex, dynamic processes that occur when materials are reacting to external forces or changing conditions. The study provides a rigorous map of where classical computing ends and quantum computing begins for this class of problems, clarifying that the power of quantum machines will be most valuable when we need to watch the system move, rather than just measure where it ends up.

Technical Summary: Polynomial-time Classical and Quantum Simulation of Quantum Impurity Models

1. Problem Statement

Quantum impurity models describe a small, strongly interacting fermionic subsystem (the "impurity") coupled to a large, non-interacting bath. These models are paradigmatic for interacting quantum matter and serve as the computational primitives for modern embedding methods like Dynamical Mean-Field Theory (DMFT) and Density Matrix Embedding Theory (DMET).

Despite their localized nature, simulating these models is non-trivial. While numerical methods like Numerical Renormalization Group (NRG) and Continuous-Time Quantum Monte Carlo (CT-QMC) are empirically successful, their rigorous computational complexity was not fully understood. Specifically, it was an open question whether static properties (ground-state energy, thermal partition functions) could be computed in polynomial time on classical computers, or if they required quantum resources. Conversely, the complexity of dynamical properties (e.g., nonequilibrium Green's functions) remained unclear.

Previous work by Bravyi and Gosset [BG17] established that ground-state energy estimation was possible in quasipolynomial time on a classical computer, while Erakovic et al. [EWH+25] provided polynomial-time quantum algorithms under strong assumptions (e.g., constant spectral gap). The question of whether an unconditional polynomial-time algorithm exists for static properties, and whether dynamical properties offer a quantum advantage, remained open.

2. Methodology

The authors develop a comprehensive framework to analyze the computational complexity of both static and dynamical properties of quantum impurity models.

2.1. Basis Transformation and Compression

The core technical innovation is a compression lemma showing that the ground state and the relevant part of the thermal state are approximately supported on a subspace whose dimension is polynomial in the system size $n$ , inverse precision $\delta^{-1}$ , and inverse bath spectral gap $\omega^{-1}$ , but independent of the impurity interaction strength.

Bandwise Krylov Basis: The authors construct a specific single-particle basis for the bath, termed the bandwise Krylov basis. This is achieved by:
1. Partitioning the bath spectrum into logarithmically spaced energy bands $[\omega_\ell, 2\omega_\ell)$ .
2. Applying a block-tridiagonalization (Krylov subspace) procedure within each band.
3. Enlarging the Impurity: The first Krylov block of each band is absorbed into the impurity. This ensures that the coupling between the "enlarged impurity" and the "residual bath" is bounded by the energy scale of the specific band ( $O(\omega_\ell)$ ), rather than the potentially large original coupling.
Weighted Occupation Statistics: Using this basis, the authors define weighted occupation statistics based on the "depth" of bath modes in the Krylov chain. They prove a commutator identity for impurity models that relates higher-order occupation statistics to lower-order ones. By bounding the "bath-replacement" terms (using the weighted positivity of the bath matrix) and the "hybridization" terms, they derive a recursion that shows the exponential decay of occupation probability with Krylov depth.
Soft-Hard Decomposition (Thermal States): For thermal states, the authors introduce a decomposition of the Hamiltonian into a "soft" (low-energy) part and a "hard" (high-energy) part. They show that the thermal state can be compressed to a subspace where the Hamiltonian takes the form $H_{\text{ref}} + V$ , where $H_{\text{ref}}$ is efficiently simulable and the perturbation $V$ satisfies $\beta \|V\| = O(\log n)$ .

2.2. Algorithmic Implementation

Classical Simulation:
- Ground States: The compressed subspace allows for exact diagonalization of the projected Hamiltonian, yielding a classical algorithm with runtime $\text{poly}(n, \delta^{-1})$ .
- Thermal States: The soft-hard decomposition reduces the problem to simulating a perturbed free-fermion system. The authors apply Continuous-Time Quantum Monte Carlo (CT-QMC). Crucially, because the effective perturbation strength scales as $\beta \|V\| = O(\log n)$ , the exponential dependence on $\beta$ typically found in CT-QMC (due to the sign problem or expansion order) is eliminated, resulting in a runtime of $\text{poly}(n, \beta, \delta^{-1})$ .
Quantum Simulation:
- The same structural results allow for efficient preparation of thermal states using Quantum Belief Propagation (QBP). The algorithm prepares the thermal state with trace-distance error $\delta$ in time $\text{poly}(n, \beta, \delta^{-1})$ .
Hardness of Dynamics:
- To prove hardness for dynamical properties, the authors construct a single-ancilla universality encoding. They show that time-dependent impurity Hamiltonians can encode arbitrary quantum circuits into a logical subspace with only a constant-factor attenuation (using $n+1$ modes for $n$ logical qubits).
- They utilize algorithmic cooling (Schulman and Vazirani [SV99]) to concentrate thermal qubits into nearly pure states, enabling the encoding of BQP-complete problems even at finite temperatures.

3. Key Results

3.1. Classical Tractability of Static Properties

The paper establishes that static properties of quantum impurity models are classically easy to compute.

Ground-State Energy: There exists a classical algorithm to estimate the ground-state energy to additive precision $\delta$ in time $\text{poly}(n, \delta^{-1})$ . This improves the previous quasipolynomial-time bound [BG17] to polynomial time.
Thermal States: There exists a classical algorithm to estimate the partition function $Z$ to relative precision $\delta$ and the expectation value of any fermionic Gaussian operator to additive precision $\delta$ in time $\text{poly}(n, \beta, \delta^{-1})$ . This provides the first rigorous polynomial-time guarantee for thermal simulation of impurity models at arbitrary temperatures.
Implication: These results rule out the possibility of a superpolynomial quantum speedup for computing static properties of impurity models.

3.2. Quantum Hardness of Dynamical Properties

In contrast to static properties, simulating dynamical quantities is hard for classical computers but easy for quantum computers.

Nonequilibrium Green's Functions: Estimating the time-dependent two-point correlation function $G_\beta(t, t') = \langle \gamma_j(t) \gamma_k(t') \rangle_\beta$ $G_{β} (t, t^{'}) = ⟨ γ_{j} (t) γ_{k} (t^{'}) ⟩_{β}$ to inverse-polynomial precision is:
- DQC1-complete at infinite temperature ( $\beta = 0$ ).
- BQP-complete at finite temperature ( $\Omega(1) \le \beta \le \text{poly}(n)$ ).
This demonstrates that the computational hardness of impurity models lies entirely in their dynamical evolution, not their static equilibrium properties.

4. Significance and Claims

The paper claims to settle the fundamental computational complexity of quantum impurity models:

Resolution of an Open Question: It proves that the longstanding empirical success of impurity solvers (like NRG) is grounded in a rigorous theoretical fact: the ground states and thermally gapped parts of Gibbs states are compressible to low-dimensional subspaces.
Clarification of Quantum Advantage: The results delineate the boundary between classical and quantum tractability. They imply that proposals for "quantum-enhanced DMFT" cannot rely on a superpolynomial speedup for the static impurity solver itself. Any potential quantum advantage in such applications must arise from the simulation of dynamical quantities (e.g., nonequilibrium Green's functions), which are shown to be complete for universal quantum computation.
Methodological Contribution: The introduction of the bandwise Krylov basis and the compression lemma provides a new structural understanding of impurity models, independent of specific interaction strengths or spectral gaps (provided the bath has a gap). This framework unifies the treatment of ground and thermal states.

The authors explicitly state that their results do not rule out polynomial quantum speedups, but they definitively rule out superpolynomial ones for static properties. They also note that their classical algorithms feature exponential dependence on the impurity size $m$ (treated as a constant), leaving open the possibility of improving this dependence for systems with extensive interacting degrees of freedom.