Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates

1 Introduction

• The paper achieves poly(t)(n^(1/D) + ln(1/ϵ))-depth convergence to the Haar measure in monomial, diamond, infinity, and trace norms for D-dimensional lattice circuits, but not in the strong measure.For D = 2, the t-dependence is t^(6+o_t(1)) ln t, building on Haferkamp’s t^(5+o_t(1)) bound; strong sublinear-depth designs remain open.Source: §1 · pp. 3–4

1.2 Our models

• The second model selects a pair of qubits uniformly at random at each step and applies a random U(4) gate, representing long-range interactions on a complete graph.For t = 2, the process maps to a random walk and then to the Ehrenfest model, with random heavy-tailed delays complicating the anti-concentration analysis.Source: §1 · pp. 4–5, §1.2 · p. 7

1.1 Connections with quantum computational supremacy experiments

• Approximate 2-designs provide anti-concentration, enabling a theorem that converts efficient approximate sampling into FBPP^NP amplitude estimation for most circuits under the stated conditions.Assuming PH is infinite and average-case approximate amplitude computation is #P-hard, this yields hardness of classical sampling, although that average-case assumption remains open.Source: §1.1 · p. 6
• The resulting anti-concentration depth improves prior linear-depth requirements to O(n ln^2 n) gates for long-range interactions and O(n√n) for two-dimensional lattices.For near-term parameters n ∼ 10^2 and δ ∼ 10^-2, these bounds are closer to practicality than the previous O(n^2) bound, subject to reasonable constants.Source: §1 · p. 5, §1.1 · p. 6

1.2 Our models

• The local model applies independent random U(d^2) gates in alternating nearest-neighbor layers, generalizing from one-dimensional chains to D-dimensional lattices.In two dimensions, the construction alternates row operations along the two lattice directions; its depth is (2c + 1)2s, with c = poly(t) and s = poly(t)·√n for t-design results.Source: §1.2 · p. 7
• The models include complete-graph circuits that repeatedly choose a random qudit pair and apply a Haar-random two-qudit gate.The circuit ensemble has size s, with s viewed as O(n ln^2 n).Source: §1.2 · p. 8

1.3 Our results

• The results establish approximate t-design bounds for spatially local circuits, using an O(√n) quasi-projector construction that yields exponentially small error in √n for c = t ln t.The construction alternates row and column circuits of O(√n) depth and repeats the process poly(t) times; the higher-dimensional theorem gives δ = 1/d^Ω(n^(1/D)).Source: §1.3 · pp. 8–10
• The local-circuit results imply anti-concentration, while a separate argument achieves anti-concentration in O(D · n^(1/D)) depth without requiring the approximate 2-design property.An ε-approximate 2-design in the monomial measure has α = δ(1 − ε) and β = (1 − δ)^2(1 − ε)^2; the alternative proof directly establishes anti-concentration.Source: §1.3 · pp. 10–11
• Spatially local random circuits on D-dimensional lattices become scramblers and decouplers after O(D · n^(1/D)) steps, improving prior bounds by removing polylogarithmic factors.Earlier work required O(n^(1/D) polylog(n)) depth for lattice scrambling [18].Source: §1.3 · p. 11, §1.4 · p. 13
• An alternative proof for anti-concentration via circuits with t = 2 and D = O(ln n) achieves depth as small as O(ln n ln ln n).The accelerated chain moves with probabilities affine in x and is exactly solved using Krawtchouk polynomials.Source: §1.3 · pp. 12–13

1.4 Previous work

• Prior work established linear-depth approximate designs or scrambling bounds with polylogarithmic overhead, whereas later work [25] proved Θ(ln n) anti-concentration for linear chains and complete graphs but left D = 2, 3, … open.The paper notes that operator-spreading results [48, 47] do not directly provide rigorous t-design constructions, and prior bounds lose powers of Hilbert-space dimension when changing norms.Source: §1.4 · pp. 13–14

1.5 Open questions

