Local random circuits scramble efficiently and, accordingly, have a range of applications in quantum information and quantum dynamics. With a global U(1) charge, however, the scrambling ability is reduced; for example, such random circuits do not generate the entire group of number-conserving unitaries. We establish two results using the statistical mechanics of k -fold replicated circuits. First, 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. Specifically, the circuits form a k c -design with k c = O ( L d ) for a system in d spatial dimensions with linear dimension L . Second, for k < k c , we derive bounds on the depth τ required for the circuit to converge to an approximate k -design. The depth is lower bounded by diffusion k L 2 ln ( L ) ≲ τ . In contrast, without number conservation τ ∼ poly ( k ) L . The convergence of the circuit ensemble is controlled by the low-energy properties of a frustration-free quantum statistical model which spontaneously breaks k U(1) symmetries. We conjecture that the associated Goldstone modes set the spectral gap for arbitrary spatial and qudit dimensions, leading to an upper bound τ ≲ k L d + 2 .
Local random circuits scramble efficiently and, accordingly, have a range of applications in quantum information and quantum dynamics. With a global U(1) charge, however, the scrambling ability is reduced; for example, such random circuits do not generate the entire group of number-conserving unitaries. We establish two results using the statistical mechanics of k -fold replicated circuits. First, 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. Specifically, the circuits form a k c -design with k c = O ( L d ) for a system in d spatial dimensions with linear dimension L . Second, for k < k c , we derive bounds on the depth τ required for the circuit to converge to an approximate k -design. The depth is lower bounded by diffusion k L 2 ln ( L ) ≲ τ . In contrast, without number conservation τ ∼ poly ( k ) L . The convergence of the circuit ensemble is controlled by the low-energy properties of a frustration-free quantum statistical model which spontaneously breaks k U(1) symmetries. We conjecture that the associated Goldstone modes set the spectral gap for arbitrary spatial and qudit dimensions, leading to an upper bound τ ≲ k L d + 2 .
Random quantum circuits are proficient information scramblers and efficient generators of randomness, rapidly approximating moments of the unitary group. We study the convergence of local random quantum circuits to unitary k-designs. Employing a statistical mechanical mapping, we give an exact expression of the distance to forming an approximate design as a lattice partition function. In the statistical mechanics model, the approach to randomness has a simple interpretation in terms of domain walls extending through the circuit. We analytically compute the second moment, showing that random circuits acting on n qudits form approximate 2-designs in O(n) depth, as is known. Furthermore, we argue that random circuits form approximate unitary k-designs in O(nk) depth and are thus essentially optimal in both n and k. We can show this in the limit of large local dimension, but more generally rely on a conjecture about the dominance of certain domain wall configurations.
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.
Optimal Scaling of Unitary Design Formation in U(1)-Symmetric Random Circuits: A Bottleneck Slower than Charge Transport
Understanding randomness formation under conservation laws is important both for characterizing chaotic phenomena in isolated quantum systems and for symmetry-constrained quantum information processing. U(1)-symmetric random circuits on an N-qubit system provide a minimal tractable setting for this problem, in which the formation rate of unitary designs was conjectured to be governed by charge transport in the underlying circuit geometry. However, whether charge transport indeed sets the slowest relaxation mode has remained an open problem, due to the difficulty in deriving a tight lower bound on the symmetric design formation rate. In this work, we resolve this problem by determining the optimal scaling of the unitary k-design formation rate for k≤O(logN) across a wide range of circuit geometries, including lattices, expander graphs, and all-to-all interactions. In particular, for k≥2, we find that the formation rate is governed by a two-particle encounter rate---the rate at which two random walkers encounter each other in a given circuit geometry. This encounter rate is parametrically smaller than the single-particle transport rate in many geometries, thereby disproving the previous conjecture. We further establish that this encounter mechanism indeed sets the design formation rate by deriving its matching lower bound with a novel proof technique based on an auxiliary subgroup ensemble. Although this encounter mode imposes a robust bottleneck on design formation in U(1)-symmetric random circuits, we also show that this bottleneck can be circumvented by using symmetry-breaking local gates and provide an explicit protocol that achieves faster design formation. These results establish a new picture of randomness formation under conservation laws and provide guiding principles for characterizing and efficiently generating symmetry-constrained randomness.
The generation of k -designs (pseudorandom distributions that emulate the Haar measure up to k moments) with local quantum circuit ensembles is a problem of fundamental importance in quantum information and physics. Despite the extensive understanding of this problem for ordinary random circuits, the crucial situations in which symmetries or conservation laws are in play are known to pose fundamental challenges and remain little understood. Here, we construct explicit local unitary ensembles that can achieve high-order unitary k -designs under transversal continuous symmetry, in the particularly important SU ( d ) case. Specifically, we define the convolutional quantum alternating (CQA) group generated by 4-local SU ( d ) -symmetric Hamiltonians as well as associated 4-local SU ( d ) -symmetric random unitary circuit ensembles and prove that they form and converge to SU ( d ) -symmetric k -designs, respectively, for all k < n ( n − 3 ) / 2 , with n being the number of qudits. A key technique that we employ to obtain the results is the Okounkov-Vershik approach to S n representation theory. To study the convergence time of the CQA ensemble, we develop a numerical method using the Young orthogonal form and the S n branching rule. We provide strong evidence for a subconstant spectral gap and certain convergence time scales of various important circuit architectures, which contrast with the symmetry-free case. We also provide comprehensive explanations of the difficulties and limitations in rigorously analyzing the convergence time using methods that have been effective for cases without symmetries, including Knabe’s local gap threshold and Nachtergaele’s martingale methods. This suggests that a novel approach is likely necessary for understanding the convergence time of SU ( d ) -symmetric local random circuits. Published by the American Physical Society 2024
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.
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.