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.
AI Summary
The paper asks how long a random quantum circuit remains incompressible when constant approximation error is allowed. It studies sequential all-to-all circuits on $n$ qubits, with each gate Haar-random on a uniformly chosen qubit pair. Complexity counts arbitrary two-qubit gates needed for an operator-norm approximation.
For every $2\le T\le D=4^n-1$, it proves $\mathcal C_{1/2}(U_T)=\Omega(T/\log T)$ except with probability $\exp[-\Omega((T/n^2)(1+\log(D/T)))]$. For $T=O(n^2)$, the failure probability improves to $\exp[-\Omega(T)]$. The complexity bound removes a factor of $n$ relative to the stated bound obtained from the optimal uniform spectral gap, while retaining the exponential time range.
The proof analyzes tangent directions obtained by varying individual gates. Adaptive selectors retain a constant fraction whose frame operator has bounded norm. Integration by parts and a smooth maximum then bound the probability of approaching any target set of size $\exp(cT)$ in normalized Hilbert–Schmidt distance. A circuit-net argument converts this into complexity growth; a separate support-counting argument handles very short circuits. The method avoids high-order designs and uniform moment gaps, but uses second-moment mixing.
Supporting examples include exponentially small small-ball probabilities for random Pauli rotations through $T=O(2^n)$ and complexity growth for Kac’s walk despite its exponentially small spectral gap. The main local-circuit theorem concerns all-to-all connectivity, retains a logarithmic loss, and has system-size-dependent failure probabilities. The Pauli and Kac examples are explicitly not optimized in time range or constants.
No sign of AI-generated textAI use disclosed
In particular, AI proposed and analyzed the final form of the selectors used in that section, which are crucial for our work.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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/logT). 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.
The paper asks how long a random quantum circuit remains incompressible when constant approximation error is allowed. It studies sequential all-to-all circuits on n qubits, with each gate Haar-random on a uniformly chosen qubit pair. Complexity counts arbitrary two-qubit gates needed for an operator-norm approximation.
For every 2≤T≤D=4n−1, it proves C1/2(UT)=Ω(T/logT) except with probability exp[−Ω((T/n2)(1+log(D/T)))]. For T=O(n2), the failure probability improves to exp[−Ω(T)]. The complexity bound removes a factor of n relative to the stated bound obtained from the optimal uniform spectral gap, while retaining the exponential time range.
The proof analyzes tangent directions obtained by varying individual gates. Adaptive selectors retain a constant fraction whose frame operator has bounded norm. Integration by parts and a smooth maximum then bound the probability of approaching any target set of size exp(cT) in normalized Hilbert–Schmidt distance. A circuit-net argument converts this into complexity growth; a separate support-counting argument handles very short circuits. The method avoids high-order designs and uniform moment gaps, but uses second-moment mixing.
Supporting examples include exponentially small small-ball probabilities for random Pauli rotations through T=O(2n) and complexity growth for Kac’s walk despite its exponentially small spectral gap. The main local-circuit theorem concerns all-to-all connectivity, retains a logarithmic loss, and has system-size-dependent failure probabilities. The Pauli and Kac examples are explicitly not optimized in time range or constants.
We prove new lower bounds on the growth of robust quantum circuit complexity -- the minimal number of gates Cδ(U) to approximate a unitary U up to an error of δ in operator norm distance. More precisely we show two bounds for random quantum circuits with local gates drawn from a subgroup of SU(4). First, for δ=Θ(2−n), we prove a linear growth rate: Cδ≥d/poly(n) for random quantum circuits on n qubits with d≤2n/2 gates. Second, for $ δ=Ω(1)$, we prove a square-root growth of complexity: Cδ≥d/poly(n) for all d≤2n/2. Finally, we provide a simple conjecture regarding the Fourier support of randomly drawn Boolean functions that would imply linear growth for constant δ. While these results follow from bounds on the moments of random quantum circuits, we do not make use of existing results on the generation of unitary t-designs. Instead, we bound the moments of an auxiliary random walk on the diagonal unitaries acting on phase states. In particular, our proof is comparably short and self-contained.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n) on n qubits. (i) Random Pauli Rotation: choose an n-qubit Pauli operator P and an angle θ∈[0,2π), both uniformly at random, and apply eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1 unitaries Ui uniformly at random from SU(4) (including central phases of the parent group) independently, and apply U2j−1 on two qubits 2j−1,2j and then U2j on two qubits 2j,2j+1. Importantly, the gap bounds are independent of n and apply for all finite dimensional unitary representations of SU(2n) uniformly.
Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary t-designs after O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be O(2cn) for some c<1. Our unconditional constant spectral gap removes this restriction.
We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal t-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for t=2.
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.
Abstract The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.
Random reversible and quantum circuits form random walks on the alternating group Alt(2n) and unitary group SU(2n), respectively, with each random gate as one step of the walk. Existing bounds on the spectral gap for the t-th moment of these random walks have inverse-polynomial dependence in both n and t. We prove that the gap for random reversible circuits is Ω(n−3) for all t≥1, and the gap for random quantum circuits is Ω(n−3) for t ≤ Θ(2n/2).Importantly, these gaps are independent of t in the respective regimes. We can further improve both gaps to n−1/polylog(n, t) for t ≤ 2Θ(n), which is tight up to polylog factors in n and t. Our spectral gap results have a number of consequences:1)Random reversible circuits with O(n4t) gates form multiplicative-error t-wise independent (even) permutations for all t ≥ 1; for t ≤ Θ(2n/6.1), we show that O~(n2t) gates suffice.2)Random quantum circuits with O(n4t) gates form multiplicative-error unitary t-designs for t ≤Θ(2n/2); for t ≤ Θ(22n/5), we show that O~(n2t) gates suffice.3)The robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, proving the robust Brown–Susskind conjecture [1], [2]. We also show an analogous result for random reversible circuits.Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the "PFC ensemble" from [3] together with an expander on the alternating group due to Kassabov [4], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians.
We study the growth of entanglement and circuit complexity in random passive linear optical networks as a function of the circuit depth. For entanglement dynamics, we start with an initial Gaussian state with all n modes equally squeezed. For random brickwork circuits, we show that entanglement, as measured by the Rényi-2 entropy, grows diffusively as a function of the depth, in contrast to the linear growth for random qubit brickwork circuits. In the other direction, for arbitrary circuit geometries we prove bounds on depths which ensure the average-case subsystem entanglement reaches within a constant factor of the maximum value in all subsystems, and bounds which ensure closeness of the random linear optical unitary to a Haar random unitary in L2 Wasserstein distance. We also consider robust circuit complexity for random one-dimensional brickwall circuits, as measured by the minimum number of gates required in any circuit that approximately implements the linear optical unitary. Viewing this as a function of the number of modes and the circuit depth, we show the robust circuit complexity for random one-dimensional brickwall circuits scales at most diffusively in the depth with high probability, again in contrast to the linear scaling for certain random qubit circuits. The corresponding Gaussian unitary U~ for the approximate implementation retains high output fidelity ∣⟨ψ∣U†U~∣ψ⟩∣2 for pure states ∣ψ⟩ with constrained expected photon-number.