Source-linked AI summary
Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
Aram Harrow, Saeed Mehraban
TL;DR
The paper addresses whether random quantum circuits can approximate Haar behavior and exhibit anti-concentration at sublinear depth, rather than requiring linear-depth constructions. It analyzes local lattice circuits and related models, proving approximate t-design and anti-concentration results with geometry-dependent depth bounds. These results support connections to scrambling, decoupling, and conditional hardness of approximate classical sampling.
Problem
Prior random-circuit t-design constructions required linear depth, while robust approximate-sampling hardness requires anti-concentration for circuit outputs.
Method
The paper analyzes nearest-neighbor random circuits on D-dimensional lattices using prior t-design constructions, composition analysis, norm equivalences, and quasi-orthogonality, alongside alternative models and Markov-chain techniques.
Results
The constructions achieve approximate t-design behavior at poly(t)(n1/D + ln(1/ϵ)) depth in several norms, while anti-concentration is obtained at O(ln n ln ln n) depth in a different model.
Takeaways & Limitations
The results reduce the depth needed for Haar-like behavior and anti-concentration, including the O(√n) scale relevant to two-dimensional lattice sampling proposals.
Takeaways & Limitations
The hardness implication assumes infinite PH and average-case #P-hardness of approximating circuit amplitudes, which remains an open question.
Abstract
from arXiv · showhide
We prove that $poly(t) \cdot n^{1/D}$-depth local random quantum circuits with two qudit nearest-neighbor gates on a $D$-dimensional lattice with n qudits are approximate $t$-designs in various measures. These include the "monomial" measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was $poly(t)\cdot n$ due to Brandao-Harrow-Horodecki (BHH) for $D=1$. We also improve the "scrambling" and "decoupling" bounds for spatially local random circuits due to Brown and Fawzi. One consequence of our result is that assuming the polynomial hierarchy (PH) is infinite and that certain counting problems are $\#P$-hard on average, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under the assumption that PH is infinite. However, to show the hardness of approximate sampling using this strategy requires that the quantum circuits have a property called "anti-concentration", meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Thus our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent proposal by the Google Quantum AI group to perform such a sampling task with 49 qubits on a two-dimensional lattice and confirms their conjecture that $O(\sqrt n)$ depth suffices for anti-concentration. We also prove that anti-concentration is possible in depth O(log(n) loglog(n)) using a different model.
1 Introduction
The paper constructs shallow random-circuit approximate t-designs on D-dimensional lattices and connects them to anti-concentration, scrambling, decoupling, and approximate-sampling hardness. It also gives sublogarithmic-depth anti-concentration results for other circuit models.
- Approximate designs: poly(t)(n1/D + ln(1/ϵ))-depth circuits converge to the Haar measure in several operationally relevant norms.The construction covers multiple approximate-design measures, though not all norms or the strong measure.
- Approximate designs: For D-dimensional lattices, the natural depth lower bound is Ω(n1/D + ln(1/ϵ)), which the paper shows is asymptotically achievable in many norms.The stated t-dependence for D = 2 is O(t ln t) times the best D = 1 dependence, with a resulting dependence of t6+ot(1) ln t.
- Approximate designs: D-dimensional nearest-neighbor circuits achieve weak monomial designs and convergence in diamond, infinity, and trace norms at O(n1/D) depth.The result generalizes the prior linear-depth random-circuit construction beyond one dimension.
- Anti-concentration: An ϵ-approximate monomial 2-design satisfies the paper’s anti-concentration property, linking approximate-design guarantees to near-maximal-entropy circuit outputs.The paper also gives a direct anti-concentration proof that does not establish the approximate 2-design property.
- Applications and limitations: Spatially local circuits are scramblers and decouplers after O(D·n1/D) steps, improving earlier bounds by removing polylogarithmic factors.The paper connects these results to approximate-sampling hardness under infinite PH and average-case #P-hardness assumptions.
2 Preliminaries
This section defines the norms, Haar reference objects, moment superoperators, and recursive circuit building blocks used to analyze random quantum circuits on lattices.
- Norms: The diamond norm measures distinguishability of superoperators, while Schatten p-norms quantify matrix size across p ∈ [1,∞].
- Haar reference: The Haar measure is the uniform distribution on unitaries over specified qudit subsets, including one- and two-qudit systems.
- Moment operators: A distribution’s quasi-projector is its expected t-fold unitary moment operator, G^(t)_µ = E_C∼µ[C^⊗t,t].
- Circuit building blocks: The construction organizes a D-dimensional lattice into rows and sub-lattices, applying alternating even- and odd-neighbor two-qudit gates along each direction.
- Anti-concentration: Expected collision probability is defined for circuit distributions and provides the anti-concentration quantity used later in the analysis.
3 Approximate t-designs by random circuits with nearest-neighbor gates on D-dimensional lattices
This section proves that the paper’s D-dimensional nearest-neighbor circuit models approximate t-designs in several measures, using comparisons between composed Haar projectors and the Haar moment operator.
- Main results: The main results establish approximate t-design properties for random circuits on D-dimensional lattices in several measures.
- Bounds: For sufficiently small D = O(ln n / ln ln n), key intermediate bounds achieve errors of the form 1/d^Ω(n^1/D).
- Proof strategy: The proof handles diagonal monomials through direct strong-design bounds and treats off-diagonal monomials separately because their Haar expectation is zero.
- Bounds: The depth scales polynomially with t, with the polynomial degree depending on D when dependence on d, t, and D is included.
3.5 Proofs of the basic lemmas stated in Section 3.1
This section develops basic operator inequalities and Haar-moment bounds used to control diagonal and off-diagonal monomials in the design proofs.
- Operator comparison: Completely positive order is preserved under composition: A_i ⪯ B_i for all i implies A_t⋯A_1 ⪯ B_t⋯B_1.
- Operator comparison: The comparison principle extends to overlapping approximate strong designs acting on different qudit subsets through their moment superoperators.
- Matrix bounds: The moment superoperator associated with a distribution is positive semidefinite, enabling the preceding diagonal-to-off-diagonal control.
- Matrix bounds: Positive semidefinite matrices have off-diagonal entries bounded by the largest diagonal entry in absolute value.
- Haar moments: The largest t-th Haar monomial moment on m qudits is at most t! d^(tm).
3.6 Proofs of the projector overlap lemmas from section 3.2
The section proves projector-overlap lemmas by representing row and column spaces through permutation-based subspaces, Gram matrices, and principal angles. These bounds show that the composed projectors approach the Haar projector, with dimension-dependent error bounds.
- Subspace construction: A square lattice with n qudits is organized into row and column subspaces built from permutation-labelled basis states.Each lattice point contains t qudit pairs, and the relevant permutation tuples exclude tuples whose entries are all equal.
- Gram-matrix analysis: The Gram matrix records pairwise inner products of the normal vectors spanning these subspaces.The proof uses Gram matrices for row and column bases to control their inner-product matrix.
- Projector comparison: ∥G_CG_R − G_Haar∥∞ ≤ cos^2 ∡(Ṽ_R, Ṽ_C), linking projector overlap to the angle between the row and column subspaces.This is Proposition 48 and forms the first step of the proof.
- Projector comparison: Jordan’s decomposition reduces the two-projector analysis to invariant one- and two-dimensional blocks parameterized by principal angles.On each two-dimensional block, the relevant singular value is governed by cos^2 θ_i.
- Final bound: The largest singular value of G_CG_R − G_Haar is bounded by 1/d^{nO(n^{1/D})}.Propositions 49 and 50 supply the remaining estimates needed for this singular-value bound.
- D-dimensional extension: For D = O(ln n / ln ln n), the row-plane projector composition satisfies ∥G_PlanesG_Rows − G_Haar∥∞ ≤ 1/d^{Ω(n^{1−1/D})}.The same regime gives computational-basis matrix-element error ε d^{nt}, with ε = 1/d^{Ω(n^{1/D})}.
4 O(n ln2 n)-size random circuits with long-range gates output anti-concentrated distributions
This section targets anti-concentration for random circuits with long-range gates by bounding their collision probability. The theorem establishes the required behavior after O(n ln^2 n) circuit size, with an additional lower-time regime characterized separately.
- Goal and strategy: The section proves anti-concentration for random circuits with long-range gates by analyzing their computational-basis collision probability.The proof strategy relates collision-probability convergence to a classical Markov-chain mixing problem.
- Main theorem: There exists a constant c such that circuit size s > c n ln^2 n satisfies the theorem’s collision-probability condition.The theorem also states a separate condition when t ≤ 1/(3c′ n ln n) for sufficiently large c′.
4.1 Background: random circuits with long-range gates and Markov chains
The background recasts second-moment behavior of random circuits as a classical Markov-chain problem. The chain tracks both Pauli-string weights and which qubits have been hit by gates, enabling collision-probability analysis.
- Moment-superoperator framework: Moment superoperators inherit convex-combination and composition rules from circuit distributions.These rules connect random-circuit ensembles to repeated applications of local moment operators.
- Markov-chain representation: For two-qubit random gates, the moment-superoperator action on Pauli-string bases is represented by stochastic matrices.The resulting dynamics can therefore be studied as a classical Markov chain on strings in {0,1,2,3}^n.
- Covered-qubit tracking: The expected collision probability depends on which qubits have been hit, because untouched qubits change the limiting value.The analysis therefore tracks H_t, the set of qubits hit by at least one gate, alongside the Pauli-string state S_t.
- Markov-chain definition: The augmented chain starts with no hit qubits and updates by selecting a random pair, expanding H_t and applying the Pauli-string transition rule.This is the chain formalized in Definition 59.
- Notation: The notation includes collision probability, Haar projectors, random-gate circuit distributions, Pauli strings, and the covered-qubit set used throughout the proof.The section’s summary table identifies these objects and their roles in the later analysis.
4.2 Proof of Theorem 13: bound on the collision probability
The proof bounds collision probability by combining Markov-chain estimates with an exact collision-probability expression. Its upper- and lower-bound arguments establish convergence toward the stationary benchmark at the stated circuit scale.
- Proof strategy: The proof first relates expected collision probability to the ∥·∥* norm of the Markov-chain probability vector.A separate exact expression for collision probability is then used to derive the lower bound.
- Upper bound: The stationary benchmark for the norm is 1/2^{n+1}, and the analysis shows convergence to a constant multiple of this value.This estimate is used to control the collision probability from above.
- Upper bound: At t = c n ln^2(n), Theorem 61 supplies the Markov-chain mixing estimate used in the upper-bound argument.The theorem is stated for a constant c and sufficiently large n.
- Conclusion: Combining Theorems 60 and 61 with t = c n ln^2(n) yields the theorem’s final collision-probability bound.The conclusion follows by combining the two Markov-chain estimates.
- Lower bound: For t ≤ 1/(3c′ n ln n), the proof uses a bound on the probability that a Hamming-weight-k string remains unchanged after one Markov-chain step.This condition supports the lower-bound analysis in the short-time regime.
4.3 Proof of Theorem 60: relating collision probability to a Markov chain
This section relates the expected collision probability of long-range random circuits to a probability-vector norm by conditioning on a covered-site process. The resulting analysis expresses conditional string probabilities through Hamming weight and bounds uncovered sites using coupon collection.
- The proof relates expected collision probability to the ∥·∥* norm of the probability vector P^(n).
- Conditioned on H_t = H, the distribution of S_t(H) depends only on its Hamming weight.
- For strings p and q, conditioning on H_t = H forces agreement outside H and assigns factors of 1/3 to nonzero bits inside H.
- The analysis decomposes the collision probability into the probability of the covered set and the conditional distribution of the string process.
- The coupon-collector bound gives Pr[H_t ⊆ H] ≤ e^(-(n-|H|)t/n).
4.4 Proof of Proposition 67: collision probability is non-increasing in time
The section proves that collision probability is non-increasing with circuit time for the specified starting state. The proof uses a positive semidefinite operator whose eigenvalues lie between zero and one, while noting that the monotonicity need not hold for every starting state.
- Collision probability is non-increasing in t for the starting state |0^n⟩.
- The proof writes the collision probability using the moment superoperator and an operator α whose eigenvalues lie between 0 and 1.
- The argument relies on |0^n⟩; for starting states such as |+⟩^⊗n, collision probability can increase after random gates are applied.
4.5 Proof of Theorem 61: the Markov chain analysis
The Markov-chain analysis replaces the original walk with a carefully accelerated chain, couples the two processes, and controls the resulting waiting time. It then combines waiting-time and mixing estimates to obtain rapid mixing in the ∥·∥* norm.
- The proof analyzes an accelerated chain whose transition probabilities are chosen to be affine functions of the Hamming-weight state.
- The accelerated process is solved through a partially accelerated and continuous-time chain, while coupling tracks how many original-chain steps correspond to accelerated steps.
- The accelerated chain mixes after O(n ln^2 n) steps in the ∥·∥* norm, and the combined theorem transfers this rapid mixing to the original chain.
- For s = O(n ln n), the wait-time theorem bounds the number of original-chain steps accumulated during s accelerated steps.
- Low-Hamming-weight sites have the largest waiting times, so the analysis bounds how often the accelerated walk visits them.
- The eigenvalue gap of the analyzed chain is exactly 4/(3n − 1).
4.6 Towards exact constants
This section estimates the time scales governing anti-concentration by analyzing escape from low Hamming weights and reaching the stationary region. The resulting conjecture links anti-concentration to a linear-times-logarithmic depth scale.
- Low-Hamming-weight Pauli strings can contribute strongly to anti-concentration because their contribution is 1/3^k while their expected wait-time is approximately n/k.
- Starting from weight k = 1, the expected escape time to k = n/2 is approximately 5n ln n/6.
- The time to reach 3n/4 − o(n) is also approximately 5n ln n/6 from the low-weight starting regime.
- If t = 5n ln n/6 + o(n ln n), then the probability of an output probability at least α/2^n is Ω(1).
- The bulk of the initial distribution reaches approximately 3n/4 in at most 5n ln n/6 + O(n), while the left tail follows the same stated time scale.
5 Alternative proof for anti-concentration of the outputs of random circuits with nearest-neighbor gates on D-dimensional lattices
This section gives an alternative classical-process proof for anti-concentration in lattice random circuits, analyzing convergence through collision probabilities. The argument generalizes across lattice dimensions and yields logarithmic-depth bounds in a long-range setting.
- Markov-chain approach: The proof uses a Markov-chain interpretation to track how random circuit applications drive an initial distribution toward the desired collision-probability behavior.The construction separates zero terms, analyzes row and column updates, and studies convergence after alternating coordinate operations.
- Mechanism: The analysis identifies persistent all-zero terms as the main obstruction to rapid collision-probability convergence.Column operations partially mix these zero states with other rows, addressing the slowdown created by row operations alone.
- General lattice bound: D-dimensional random circuits achieve collision-probability bounds at depth O(Dn^(1/D) + D ln(D/ϵ)).The bound is stated for the generalized lattice construction and its expected collision probability.
- Long-range gates: O(ln n ln ln n)-depth random circuits with long-range gates have the stated expected collision-probability behavior.This follows by setting D = ln n in the preceding theorem.
6 Scrambling and decoupling with random quantum circuits
The paper applies its collision-probability techniques to scrambling and weak decoupling for spatially local random circuits. It improves long-range scrambling bounds and gives dimension-dependent lattice guarantees, while distinguishing the stronger decoupling model it does not address.
- Scope: The method reconstructs weak scrambling and decoupling results but does not yield results for Brown and Fawzi’s stronger decoupling model.The paper also notes that no D-dimensional lattice bound was given in the cited prior scrambling result.
- Scrambling: For constant D, s = O(D · n^(1/D) + ln D) yields a 1/poly(n)-approximate scrambler.When D = O(ln n), this corresponds to O(ln n ln ln n)-depth circuits.
- Scrambling: O(ln n ln ln n) depth improves Brown and Fawzi’s O(ln^2 n) scrambling bound for long-range random circuits.The paper states that O(ln n) may be the correct bound, but does not establish that conjectured value.
- Weak decoupling: For constant D, s = O(D · n^(1/D)) gives a 1/poly(n)-approximate weak decoupler when m < c′n^(1/D).The result applies for c = 1 and a constant c′ < 1.
A Proof of Theorem 3
This proof establishes approximate-sampling hardness by combining Stockmeyer’s probability-estimation procedure with anti-concentration from approximate 2-designs. It relates a classical sampler close in total variation to estimates of circuit output probabilities.
- Circuit family: The proof constructs a family Cx by applying a random approximate-design circuit and then random computational-basis bit flips.This family supports the reduction used in the theorem.
- Classical-sampling reduction: The proof assumes a BPP sampler whose output distribution is within total variation distance ϵ of the quantum circuit distribution.It then uses Stockmeyer’s result to obtain multiplicative estimates of the sampler’s output probabilities.
- Approximate-design moments: A 1/poly(n)-approximate 2-design preserves the relevant Haar second and fourth moments up to inverse-polynomial error.These moment relations are the input to the Paley-Zygmund argument.
B Basic properties of the Krawtchouk polynomials
This appendix records symmetry and orthogonality properties of Krawtchouk polynomials. The results are derived using factorial expressions, overlap identities, and generating functions.
- Symmetry: The relevant factorial expression is symmetric in x and t, implying a corresponding symmetry for the associated Krawtchouk-polynomial quantity.The proof establishes symmetry term by term and then transfers it to the full expression.
- Orthogonality: The appendix states an orthogonality relationship for Krawtchouk polynomials when p and q lie in [0, 1] and satisfy p + q = 1.The polynomials are introduced through a binomially weighted function space.
- Proof method: The orthogonality proof uses the generating function and compares polynomial overlaps under the defined binomial norm.Equating the resulting expressions for all real y and z yields the stated relation.
Declarations
The authors report equal contribution, disclose funding sources, and state that they have no relevant financial or non-financial conflicts.
- The authors contributed equally to this work.
- AWH received funding from NSF, the NSF QLCI program, and an ARO contract.
- SM received funding from the NSF.
- The authors disclosed no relevant financial or non-financial interests.