Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.12773

An efficient classical algorithm for OTOCs in chaotic quantum dynamics

Yunchao Liu, Yihui Quek, Shreya Vardhan, Tianci Zhou

Published Nov 9, 2026• 0 citations
arXivHTMLPDF

Abstract

Estimating out-of-time-ordered correlators (OTOCs) in individual instances of random quantum circuits has been proposed as a candidate for verifiable quantum advantage, and demonstrated to be hard for conventional classical algorithms such as tensor networks and Monte Carlo. Using insights from quantum chaos, we develop and implement a polynomial-time classical algorithm for the four-point ${\rm OTOC}^{(1)}$ and the eight-point ${\rm OTOC}^{(2)}$ in typical instances of one-dimensional (1D) quantum circuits. Our results demonstrate average-case classical tractability of estimating OTOCs in the sensitive regime where circuit-to-circuit fluctuations are large. Our algorithm organizes the OTOC into a rapidly converging series, where the leading term includes contributions from histories within permutation degrees of freedom in the replicated Hilbert space, and subleading terms arise from excursions outside this space. Although chaos is often viewed as an insurmountable barrier to classical simulation, our algorithm exploits a form of dephasing caused by chaos, which suppresses the subleading terms. We provide strong theoretical and numerical evidence to support this suppression. Further, we demonstrate that practical implementations of our algorithm estimate ${\rm OTOC}^{(1)}$ and ${\rm OTOC}^{(2)}$ in 1D circuits with high accuracy, achieving higher signal-to-noise ratio at larger circuit depths compared to recent 2D experiments by Google. Extending our algorithm to higher dimensions, and resolving the status of quantum advantage in 2D OTOCs, remain open problems.

DOI
10.48550/arxiv.2611.12773

Related papers

Towards verifiable quantum advantage with random circuits: Observables that survive concentration

Antonio A. Mele, Francesco A. Mele, Jarrod R. McClean +1 more

Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.

quant-pharXiv:2609.37890•Sep 30, 2026•1 citation

Out-of-Time-Order Correlator Spectroscopy

Keisuke Fujii

Out-of-time-order correlators (OTOCs) are central probes of quantum scrambling, and their generalizations have recently become key primitives for both benchmarking quantum advantage and learning the structure of Hamiltonians. Yet their behavior has lacked a unified algorithmic interpretation. We show that higher-order OTOCs naturally fit within the framework of quantum signal processing (QSP): each $\mathrm{OTOC}^{(k)}$ measures the $2k$-th Fourier component of the phase distribution associated with the singular values of a spatially resolved truncated propagator. This explains the contrasting sensitivities of time-ordered correlators (TOCs) and higher-order OTOCs to causal-cone structure and to chaotic, integrable, or localized dynamics. Based on this understanding, we further generalize higher-order OTOCs by polynomial transformation of the singular values of the spatially resolved truncated propagator. The resultant signal allows us to construct frequency-selective filters, which we call \emph{OTOC spectroscopy}. This extends conventional OTOCs into a mode-resolved tool for probing scrambling and spectral structure of quantum many-body dynamics.

quant-pharXiv:2511.22654•Nov 28, 2025•3 citations

Higher Order OTOCs in Chaotic Quantum Maps: Ruelle-Pollicott Resonances and Asymptotic Freeness

Nicolás Gómez Brucks, Ignacio García-Mata, Diego A. Wisniacki

Out-of-time-ordered correlators (OTOCs) measure the scrambling of information and are a powerful diagnostic of chaos. In chaotic quantum systems with a classical analog, their relaxation towards equilibrium is dictated by the classical Ruelle--Pollicott resonances. We investigate higher-order OTOCs in quantum maps, prototypical one-body systems with a classical limit showing all the essential features of chaotic dynamics. We demonstrate numerically that in the intermediate-time regime they decay exponentially at a rate that depends only on the parity of the order: odd-order OTOCs decay at the same rate as classical correlations, given by the leading Ruelle--Pollicott resonance, and even-order ones at twice that rate. Both are far slower than the naive expectation, under which the rate would grow in proportion to the order. We then mimic the effect of an environment by defining a coarse-grained superoperator whose effect is to introduce decoherence into the system, and find that the expected proportionality between rate and order is thereby restored. Finally, we show that at long times each higher-order OTOC becomes dominated by a single free cumulant, whose saturation value falls off inversely with the dimension of the Hilbert space, signalling the emergence of asymptotic freeness and highlighting the relevance of free probability theory as a framework for the study of quantum chaos.

nlin.CDCross-listedarXiv:2610.34615•Oct 27, 2026•0 citations

Probing chaos and thermalization through out-of-time-ordered correlators in random field spin chains

C Jisha, Shivam Mishra, Ravi Prakash

