REVIEW 7 cited by
Incompressibility and spectral gaps of random circuits
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Random reversible and quantum circuits form random walks on the alternating group $\mathrm{Alt}(2^n)$ and unitary group $\mathrm{SU}(2^n)$, respectively. Known 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 $\Omega(n^{-3})$ for all $t\geq 1$, and the gap for random quantum circuits is $\Omega(n^{-3})$ for $t \leq \Theta(2^{n/2})$. These gaps are independent of $t$ in the respective regimes. We can further improve both gaps to $n^{-1}/\mathrm{polylog}(n, t)$ for $t\leq 2^{\Theta(n)}$, which is tight up to polylog factors. Our spectral gap results have a number of consequences: 1) Random reversible circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error $t$-wise independent (even) permutations for all $t\geq 1$; for $t \leq \Theta(2^{n/6.1})$, we show that $\tilde{\mathcal{O}}(n^2 t)$ gates suffice. 2) Random quantum circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error unitary $t$-designs for $t \leq \Theta(2^{n/2})$; for $t\leq \Theta(2^{2n/5})$, we show that $\tilde{\mathcal{O}}(n^2t)$ gates suffice. 3) The robust quantum circuit complexity of random circuits grows linearly for an exponentially long time, proving the robust Brown--Susskind conjecture [BS18,BCHJ+21]. Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the ``$\mathrm{PFC}$ ensemble'' from [MPSY24] together with an expander on the alternating group due to Kassabov [Kas07a], 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.
Forward citations
Cited by 7 Pith papers
-
Apparent Universal Behavior in Second Moments of Random Quantum Circuits
Most random circuit geometries form approximate 2-designs in O(log n) depth with explicit constants; bridge/lollipop graphs need Ω(n²) gates, and 10-20 layers suffice for 50-qubit near-random circuits.
-
Growth and collapse of subsystem complexity under random unitary circuits
Under random brickwork circuits, regions larger than half the system have complexity growing linearly in time, while a smaller region thermalizes to essentially zero complexity by T=ℓ/2 — with holographic and replica ...
-
Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms
Clebsch-Gordan transforms give exact compressed oracles for Haar-random unitary group actions, with efficient circuits for U(d).
-
Resource quantification for programming low-depth quantum circuits
A tight worst-case program cost of Θ(N polylog N) qubits is established for programming low-depth brickwork quantum circuits on N qubits.
-
Shallow quantum circuit for generating extremely low-entangled approximate state designs
Approximate state t-designs can be built from low-entanglement states via random injective maps, but the claimed tight lower bound on magic fails for small t since stabilizer states form an exact 2-design with zero magic.
-
Anti-concentration is (almost) all you need
For LU-invariant local random quantum circuits, anti-concentration implies a relative-error state 2-design with error ≈ 4× the anti-concentration error, making the two properties equivalent.
-
Thermalization with partial information
A maximum channel entropy principle, backed by a microcanonical-style derivation, identifies the canonical noisy channel that models thermalization under partial information.
Discussion (0). Sign in to comment.