Imagine you're running a massive restaurant kitchen. You have one temperamental head chef (the impurity) and a hundred line cooks (the bath) who individually follow simple rules. If someone asks 'what's the kitchen's energy bill at the end of the night?' — that's a static question, and it turns out you can answer it by clever bookkeeping without simulating every pan-flip in real time. But if someone asks 'what happens to order flow when the head chef starts yelling at 7:43 PM?' — that's a dynamical question, and you genuinely need to replay the chaos as it unfolds. This paper proves that distinction is fundamental, not just practical. The committed claim: static properties of quantum impurity models — ground-state energy and thermal partition functions — can be computed in polynomial time on classical hardware, full stop. The ground-state result improves a previous quasipolynomial-time algorithm to genuine polynomial time. The partition function result is entirely new — no prior rigorous polynomial-time guarantee existed. Meanwhile, computing nonequilibrium Green's functions (the canonical dynamical quantity) is BQP-complete, meaning it captures the full power of quantum computation even at finite temperature. This is a complexity theory paper, not a numerics paper. The algorithmic family is classical simulation via structural decomposition of the impurity-bath coupling. The key structural insight is that impurity models have a special form — a small interacting region coupled to a large free-fermion bath — and that structure can be exploited to avoid the exponential blowup that plagues general strongly correlated systems. The quantum hardness result for dynamics uses a reduction showing that impurity Green's functions can encode universal quantum circuits. The tools span quantum complexity theory (BQP-completeness), classical algorithms (partition function estimation via polynomial interpolation and determinantal techniques), and condensed matter physics (Anderson and Kondo models, DMFT). The ladder here is unusual because the comparison isn't 'our number beats your number' — it's 'our complexity class beats your complexity class.' The previous best rigorous classical algorithm for impurity ground-state energy ran in quasipolynomial time — poly(n) × exp(polylog(n)) — established by Bravyi and Gosset (2017) for a related free-fermion-plus-perturbation setting, extended conceptually to impurity models. This paper collapses that to strict poly(n, δ⁻¹). For partition functions, no prior polynomial-time guarantee existed at all. On the quantum side, the BQP-completeness of Green's functions is new and sharp — previous work established QMA-hardness for general Hamiltonian ground states but hadn't pinpointed where quantum advantage lives specifically within impurity physics. Integrity is strong for a theory paper. The results are proved, not simulated. The ground-state algorithm and partition function algorithm come with explicit polynomial bounds. The BQP-completeness reduction is a formal proof, not a heuristic argument. The main caveat is that 'polynomial time' can hide large exponents — the paper establishes asymptotic tractability, not necessarily practical speed. No benchmarks or code are involved because this is pure complexity theory; the relevant validation is mathematical proof, which is the gold standard for claims of this type. The paper is 73 pages with detailed proofs. The milestone question is where things get concrete for practitioners. DMFT (dynamical mean-field theory) — the workhorse of modern electronic structure for correlated materials — requires solving an impurity model at every self-consistency step. The static solver result means the DMFT self-consistency loop for equilibrium properties is classically tractable in principle. The dynamics result means that computing spectral functions, transport coefficients, and out-of-equilibrium responses via impurity solvers is a genuine quantum computing use case — not just 'quantum might help,' but 'this problem is as hard as quantum computing gets.' The next concrete target: an efficient classical implementation of the polynomial-time static solver that competes with existing heuristic impurity solvers (like CT-QMC) on systems with 5-10 bath orbitals, demonstrating that the theoretical tractability translates to practical speedup. The obvious experiment not run: no numerical implementation. This is a theory paper through and through — 73 pages, 1 figure. The authors establish existence of polynomial-time algorithms but don't implement them or benchmark against existing solvers like CT-QMC, ED, or NRG. The honest read: this is (c) — different paper, different team, different skill set. The theory is the contribution. But until someone implements these algorithms and measures wall-clock time against CT-QMC on real impurity problems, the practical impact remains potential rather than demonstrated.
