{"id":"arxiv/2609.17457","url":"https://arxiv.org/abs/2609.17457","tags":["quant-ph","math-ph"],"score":0,"title":"One Gate at a Time: Complexity Growth in Random Quantum Circuits","domain":"quant-ph","source":"arxiv","authors":["Zhi Li"],"reviews":0,"subject":"quant-ph","summary":"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\\leq T\\leq 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 $\\mathrm{poly}(n)$. Drawing on insights from stochastic calculus, geometric functional analysis, and randomized linear algebra, our approach exploits the circuit's…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}