• Strong t-designs may or may not be achievable with sub-linear-depth random circuits, depending on whether off-diagonal moments fall below 1/d3nt.The paper cannot rule out that strong designs require linear depth.Source: §1.5 · p. 14
• The actual constants in anti-concentration and design-size bounds remain unclear, with a conjectured complete-graph leading term involving 5n(ln n + ϵ) and a D-dimensional constant suggested to be ≈1.The conjectured complete-graph bound concerns O(ϵ)-approximate 2-designs, while the paper’s prior upper bound was O(n ln2 n).Source: §1.5 · pp. 14–15
• The paper questions whether its n-dependence and t^α scaling are optimal, noting α ≳5 and lower bounds of Ω(t ln n) for any circuit and Ω(n1/D) in D dimensions.Recent evidence suggests α = 1 for D = 1, but uncontrolled approximations prevent extending the argument even to D = 2; the dependence on n is believed essentially optimal.Source: §1.5 · p. 14
• For arbitrary interaction graphs, the paper asks whether t-design time is governed by diameter, expansion, mixing time, or cover time, and whether a comparison or censoring lemma holds for related circuit families.It conjectures O(l) depth for graphs with large expansion and diameter l, but suspects tight bottlenecks such as binary trees can require linear depth.Source: §1.5 · p. 14
• The paper leaves unresolved the dynamics before depth n1/D and the anti-concentration threshold in D-dimensional lattices, whose proven lower bound is Ω(ln n) despite an expected Ω(n1/D) heuristic.A later result [25] gives O(ln n) anti-concentration depth for D = 1, motivating the possibility of O(ln n) depth also for higher dimensions.Source: §1.5 · p. 15

2.1 Basic definitions

• The preliminaries define the diamond norm, positive and completely positive maps, Haar measures, expected monomials, moment superoperators, and quasi-projectors.These definitions provide the basic operator and design framework used in subsequent sections.Source: §2.1 · p. 15

2.2 Operator definitions of the models

• The paper models lattice circuits using alternating even- and odd-neighbor gates, Haar projectors on rows or sub-lattices, and recursive constructions in arbitrary dimension.A D-dimensional lattice is viewed as n^(1/D) sub-lattices, each containing n^((D-1)/D) qudits.Source: §2.1 · p. 16, §2.2 · p. 17

2.2.1 Summary of the definitions

• A notation summary consolidates the norms, Haar projectors, row and plane operators, collision probabilities, lattice-circuit distributions, and angle notation used later.The summary distinguishes the two-dimensional row operators gR and gC and the general D-dimensional circuit distributions.Source: §2.2.1 · p. 18

2.3 Elementary tools

• The analytical toolkit includes Schatten-norm identities, Haar-projector and Weingarten expansions, spectral and unitarily invariant norm lemmas, hybrid bounds, tensor-product estimates, and stochastic coupling.In particular, composing a superoperator with a trace-preserving completely positive map does not increase the diamond norm.Source: §2.3 · pp. 18–19

2.4 Various measures of convergence to the Haar measure

• The paper defines approximate t-design convergence through monomial, diamond, trace, tensor-product-expander, anti-concentration, scrambling, and weak-decoupling measures.Anti-concentration is characterized by an upper bound on the fourth moment of an output amplitude relative to the Haar value, while scrambling and decoupling quantify reduced-state behavior on bounded-size subsystems.Source: §2.4 · pp. 20–21

3.1.1 Comparison lemma for random quantum circuits

• The proof combines completely positive comparison of overlapping approximate designs with separate control of diagonal and off-diagonal monomials relative to Haar moments.The comparison lemma composes cp orderings, while off-diagonal monomials require an additional bound beyond the direct strong-design argument for diagonal monomials.Source: §3.1.1 · p. 21, §3.1.2 · p. 22, §3.3 · p. 23

3.2 Gap bounds for the product of overlapping Haar projectors

• Overlapping Haar-projector products supply the key analytic estimates, including operator-norm and matrix-element errors of order 1/d^Ω(n^(1/D)) for D=O(ln n/ln ln n).These estimates are used to compare circuit moment operators with the Haar quasi-projector.Source: §3.2 · p. 22, §3.4 · p. 27

