PreprintarXiv licencearXiv
One Gate at a Time: Complexity Growth in Random Quantum Circuits
Abstract
A random unitary quantum circuit is expected to be incompressible for exponentially long times. We show that the constant-error circuit complexity of a random unitary circuit grows almost linearly with time as Ω(T/log T). The bound holds for all 2≤ T≤ 4n where n is the system size, and involves no other n-dependence. This improves previous lower bounds derived from spectral gaps and unitary designs by a factor of poly(n). Drawing on insights from stochastic calculus, geometric functional analysis, and randomized linear algebra, our approach exploits the circuit's response to variations of individual gates and requires no control over convergence to high-order unitary designs.
Related
- Spectral gaps and slow modes of Pauli rotations and random quantum circuits
- Sustained growth of quantum circuit complexity in many-body Hamiltonian dynamics
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- Random unitary circuits with constant spectral gap
- A note on the complexity of random subspace model-based methods for derivative-free optimization
BibTeX
@misc{li2026gate,
title = {{One Gate at a Time: Complexity Growth in Random Quantum Circuits}},
author = {Zhi Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17457},
eprint = {2609.17457},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17457},
}
RIS
TY - UNPB
TI - One Gate at a Time: Complexity Growth in Random Quantum Circuits
AU - Zhi Li
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17457
UR - https://arxiv.org/abs/2609.17457
AB - A random unitary quantum circuit is expected to be incompressible for exponentially long times. We show that the constant-error circuit complexity of a random unitary circuit grows almost linearly with time as Ω(T/log T). The bound holds for all 2≤ T≤ 4^n where n is the system size, and involves no other n-dependence. This improves previous lower bounds derived from spectral gaps and unitary designs by a factor of poly(n). Drawing on insights from stochastic calculus, geometric functional analysis, and randomized linear algebra, our approach exploits the circuit's response to variations of individual gates and requires no control over convergence to high-order unitary designs.
ER -