We consider a class of random quantum circuits where at each step a gate from a universal set is applied to a random pair of qubits, and determine how quickly averages of arbitrary finite-degree polynomials in the matrix elements of the resulting unitary converge to Haar measure averages. This is accomplished by mapping the superoperator that describes t order moments on n qubits to a multilevel SU(4^{t}) Lipkin-Meshkov-Glick Hamiltonian. We show that, for arbitrary fixed t, the ground-state manifold is exactly spanned by factorized eigenstates and, under the assumption that a mean-field ansatz accurately describes the low-lying excitations, the spectral gap scales as 1/n in the thermodynamic limit. Our results imply that random quantum circuits yield an efficient implementation of ϵ approximate unitary t designs.
We consider a class of random quantum circuits where at each step a gate from a universal set is applied to a random pair of qubits, and determine how quickly averages of arbitrary finite-degree polynomials in the matrix elements of the resulting unitary converge to Haar measure averages. This is accomplished by mapping the superoperator that describes t order moments on n qubits to a multilevel SU(4^{t}) Lipkin-Meshkov-Glick Hamiltonian. We show that, for arbitrary fixed t, the ground-state manifold is exactly spanned by factorized eigenstates and, under the assumption that a mean-field ansatz accurately describes the low-lying excitations, the spectral gap scales as 1/n in the thermodynamic limit. Our results imply that random quantum circuits yield an efficient implementation of ϵ approximate unitary t designs.
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.
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.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong ε-approximate unitary k-design on n qubits, the distribution of each output probability is within O(k−1/2(1+k/2n)−1/2+ε) in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters 1 and 2n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance O(k−1/2+ε). Every strong ε-approximate unitary k-design invariant on logk+O(1) qubits achieves error 2−Ω(k)+O(ε) in Kolmogorov distance and 2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong ε-approximate k-design is concentrated around its Haar value n−Θ(1): its mean differs from the Haar mean by O(k−1/4+ε1/2) and its standard deviation is O(2−n/2+k−1/8+ε1/4). Consequently, a trusted device sampling such circuits generates n−O(1) bits of entropy per sample, which makes them useful for random number generation.
We study the scaling of the convergence of several statistical properties of a recently introduced random unitary circuit ensemble towards their limits given by the circular unitary ensemble. Our study includes the full distribution of the absolute square of a matrix element, moments of that distribution up to order eight, as well as correlators containing up to 16 matrix elements in a given column of the unitary matrices. Our numerical scaling analysis shows that all of these quantities can be reproduced efficiently, with a number of random gates which scales at most as ${n}_{q}{[\mathrm{ln}({n}_{q}∕ϵ)]}^{\ensuremath{\nu}}$ with the number of qubits nq for a given fixed precision ϵ and $\ensuremath{\nu}>0$.
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.
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.