Classical Algorithm Cracks Quantum Chaos Benchmark — in Polynomial Time

A team shows that OTOCs, proposed as a path to verifiable quantum advantage, can be efficiently computed classically in 1D circuits by exploiting the very chaos that was supposed to make them hard.

Imagine you're trying to predict the exact position of every ball after a break shot in pool. Chaos makes the trajectories wildly sensitive to initial conditions — seemingly impossible to track. But what if you didn't need the exact trajectory of every ball, just the statistical signature of how the chaos spread? That's the core trick here: instead of fighting quantum chaos, this algorithm rides it. The dephasing that makes individual quantum amplitudes unpredictable also suppresses the terms that make the computation hard. The paper's committed claim: there exists a polynomial-time classical algorithm that accurately estimates four-point and eight-point out-of-time-ordered correlators (OTOCs) in typical instances of 1D random quantum circuits. OTOCs have been proposed — notably by Google's quantum team — as a candidate for verifiable quantum advantage, the idea being that these quantities live in a regime where circuit-to-circuit fluctuations are large, making conventional classical methods like tensor networks and Monte Carlo choke. This paper says: not so fast. The algorithm works by organizing the OTOC into a rapidly converging series expansion within the replicated Hilbert space. The leading term captures contributions from histories that stay within permutation degrees of freedom (a structured, low-dimensional subspace), while subleading terms arise from excursions outside it. The key insight is that quantum chaos itself — through a dephasing mechanism — exponentially suppresses those subleading excursion terms. Chaos doesn't make the problem harder; it makes the approximation better. The authors provide both analytical arguments and numerical evidence for this suppression. On the ladder: the authors directly benchmark against Google's recent 2D OTOC experiments and demonstrate that their classical algorithm achieves higher signal-to-noise ratio at larger circuit depths than the quantum hardware results, at least in 1D. This is a pointed comparison — it says the quantum experiment's claimed advantage regime is classically accessible in one dimension. Classical tensor network and Monte Carlo approaches were previously the main competitors, and this paper leapfrogs both by exploiting structure those methods ignore. Integrity is solid but not airtight. The evidence is a combination of theoretical analysis (convergence bounds on the series) and numerical simulation on classical hardware. There's no independent replication, and the benchmarks weren't pre-registered — but the comparison to Google's published experimental data is a strong anchor. The authors are admirably honest about scope: the algorithm is demonstrated for 1D circuits, and they explicitly flag that extending to 2D and resolving the quantum advantage question there remain open problems. This is not a paper that overclaims. The milestone question is clear. 1D is solved (classically tractable). 2D is the prize — Google's experiments are in 2D, and the status of quantum advantage for 2D OTOCs is unresolved. The gap between 1D and 2D is not just a matter of scaling; it's a qualitative question about whether the dephasing suppression that makes the 1D algorithm work extends to higher-dimensional circuits where the permutation-subspace structure may be richer. The obvious next experiment is running this algorithm (or its natural extension) on 2D circuit instances and seeing whether the series still converges fast enough. The authors explicitly name this as an open problem. The honest read: this is almost certainly option (a) — the 2D case is genuinely harder, not just computationally more expensive. The permutation-subspace structure in 2D may not produce the same clean suppression, and the authors know this. They're being careful, not hiding a negative result.