Out-of-time-ordered correlators (OTOCs) have emerged as a diagnostic of information scrambling and quantum chaos in many-body systems. We investigate the imprints of chaos in the dynamics of OTOCs in the Heisenberg spin-$1/2$ chain with random fields. The system is parameterized to exhibit a crossover from integrable to chaotic dynamics. We demonstrate numerically that the approach to saturation of the OTOC can distinguish between integrable and chaotic regimes, with a power-law $(1/t)$ relaxation for integrable systems and a higher-degree power-law decay $(1/t^α; α\ge 1)$ followed by an exponential relaxation for the chaotic regime. We further show that long-range spectral statistics, such as the number variance, are more effective in characterizing quantum chaos in the regime near saturation of OTOC. We also demonstrate that the relaxation and initial scrambling regimes exhibit distinct and universal features, with the former being sensitive and the latter being robust against different realizations of random-fields. The long-time saturation of OTOC also fluctuates with different realizations, and its exact expression is derived through the Eigenstate Thermalization Hypothesis.

quant-pharXiv:2606.18982•Jun 18, 2026•1 citation

Quantum chaos in finite many-body systems

Jakub Novotný

In this work, we show, that relative oscillations in asymptotic times of microcanonical Out-of-Time-Order correlators (OTOCs) are suppressed by chaos with the size of the sys- tem. Therefore they can serve as an indicator of quantum chaos in quantum systems. We demonstrate this phenomenon on numerical results of the Out-of-Time-Order correlators from a model with hamiltonian based on the u(3) algebra. Firstly we prove, that this model can be used not only for the description of molecular vibrations, but also Bose- Einstein condensate. Then we employ several methods for the analysis of both quantum and classical chaos, namely spectral statistics such as Nearest Neighbour Spacing Distri- bution and Brody distribution, Inverse Participation Ratio, Poincaré sections, Lyapunov exponent, and the chaotic fraction of classical phase space. We compare these results with relative oscillations of microcanonical Out-of-Time-Order correlators and show, that their suppression corresponds with the chaoticity of the quantum system and the fraction of chaotic regions of the classical phase space. 1

•Jan 1, 2022•0 citations

Random permutation circuits beyond qubits are quantum chaotic

Bruno Bertini, Katja Klobas, Pavel Kos +1 more

Random permutation circuits were recently introduced as minimal models for local many-body dynamics that can be interpreted both as classical and quantum. Standard dynamical complexity indicators such as damage spreading and out-of-time-order correlators (OTOCs), show that these systems exhibit sensitivity to initial conditions in the classical setting and operator scrambling in the quantum setting. Here, we address their quantum chaoticity—a stricter property—by studying the time evolution of local operator entanglement (LOE). We show that the behavior of LOE in random permutation circuits depends on the dimension of the local configuration space q . When q = 2 , i.e., the circuits act on qubits, random permutations are Clifford and the LOE of any local operator is bounded by a constant, indicating that they are not truly chaotic. On the other hand, when the dimension of the local configuration space exceeds two, the LOE grows linearly in time. We prove this in the limit of large q and present numerical evidence that a three-dimensional local configuration space is sufficient for a linear growth of LOE. Our findings highlight that quantum chaos can be produced by essentially classical dynamics. Moreover, we show that LOE can be defined also in the classical realm and put it forward as a universal indicator chaos, both quantum and classical.

