The spectral gap of local random quantum circuits is a fundamental property that determines how close the moments of the circuit's unitaries match those of a Haar random distribution. When studying spectral gaps, it is common to bound these quantities using tools from statistical mechanics or via quantum information-based inequalities. By focusing on the second moment of one-dimensional unitary circuits where nearest-neighboring gates act on sets of qudits (with open and closed boundary conditions), we show that one can exactly compute the associated spectral gaps. Indeed, having access to their functional form allows us to prove several important results, such as the fact that the spectral gap for closed boundary condition is exactly the square of the gap for open boundaries, as well as improve on previously known bounds for approximate design convergence. Finally, we verify our theoretical results by numerically computing the spectral gap for systems of up to 70 qubits, as well as comparing them to gaps of random orthogonal and symplectic circuits.
A fundamental question is understanding the rate at which random quantum circuits converge to the Haar measure. One quantity which is important in establishing this rate is the spectral gap of a random quantum ensemble. In this work we establish a new bound on the spectral gap of the t-th moment of a one-dimensional brickwork architecture on N qudits. This bound is independent of both t and N, provided t does not exceed the qudit dimension q. We also show that the bound is nearly optimal. The improved spectral gaps gives large improvements to the constant factors in known results on the approximate t-design depths of the 1D brickwork, of generic circuit architectures, and of specially-constructed architectures which scramble in depth O(log N). We moreover show that the spectral gap gives the dominant epsilon-dependence of the t-design depth at small epsilon. Our spectral gap bound is obtained by bounding the N-site 1D brickwork architecture by the spectra of 3-site operators. We then exploit a block-triangular hierarchy and a global symmetry in these operators in order to efficiently bound them. The technical methods used are a qualitatively different approach for bounding spectral gaps and and have little in common with previous techniques.
Random quantum circuits are a central concept in quantum information theory with applications ranging from demonstrations of quantum computational advantage to descriptions of scrambling in strongly interacting systems and black holes. The utility of random quantum circuits in these settings stems from their ability to rapidly generate quantum pseudorandomness. In a seminal paper by Brand\~ao, Harrow, and Horodecki [Commun. Math. Phys. 346, 397 (2016)] it was proven that the
tth moment operator of local random quantum circuits on
n qudits with local dimension
q has a spectral gap of at least $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1}{t}^{\ensuremath{-}5\ensuremath{-}3.1/ln(q)})$, which implies that they are efficient constructions of approximate unitary designs. As a first result, we use Knabe bounds for the spectral gaps of frustration-free Hamiltonians to show that one-dimensional random quantum circuits have a spectral gap scaling as $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1})$, provided that
t is small compared to the local dimension: ${t}^{2}\ensuremath{\le}O(q)$. This implies a (nearly) linear scaling of the circuit depth in the design order
t. Our second result is an unconditional spectral gap bounded below by $\mathrm{\ensuremath{\Omega}}[{n}^{\ensuremath{-}1}{ln}^{\ensuremath{-}1}(n){t}^{\ensuremath{-}\ensuremath{\alpha}(q)}]$ for random quantum circuits with all-to-all interactions. This improves both the
n and
t scaling in design depth for the nonlocal model. We show this by proving a recursion relation for the spectral gaps involving an auxiliary random walk. Lastly, we solve the smallest nontrivial case exactly and combine with numerics and Knabe bounds to improve the constants involved in the spectral gap for small values of
t.
Random circuits giving rise to unitary designs are key tools in quantum information science and many-body physics. In this work, we investigate a class of random quantum circuits with a specific gate structure. Within this framework, we prove that one-dimensional structured random circuits with non-Haar-random local gates can exhibit substantially more global randomness compared to Haar-random circuits with the same underlying circuit architecture. In particular, under a solvability condition, we exactly diagonalize the second-moment operators for these structured random circuits by establishing a link to free-fermionic models, and we show that their spectral gaps can exceed those of Haar-random circuits. While solvable structured random circuits exhibit free-fermionic behavior, the underlying fixed gate need not be a matchgate. Our findings have applications in improving circuit depth bounds for randomized benchmarking, in generating approximate unitary 2-designs from shallow random circuits, and in enabling exact analyses of quantum many-body dynamics.
The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.
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) independently, and apply
U2j−1 on two qubits
2j−1,2j and then
U2j on two qubits
2j,2j+1. Importantly, the spectral gap lower bounds are independent of
n and apply for all finite dimensional unitary representations of
SU(2n) uniformly, including those that appear in unitary
t-designs. We also prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit.
We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed
2-qudit interactions. Prior work has established that such
n-qudit circuits with local dimension
q on 1D, complete, and
D-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group
U(qn) after polynomially many gates. Here, we extend those results by proving that RQCs comprised of
O(poly(n,k)) gates on a wide class of graphs form approximate unitary
k-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form
k-designs after
O(∣E∣npoly(k)) gates, where
∣E∣ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For
k≤4, we show that RQCs on graphs of certain maximum degrees form designs after
O(∣E∣n) gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.