In the recent quantum echoes experiment, Google Quantum AI showed that out-of-time-order correlators (OTOCs) for random-circuit time evolution can be measured using a quantum processor more than 10,000x faster than they can be computed to similar accuracy via classical computation. This claim was substantiated by comparison with a variety of state-of-the-art classical simulation methods. One classical simulation method that was not explicitly tested was tensor networks with belief propagation (TNBP). TNBP should be poorly suited to simulating Google's echoes experiment: the states involved are highly entangled, a challenge for tensor network states; and the Willow chip has dense 2D connectivity, a challenge for belief propagation. Here we confirm, via a combination of theoretical scaling arguments and explicit numerical simulation, the intuition that TNBP is unable to simulate the quantum echoes experiment. We show that the OTOC circuits generate enough entanglement that they are largely incompressible, implying that other approaches in which OTOCs are computed by evolving a tensor network state in the Schrödinger picture will also fail. Our results further reinforce the claim that the quantum echoes experiment cannot be reproduced by classical computation.
In the recent quantum echoes experiment, Google Quantum AI showed that out-of-time-order correlators (OTOCs) for random-circuit time evolution can be measured using a quantum processor more than 10,000x faster than they can be computed to similar accuracy via classical computation. This claim was substantiated by comparison with a variety of state-of-the-art classical simulation methods. One classical simulation method that was not explicitly tested was tensor networks with belief propagation (TNBP). TNBP should be poorly suited to simulating Google's echoes experiment: the states involved are highly entangled, a challenge for tensor network states; and the Willow chip has dense 2D connectivity, a challenge for belief propagation. Here we confirm, via a combination of theoretical scaling arguments and explicit numerical simulation, the intuition that TNBP is unable to simulate the quantum echoes experiment. We show that the OTOC circuits generate enough entanglement that they are largely incompressible, implying that other approaches in which OTOCs are computed by evolving a tensor network state in the Schrödinger picture will also fail. Our results further reinforce the claim that the quantum echoes experiment cannot be reproduced by classical computation.
Quantum annealing and quantum approximate optimization algorithms hold a great potential to speed-up optimization problems. This could be game-changing for a plethora of applications. Yet, in order to hope to beat classical solvers, quantum circuits must scale up to sizes and performances much beyond current hardware. In that quest, intense experimental effort has been recently devoted to optimizations on 3-regular graphs, which are computationally hard but experimentally relatively amenable. However, even there, the amount and quality of quantum resources required for quantum solvers to outperform classical ones is unclear. Here, we show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000 two-qubit gates with all-to-all connectivity. To this end, we develop a graph tensor-network quantum annealer (GTQA) able of high-precision simulations of Trotterized circuits of near-adiabatic evolutions. Based on a recently proposed belief-propagation technique for tensor canonicalization, GTQA is equipped with re-gauging and truncation primitives that keep approximation errors small in spite of the circuits generating significant amounts of entanglement. As a result, even with a maximal bond dimension as low as 4, GTQA produces solutions competitive with those of state-of-the-art classical solvers. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. In contrast, for degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states. On one hand, our findings showcase the potential of GTQA as a powerful quantum-inspired optimizer. On the other hand, they considerably raise the bar required for experimental demonstrations of quantum speed-ups in combinatorial optimizations.
Out-of-time-order correlators (OTOCs) are the main tool for probing quantum chaos and scrambling, and have become crucial probes in many areas of quantum computing. However, the measurement of OTOCs is difficult to implement on analog quantum computers due to the requirement of backward time evolution. In this paper, we develop and implement a randomized measurement protocol to compute OTOCs on Aquila by QuEra Computing. Unlike traditional methods that require backward time evolution, our approach utilizes a sequence of global randomized quenches that approximates the unitary 2-design properties necessary for extracting infinite-temperature OTOCs from statistical correlations. We demonstrate the protocol's success by explicitly observing the lightcone of information propagation in 1D Rydberg chains, and compare hardware results to both state-vector simulations and matrix product state (MPS) tensor network calculations. This work establishes the first demonstration of fully analog randomized OTOC measurements in neutral-atom simulators, providing a scalable pathway to probe quantum chaos in complex many-body systems.
Classical simulations of quantum circuits play a vital role in the development of quantum computers and in taking the temperature of the field. Here, we classically simulate various physically-motivated circuits using 2D tensor network ansätze for the many-body wavefunction, which match the geometry of the underlying quantum processor. We employ a generalized boundary Matrix Product State contraction algorithm to controllably generate samples from the resultant tensor network states. Our approach systematically converges both the quality of the final state and the samples drawn from it to the true distribution defined by the circuit, with GPU hardware providing significant speedups over CPU hardware. Using these methods, we simulate the largest local unitary Jastrow ansatz circuit from recent IBM experiments to numerical precision. We also study a domain-wall quench in a 2D discrete-time Heisenberg model on large heavy-hex and rotated square lattices, reflecting IBM’s and Google’s latest processors, respectively. We observe a rapid buildup of complex loop correlations on the Google Willow geometry, which significantly impacts local properties of the system. Meanwhile, loop correlations build up extremely slowly on heavy-hex processors, with almost negligible impact even at large circuit depths. Our results underscore the role processor geometry plays in classical simulability.
A recent quantum simulation of observables of the kicked Ising model on 127 qubits implemented circuits that exceed the capabilities of exact classical simulation. We show that several approximate classical methods, based on sparse Pauli dynamics and tensor network algorithms, can simulate these observables orders of magnitude faster than the quantum experiment and can also be systematically converged beyond the experimental accuracy. Our most accurate technique combines a mixed Schrödinger and Heisenberg tensor network representation with the Bethe free entropy relation of belief propagation to compute expectation values with an effective wave function-operator sandwich bond dimension >16,000,000, achieving an absolute accuracy, without extrapolation, in the observables of <0.01, which is converged for many practical purposes. We thereby identify inaccuracies in the experimental extrapolations and suggest how future experiments can be implemented to increase the classical hardness.
Belief propagation has recently emerged as a powerful framework for evaluating tensor networks in higher dimensions, combining computational efficiency with provable analytical guarantees. In this work, we develop the first end-to-end theory of tensor network belief propagation for a class of projected entangled pair states satisfying \emph{strong injectivity}. We show that when the injectivity parameter exceeds a constant threshold, BP fixed points can be found efficiently, and a cluster-corrected BP algorithm computes physical quantities to 1/poly(N) error in poly(N) time for an N qubit system. We further identify a striking phenomenon we term \emph{algorithmic locality}: local perturbations of the tensor network affect the BP fixed point with an influence decaying rapidly with distance. Moreover, through the cluster expansion, this locality extends to observables, implying that local expectation values can be approximated from local data with controlled accuracy. We exhibit three regimes admitting strong injectivity: random Gaussian PEPS with large physical dimension, high-temperature Gibbs states of commuting two-body Hamiltonians, and fixed-depth quantum circuits subject to sufficiently strong depolarizing noise. Our bounds are worst-case sufficient conditions and do not identify sharp algorithmic transitions.
For years, the quantum computing community has benchmarked its progress using simplified, independent noise models, leaving us to navigate the complexities of large-scale devices largely by feel. This commentary analyzes Google's recent out-of-time-order correlator (OTOC) experiments on the 65-qubit Willow processor (Nature 646, 825–830, 2025) and proposes that the primary value of the technique is as a new diagnostic tool rather than a pure quantum-advantage benchmark. The method, combining OTOC measurements with a Pauli insertion protocol, provides a direct, quantitative probe of many-body quantum interference. Two quantitative findings anchor the argument: (1) a simple independent-error model undershoots the observed SNR by roughly an order of magnitude (χ²/ν ≈ 14.2; experimental SNR 3.9 vs. model 0.4), and (2) the Pauli-insertion protocol differentiates small-loop and large-loop interference, with 1-ρ ≈ 0.003 for OTOC⁽¹⁾ versus 1-ρ ≈ 0.445 for OTOC⁽²⁾. We score these results against Gil Kalai's 2016 and 2023 predictions about correlated noise, finding direct experimental signatures for most of his claims. This follow-up to the author's 2024 analysis of Google Willow reframes a quantum-advantage result as the first scalable stethoscope for correlated noise in large quantum processors.