arXiv:2610.02130
Quantum impurity models: easy at equilibrium, universal in motion
Srinivasan Arunachalam, Sergey Bravyi, Anirban Chowdhury, Arkopal Dutt, Alexandru Gheorghiu, Zhi Li
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.
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