PaperlayerView exact revision on arXiv

Source-linked AI summary

Local random quantum circuits are approximate polynomial-designs

Fernando G. S. L. Brandao, Aram W. Harrow, Michal Horodecki

arXiv:1208.0692v4quant-ph

TL;DR

Polynomial-size local random circuits were already known to form approximate unitary 3-designs, but whether they could form higher-order designs remained open. This paper connects circuit convergence to Hamiltonian spectral gaps and proves polynomial-design results, while also establishing a topological-order result for one-dimensional parallel circuits.

  • Problem

    Before this work, polynomial-size random quantum circuits were known to be approximate unitary 3-designs, while the conjecture that they form approximate poly(n)-designs remained unresolved.

    Source: §I · p. 2

  • Method

    The proof connects the random-circuit design problem to spectral gaps of local quantum Hamiltonians and uses a tensor-product-expander result for universal gate sets with algebraic entries.

    Source: §I · p. 2, B. Other Universal Sets of Gates · p. 5

  • Results

    The paper proves that polynomial-size local random circuits form approximate unitary poly(n)-designs and that Cn-step one-dimensional parallel circuits yield (n/4, 2^-n/8)-TQO for most pairs of orthogonal states.

    Source: §I · p. 2, §III · p. 12

  • Takeaways & Limitations

    The paper establishes that one-dimensional parallel random circuits generate topological order at the fastest possible rate stated for that setting.

    Source: §III · p. 12

    Extensions to arbitrary universal gate sets remain open; the stated results cover sets whose gates have algebraic entries.

    Source: §X · p. 34

Abstract

from arXiv · show

We prove that local random quantum circuits acting on n qubits composed of O(t^{10} n^2) many nearest neighbor two-qubit gates form an approximate unitary t-design. Previously it was unknown whether random quantum circuits were a t-design for any t > 3. The proof is based on an interplay of techniques from quantum many-body theory, representation theory, and the theory of Markov chains. In particular we employ a result of Nachtergaele for lower bounding the spectral gap of frustration-free quantum local Hamiltonians; a quasi-orthogonality property of permutation matrices; a result of Oliveira which extends to the unitary group the path-coupling method for bounding the mixing time of random walks; and a result of Bourgain and Gamburd showing that dense subgroups of the special unitary group, composed of elements with algebraic entries, are infty-copy tensor-product expanders. We also consider pseudo-randomness properties of local random quantum circuits of small depth and prove that circuits of depth O(t^{10}n) constitute a quantum t-copy tensor-product expander. The proof also rests on techniques from quantum many-body theory, in particular on the detectability lemma of Aharonov, Arad, Landau, and Vazirani. We give applications of the results to cryptography, equilibration of closed quantum dynamics, and the generation of topological order. In particular we show the following pseudo-randomness property of generic quantum circuits: Almost every circuit U of size O(n^k) on n qubits cannot be distinguished from a Haar uniform unitary by circuits of size O(n^{(k-9)/11}) that are given oracle access to U.

I. INTRODUCTION

Haar-random unitaries are useful but require exponentially many gates and random bits, motivating efficiently implementable pseudorandom alternatives. The paper advances the unitary-design conjecture with local random circuits and gives bounds for Haar gates and certain algebraic universal gate sets.

I. INTRODUCTION

  • Haar-random unitaries support many quantum-information protocols, but implementing one requires exponentially many two-qubit gates and random bits.The introduction motivates efficiently implementable pseudorandom unitaries as possible substitutes in some respects.Source: §I · p. 1
  • An approximate unitary t-design mimics Haar-measure properties for degree-at-most-t polynomials, and the paper proves polynomial-size local random circuits form approximate unitary poly(n)-designs.Before this work, polynomial random circuits were known to be approximate 3-designs, and the proof connects designs to spectral gaps of many-body Hamiltonians.Source: §I · p. 2