3.3 Proof of Theorem 8; t-designs on two-dimensional lattices

• For two-dimensional lattices, Theorem 8 bounds the design error by a term decaying as e^(-s/poly(t)) with s proportional to √n, plus a d^(-Ω(c√n)) term.The proof first controls diagonal monomials through strong-design comparisons and then bounds off-diagonal monomials, whose Haar expectation is zero.Source: §3.3 · pp. 23, 24, 26

3.4 Proof of Theorem 9; t-designs on D-dimensional lattices

• Theorem 9 establishes a 1/d^Ω(n^(1/D))-approximate t-design for D-dimensional lattice circuits, for sufficiently large c depending on D and t.The proof treats D and t as constants and proceeds inductively from the two-dimensional result.Source: §3.4 · pp. 27, 29
• For higher dimensions, the proof recursively constructs row designs and uses induction on D to obtain the 1/d^Ω(n^(1/D)) error bound.The induction starts from D=2, while the required circuit depth parameter satisfies s=O(n^(1/D)).Source: §3.4 · pp. 27, 28, 30
• The proof yields depth scaling polynomially with t, with the polynomial degree depending on D, while the lattice-size exponent scales as Ω(n^{1/D}).The argument requires choosing the constant in the Ω(n^{1/D}) exponent sufficiently larger than the constant in the O(n^{1/D}) exponent.Source: §3.4 · p. 30
• The induction establishes ε_D,n = 1/d^{Ω(n^{1/D})} from the assumption ε_{D−1,n} = 1/d^{Ω(n^{1/D−1})}.This is the D-dimensional extension step used in the proof of Theorem 9.Source: §3.4 · p. 31
• The remaining proof steps follow from the proof of part 2.Source: §3.4 · p. 31

3.5.1 Comparison lemma for random quantum circuits

• Complete-positive order is preserved when composing ordered superoperators, yielding the comparison lemma by induction over circuit layers.If A ⪯ B and C ⪯ D, then AC ⪯ BD because BD − AC is completely positive; the multi-layer result follows inductively.Source: §3.5.1 · p. 32

3.5.2 Bound on the value of off-diagonal monomials

• Off-diagonal monomial values are bounded using positive semidefiniteness: the largest absolute off-diagonal entry cannot exceed the largest absolute diagonal entry.The proof applies this fact to a positive semidefinite matrix arising from the relevant moment operators.Source: §3.5.2 · pp. 32–33

3.5.3 Bounds on the moments of the Haar measure

• The largest t-th monomial moment of the Haar measure is at most t! d_tm.Unbalanced moments have zero expectation, so the same bound applies; the proof uses Hölder’s inequality and a closed-form moment expression.Source: §3.5.3 · p. 34

3.6.1 Extended quasi-orthogonality of permutation operators with application to random circuits on 2-dimensional lattices

• The permutation-state bases exclude tuples whose permutations are all equal, but remain nonorthogonal and can become linearly dependent when t > dn.The row, column, and Haar subspaces are built from maximally entangled states indexed by permutation tuples; Gram matrices control their overlaps.Source: §3.6.1 · pp. 34–35
• For the two-dimensional lattice, the composition of the row and column quasi-projectors is close to the Haar projector, with ||GCGR − GHaar||∞ ≤ 1/dΩ(√n).The proof relates the projector difference to the angle between the row and column subspaces, then bounds that angle using Gram matrices of permutation states.Source: §3.6.1 · pp. 35–36

3.6.2 Extended quasi-orthogonality of permutation operators with application to random circuits on D-dimensional lattices

