Researchers led by Laura Lewis at Google Quantum AI and the University of California, Berkeley, have developed the first classical algorithm capable of efficiently approximating first-order out-of-time-order correlators (OTOCs) in one-dimensional quantum circuits. These quantities are key to understanding information scrambling and quantum chaos, areas where demonstrating quantum advantage has proven difficult.
The new algorithm, dubbed “window propagation”, works on Haar-random brickwork circuits at arbitrary depths with inverse-polynomial mean-squared error, establishing a foundation for understanding the classical complexity of OTOC estimation. This work represents a family of non-trivial quantum circuits for which a provable, polynomial time algorithm is now known.
Window Propagation Algorithm for 1D OTOC Simulation
The window propagation algorithm achieves polynomial-time classical simulation of first-order out-of-time-order correlators (OTOCs) within one-dimensional brickwork random circuits, a feat previously lacking rigorous guarantees. The algorithm’s success hinges on the constraints of one-dimensional circuits, a deliberate focus that allowed researchers to exploit properties unavailable in more complex, multi-dimensional systems. While quantum computers can efficiently estimate OTOCs through direct state preparation and measurement, no previously established classical algorithm offered comparable speed with provable correctness.
The new method allows for approximation of these quantities with an inverse-polynomial mean-squared error, meaning the accuracy improves rapidly as computational resources increase. Numerical experiments validated the algorithm’s performance, comparing its results to exact computations on Clifford circuits with 768 T-gates and on Haar-random circuits.
The work deliberately focuses on first-order OTOCs in one dimension, acknowledging that current quantum advantage proposals center on estimating second-order OTOCs in two-dimensional circuits. “Our main result is a polynomial-time classical simulation algorithm for in 1D random brickwork circuits of arbitrary depths,” the paper states, clarifying the scope of the achievement. The researchers also note a distinction from related work, highlighting that their algorithm incorporates both window and diameter truncation techniques, while other approaches lack end-to-end correctness proofs or runtime guarantees.
OTOCs as Probes of Quantum Chaos and Scrambling
Beyond the immediate algorithmic achievement, the work contributes to a deeper understanding of the classical complexity surrounding OTOC estimation. The ability to efficiently simulate these quantities in a specific, well-defined system provides a foundation for exploring the boundaries between classical and quantum computational capabilities.
The research highlights the importance of circuit structure in determining computational tractability, suggesting that certain classes of circuits may be more amenable to classical simulation than previously thought. This insight could guide the development of new algorithms and inform the design of future quantum experiments aimed at demonstrating a definitive quantum advantage.
Classical Hardness of OTOC Estimation Remains Open
While recent work has demonstrated sensitivity of OTOCs to circuit details, confirming their relevance in chaotic systems, a rigorously proven, efficient classical algorithm for their estimation remained elusive until now. Further validation involved simulations on Haar-random circuits, providing a benchmark against known values. This comparison confirms the algorithm’s accuracy and scalability within the defined constraints of one-dimensional brickwork circuits. The study’s findings build on previous conjectures and empirical explorations of OTOCs, providing a rigorous mathematical guarantee for the first time.
First-Order OTOCs in Haar-Random Brickwork Circuits
Numerical experiments comparing the new algorithm to exact computation reveal excellent agreement, demonstrating its practical viability for simulating quantum systems. The team tested the “window propagation” algorithm on both 1D brickwork random circuits and Clifford circuits containing 768 T-gates, confirming its accuracy across different circuit types. The algorithm’s efficiency stems from its focus on a specific circuit structure.
Empirical analysis of these circuits shows a wall-clock scaling of approximately to achieve a target accuracy, where n represents the number of qubits. This scaling behavior suggests a pathway toward simulating larger systems, although the researchers acknowledge that the most interesting regime for observing behavior occurs when the circuit depth falls within a specific range, specifically, when |d-5n/3| ≤ c , for a constant c greater than zero.
Outside this range, estimating OTOCs becomes either trivial or approaches zero, highlighting the importance of circuit parameters. They also pose questions about the scalability of these findings to higher dimensions and higher-order OTOCs, areas ripe for future investigation.
Mean-Squared Error and Algorithm Scalability
The researchers focused on the intermediate depth regime, d = Θ(n), where OTOCs exhibit significant instance-to-instance fluctuations, making accurate estimation particularly difficult. Results for both circuit types demonstrate strong agreement with exact simulation, confirming the algorithm’s ability to accurately approximate OTOCs within the defined parameters. This analysis simplifies the problem by showing that bounding the error at each iteration is sufficient to determine the overall error.
Limitations: Algorithm Does Not Extend to 2D OTOCs
Extending the newly developed algorithm to two-dimensional systems presents a significant challenge, as the techniques used to achieve polynomial-time simulation in one dimension do not directly translate. Specifically, the algorithm’s efficiency relies on properties unique to 1D brickwork circuits, and these properties are lost when moving to higher dimensions. A related algorithm, detailed in a separate publication, constrains the duration of these deviations, while the current work restricts them spatially, highlighting a fundamental difference in approach.
The limitations are not absolute, however, and the researchers explored potential avenues for generalization. Outside this range, the simulation either becomes trivial or the circuits behave as unitary designs, rendering the calculations less meaningful. The work emphasizes that while the algorithm represents a step forward, it does not yet provide a solution for simulating quantum chaos in more complex, two-dimensional systems, a goal central to many current quantum advantage proposals.
Establishing Foundations for Quantum Chaos Diagnostics
The ability to efficiently simulate out-of-time-order correlators (OTOCs) in one dimension marks a new benchmark in understanding quantum chaos, as researchers have established the first provably polynomial-time classical algorithm for approximating first-order OTOCs in Haar-random brickwork circuits. Instead, the work establishes a foundational understanding of classical complexity for OTOC estimation within a specific, yet non-trivial, circuit family.
👉 More information
🗞 A provably efficient classical algorithm for simulating OTOC$^{(1)}$ in 1D
✍️ Laura Lewis, Antonio A. Mele, Ronald de Wolf, Jarrod R. McClean and Amira Abbas (Google Quantum AI, Venice, CA, USA)
🧠 ArXiv: https://arxiv.org/abs/2611.24640v1




See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