A. Haar Uniform Gates

  • The paper studies local circuits that apply Haar-random two-qudit gates to neighboring pairs and parallel circuits that apply independent gates on alternating pairings.The parallel model assumes an even number of qudits.Source: A. Haar Uniform Gates · p. 4
  • For Haar gates, local circuits of the stated length form ε-approximate t-designs, as do parallel local circuits with their separately stated length bound.The bounds are given in p097 and p098; the supplied passages do not preserve their full expressions clearly enough to report them here.Source: A. Haar Uniform Gates · p. 5

B. Other Universal Sets of Gates

  • For universal gate sets with inverses and algebraic entries in SU(d^2), the paper gives local and parallel ε-approximate t-design bounds with a gate-set-dependent constant.The proof uses Bourgain and Gamburd’s result that such gate sets yield an infinite tensor-product expander with nonzero gap; the gap’s dependence on dimension is not specified.Source: B. Other Universal Sets of Gates · p. 5

C. Optimality of Results

The paper discusses bounds on design size, limitations of its geometric and gate-set results, and applications to pseudorandomness, equilibration, and topological order. It also distinguishes established findings from open questions and conjectured extensions.

C. Optimality of Results

  • The paper states that design-size dependencies on t and n cannot be improved by more than polynomial factors, while its lower bound stops improving around t ∼ d^n.At that scale, O(d^2n) two-qudit gates suffice to implement any unitary, including one realizing the Haar measure.Source: C. Optimality of Results · p. 6

D. Classical analogues

  • The permutation-state quasi-orthogonality property used in the quantum proof fails for the corresponding partition states in the classical case.The authors therefore describe a direct transfer of their techniques to the classical reversible-circuit result as difficult.Source: D. Classical analogues · p. 6

III. APPLICATIONS

  • Random circuits’ approximate poly(n)-design property supports the conclusion that most sufficiently large circuits have high circuit complexity, rather than substantially shorter decompositions.The paper also states that random circuits cannot be distinguished from Haar-random unitaries by significantly shorter circuits.Source: §III · pp. 8, 9, 11
  • For fast equilibration, the paper strengthens a connection between subsystem equilibration and the complexity of the unitary diagonalizing a Hamiltonian, but does not establish the hoped-for full connection.It proves that most sufficiently large circuits yield Hamiltonians with fast subsystem equilibration and large circuit complexity; it does not show that most circuits in a specified intermediate complexity range equilibrate quickly.Source: §III · p. 11
  • After Cn steps, most one-dimensional parallel local random circuits map any two orthogonal states to states with (n/4, 2^-n/8)-TQO.The stated probability exceeds 1 − 2^-n/8, and the paper says this saturates the fastest possible rate in one dimension.Source: §III · p. 12

A. Local random circuits

The proof translates circuit-design convergence into a spectral-gap problem for a local Hamiltonian. It combines structural properties of that Hamiltonian with gap bounds and a path-coupling argument.

A. Local random circuits

  • The t-design mixing problem is recast as lower-bounding the spectral gap of a local Hamiltonian whose zero eigenspace has dimension t!.The circuit walk’s convergence rate is related to that gap.Source: A. Local random circuits · pp. 12–13
  • A quasi-orthogonality property of permutation states helps bound the Hamiltonian gap using Nachtergaele’s result for frustration-free local Hamiltonians.The paper identifies this as a step in deriving a useful lower bound on the gap.Source: A. Local random circuits · p. 14
  • The lemmas establish approximate t-designs with polynomial circuit size for each fixed t, but do not specify how t depends on circuit size.This qualification separates the fixed-t conclusion from the paper’s stronger main result.Source: A. Local random circuits · p. 14
  • Oliveira’s unitary-group path-coupling method bounds random-walk convergence, which the proof uses in reverse to lower-bound the Hamiltonian gap.The authors say an exponentially small convergence-time bound suffices for their theorem’s first part.Source: A. Local random circuits · pp. 14–15