• For D = O(ln n / ln ln n) with a sufficiently small constant, ||GPlanes(D)GRows(D,n) − GHaar||∞ ≤ 1/dΩ(n1−1/D).The proof generalizes the two-dimensional angle and overlap-matrix arguments to plane and row permutation subspaces.Source: §3.6.2 · p. 40
• Under the same D = O(ln n / ln ln n) condition and sufficiently large c, computational-basis entries of ˜Gn,D,c − GHaar are bounded by ϵ dnt, where ϵ = 1/dΩ(n1/D).This is obtained by applying the generalized projector-overlap result to the operator ˜Gn,D,c.Source: §3.6.2 · pp. 41–42
• For D = O(ln n / ln ln n) and sufficiently large c, the projector overlap satisfies |⟨x| ˜G_n,D,c − G_Haar |y⟩| ≤ ϵ d^{nt}, with ϵ = 1/d^{Ω(n^{1/D})}.The proof uses induction on dimension, with the D = 2 case supplied by Lemma 39.Source: §3.6.2 · p. 42
• The induction propagates the squared diagonal overlap bound from (D−1)-dimensional sublattices to the full D-dimensional lattice.The argument assumes max_x |⟨x|(˜G_{n^{1−1/D},D−1,c} − G_Haar)^2|x⟩| ≤ ϵ d^{n^{1−1/D}t} and proves the corresponding n-qudit bound.Source: §3.6.2 · pp. 42–43
• The operator-norm estimate is obtained by bounding tensor-product superoperators and their Gram matrices, yielding ∥Λ∥∞ = 1/d^{O(c n^{1−1/D})}.The Gram-matrix estimate uses ∥J_1 − id∥∞ = O(t^2)/d^{n^{1/D}} and shows the resulting norm is at most 1/2 for large n with constant t and D.Source: §3.6.2 · pp. 44–45

• The proof relates expected collision-probability convergence to mixing of a classical Markov chain.The section introduces notation first, then proves the theorem using lemmas developed later.Source: §4 · p. 46
• The theorem establishes anti-concentration once the circuit size satisfies s > c n ln^2 n.Source: §4 · p. 46
• The result additionally applies when t ≤ 1/(3c′ n ln n) for sufficiently large c′.Source: §4 · p. 46

4.1 Background: random circuits with long-range gates and Markov chains

• For second moments, the moment superoperator acts as a stochastic matrix on Pauli strings, yielding a classical Markov chain on S = {0, 1, 2, 3}^n.Two-qubit Haar gates induce the corresponding local stochastic transitions on Pauli-string coordinates.Source: §4.1 · pp. 46–47
• Moment superoperators preserve convex combinations and compose under circuit composition, providing the basic algebraic tools for analyzing random-circuit ensembles.These properties are stated as Fact 58 for distributions over circuits.Source: §4.1 · p. 46
• The analysis augments the Pauli-string chain with H_t, the set of qubits hit by at least one gate, because untouched qubits change the limiting collision probability.If m qubits are never acted on, the expected collision probability approaches approximately 2^m/2^n rather than 1/2^(n+1).Source: §4.1 · p. 47
• Definition 59 initializes H_0 = ∅ and a nonzero Pauli string, then repeatedly selects a random pair, updates H_t, and randomizes the selected coordinates unless both are zero.The joint process (S_t, H_t) is the Markov chain used to model the circuit evolution.Source: §4.1 · p. 47

4.1.1 Summary of the definitions

• The definitions summary identifies Coll(C), Haar projectors, the random two-qubit-gate circuit distribution, Pauli-string chains, covered sets H_t, and accelerated chains used later in the analysis.It also records quantities such as |S_t|, transition matrices P and Q, and waiting times for accelerated-chain steps.Source: §4.1.1 · pp. 47–48

Norm formulation

• The expected collision probability is related to the ∥·∥∗ norm of the Markov-chain weight distribution, whose stationary value is 1/2^(n+1).Source: §4.2 · p. 48

Lower bound

• The lower bound uses Theorem 62’s exact collision-probability expression in terms of the Markov chain S_0, S_1, … and bounds it according to the probability of no one-step change.The argument assumes t ≤ 1/(3c′) n ln n.Source: §4.2 · p. 49

Upper bound

• The upper-bound proof has two major steps and combines Theorems 60 and 61 with t = cn ln^2(n).The resulting estimate is stated for n larger than a universal constant, with c adjusted to cover smaller n.Source: §4.2 · p. 49
• The combined upper bound is at most 1/2^n (1 + 28(1 + 2/(n^(c ln n)))^n).Source: §4.2 · p. 49

