One Gate at a Time: Complexity Growth in Random Quantum Circuits

• URL: http://arxiv.org/abs/2609.17457v1
• Date: Tue, 15 Sep 2026 16:58:25 GMT
• Title: One Gate at a Time: Complexity Growth in Random Quantum Circuits
• Abstract summary: We show that the constant error circuit complexity of a random unitary circuit grows almost linearly with time as $(T/log T)$.<n>This improves previous lower bounds derived from spectral gaps and unitary designs by a factor of $mathrmpoly(n)$.
• Score: 3.34407072562438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\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 response to variations of individual gates and requires no control over convergence to high-order unitary designs.

Related papers

• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• Transmutation based Quantum Simulation for Non-unitary Dynamics [35.35971148847751]
  We present a quantum algorithm for simulating dissipative diffusion dynamics generated by positive semidefinite operators of the form $A=Ldagger L$.<n>Our main tool is the Kannai transform, which represents the diffusion semigroup $e-TA$ as a Gaussian-weighted superposition of unitary wave propagators.
  arXiv  Detail & Related papers  (2026-01-07T05:47:22Z)
• Quantum Relative Entropy Decay Composition Yields Shallow, Unstructured k-Designs [0.40611352512781856]
  A major line of questions in quantum information and computing asks how quickly locally random circuits converge to resemble global randomness.<n>It was recently shown that on n qudits, random circuits with slightly structured architectures converge to k-designs in depth O(log n), even on one-dimensional connectivity.<n>We show that a constant number of layers of a parallel random circuit on a family of architectures including one-dimensional brickwork' has O(logn) per-layer multiplicative entropy decay.
  arXiv  Detail & Related papers  (2025-10-09T17:53:27Z)
• Strong random unitaries and fast scrambling [37.03163411089211]
  We show that strong unitary designs can form in circuit depth $O(log2 n)$ in circuits composed of independent two-qubit Haar-random gates.<n>Our results provide an operational proof of the fast scrambling conjecture from black hole physics.
  arXiv  Detail & Related papers  (2025-09-30T14:23:46Z)
• Quantum complexity and localization in random and time-periodic unitary circuits [0.0]
  We study the growth and saturation of Krylov spread (K-) complexity under random quantum circuits.<n>Our numerical analysis encompasses two classes of random circuits: brick-wall random unitary circuits and Floquet random circuits.
  arXiv  Detail & Related papers  (2024-09-05T16:10:54Z)
• Incompressibility and spectral gaps of random circuits [2.359282907257055]
  reversible and quantum circuits form random walks on the alternating group $mathrmAlt (2n)$ and unitary group $mathrmSU (2n)$, respectively.<n>We prove that the gap for random reversible circuits is $Omega(n-3)$ for all $tgeq 1$, and the gap for random quantum circuits is $Omega(n-3)$ for $t leq Theta(2n/2)$.
  arXiv  Detail & Related papers  (2024-06-11T17:23:16Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• Unitary k-designs from random number-conserving quantum circuits [0.0]
  Local random circuits scramble efficiently and accordingly have a range of applications in quantum information and quantum dynamics. We show that finite moments cannot distinguish the ensemble that local random circuits generate from the Haar ensemble on the entire group of number-conserving unitaries.
  arXiv  Detail & Related papers  (2023-06-01T18:00:00Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.<n>This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  We prove new lower bounds on the growth of robust quantum circuit complexity. We show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$.
  arXiv  Detail & Related papers  (2023-03-29T18:06:03Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.