Quantum computing · Theory and numerics (AI-assisted)
A provably efficient classical algorithm for simulating OTOC(1) in 1D
arXiv:2611.24640v1 ↗PDF ↗Submitted 18 November 2026
- Question
- Out-of-time-order correlators (OTOCs) of random circuits keep a circuit-dependent signal at depths where ordinary correlators have decayed, and estimating them has been proposed and demonstrated as a route to quantum advantage. Their ensemble mean can be computed classically; the hard part is the fluctuation from one circuit to the next at depths linear in the number of qubits. For the simplest case, first-order OTOCs of one-dimensional random brickwork circuits, classical heuristics work well in practice, and a recent algorithm needs an unproved assumption. Is there a classical algorithm with a proof?
- Result
- Yes. Window propagation evolves the two-copy butterfly operator backwards through the circuit, truncates it after each layer to terms whose departure from the Haar-invariant operators is confined to a window of logarithmic width, and reads off the OTOC. For Haar-random brickwork circuits on \(n\) qubits of any depth \(d\) its output has mean-squared error at most \(\varepsilon\), averaged over circuits, in time polynomial in \(n\), \(d\) and \(1/\varepsilon\). The guarantee also holds for two-qubit gates forming a 4-design. In numerics a window of three sites already tracks exact values for 22-qubit circuits of depth 32, the error falls quickly with the window and barely depends on system size, and the run time grows roughly as \(n^{2.26}\) (2.1 s for 100 qubits).
The paper in detail
For a circuit \(U\), a butterfly operator \(B=X_n\) at one end of a chain and a measurement operator \(M=Z_1\) at the other, the \(K\)th-order OTOC is \(f^{(K)}(U)=\operatorname{tr}\bigl((U^\dagger BUM)^{2K}\rho\bigr)\). The paper treats \(K=1\) at infinite temperature, \(\rho=\mathbb I/2^n\), for brickwork circuits of Haar-random two-qubit gates. At small depth the light cone of \(U^\dagger BU\) misses \(M\), the operators commute and \(f=1\); at large depth the circuit is close to a unitary design and \(f\approx0\). In between, at depths linear in \(n\), the value fluctuates from circuit to circuit, and estimating it for a given circuit to mean-squared error \(\varepsilon\) is the task. A quantum computer does this with a simple interferometric circuit; the question is whether a classical computer can too.
Window propagation rewrites \(f^{(1)}\) with the swap trick as a linear functional of the two-copy operator \((U^\dagger BU)^{\otimes2}\) and evolves it backwards layer by layer. On each pair of corresponding qubits it uses a basis containing the identity \(\mathbb I\), the swap \(\mathbb F\), and fourteen operators orthogonal to both. Averaged over random gates, the evolved operator is a combination of products of \(\mathbb I\) and \(\mathbb F\), with an identity region on one side, a flip region on the other, and a moving wall between them; that average is what earlier Monte Carlo methods compute. A particular circuit deviates from it, and the algorithm keeps the deviation only where it matters: after each layer it drops terms whose non-invariant sites span more than \(k\) sites (diameter truncation), and it projects onto terms of the form identity, then an arbitrary operator on at most \(w=3k\) sites, then flip (window truncation).
The proof bounds the two truncations separately and adds the errors over the \(d/2\) iterations. Inserting independent single-qubit Haar gates, which leaves the circuit distribution unchanged, makes the evolved butterfly and the forward-evolved measurement operator independent at any cut. Non-invariant sites far apart then contribute only through the overlap of two independent random operators, which decays as \(\alpha^k\). Once the non-invariant part is confined to \(k\) sites, any term wider than \(3k\) must be invariant on a block of \(k\) sites on one side, where the Haar projection halves the average weight per site. With \(k=O(\log(d/\varepsilon))\) both errors are below \(\varepsilon\), and the number of retained terms is polynomial.
In practice the diameter truncation turned out to be redundant, the best error at each width being attained without it, and the error decays rapidly with \(w\) with only weak dependence on \(n\), suggesting a width of order \(\log(1/\varepsilon)\), which the authors leave open. They also benchmark 512-qubit Clifford circuits with 768 randomly placed \(T\) gates against exact simulation. The natural extension to second-order OTOCs replaces identity and flip by the 24 permutations of four copies, but random gates crossing an interface create new permutation regions, so a bounded-interface ansatz is not preserved; in two dimensions the analogue of the wall becomes a membrane. Both are left open.
Transferable methods
Identity–flip structure of the two-copy evolved butterfly
The first-order OTOC is quadratic in the evolved butterfly, so it is linear in its two-copy tensor power. Haar averages of two-copy operators are spanned by the identity and swap on each pair of qubits, and these are left unchanged by every later gate. Writing the evolved operator as this invariant background plus a deviation is what makes a local truncation meaningful.
For any operators, \(\operatorname{tr}(XY)=\operatorname{tr}\bigl((X\otimes Y)\mathbb F\bigr)\), so \[f^{(1)}(U)=\frac1{2^n}\operatorname{tr}\bigl((U^\dagger BUM)^2\bigr)=\frac1{2^n}\operatorname{tr}\bigl((U^\dagger BU)^{\otimes2}(M\otimes M)\,\mathbb F_{\mathrm{all}}\bigr).\] For a Haar-random gate on a system of dimension \(D\) the second-moment average is \(\mathbb E_G[(G^\dagger AG)^{\otimes2}]=c_{\mathbb I}\mathbb I+c_{\mathbb F}\mathbb F\) with \(c_{\mathbb I}=(\operatorname{tr}A-\operatorname{tr}(A\mathbb F)/D)/(D^2-1)\) and \(c_{\mathbb F}=(\operatorname{tr}(A\mathbb F)-\operatorname{tr}A/D)/(D^2-1)\).
Editorial step: for the first gate touching \(B=X_n\), \(A=(\mathbb I\otimes X)^{\otimes2}\) on a two-qubit system, \(D=4\), \(\operatorname{tr}A=0\) and \(\operatorname{tr}(A\mathbb F)=\operatorname{tr}\bigl((\mathbb I\otimes X)^2\bigr)=4\), which gives \(-\tfrac1{15}\mathbb I+\tfrac4{15}\mathbb F\) on that pair, Eq. (III.5). A gate whose two sites carry \(\mathbb I\) and \(\mathbb F\) averages to \(\tfrac25(\mathbb I\mathbb I+\mathbb F\mathbb F)\), and uniform pairs are fixed. In the final trace each site contributes 1 for \(\mathbb I\) and 2 for \(\mathbb F\), except that \(\mathbb F\) on the site of \(M=Z_1\) contributes 0. The mean OTOC is therefore a random walk of the wall between an identity region and a flip region, which is how the average over circuits is computed exactly.
Editorial check: exact simulation of 150 Haar brickwork circuits on 8 qubits gives means of 1.000, 0.715, 0.451, 0.263, 0.161 at depths 4, 8, 10, 12, 14, against 1.000, 0.720, 0.452, 0.266, 0.151 from this wall random walk. The circuit-to-circuit standard deviation is 0.165 at depth 8 and 0.160 at depth 10, which is the circuit-specific signal an algorithm must capture beyond the mean.
How to reuse it
Any quantity quadratic in an evolved operator (purities, Rényi-2 entropies, frame potentials, cross-entropy benchmarks) can be written as a linear functional of a two-copy operator and organised by its deviation from the Haar-invariant permutation operators. Tracking only the deviation is a natural starting point for simulation algorithms with average-case guarantees.
Two truncations and why their errors are exponentially small
Two locality statements justify the cuts. Sites where the operator is non-invariant and that lie far apart contribute only through the overlap of two independent random operators, which is exponentially small in their distance. A term wider than the retained window must be invariant over a whole block of sites on one side, and the Haar projection removes a constant fraction of a term's weight on each such site.
Diameter truncation discards a basis term \(A\) when \(\operatorname{diam}(S_A)>k\), where \(S_A\) is the set of sites on which \(A\) is not in \(\operatorname{span}\{\mathbb I,\mathbb F\}\). It is an orthogonal projection, so the total error is bounded by the sum of single-iteration errors. At iteration \(j\) the circuit is cut at that layer: the backward-evolved butterfly and the forward-evolved measurement operator depend on disjoint, independent gates, and only sites inside both light cones can change the OTOC. Bounding the overlap of the two independent random operators on an interval of length \(k\) gives \[\mathbb E_U\bigl|g_k(U)-f^{(1)}(U)\bigr|^2\le O(d\,\alpha^k)\] for a universal \(0<\alpha<1\).
For the window truncation, split the chain into a prefix, a block \(L\) of \(k\) sites, a middle block of \(k\) sites, a block \(R\) of \(k\) sites and a suffix. A term of width above \(3k\) whose non-invariant sites span at most \(k\) must be invariant on all of \(L\) or all of \(R\), so \((\mathrm{id}-\mathrm{Proj}_L)(\mathrm{id}-\mathrm{Proj}_R)A=0\) and \(\mathbb E\|A\|_F^2\le\mathbb E\|\mathrm{Proj}_LA\|_F^2+\mathbb E\|\mathrm{Proj}_RA\|_F^2\). For a random Pauli product the projection keeps \(\mathbb I\otimes\mathbb I\), maps \(Q\otimes Q\) to \(\tfrac13(XX+YY+ZZ)\) and kills mismatched pairs, so per site \[\mathbb E\,\frac{\|\mathrm{Proj}_i(P_i\otimes P_i)\|_F^2}{\|\mathbb I\otimes\mathbb I\|_F^2}=\frac14+\frac34\cdot\frac13=\frac12,\] and over \(k\) sites \(2^{-k}\). The appendix extends this to the actual evolved terms, giving \(O(d\,2^{-k})\).
Editorial check: computing the projection onto \(\operatorname{span}\{\mathbb I,\mathbb F\}\) with the Hilbert–Schmidt Gram matrix, which is needed because \(\mathbb I\) and \(\mathbb F\) are not orthogonal, reproduces the factor \(\tfrac12\) exactly. With both errors \(O(d\alpha^k)+O(d2^{-k})\le\varepsilon\) for \(k=O(\log(d/\varepsilon))\), a window of width \(3k\) holds \(16^{3k}=\mathrm{poly}(d/\varepsilon)\) basis terms at each of \(O(n)\) positions, which gives the polynomial run time.
How to reuse it
Average-case guarantees for operator-truncation methods (Pauli propagation, light-cone and tensor-network truncations) can often be proved the same way: cut the circuit, use independence of the two halves to bound long-range contributions, and use the per-site contraction of a Haar projection to bound wide ones.
Context & limitations
Why it matters. This is the first classical algorithm for any OTOC with a rigorous accuracy and run-time guarantee. It turns earlier numerical evidence, including the membrane cluster expansion of Liu, Quek, Vardhan and Zhou (arXiv:2611.12773, covered on this page on 11 November), into a theorem for first-order OTOCs without the bubble-suppression assumption that work needs. It identifies a non-trivial family of circuits, inside the regime where OTOCs fluctuate, that is provably easy, and so narrows the search for advantage to higher-order OTOCs in two dimensions, which is what the advantage experiments use.
Limitations. The guarantee is on average over Haar-random brickwork circuits, with high-probability additive error obtained through Markov's inequality, not for worst-case circuits; worst-case estimation of these quantities is DQC1- or BQP-complete. It covers first-order OTOCs in one dimension only and does not apply to the second-order OTOCs in two dimensions of recent advantage proposals; Section VII explains why the natural generalisations meet obstacles. The proven window width grows as \(\log(d/\varepsilon)\) with large constants, and the operation count is \(O(n^3d)\) at fixed width; the numerically observed sufficiency of a width independent of \(n\) is unproven. Extensions to the zero state and to butterfly and measurement operators in the bulk are announced for later work. The authors state that key sticking points of the proof were resolved in sessions with ChatGPT 6 Astra after earlier models had failed, that they verified and simplified the full proof, and that GPT Codex, Claude 5.5 and Fable assisted with numerics and figures.