Markov-chain formulation

• The expected collision probability is related to the ∥·∥∗ norm of the Markov-chain probability vector P^(m), establishing the framework for Theorem 60.The argument first expresses collision probability using the moment superoperator and then applies intermediate results culminating in Theorem 60.Source: §4.3 · pp. 49, 50, 52

Conditional state distribution

• Conditioned on H_t = H, the unhit coordinates of S_t must match the initial string, while S_t(H) is distributed according only to its Hamming weight.Each nonzero symbol on the covered sites contributes a factor of 1/3 because symbols 1, 2, and 3 are equally likely.Source: §4.3 · pp. 50–51

Collision-probability decomposition

• The conditional distribution yields a 1/3^k factor for strings whose covered substring has Hamming weight k, reducing collision probabilities to Hamming-weight probabilities.This identity is obtained by combining the conditional state distribution with the distribution of the covered set H_t.Source: §4.3 · p. 51

Coupon-collector bound

• The proof controls uncovered sites using the coupon-collector estimate Pr[H_t ⊆ H] ≤ e^−(n−|H|)t/n.This bound supplies the remaining probabilistic control needed before applying the derived collision-probability expression to Theorem 60.Source: §4.3 · pp. 51–52

Monotonicity result

• The collision probability Coll(C) cannot increase as the number of steps t grows.This monotonicity allows bounds for a distribution of original-chain times to address the accelerated-chain time-variance issue.Source: §4.4 · p. 52

Proof mechanism

• The proof uses vanishing off-diagonal Pauli terms and a positive semidefinite operator whose eigenvalues lie between 0 and 1.These properties imply that the trace expression governing collision probability cannot increase with t.Source: §4.4 · p. 52

Limitation

• The monotonicity relies on starting from |0n⟩; for |+⟩⊗n, collision probability can increase after random gates are applied.Thus Proposition 67 does not hold for arbitrary initial states.Source: §4.4 · p. 52

4.5 Proof of Theorem 61: the Markov chain analysis

• The proof uses a partially accelerated chain whose transition probabilities become affine in the state variable, enabling an exact analysis via Kac’s method.The analysis then relates this accelerated walk back to the original chain by estimating how long the original process must wait at each site.Source: §4.5 · pp. 53–54

4.5.1 Coupling between X and Y chains

• The coupling makes one accelerated-chain step correspond to one or more original-chain steps, while allowing the original chain to advance when the accelerated chain waits.The transition probabilities of the coupled process are shown to match those of the original chain.Source: §4.5 · p. 54, §4.5.1 · p. 55
• After O(n ln n) accelerated steps, the wait-time theorem bounds the probability that the original chain has waited excessively, and the combined estimates yield rapid mixing in the ∥·∥∗ norm.The proof combines the wait-time and accelerated-chain mixing bounds to establish the target estimate for the original chain.Source: §4.5.1 · pp. 56–57

4.5.2 Wait-time analysis

• The wait-time analysis controls visits to low-weight sites, which have the largest delays, using tail bounds for site visits and an Ornstein–Uhlenbeck-inspired description of the accelerated walk.The accelerated walk is biased toward 3n/4, and its continuous-time analogue provides the estimates needed for rare visits to problematic sites.Source: §4.5.2 · p. 57

Then we can bound

• The remaining wait-time bound combines control of the minimum visited site with concentration inequalities for sums of geometric random variables.This combines site-visit estimates and geometric-tail bounds to control the total waiting time.Source: Then we can bound · pp. 58–60
• E[T_left(s)|A] = O(n ln^2 n + s ln n), and when s = O(n ln n), it is O(n ln^2 n).The bound is obtained by maximizing the conditioned wait time over the most frequently visited minimum site and applying Proposition 75.Source: Then we can bound · pp. 60–61

4.5.3 Proof of Proposition 76: Connection with the Ornstein-Uhlenbeck process

