Source-linked AI summary
Random Quantum Circuits are Approximate 2-designs
Aram W. Harrow, Richard A. Low
TL;DR
The paper addresses the exponential cost of obtaining Haar-like random unitaries from random circuits. It analyzes first- and second-moment convergence for broad universal gate sets and shows polynomial-length circuits suffice for approximate 1- and 2-designs, with improved related convergence bounds.
Problem
Exactly sampling the Haar distribution is inefficient, while prior approximate-design constructions used longer circuits or restricted gate sets.
Method
The paper analyzes moment evolution in random circuits formed by applying universal two-qubit gates to randomly chosen qubit pairs.
Results
O(n(n + log 1/ǫ)) random gates yield an ǫ-approximate 2-design for broad gate classes, including universal and stabilizer settings.
Takeaways & Limitations
The result gives efficient approximate 1- and 2-unitary designs and improves applications including dispersing circuits and entanglement growth.
Takeaways & Limitations
The stated bound has a dimension factor, and the strongest efficiency claim assumes a gate set universal on U(4) or its stabilizer subgroup.
Abstract
from arXiv · showhide
Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group.
1 Introduction: Pseudo-Random Quantum Circuits
Random circuits use universal two-qubit gates applied to random qubit pairs to generate pseudo-random unitaries, avoiding the exponential cost of approximating the full Haar distribution. The paper analyzes their lower-order moments and establishes efficient approximate designs for broad circuit classes.
- A k-design matches the kth moments of the Haar distribution, which suffices for most uses of random states or unitaries.
- O(n(n + log 1/ǫ)) steps yield an ǫ-approximate 2-design for a broad class of natural random circuit models.
- Random circuits choose gates from a universal two-qubit set and apply them to randomly selected qubit pairs at each step.
- The framework simplifies and generalizes earlier analyses of random circuits.
- Exponential resources are required to approximate the full Haar distribution, motivating approximation through lower-order moments.
- The analysis maps second-moment evolution to a classical Markov chain and extends convergence results to multiple random-gate steps.
2 Preliminaries
The preliminaries define state and unitary designs, approximate closeness, and the random-circuit framework used to analyze moment convergence. They also establish the gate-set conditions and bounds underlying the main 2-design result.
- A state k-design is an ensemble whose k copies are indistinguishable from copies of a uniformly random state.
- A unitary k-design reproduces Haar averages for degree-k polynomials in U and degree-k polynomials in U*.
- Approximate unitary designs are measured using diamond-norm closeness, which captures distinguishability even with arbitrary entangled ancillas.
- Theorem 2.9 identifies universal gate sets and two-qubit approximate or exact k-designs as k-copy gapped distributions.
- Theorem 2.10 gives t ≥ C(n(n + log 1/ǫ)) for an ǫ-approximate unitary 2-design under either closeness definition.
3 Analysis of the Moments
The analysis represents Haar moments through operators on tensor-power spaces and characterizes their invariant subspace using permutation operators. It then shows that universal gate distributions preserve this subspace while contracting its orthogonal complement, establishing the required spectral gap.
- Haar moment structure: The Haar moment operator T(p) commutes with U^⊗k and is a linear combination of permutations from the symmetric group S_k.This symmetry identifies the permutation-operator subspace as the relevant invariant sector.
- Haar moment structure: The Haar operator ˆG is a symmetric projector with eigenvalues 0 and 1; permutation operators have eigenvalue 1, while orthogonal vectors have eigenvalue 0.The projector structure follows from the eigenvector characterization and symmetry results.
- Haar moment structure: For k = 2, the invariant subspace is generated by the identity and swap permutation operators.These are the two permutation operators appearing at second moment order.
- Circuit evolution: The second-moment evolution eliminates off-diagonal Pauli coefficients while conserving the sum of diagonal coefficients, enabling a Markov-chain analysis.The conserved diagonal mass can be renormalized into a probability distribution.
- Universal distributions: A universal distribution on U(d) is k-copy gapped for every positive integer k, and therefore is 2-copy gapped when k = 2.All Haar-invariant eigenvectors with eigenvalue one remain fixed, while the rest contract under the universal distribution.
4 Convergence
Random-circuit first and second moments converge to the Haar moments in polynomial length, with the second-moment analysis reducing diagonal coefficients to a Markov chain and controlling off-diagonal coefficients directly. The resulting bounds apply broadly across universal gate sets, with tighter gap and mixing-time results for the U(4) case.
- 4.2 Second Moments Convergence: For k = 2, diagonal Pauli coefficients evolve as a Markov chain, while coefficients with distinct Pauli labels decay directly as qubits are selected.This separates the convergence proof into a random-walk analysis for γ(p, p) and direct decay bounds for γ(p1, p2) with p1 ≠ p2.
- 4.4 Convergence Proof: The proof extends from nonnegative diagonal coefficients to arbitrary states through Corollary 2.12, while the initial Markov-chain lemma assumes normalized nonnegative coefficients.The restriction arises because diagonal coefficients can be interpreted as a probability distribution only when they are nonnegative and sum to one.
- 4 Convergence: Random circuits of length O(n(n + log 1/ǫ)) form ǫ-approximate 2-designs in a broad class of natural models.The analysis proves rapid convergence of the second moments to those of the Haar-distributed unitary.
- 4.4 Convergence Proof: The U(4) chain has eigenvalue gap Θ(1/n), improving the elementary Ω(1/n^2) bound and yielding tight convergence bounds up to constants.The comparison analysis transfers the U(4) gap to universal 2-copy-gapped gate distributions.
5 Tight Analysis for the U(4) Case
The U(4) analysis reduces second-moment convergence to Markov-chain mixing and proves tight O(n log n + n log 1/ε)-scale bounds. A zero chain captures the slow part of the dynamics, while coupon-collector reasoning controls the full chain.
- Second Moments Convergence: The second-moment coefficients evolve through a classical Markov chain whose mixing determines convergence to the Haar second moments.The chain is analyzed through Pauli coefficients and stationary-distribution convergence.
- Full-Chain Mixing: The full chain mixes in O(n(n + log 1/ε)) steps, with the n log n component arising from ensuring every site is hit.After the zero chain mixes, a coupon-collector argument controls the remaining non-zero-site distribution.
- The Zero Chain: The zero chain counts non-zero positions and has state space Ω = {1, 2, . . . , n}, with transitions determined by paired zero and non-zero sites.It is a lazy one-dimensional random walk, and its movement probability increases as the number of zeroes decreases.
- Mixing Bounds: The zero chain has 2-norm mixing time O(n log 1/ε).The proof uses an eigenvalue-gap lower bound and a standard 2-norm mixing estimate.
- Mixing-Time Proof: The proof partitions the walk into regions and uses Chernoff and log-Sobolev arguments to establish the O(n log n) upper bound.The stationary distribution is concentrated near 3n/4 non-zero sites, providing the regime used in the mixing argument.
6 Main Result
The main result converts Markov-chain mixing into approximate 2-design convergence using Pauli expansions and norm bounds. The resulting circuit length is polynomial, though a dimension factor remains under the stronger diamond-norm requirement.
- Proof of Theorem 2.10: The proof establishes an approximate 2-design by bounding convergence of Pauli-basis second moments in the 2-norm.The supremum can be restricted to physical states, and Pauli orthogonality supplies the key norm estimate.
- Main Bound: O(n(n + log 1/ε)) steps suffice for the random circuit to achieve the paper’s approximate 2-design guarantee.This bound applies to the stated circuit model and follows from the second-moment convergence analysis.
- Norm Dependence: The stronger diamond-norm proof retains a dimension factor, whereas the Dankert et al. measure admits the same O(n(n + log 1/ε)) circuit length.The paper contrasts this with an explicit construction requiring O(n log 1/ε) steps in that measure.
7 Conclusions
The paper concludes that random circuits efficiently form approximate 1- and 2-designs under broad gate assumptions, with applications to decoupling, quantum speedups, and entanglement growth.
- Conclusions: Tight convergence results for the first two moments establish efficient approximate 1- and 2-unitary designs.The framework is described as readily generalizable to k-designs, although proving the general case remains future work.
- Gate Assumptions: The result holds for universal two-qubit gate sets that are also universal on U(4), and U(4) gates may be replaced by any approximate two-qubit 2-design.The replacement does not change the asymptotic convergence properties.
- Applications: Applying a random 2-design unitary and discarding part of one system gives an efficient method for decoupling two quantum systems.This reduces encoding complexity in cited quantum Shannon theory constructions to O(n^2), while decoding remains inefficient.
- Applications: O(n^2)-length circuits suffice for the cited dispersing-circuit application, replacing its earlier O(n^3) length requirement.The paper notes that a specialized argument might improve this further for computational-basis inputs.
- Applications: The analysis improves the cited entanglement-growth bound to O(n(n + log 1/ε)) steps from O(n^2(n + log 1/ε)).This concerns almost maximal entanglement in systems with random two-party interactions.
A.1 Permutation Operators
This appendix develops permutation-operator identities and uses them to obtain the Pauli expansion of the swap operator.
- Permutation Identities: The appendix introduces permutation-operator lemmas that are used repeatedly in later calculations.The first lemma evaluates matrix elements associated with cycles and tensor-product operators.
- Swap Expansion: The swap operator F on two d-dimensional systems is expanded in a basis using the cycle-evaluation lemma.The proof expands F in the basis and identifies the resulting coefficients.
A.2.1 Asymmetric Simple Random Walk
The analysis develops concentration and backward-motion bounds for asymmetric one-dimensional random walks, including walks whose bias varies but remains bounded below. These results also yield a weaker concentration bound on site-visit counts and occupation time.
- An asymmetric simple random walk moves right with probability p and left with probability q = 1 − p.
- The position after k steps is tightly concentrated around k(p − q).The proof applies a Chernoff bound after mapping binary movement indicators to ±1 variables.
- The same concentration approach extends to walks with step-dependent probabilities p_i ≥ p and q_i ≤ 1 − p.The lower-bound bias supplies a common comparison distribution for the Chernoff argument.
- The walk’s occupation time is concentrated well enough that the time spent at positions ≤ x is about x/µ.This follows from concentration of the walk near position tµ and supports later waiting-time bounds.
- If p > q, the probability of eventually reaching an absorbing barrier at distance a is (q/p)^a, and finite-time absorption is no more likely.
A.2.2 Waiting Time
The waiting-time analysis models delays at each site by geometric random variables whose parameters grow with position. Independence and geometric-series bounds then provide concentration for the total waiting time.
- At position x, the waiting time is stochastically dominated by a geometric variable with parameter 2x/5n.The general form used is W(x) ∼ Geo(βx/n), with β = 2/5 in this application.
- The total waiting time is analyzed by summing independent site-level geometric waiting times.Independence permits factorization of the relevant moment-generating calculation.
- Summing the resulting geometric series yields an explicit concentration bound for the total waiting time.The proof selects α = 1/2 for simplicity and uses 1 − x ≤ e^−x.
A.2.3 Phase 1
In phase 1, the walk has a sufficiently strong rightward bias that it reaches n^δ in n^δ accelerated steps with high probability. The waiting-time bound then implies successful completion with high probability.
- For δ < 1/2, the probability of moving right at every step remains close to one through n^δ accelerated steps.
- With high probability, the walk reaches n^δ in n^δ accelerated steps.
- The phase-1 waiting time is bounded using the geometric waiting-time concentration result because each site is hit exactly once on the all-right event.
- Phase 1 therefore completes successfully with high probability by combining the all-right event with the waiting-time bound.
A.2.4 Phase 2
Phase 2 moves from n^δ/2 toward θn under a rightward bias, while controlling excessive waiting and backward excursions. The broader mixing analysis then uses restricted-chain and log-Sobolev arguments to obtain O(n log n)-scale bounds.
- A.2.4 Phase 2: Phase 2 starts at n^δ/2 and targets θn for 0 < θ < 3/4, with right-move probability at least p = 3(1 − θ).
- A.2.4 Phase 2: Waiting-time control relies on restricting the walk to positions at least n^δ/2 because delays increase as the walk moves backward.
- A.2.4 Phase 2: The phase-2 waiting path is compared through visit-count orderings to a walk that distributes visits across an initial interval of sites.This stochastic domination reduces the bound to the geometric-waiting-time lemma.
- A.2.4 Phase 2: The phase-2 analysis controls three failure modes: failure to reach θn, excessive waiting time, and return to n^δ/2.These events are bounded separately using lemmas for forward progress, waiting time, and backward absorption, then combined by a union bound.
- A.2.5 Phase 3: The final phase starts at θn and uses log-Sobolev comparisons for restricted zero chains to establish O(n log n) mixing-time bounds.The comparison constructs chains with the same stationary distribution and derives a gap of Ω(1/n).
- A.2.5 Phase 3: High-probability bounds are converted into full mixing-time bounds by repeating O(n log n)-step blocks until the failure probability falls below the target distance ε.