B. Parallel local random circuits

The parallel-circuit proof transfers the local-circuit gap result through the detectability lemma. The Hamiltonian’s ground-space structure and a quasi-orthogonality bound support the gap analysis.

B. Parallel local random circuits

  • The detectability lemma is the tool used to analyze parallel local random circuits from the local-circuit result.The argument applies the lemma to the frustration-free Hamiltonian with projective local terms to bound the parallel-model gap.Source: B. Parallel local random circuits · pp. 15–16

A. Proof of Lemma 16

  • The proof of the local-to-parallel gap relation uses the odd- and even-bond projectors and the detectability-lemma bound.The supplied result passage states that the parallel-model gap is at least a quantity involving n and the local gap, but its expression is incomplete.Source: B. Parallel local random circuits · pp. 15–16

B. Properties of Hn,t

  • The Hamiltonian’s zero eigenspace is described through permutation representations, and its projector satisfies a stated bound when t^2 ≤ d^n.These structural properties are presented as ingredients for estimating the gap.Source: B. Properties of Hn,t · p. 17

C. Proof of Lemma 18

The proof of Lemma 18 applies Nachtergaele’s criterion to a translationally invariant chain of nearest-neighbor projector interactions, then chooses the interval parameter to establish the needed bounds.

C. Proof of Lemma 18

  • The chain has translationally invariant nearest-neighbor projector interactions, with each interval Hamiltonian assumed to have minimum eigenvalue zero.The ground space is that of the interval Hamiltonian.Source: C. Proof of Lemma 18 · p. 19
  • For n ≥ ⌈2.5 log_d(4t)⌉, the proof applies Nachtergaele’s Lemma 23 with n_l = 2l and ε_l = 1/(2^l).The stated choice of ε_l is taken from the supplied passage’s expression; the lemma’s remaining conditions are not reproduced there.Source: C. Proof of Lemma 18 · pp. 19–20
  • Choosing l ≥ ⌈2.5 log_d(4t)⌉ gives M ≤ (2l)^-1, which the proof uses with Lemma 23 to obtain Eq. (69).The preceding inequality is justified by Eq. (54) of Lemma 17 under t^2 < d^l.Source: C. Proof of Lemma 18 · p. 20
  • To establish Eq. (75), the proof defines a linear map using an orthonormal set of vectors indexed by permutations and invokes the bound in Eq. (78).The passage identifies Eq. (55) of Lemma 17 as an intermediate step.Source: C. Proof of Lemma 18 · pp. 20–21

D. Proof of Lemma 19

The proof of Lemma 19 uses path coupling on the unitary group: a local contraction in L2 Wasserstein distance yields a global one. It constructs a useful coupling over multiple steps and extends the argument from three sites to n sites.

D. Proof of Lemma 19

  • Oliveira’s path-coupling result turns a local contraction in L2 Wasserstein distance into a global contraction for walks on the unitary group.The proof applies this result to bound convergence of the local random walk.Source: D. Proof of Lemma 19 · p. 21
  • For three sites, the proof couples two walk steps nontrivially so that infinitesimally close unitaries move closer on average.A single step may fail to contract when the relevant partial traces of the perturbation vanish; the second step can move such cases into contracting ones.Source: D. Proof of Lemma 19 · pp. 22, 25
  • The three-site contraction is first bounded in Frobenius distance and then transferred to Riemannian distance using their local equivalence for nearby unitaries.The stated relation bounds the Riemannian distance by the Frobenius distance plus a quadratic correction.Source: D. Proof of Lemma 19 · p. 24
  • For n sites, the proof uses k = n − 1 steps and couples the k! paths whose sequence contains no repeated pair of sites.The other k^k − k! paths use trivial coupling and have no shrinking; the coupled paths have factor 1 − (d^2 + 1)^-(n−2).Source: D. Proof of Lemma 19 · p. 26

E. Proof of Lemma 20