• The auxiliary birth-and-death chain is stochastically dominated by the original chain, and its Poissonized Hamming-weight analysis yields the bound expected for an Ornstein–Uhlenbeck process.Poissonization makes the numbers of visits to sites independent Poisson variables, enabling the subsequent concentration analysis.Source: §4.5.3 · pp. 61–63

4.5.4 Proof of Theorem 73: exact solution to the Markov chain Q

• The transition matrix Q has n explicitly determined eigenvalues, with exact eigenvalue gap 4/(3n−1).The stationary distribution is binomial-centered around 3(n−1)/4, with mean 3n/4 + 1/4, shifted by approximately 1/4 relative to the non-accelerated chain.Source: §4.5.4 · pp. 64–65

4.5.5 Exact solution to the Markov chain Q implies a good upper bound on ∥Q^t∥2

• The exact spectral solution reduces the bound on ∥Q^t∥2 to eigenvector overlaps, which are evaluated using Krawtchouk-polynomial expansions and their symmetry and orthogonality.The analysis uses reversibility, biorthogonal left and right eigenvectors, and separate estimates for the m = 0 and m > 0 contributions.Source: §4.5.5 · pp. 65–68

4.5.5 Exact solution to the Markov chain Q implies a good upper bound on ∥Qt∥2

• The exact solution of Markov chain Q, together with Lemma 86 symmetry, yields a good upper bound on ||Q^t||_2 and completes the proof of Theorem 73.The argument applies a corollary of Proposition 84 and substitutes it into the preceding bound.Source: §4.5.5 · pp. 68–69

4.5.6 Proof of Proposition 74: Combining wait-time analysis with the analysis of the accelerated chain

• Proposition 74 is proved by decomposing the event {X_τ = k} over accelerated-chain paths and wait-time intervals, then separately bounding the resulting time-average contributions.The first contribution is controlled using monotonicity of T_left and the dual-norm bound ||(1,1,...)||_* ≤ 1/2; the second uses wait-time interval cases and stochastic domination of T_right by Bin(s, 1/2).Source: §4.5.6 · pp. 69–70

Motivation

• Low-weight Pauli strings may dominate anti-concentration because their contributions scale as 1/3^k and their expected wait times as approximately n/k, despite the initial weight concentrating near n/2.Sufficient probability mass remains at low weights to produce a nontrivial lower bound.Source: §4.6 · p. 72

Time-scale estimates

• Starting from weight 1, the expected escape time to weight n/2 and the time to reach 3/4n are both approximately 5/6 n ln n.These estimates motivate the conjectured anti-concentration threshold.Source: §4.6 · p. 72

Conjecture

• At time 5/6 n ln n + o(n ln n), the conjecture predicts Pr[|⟨x|C|0⟩|^2 ≥ α/2^n] = Ω(1).A special case of this anti-concentration conjecture was recently resolved in [25].Source: §4.6 · p. 72

Birth-death-chain analysis

• The constant-factor analysis models the relevant dynamics as a birth-death chain and bounds hitting times through its transition probabilities and stationary distribution.The argument uses inequalities proven in [8] and obtains only 1 + O(1/n) corrections in the resulting estimate.Source: §4.6 · pp. 72–73

Initial-distribution regimes

• Both the bulk, starting near n/2 and reaching 3/4n, and the initial left tail, reaching approximately 0.74n, require 5/6 n log n + O(n).The right tail is less demanding because it has shorter wait times and is suppressed by the 1/3^k factors.Source: §4.6 · p. 73

5.1 The D = 2 case

• The D = 2 proof reduces the previously established anti-concentration result to a classical probabilistic process, potentially extending to random circuits on arbitrary graphs.It analyzes convergence of a Markov-chain distribution toward its limiting form and asks how quickly this convergence occurs.Source: §5.1 · pp. 74–75
• Alternating row and column circuit applications remove all-zero terms that otherwise keep collision probabilities high, with nonzero rows becoming mapped to their stationary distribution in one application.Applying column updates partially mixes zero states across rows; after a constant number of alternating applications, these zeros disappear with sufficiently large probability.Source: §5.1 · pp. 75–76

5.2 Generalization to arbitrary D-dimensional case

