Quantum weekly, September 25–October 2, 2026 | 0.85 against 0.65, and a classical algorithm for equilibrium

Berlin's Dahlem Center for Complex Quantum Systems, with the Fraunhofer Heinrich Hertz Institute and Helmholtz-Zentrum Berlin, posted a proof on 1 October that decoded quantum interferometry beats every polynomial-time classical algorithm on one optimization task. On balanced folded optimal polynomial intersection, the DQI algorithm guarantees an expected score of 0.8571 at code rate 3/10. The classical threshold, attained by Prange's algorithm under the quantifiers the paper fixes, sits at 0.65, and exceeding that threshold by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries 1.

The framework is two years old. Its quantum half applies a Fourier transform to an optimization problem and turns it into a decoding problem; its classical or quantum half then decodes; the framework's journal version carries the DOI 10.1038/s41586-025-09527-5 2. The papers this week work on that second half, and the strength of the advantage moves with it.

Two independent groups also redrew a boundary in the other direction. On 1 October, IBM Research published a proof that the ground energy, the free energy and a classical description of the thermal state of a quantum impurity model are all reachable in polynomial time on a classical computer, while the model's time evolution is BQP-complete 3. A group split across UC Berkeley, Sandia National Laboratories, the University of Cambridge and the University of New Mexico reached the same boundary the same day by different methods, adding that nonequilibrium Green's functions capture the full power of quantum computation even at finite temperature 4.

Read together with Google Quantum AI's own bounds on the same interferometry framework, which rule out an advantage in the regimes that group can analyse 5, the week's question is the one no paper title settles: what is the classical object on the other side of the comparison, and how far did it move?

Folded OPI is a promise task. Its acceptance sets are drawn randomly and reached through membership oracles, and the paper's construction, set out around its Figure 3, reduces a block max-LINSAT instance to that form 1. Oracle access is what lets a lower bound be proved at all: a classical algorithm can be denied the structure that a concrete instance would hand it.

At a code rate of 3/10 the separation is 0.8571 against 0.65 for the plain algorithm and 0.9583 for the modified one. Above rate 1/2 the classical side falls back on exact search, which is where the green segment in the figure takes over.

The paper's own framing of the open question is worth quoting, because it was open until this week: "A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms" 1. Earlier DQI analyses showed it outperforming the best known classical algorithms; a lower bound against arbitrary classical algorithms is a different object, and it is the one supplied here.

The proof stops short of a device. It names no circuit and no decoder, and the promise problem is built to be hard for a classical algorithm. The distance between this result and a hardware demonstration is the distance between an oracle and an instance.

Google Quantum AI, with JPMorganChase's applied research group, Harvard and Sandia, published bounds on 30 September that close the question in the other direction for the regimes it examines. The paper derives DQI satisfaction guarantees when the decoder is imperfect, generalises them to random instances, and then proves both upper and lower bounds on the approximate optimum DQI can reach when its decoder is classical 5. Those bounds rule out a quantum advantage in the regimes analysed.

The paper argues that earlier no-go results were too pessimistic. Those results leaned on a code's minimum distance; the authors treat the true decodability threshold of the noise channel as the governing quantity, which is a looser and more realistic standard. The same paper shows that minimum-weight decoding of homological cycle codes is NP-hard for every field of size greater than two, in contrast with the binary case. The pessimistic reading and the closing bound come from the same authors, which is the most useful kind of result for a reader deciding what to believe.

One family survives. On a set of regular Max-k-Cut instances the paper proves that DQI efficiently achieves a nontrivial satisfaction-fraction guarantee 5. Where the classical side has no matching lower bound, the paper calls it a guarantee and nothing more.

UCLA, Google Quantum AI and Harvard applied the same framework to Gibbs sampling of classical Ising spin glasses, and there the outcome differs. Above the dynamical transition temperature, shattering and disorder chaos form a topological barrier that blocks Glauber dynamics and every algorithm whose output distribution is stable under perturbations of its input. DQI equipped with a quantum decoder, and a classical algorithm based on Prange's method, both cross that barrier: when the average degree is D = αk with α > 1, each samples at any inverse temperature below tanh⁻¹(1/α), well past the dynamical threshold 6.

Two features of that result matter for anyone reading it as a quantum claim. The crossing is proved for two algorithms, one of which is classical, so the barrier is a statement about stable algorithms, and a classical method clears it too. And the reason DQI reaches lower temperatures is stated in the abstract: the Gibbs sampling problem reduces to a quantum decoding problem, and the reachable temperature is fixed by how well the decoding algorithms perform 6.