The proof of Lemma 20 uses Wasserstein control to bound a t-copy test quantity, by showing that its defining function is 2t-Lipschitz.

E. Proof of Lemma 20

  • A trace-norm variational characterization supplies an operator X with ∥X∥₁ ≤ 1 for the proof’s test-function argument.The passage states the characterization as ∥A∥∞ = max_X{tr(AX) : ∥X∥₁ ≤ 1}.Source: E. Proof of Lemma 20 · p. 27
  • The proof defines f(U) = tr(U^⊗t,t X) and uses its 2t-Lipschitz property to relate Wasserstein distance to the lemma’s bound.It first normalizes f by 2t to obtain a 1-Lipschitz function.Source: E. Proof of Lemma 20 · p. 27
  • The Lipschitz bound follows from a hybrid argument that gives ∥U^⊗t,t − V^⊗t,t∥∞ ≤ 2t∥U − V∥₂.The proof also uses ∥X∥₁ ≤ 1 in bounding the trace.Source: E. Proof of Lemma 20 · p. 27

VI. PROOF OF COROLLARY 7

The proof transfers the Haar-random circuit analysis to circuits drawn from a universal gate set with algebraic entries. It gives gate-count bounds for local and parallel circuits that form approximate t-designs.

VI. PROOF OF COROLLARY 7

  • The corollary assumes a universal gate set containing inverses, with each gate in SU(d²) having algebraic entries.The proof replaces Haar measure in the local-circuit distribution with uniform measure over the gate set.Source: §VI · p. 28
  • G-local and G-parallel circuits are stated to form ε-approximate t-designs at the respective lengths given in the corollary.The supplied length expressions are not fully legible, so no gate-count values are restated here.Source: §VI · p. 28
  • The proof uses a constant λ < 1 independent of t to bound the gate-set operator away from the Haar-projected subspace.The Haar operator is a projector, while the gate-set operator acts trivially on its projected subspace; the proof controls the orthogonal space.Source: §VI · p. 28
  • For parallel circuits, the proof replaces the sequential operator with alternating products of local gate-set operators on odd and even bonds.It bounds the non-Haar terms using the orthogonal block decomposition.Source: §VI · p. 29

VII. PROOF OF PROPOSITION 8

This section proves lower bounds on the size of approximate t-designs, showing that designs require large circuits. The bounds match the paper’s Corollary 6 up to polynomial factors.

VII. PROOF OF PROPOSITION 8

  • An approximate t-design must have large support; determining its rate of scaling suffices for the lower bound pursued here.The section distinguishes this goal from sharper known bounds for exact t-designs and approximate 2-designs.Source: §VII · p. 29
  • The support argument twirls a maximally entangled state on the symmetric subspace, obtaining a maximally mixed state whose rank constrains approximation.The symmetric subspace is an irreducible representation under U(N) acting as U^⊗t.Source: §VII · p. 30
  • A diamond-norm covering discretizes circuits with at most r two-qudit gates by specifying gate locations and approximating each gate to accuracy ε/r.The covering definition requires every circuit to lie within the chosen distance of some net element.Source: §VII · p. 30
  • Approximate t-designs require large circuits, with lower bounds matching Corollary 6 up to polynomial factors.The proposition considers ε-approximate t-designs on n qudits for ε ≤ 1/4 and t ≤ d^n/2.Source: §VII · pp. 29–30
  • Replacing each circuit unitary by its nearest covering element gives an (ε + tδ)-approximate design, and δ = ε/2t yields a 2ε-approximate design.This transfers the design property to a distribution supported on the finite covering set.Source: §VII · pp. 30–31

VIII. PROOF OF COROLLARIES 10 AND 12

The section applies measure concentration for t-designs and circuit coverings to prove pseudorandomness results. It concludes that random circuits resist shorter oracle distinguishers and that most states from sufficiently large circuits are hard to distinguish from maximally mixed states.