arXiv:2508.10890•Physical review. B./Physical review. B•Dec 30, 2025•6 citations
Estimating out-of-time-ordered correlators (OTOCs) in individual instances of random quantum circuits has been proposed as a candidate for verifiable quantum advantage, and demonstrated to be hard for conventional classical algorithms such as tensor networks and Monte Carlo. Using insights from quantum chaos, we develop and implement a polynomial-time classical algorithm for the four-point OTOC(1){\rm OTOC}^{(1)}OTOC(1) and the eight-point OTOC(2){\rm OTOC}^{(2)}OTOC(2) in typical instances of one-dimensional (1D) quantum circuits. Our results demonstrate average-case classical tractability of estimating OTOCs in the sensitive regime where circuit-to-circuit fluctuations are large. Our algorithm organizes the OTOC into a rapidly converging series, where the leading term includes contributions from histories within permutation degrees of freedom in the replicated Hilbert space, and subleading terms arise from excursions outside this space. Although chaos is often viewed as an insurmountable barrier to classical simulation, our algorithm exploits a form of dephasing caused by chaos, which suppresses the subleading terms. We provide strong theoretical and numerical evidence to support this suppression. Further, we demonstrate that practical implementations of our algorithm estimate OTOC(1){\rm OTOC}^{(1)}OTOC(1) and OTOC(2){\rm OTOC}^{(2)}OTOC(2) in 1D circuits with high accuracy, achieving higher signal-to-noise ratio at larger circuit depths compared to recent 2D experiments by Google. Extending our algorithm to higher dimensions, and resolving the status of quantum advantage in 2D OTOCs, remain open problems.
Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.
Out-of-time-order correlators (OTOCs) are central probes of quantum scrambling, and their generalizations have recently become key primitives for both benchmarking quantum advantage and learning the structure of Hamiltonians. Yet their behavior has lacked a unified algorithmic interpretation. We show that higher-order OTOCs naturally fit within the framework of quantum signal processing (QSP): each OTOC(k)\mathrm{OTOC}^{(k)}OTOC(k) measures the 2k2k2k-th Fourier component of the phase distribution associated with the singular values of a spatially resolved truncated propagator. This explains the contrasting sensitivities of time-ordered correlators (TOCs) and higher-order OTOCs to causal-cone structure and to chaotic, integrable, or localized dynamics. Based on this understanding, we further generalize higher-order OTOCs by polynomial transformation of the singular values of the spatially resolved truncated propagator. The resultant signal allows us to construct frequency-selective filters, which we call \emph{OTOC spectroscopy}. This extends conventional OTOCs into a mode-resolved tool for probing scrambling and spectral structure of quantum many-body dynamics.
Out-of-time-ordered correlators (OTOCs) measure the scrambling of information and are a powerful diagnostic of chaos. In chaotic quantum systems with a classical analog, their relaxation towards equilibrium is dictated by the classical Ruelle--Pollicott resonances. We investigate higher-order OTOCs in quantum maps, prototypical one-body systems with a classical limit showing all the essential features of chaotic dynamics. We demonstrate numerically that in the intermediate-time regime they decay exponentially at a rate that depends only on the parity of the order: odd-order OTOCs decay at the same rate as classical correlations, given by the leading Ruelle--Pollicott resonance, and even-order ones at twice that rate. Both are far slower than the naive expectation, under which the rate would grow in proportion to the order. We then mimic the effect of an environment by defining a coarse-grained superoperator whose effect is to introduce decoherence into the system, and find that the expected proportionality between rate and order is thereby restored. Finally, we show that at long times each higher-order OTOC becomes dominated by a single free cumulant, whose saturation value falls off inversely with the dimension of the Hilbert space, signalling the emergence of asymptotic freeness and highlighting the relevance of free probability theory as a framework for the study of quantum chaos.
Out-of-time-ordered correlators (OTOCs) have emerged as a diagnostic of information scrambling and quantum chaos in many-body systems. We investigate the imprints of chaos in the dynamics of OTOCs in the Heisenberg spin-1/21/21/2 chain with random fields. The system is parameterized to exhibit a crossover from integrable to chaotic dynamics. We demonstrate numerically that the approach to saturation of the OTOC can distinguish between integrable and chaotic regimes, with a power-law (1/t)(1/t)(1/t) relaxation for integrable systems and a higher-degree power-law decay (1/tα;α≥1)(1/t^α; α\ge 1)(1/tα;α≥1) followed by an exponential relaxation for the chaotic regime. We further show that long-range spectral statistics, such as the number variance, are more effective in characterizing quantum chaos in the regime near saturation of OTOC. We also demonstrate that the relaxation and initial scrambling regimes exhibit distinct and universal features, with the former being sensitive and the latter being robust against different realizations of random-fields. The long-time saturation of OTOC also fluctuates with different realizations, and its exact expression is derived through the Eigenstate Thermalization Hypothesis.
In this work, we show, that relative oscillations in asymptotic times of microcanonical Out-of-Time-Order correlators (OTOCs) are suppressed by chaos with the size of the sys- tem. Therefore they can serve as an indicator of quantum chaos in quantum systems. We demonstrate this phenomenon on numerical results of the Out-of-Time-Order correlators from a model with hamiltonian based on the u(3) algebra. Firstly we prove, that this model can be used not only for the description of molecular vibrations, but also Bose- Einstein condensate. Then we employ several methods for the analysis of both quantum and classical chaos, namely spectral statistics such as Nearest Neighbour Spacing Distri- bution and Brody distribution, Inverse Participation Ratio, Poincaré sections, Lyapunov exponent, and the chaotic fraction of classical phase space. We compare these results with relative oscillations of microcanonical Out-of-Time-Order correlators and show, that their suppression corresponds with the chaoticity of the quantum system and the fraction of chaotic regions of the classical phase space. 1
Random permutation circuits were recently introduced as minimal models for local many-body dynamics that can be interpreted both as classical and quantum. Standard dynamical complexity indicators such as damage spreading and out-of-time-order correlators (OTOCs), show that these systems exhibit sensitivity to initial conditions in the classical setting and operator scrambling in the quantum setting. Here, we address their quantum chaoticity—a stricter property—by studying the time evolution of local operator entanglement (LOE). We show that the behavior of LOE in random permutation circuits depends on the dimension of the local configuration space q . When q = 2 , i.e., the circuits act on qubits, random permutations are Clifford and the LOE of any local operator is bounded by a constant, indicating that they are not truly chaotic. On the other hand, when the dimension of the local configuration space exceeds two, the LOE grows linearly in time. We prove this in the limit of large q and present numerical evidence that a three-dimensional local configuration space is sufficient for a linear growth of LOE. Our findings highlight that quantum chaos can be produced by essentially classical dynamics. Moreover, we show that LOE can be defined also in the classical realm and put it forward as a universal indicator chaos, both quantum and classical.