Two more papers from the same group push the decoding half in different directions. One retains classical decoding and admits global constraints on how often each symbol appears, which widens the class of optimization problems the framework reaches beyond coordinate-wise constraints 7. The other is a clean illustration of how fast the classical side can move.

Vector subset sum over F₃ⁿ asks for a nonempty subset of m random vectors that sums to zero, and the smaller m is, the harder the problem. A 2022 quantum algorithm solved it at m ≈ n²/2. A classical algorithm presented at STOC 2026 cut that to about n²/3, which removed the prospect of an exponential quantum speedup in that regime. The paper posted on 30 September restores it: for any fixed ε > 0, a quantum algorithm solves the problem in polynomial time with m = ε·n² vectors, and the paper establishes a full sample–time tradeoff that interpolates between exponential and polynomial runtime 8. Its main ingredient is a deterministic classical algorithm for binary-error Learning-with-Errors, which is of independent interest to cryptographers.

The pattern across these five papers sits in the decoding step. The interference step is common to all of them. What varies is what performs the decoding, and what the classical baseline is allowed to assume. The advantage follows the decoder.

Quantum impurity models describe a small interacting subsystem embedded in a large bath of free fermions. They are workhorses of electronic structure, and their complexity had been pinned down only loosely: the best previous algorithm for the ground energy ran in quasipolynomial time. IBM Research's proof brings that down to poly(n, 1/ε) for additive error ε, and computes the Helmholtz free energy together with a classical description of the thermofield double state in poly(n, β, 1/ε) at inverse temperature β 3. The mechanism is a basis organised by energy scale and Krylov depth, in which multi-particle bath excitations are exponentially suppressed.

The Berkeley, Sandia and Cambridge paper reaches the same conclusion about statics and states the consequence plainly: its results rule out superpolynomial quantum speedups for computing static properties of these models, and open the out-of-equilibrium direction instead 4. Its thermal result is the first rigorous polynomial-time guarantee for equilibrium simulation of the class.

Both papers turn the same corner, and each gives the other company at the level of the mechanism. The IBM construction and the Berkeley construction exploit the same structural fact about the bath, expressed in different bases. IBM's universality result is the sharper of the two: simulating e^{-iHt} is BQP-complete for a time-independent Hamiltonian with a fixed, constant impurity size, so dynamics carries the full power of quantum computation 3. Its construction realises a stationary quantum processor whose program arrives as a stream of freely propagating fermions.

For a reader weighing where to spend quantum hardware, the pair gives a usable rule. Equilibrium properties of this model class are a classical task now, and any resource estimate that assumes otherwise overstates the quantum case. The out-of-equilibrium side keeps its claim, and the paper that supports it is a complexity statement about a family of Hamiltonians.

The strongest structural claim of the week comes from the mathematics department at the Technical University of Munich and MCQST. Libor Caha, Robert Koenig and Louis Paletta constructed a problem that a 2D-local quantum circuit solves with high probability while any polynomial-size AC⁰ circuit fails on some instances, and they did it for circuits subject to local stochastic noise below a constant threshold 9.

Three properties arrive together for the first time in one separation, on the authors' own account: it applies to planar devices, it incorporates noise-resilience, and it is unconditional, resting on quantum mechanics with no complexity assumption 9. Planarity matters because superconducting arrays and photonic repeater networks confine qubits to 2D grids with nearest-neighbour operations. Noise-resilience matters because a separation that evaporates once the circuit is imperfectly implemented says nothing about a laboratory.

The compared class is AC⁰, constant-depth classical circuits with unbounded fan-in, which is a weak adversary. A separation from AC⁰ is a lower bar than a separation from all polynomial-time classical algorithms, and this week's other papers set their bars in different places. The Munich result is the one that survives the engineering constraints, and its adversary is the smallest.

An advantage claim that resists independent checking stays a claim, and two Google Quantum AI papers this week work on the checking half. The first, with the Free University of Berlin and Caltech, is about a specific obstruction. Estimating out-of-time-order correlators in random circuits had been proposed as a verifiable task, but the circuit-to-circuit fluctuations that carry the signal might conceivably wash out as the system grows, which would leave the measurement constant across instances and therefore useless. Mele, Mele, McClean and O'Brien prove that the fluctuations stay inverse-polynomial at system-scale depths for broad classes of local random circuits in any fixed spatial dimension 10. In one-dimensional Haar-random brickwork circuits, macroscopically many gates contribute to the fluctuations while each layer confines them to a sublinear-width region.