• For arbitrary D, the proof generalizes the two-dimensional argument through coordinate-wise approximate-design bounds to obtain an O(Dn^1/D + D ln(D/ϵ))-depth collision-probability result.The construction successively separates all-zero rows, planes, and higher-dimensional coordinate slices, reducing their probabilities at each coordinate update.Source: §5.2 · p. 77
• Long-range gates yield expected collision-probability guarantees in O(ln n ln ln n) depth by setting D = ln n in the general theorem.This is presented as Corollary 92 of the arbitrary-dimensional analysis.Source: §5.2 · p. 77

Scope

• The method does not yield results for Brown and Fawzi’s stronger decoupling notion.The section therefore addresses their scrambling and weak-decoupling results rather than the stronger model introduced in.Source: §6 · p. 78

Scrambling

• O(ln n ln ln n) depth suffices for 1/poly(n)-approximate scrambling when D = O(ln n), improving Brown and Fawzi’s O(ln^2 n) long-range bound [18].The result also provides a bound for D-dimensional lattices, which was not given in [18].Source: §6 · p. 78
• The scrambling proof reduces the second-moment calculation to a Markov-chain process whose probability of remaining at weight at most n/3 is poly(n)/2^n.This reconstructs theorem A.1 of [18].Source: §6 · pp. 78–79

Weak decoupling

• For constant D, depth s = O(D · n1/D) with c = 1 yields a 1/poly(n)-approximate weak decoupler whenever m < c′n1/D for some c′ < 1.The weak-decoupling guarantee applies to the two input models considered: a pure state or a maximally entangled state on AA′.Source: §6 · p. 79
• The weak-decoupling depth improves over Brown and Fawzi’s n1/D · O(ln n) bound for m = poly(n) [18].The section studies weak decoupling, defined by trace-distance closeness of ρMS to the maximally mixed state on MS.Source: §6 · pp. 79–80

Reduction from approximate sampling

• Assuming a BPP sampler produces q_x within total variation distance ϵ of p_x, Stockmeyer’s theorem yields an FBPP^NP procedure approximating its output probabilities multiplicatively.Here p_x = |⟨x|C|0⟩|^2 for a random circuit C drawn from μ.Source: A Proof of Theorem 3 · p. 81

Anti-concentration

• For every output string y, at least 1/8 − 1/poly(n) of unitaries from the approximate 2-design satisfy p_y ≥ 1/2^(n+1).The proof transfers this anti-concentration statement to the ensemble C_x, which appends uniformly random X gates to a circuit drawn from μ.Source: A Proof of Theorem 3 · p. 81

Moment bounds

• The moment calculation uses Haar second and fourth moments together with μ being a 1/poly(n)-approximate 2-design.The fourth moment under μ is bounded by the corresponding Haar expression up to a 1 + 1/poly(n) factor.Source: A Proof of Theorem 3 · p. 81

Anti-concentration

• Paley–Zygmund applied to these moments supplies the constant-fraction lower bound needed in the reduction.This is the final probabilistic step establishing the stated anti-concentration guarantee.Source: A Proof of Theorem 3 · p. 81

B Basic properties of the Krawtchouk polynomials

• The Krawtchouk polynomials satisfy a symmetry relation in x and t.The symmetry follows because the relevant factorial expression is symmetric in x and t.Source: B Basic properties of the Krawtchouk… · p. 82
• The section states an orthogonality relationship for Krawtchouk polynomials defined for p, q ∈ [0, 1] with p + q = 1.The relationship is formulated using the binomial norm on functions from [N] to R.Source: B Basic properties of the Krawtchouk… · p. 82
• The orthogonality proof uses a generating function and compares overlaps (g_p(y), g_p(z)) for real y and z.Equating the two overlap expressions for all y and z yields the stated relationship.Source: B Basic properties of the Krawtchouk… · pp. 82–83

Declarations

• The authors contributed equally, acknowledged NSF and ARO funding, and disclosed no relevant financial or non-financial interests.AWH and SM received support through specified NSF grants, while AWH also received NSF QLCI and ARO funding.Source: Declarations · p. 83