Google: A Verifiable Quantum Advantage (research.google)

Google Quantum AI reports a verifiable quantum advantage via a new algorithm, Quantum Echoes, that measures out-of-time-order correlators (OTOCs)—expectation-value observables that quantify quantum chaos. On the Willow processor they ran forward (U) and backward (U†) random-circuit evolutions with an intermediate perturbation B and probe M across large qubit arrays (experiments used up to 103 qubits), producing first- and second-order OTOCs. Unlike prior random‑circuit sampling, OTOCs are repeatable expectation values that can be checked on other quantum devices or even in natural quantum systems, making the result both verifiable and practically relevant. Technically, higher‑order OTOCs behave like many‑body interferometers: repeated forward/backward loops amplify correlated signals when U† closely inverts U, producing constructive interference and a slow power‑law decay of measured signals. This amplification makes them far easier to measure on a quantum device than to simulate classically. Google’s analysis and nine classical red‑team simulation attempts show fundamental barriers for classical algorithms (storage of exponentially many complex amplitudes, sign/phase “interference” that breaks quantum‑Monte‑Carlo approaches); the Willow runs took ~2 hours versus an estimated 13,000× slower classical cost. They also demonstrate an application path—Hamiltonian learning via NMR—reporting an initial NMR proof‑of‑principle (not yet beyond classical) where quantum OTOC simulations improved molecular models, pointing toward practical, verifiable quantum advantage for real‑world physical inference.