VIII. PROOF OF COROLLARIES 10 AND 12

  • The proof applies Low’s concentration lemma for polynomial functions on U(D) when 2mK ≤ t, including to a function defined from a POVM element.For the POVM-derived function, the proof specifies D = d^n and K = 2.Source: §VIII · pp. 31–32
  • For fixed d and sufficiently large n, all but a 2^-Ω(n) fraction of states generated by size-n^k circuits, k ≥ 10, resist circuits distinguishing them from maximally mixed with bias above n^-Ω(1).Source: §VIII · p. 31
  • A δ/2-covering of size-r circuits supports a union-bound step in the concentration argument.Source: §VIII · p. 32
  • When δ and d are constant and r log(r) ≪ s^(1/11)n^(9/11), the probability bound in the proof is negligible.Source: §VIII · p. 32
  • Random circuits cannot be distinguished from Haar-random unitaries by significantly shorter circuits in the stated oracle-access setting.The oracle circuit has size r, acts on at most r qudits, and may use the unitary oracle on its first n qudits.Source: §VIII · p. 32

IX. PROOF OF COROLLARY 15

For any two orthogonal n-qubit states, the corollary shows that random parallel local circuits yield nearly identical marginals on regions up to size n/4, with high probability. The discussion identifies limitations and open questions concerning gate sets, geometry, incompressibility, and time-independent dynamics.

IX. PROOF OF COROLLARY 15

  • With probability greater than 1−2^-n/8, random parallel local circuits give orthogonal n-qubit states nearly identical marginals on every region of size at most n/4, yielding (n/4, 2^-n/8)-TQO.The circuit uses Cn steps of the parallel local random circuit model.Source: §IX · p. 33

X. DISCUSSION AND OPEN QUESTIONS

  • Rapid scrambling and log-Sobolev conditions remain alternative rapid-mixing criteria to investigate, alongside which approximate-design definition best fits applications.The authors say more work could clarify the latter question.Source: §X · p. 34
  • The results currently cover universal gate sets with algebraic entries, while extending them to arbitrary universal sets remains open.The authors believe this restriction is a technicality.Source: §X · p. 34
  • For nearest-neighbor circuits in one dimension, the results are nearly optimal; for other geometries, they are likely far from optimal.Mixing in time comparable to graph diameter is plausible for general graphs, but established here only for graphs of linear diameter.Source: §X · p. 34
  • Whether the results can be strengthened to prove quantum-circuit incompressibility remains open.The discussion points to Application II for further discussion.Source: §X · p. 34
  • For random time-independent Hamiltonians, Anderson localization prevents mixing in many cases, and explaining rapid mixing and thermalization remains an open question.The passage contrasts this situation with classical time-independent stochastic processes.Source: §X · p. 34

Appendix A: Facts about designs and tensor-product expanders

The appendix sets up an easier-to-prove condition for the design definition and records symmetric-subspace and Schur-duality facts used in the technical arguments.

Appendix A: Facts about designs and tensor-product expanders

  • The symmetric subspace consists of vectors invariant under every permutation action, and the density matrices considered are supported within it.The support claim follows because each density matrix is a mixture of states lying in that subspace.Source: Appendix A · p. 35
  • The appendix introduces an easier-to-prove condition to relate the paper’s design definition to the proof strategy.The condition is introduced for a measure on U(N).Source: Appendix A · p. 35
  • The appendix invokes Schur duality, identifying λ with a U(N) irrep, Pλ with an S_t irrep, and the stated Φ vectors with maximally entangled states.The passage also refers to partitions of t into at most N parts.Source: Appendix A · p. 35
  • For Lemma 4, the first inequality is attributed to [61] and the second to Lemma 3; the latter uses stability of the 2→2 norm under tensoring with identity.The passage identifies [61] as the source of the first inequality.Source: Appendix A · p. 36

Related papers

Loading 1208.0692v4…