The paper is precise about what that settles. Strong concentration is ruled out as an obstruction to OTOC-based proposals for verifiable quantum advantage, and the classical hardness of the task remains open; as a byproduct the authors give a classical algorithm that improves on brute-force simulation of OTOCs in one dimension 10.

The second paper attacks the same problem from the error side, and it published on 25 September, at the edge of this week's window. Philippe Suchsland, Thomas Schuster, Manuel Rudolph, Nicholas Noll, Thomas E. O'Brien and Zlatko Minev represent a circuit's noise response through a compact object they call the reactivity function, then build two mitigation methods on it. Across three circuit families taken from published experiments, the methods remove conventional zero-noise-extrapolation biases as large as 30% and, at a root-mean-square error near 10⁻², cut sampling cost against probabilistic error cancellation by up to a factor of 10³ 11. The Google Quantum AI authors are joined by one at EPFL.

Sampling cost decides whether a verification experiment fits in a queue this year, so a factor of 10³ against the exact method changes which experiments get run.

Quantinuum's own contribution this week is a hardware result, and its finding is about how algorithms are chosen. Etienne Granet and Henrik Dreyer compared two circuits that prepare the ground state of a tight-binding chain at matched gate count and matched circuit depth on Quantinuum System Model H2. Beyond a system size, the adiabatic evolution reaches significantly lower energy densities than the fermionic Fourier transform, and the reason is precision: the FFT resolves momenta to 1/N, which demands long-range couplings in real space, and those propagate errors faster 12.

The same argument produces a cheaper momentum measurement, less precise than the FFT and good enough to beat it on spectral-function measurement on the same machine 12. Gate count and circuit depth are the two numbers almost every resource estimate optimises, and this result prices a third axis, noise sensitivity, on a real processor.

IonQ's paper takes the other half of the same habit. Claims for quantum neural networks rest on comparisons with classical models that belong to different function classes, which makes the outcome hard to interpret in either direction. Oliver Knitter, Jonathan Mei, Sang Hyub Kim, Chi Chen, Masako Yamada and Martin Roetteler built a stochastic classical network, the Neural Fourier Surrogate, that learns coefficients over exactly the finite Fourier series support a data-reuploading quantum neural network can express. On a selection of tabular benchmark datasets it is broadly competitive with established classical baselines and comparable in performance to the quantum networks it is matched to, which makes it a natural classical baseline for that comparison 13. The work is authored at IonQ's College Park office and reports no hardware run.

Both papers leave the same instruction to a reader holding a performance claim: identify the object on the other side of the comparison, and check whether it was chosen to be strong.

For the Berlin separation, the assumption to test is the promise. Folded OPI reaches its lower bound through membership oracles, so the next useful result is an instance family whose structure is both usable and hard enough for the bound to survive contact with it.

For the cycle-code bounds, the open cell is the Max-k-Cut family. A classical lower bound there would close it; a decoder that beats the thresholds the paper assumes would reopen the regimes it currently rules out. Both are stated as open in the paper.

For the Gibbs-sampling result, the crossing is proved and the cost is not. An implementation of the quantum decoder with its latency measured would turn a temperature range into an engineering budget.

For the impurity models, the equilibrium algorithms are constructive, and the question a resource estimator will ask is how they scale on a real instance. On the dynamics side, the comparable statement is a run on an out-of-equilibrium impurity problem with its logical error rate reported.

For the planar separation, the adversary is AC⁰. Anyone who wants to read the result as a statement about quantum computers in a laboratory will want the same construction against a stronger classical class, and the paper is explicit that the noise threshold is a constant.

The commercial record this week is thin. EPB's 1 October release reports that EPB Quantum and IonQ launched CQ Connect, a webinar series, alongside a quantum-in-business conference in Chattanooga where IonQ's chairman and chief executive gave the keynote; the release adds no measurement of its own, and the 14.6% engineering-acceleration figure it repeats was published on 17 September 14. Quantinuum's newsroom carries no technical release since 11 September, and its one dated post inside the window is a summer-school account 15. PsiQuantum's newsroom carries no item inside the window at all; its most recent entry is dated 10 September 16. Google Quantum AI's blog route remains behind an access wall, and its publishable output this week is the preprint set above 17.