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.
AI Summary
The paper asks whether fixed-order out-of-time-order correlators (OTOCs) retain inverse-polynomial circuit-to-circuit fluctuations at depths where information has propagated across a local random circuit. Such fluctuations are necessary for instance-dependent, reproducible observable-estimation tasks proposed for quantum advantage.
For every fixed order $k$, it proves inverse-polynomial variance at suitable depths for broad bounded-degree local architectures, including fixed-dimensional lattices, arbitrary input states, and suitable non-Haar gate ensembles. The argument converts a change $\Delta$ in the ensemble mean over a depth interval of width $W$ into variance $\Omega(\Delta^2/W^2)$ at some depth. It combines finite-dimensional reverse-variance inequalities for constant-size random gate blocks with unitary-design convergence, which certifies that the mean moves away from its pre-light-cone value of $1$. A persistence bound extends non-concentration across $\Omega(\log n)$ consecutive depths.
For first-order endpoint OTOCs in one-dimensional Haar brickwork circuits, the mean transitions near depth $5n/3$ within a $\Theta(\sqrt n)$ window. Throughout this window, variance is $\Omega(n^{-1/2})$, uniformly over input states. Single-gate conditional-mean analysis identifies $\Theta(n^{3/2})$ gates with orthogonal contributions of $\Omega(n^{-2})$, arranged in an eye-shaped region of layerwise width $O(\sqrt n)$.
For the infinite-temperature first-order OTOC at the critical depth, averaging outside an enlarged eye and sampling conditional Pauli distributions yields runtime $\operatorname{poly}(n)2^{O(\sqrt{n\log n})}$ for inverse-polynomial accuracy and failure probability. Classical hardness remains unproved; variance upper bounds and tight scaling are unknown. The general higher-order theorem locates fluctuations only existentially, and the gate-level characterization and simulation guarantee do not extend to higher orders.
Little sign of AI-generated textAI use disclosed
GPT-5.5 was used extensively during the research process to explore and refine proof ideas and to perform numerical experiments that guided intuition about what to prove next.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks whether fixed-order out-of-time-order correlators (OTOCs) retain inverse-polynomial circuit-to-circuit fluctuations at depths where information has propagated across a local random circuit. Such fluctuations are necessary for instance-dependent, reproducible observable-estimation tasks proposed for quantum advantage.
For every fixed order k, it proves inverse-polynomial variance at suitable depths for broad bounded-degree local architectures, including fixed-dimensional lattices, arbitrary input states, and suitable non-Haar gate ensembles. The argument converts a change Δ in the ensemble mean over a depth interval of width W into variance Ω(Δ2/W2) at some depth. It combines finite-dimensional reverse-variance inequalities for constant-size random gate blocks with unitary-design convergence, which certifies that the mean moves away from its pre-light-cone value of 1. A persistence bound extends non-concentration across Ω(logn) consecutive depths.
For first-order endpoint OTOCs in one-dimensional Haar brickwork circuits, the mean transitions near depth 5n/3 within a Θ(n) window. Throughout this window, variance is Ω(n−1/2), uniformly over input states. Single-gate conditional-mean analysis identifies Θ(n3/2) gates with orthogonal contributions of Ω(n−2), arranged in an eye-shaped region of layerwise width O(n).
For the infinite-temperature first-order OTOC at the critical depth, averaging outside an enlarged eye and sampling conditional Pauli distributions yields runtime poly(n)2O(nlogn) for inverse-polynomial accuracy and failure probability. Classical hardness remains unproved; variance upper bounds and tight scaling are unknown. The general higher-order theorem locates fluctuations only existentially, and the gate-level characterization and simulation guarantee do not extend to higher orders.
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) and the eight-point 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) and 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.
Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback remains: verification seems to require classical computation exponential in the system size, n. As an attempt to overcome this difficulty, we propose a new candidate for quantum advantage experiments with otherwise random "peaked circuits", i.e., quantum circuits whose outputs have high concentrations on a computational basis state. Naturally, the heavy output string can be used for classical verification. In this work, we analytically and numerically study an explicit model of peaked circuits, in which τr layers of uniformly random gates are augmented by τp layers of gates that are optimized to maximize peakedness. We show that getting 1/poly(n) peakedness from such circuits requires τp=Ω((τr/n)0.19) with overwhelming probability. However, we also give numerical evidence that nontrivial peakedness is possible in this model -- decaying exponentially with the number of qubits, but more than can be explained by any approximation where the output of a random quantum circuit is treated as a Haar-random state. This suggests that these peaked circuits have the potential for future verifiable quantum advantage experiments. Our work raises numerous open questions about random peaked circuits, including how to generate them efficiently, and whether they can be distinguished from fully random circuits in classical polynomial time.
We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δ, with parallel runtime 2O(d)loglog(n/δ) and n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within exp(−Ω(mlogm)) additive error is hard for any classical computer, where m is the number of gates in the quantum computation. More precisely, we show that the above problem is #P-hard under BPPNP reduction. In the recent experiments, the quantum circuit has n-qubits and the architecture is a two-dimensional grid of size n×n. Indeed for constant depth circuits approximating the output probabilities to within 2−Ω(nlogn) is hard. For circuits of depth logn or n for which the anti-concentration property holds, approximating the output probabilities to within 2−Ω(nlog2n) and 2−Ω(n3/2logn) is hard respectively. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.
We construct protocols for classically verifiable quantum advantage and classical verification of BQP computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of BQP=BPP, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493).
We also construct two simple protocols for classically verifying arbitrary BQP computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of BQP computations under computational assumptions in the standard model.
As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.