Towards verifiable quantum advantage with random circuits: Observables that survive concentration
Abstract
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.
Related
- Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
- Verifiable quantum advantage in extremely low depth
- Verifiable quantum advantage based on polynomials with planted structures
- Leveraging verifiable structure in quantum circuits to find more efficient compilations with agentic AI
- Experimentally Testable Quantum Advantage in Shallow Circuits
BibTeX
@misc{mele2026towards,
title = {{Towards verifiable quantum advantage with random circuits: Observables that survive concentration}},
author = {Antonio A. Mele and Francesco A. Mele and Jarrod R. McClean and Thomas E. O'Brien},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37890},
eprint = {2609.37890},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37890},
}
RIS
TY - UNPB
TI - Towards verifiable quantum advantage with random circuits: Observables that survive concentration
AU - Antonio A. Mele
AU - Francesco A. Mele
AU - Jarrod R. McClean
AU - Thomas E. O'Brien
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37890
UR - https://arxiv.org/abs/2609.37890
AB - 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.
ER -