Source-linked AI summary
Incompressibility and spectral gaps of random circuits
Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, Xinyu Tan
TL;DR
The paper addresses the open question of whether random-circuit moment operators can have spectral gaps independent of t. It combines structured expander walks with randomly chosen local gates, proving near-optimal gaps in exponential t-ranges and showing linear growth of robust quantum circuit complexity for an exponentially long time.
Problem
A spectral gap independent of t was an open question, and such a gap is known to imply that random circuits of depth O(t poly(n)) form t-designs.
Source: §1 · p. 3Method
The proof combines a structured walk using Kassabov’s alternating-group expander and a modified PFC ensemble with local random circuits, using frustration-free Hamiltonian tools to preserve the gap.
Source: §1 · p. 3Results
Near-optimal gaps of ˜Ω(1/n) hold for random reversible circuits up to t≤Θ(2^(n/6.1)) and random quantum circuits up to t≤Θ(2^(2n/5)); robust quantum circuit complexity grows linearly for an exponentially long time.
Source: §1.4 · pp. 11–12Takeaways & Limitations
The spectral-gap estimate implies approximate unitary t-designs and approximate t-wise independent permutations after ˜O(n^2t) gates.
Source: §1.4 · p. 12The quantum gap result assumes t≤Θ(2^(n/2)); the authors say they cannot rule out that this condition is fundamental to a 1/poly(n) gap.
Source: §1.4 · p. 12
Abstract
from arXiv · showhide
Random reversible and quantum circuits form random walks on the alternating group $\mathrm{Alt}(2^n)$ and unitary group $\mathrm{SU}(2^n)$, respectively. Known bounds on the spectral gap for the $t$-th moment of these random walks have inverse-polynomial dependence in both $n$ and $t$. We prove that the gap for random reversible circuits is $\Omega(n^{-3})$ for all $t\geq 1$, and the gap for random quantum circuits is $\Omega(n^{-3})$ for $t \leq \Theta(2^{n/2})$. These gaps are independent of $t$ in the respective regimes. We can further improve both gaps to $n^{-1}/\mathrm{polylog}(n, t)$ for $t\leq 2^{\Theta(n)}$, which is tight up to polylog factors. Our spectral gap results have a number of consequences: 1) Random reversible circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error $t$-wise independent (even) permutations for all $t\geq 1$; for $t \leq \Theta(2^{n/6.1})$, we show that $\tilde{\mathcal{O}}(n^2 t)$ gates suffice. 2) Random quantum circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error unitary $t$-designs for $t \leq \Theta(2^{n/2})$; for $t\leq \Theta(2^{2n/5})$, we show that $\tilde{\mathcal{O}}(n^2t)$ gates suffice. 3) The robust quantum circuit complexity of random circuits grows linearly for an exponentially long time, proving the robust Brown--Susskind conjecture [BS18,BCHJ+21]. Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the ``$\mathrm{PFC}$ ensemble'' from [MPSY24] together with an expander on the alternating group due to Kassabov [Kas07a], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians.
1 Introduction
This section presents spectral-gap bounds for random reversible and quantum circuits in specified regimes, along with the structured-walk and circuit methods used to establish them. It describes their implications for design formation and circuit-complexity growth, including limitations on the quantum moment regime.
1 Introduction
- Random-circuit mixing connects spectral gaps to t-designs, which approximate the uniform measure’s t-th moments and support randomized algorithms and studies of chaotic dynamics.The introduction names randomized benchmarking [MGE12] [KLR+08], classical shadows [HKP20], and derandomization as applications.Source: §1 · p. 3, §1.1 · p. 4
- The gap analysis combines a structured walk with an expander on Alt(2^n) using Kassabov’s generators [Kas07a], then transfers the gap to local random circuits using frustration-free Hamiltonian tools.The construction modifies the PFC ensemble [MPSY24]; the transfer uses the detectability lemma [AALV09, AAV16] and its converse [Gao15].Source: §1 · p. 3
1.1 Previous work
- Prior random-circuit gap bounds depended inversely on both n and t; the paper reports linear-in-t design sizes through its t-independent gap, improving on earlier scaling [BHH16].The cited discussion notes that previous proven design-size bounds had at least quadratic dependence on t.Source: §1.1 · pp. 4, 6
1.2 Results: spectral gaps, t-designs, and circuit complexity growth
- Random reversible circuits have an Ω(n^-3) gap for all t ≥ 1, while random quantum circuits have an Ω(n^-3) gap for t ≤ Θ(2^(n/2)).The introduction identifies a t-independent inverse-polynomial spectral gap as the main technical result.Source: §1 · p. 3, §1.2.1 · p. 6, §1.2.2 · p. 8
1.2.1 Random reversible circuits
- For t ≤ Θ(2^(n/6.1)), random reversible circuits achieve an amplified gap of Ω(n^-1 log(nt)^-3) and multiplicative-error permutation t-designs with O(n(nt + log(1/ε))log^3(nt)) gates.The paper also states that connected circuit layouts admit a 1/poly(n) gap, and structured rather than random circuits can achieve these designs in depth O(nt).Source: §1.2.1 · p. 7
1.2.2 Random quantum circuits
- Random quantum circuits are generalized to arbitrary architectures by replacing qubit permutations with random sequences of SWAP gates matching the connectivity.The analysis uses eigenvalue results for Cayley graphs on the symmetric group generated by transpositions.Source: §1.2.2 · p. 8
- For t ≤ Θ(2^(2n/5)), quantum circuits have an amplified gap and achieve multiplicative-error unitary t-designs with linear-in-t gate or brickwork-depth bounds up to polylogarithmic factors.The bounds are O(n(nt + log(1/ε))(log t)^4) gates for 2-local all-to-all circuits and O((nt + log(1/ε))(log t)^7) brickwork depth.Source: §1.2.2 · p. 8
1.2.3 Circuit complexity growth
- Random reversible circuits with L ≤ O(2^n) gates require at least L/poly(n) gates to implement, with probability at least 1 − 2^-Ω(L/n^3).The introduction presents the corresponding incompressibility result for both random quantum and reversible circuits, resolving the robust Brown–Susskind conjecture [BS18] [BCHJ+21].Source: §1 · p. 3, §1.2.3 · p. 9
- For all-to-all random quantum circuits with L ≤ O(2^(n/2)) gates, robust complexity grows linearly with probability at least 1−e^−Ω(L/n^3), resolving the Brown–Susskind conjecture [BS18] [BCHJ+21].The paper also reports an analogous incompressibility result for random reversible circuits.Source: §1.2.3 · p. 9, §1.4 · p. 12
1.3 Proof overview
- The proof uses Kassabov’s alternating-group expander [Kas07a] and the PFC ensemble [MPSY24], replacing structured components with short circuit implementations.Kassabov’s generators can be implemented with O(n) NOT, CNOT, and Toffoli gates; the quantum construction substitutes local circuit ensembles for PFC components.Source: §1.3 · pp. 10–11
- Frustration-free Hamiltonian tools relate structured-walk gaps to local random circuits, while overlap methods improve the n-dependence to ˜Ω(1/n) at a polylogarithmic cost in t.The reversible proof uses a permutation overlap lemma and large-N interpolation; the quantum construction also simulates phases through conjugated Pauli Z gates.Source: §1.3 · p. 11
1.4 Discussion and outlook
- The gap is ˜Ω(1/n) for all-to-all reversible circuits when t ≤ Θ(2^(n/6.1)) and for all-to-all and brickwork quantum circuits when t ≤ Θ(2^(2n/5)).The authors note that these estimates imply approximate t-designs and t-wise independent permutations after ˜O(n^2t) gates.Source: §1.4 · pp. 11–12
- The authors cannot rule out that the quantum 1/poly(n) gap requires t ≤ Θ(2^(n/2)), and leave the precise large-t gap unresolved.They report numerical evidence suggesting the large-t gap may equal the t = 2 gap, but say they do not know how to make the proposed explanation precise.Source: §1.4 · p. 12
2 Quantifying mixing rates
This section develops ways to quantify random-walk mixing, relating spectral gaps to design guarantees and to additive- and multiplicative-error bounds. It also compares spectral gaps for convolution and averaging of subgroup Haar measures, showing that enlarging the sampled subgroups cannot decrease the gap.
2.1 Essential norm of moment operators and the spectral gap
- The essential norm measures the represented walk away from the trivial subrepresentation: Haar averaging projects onto that subrepresentation, and an exact unitary t-design has zero essential norm.The spectral gap is defined through this essential norm.Source: §2.1 · pp. 13–14
2.2 Multiplicative vs additive error approximate t-designs
- Gap amplification converts spectral-gap bounds into multiplicative-error unitary and permutation t-designs after repeated convolution.The section notes that multiplicative error is stronger than additive error and is needed for some applications, including adaptive queries to t copies [Kre21].Source: §2.2 · p. 15
2.3 Trace norm to spectral norm
- Appending the inverse to an approximate unitary design converts a trace-norm (1→1) error bound into the same essential-norm (2→2) bound, without a dimension-dependent factor.The conversion applies when the resulting composition is symmetric under inversion.Source: §2 · p. 13, §2.3 · p. 17
2.4 Kazhdan constants
- Kazhdan constants yield spectral-gap lower bounds, degrade by at most a factor k under generator replacement by products of length k, and give a sharp quadratic dependence for the gap bound.The section illustrates the sharpness with the cyclic group Z/mZ and generators {−1, 0, 1}.Source: §2.4 · pp. 18–20
2.5 Gaps of convolutions and convex combinations of subgroup distributions
- The detectability bounds originate in the study of gapped frustration-free Hamiltonians.The presentation follows [AAV16] and invokes Gao’s quantum union bound [Gao15].Source: §2.5 · pp. 20–21
- For compact subgroups with each commuting element-wise with all but ℓ others, the convolution and average walks’ spectral gaps are quantitatively related in any unitary representation.The proof represents subgroup Haar averages as projectors onto trivial subgroup subrepresentations and applies the detectability lemma and its converse [AAV16] [Gao15].Source: §2.5 · pp. 20–21
- Replacing sampled compact subgroups by larger compact groups can only increase the spectral gap, a property that need not hold for arbitrary subsets.A group's Haar average projects onto its invariant subspace, which is contained in the invariant subspace of any subgroup.Source: §2.5 · p. 22
3 Spectral gaps for random reversible circuits
Random reversible circuits have a spectral gap of Ω(n^-3) for every t ≥ 1. The proof builds on Kassabov’s generators and bootstraps the gap using smaller subsystems.
3 Spectral gaps for random reversible circuits
- The all-to-all walk samples three distinct bit positions and applies a uniformly random permutation to those bits.This defines the random reversible-circuit model used in the section.Source: §3 · p. 22
3.1 A t-independent spectral gap from Kassabov’s generators
- Kassabov’s generators have uniformly positive Kazhdan constants and can be implemented using O(n) reversible gates without ancillas.Each generator uses NOT, control-NOT, and Toffoli gates, with each bit acted on by O(1) gates.Source: §3 · p. 23
- Kassabov’s generators yield an O(n)-triple structured walk whose gap is used to prove the t-independent reversible-circuit bound.The proof replaces NOT, CNOT, and Toffoli gates in the generators with random three-bit operations, then averages over bit-label permutations.Source: §3.1 · pp. 23–24
3 Spectral gaps for random reversible circuits
- For all n ≥ 4 and t ≥ 1, the random reversible-circuit walk has spectral gap Ω(n^-3).The proof of Theorem 1.1 obtains this bound by averaging relabelings of a structured walk.Source: §3 · p. 22, §3.1 · p. 24
3.2 Bootstrapping spectral gap for random reversible circuits: a proof of Theorem 1.2
- The bootstrapping proof relates the n-bit gap to that of a smaller subsystem and sets its size to Θ(log(nt)).It uses the recurrence ∆(n) ≥ δ(n)∆(n−1) to connect gaps at adjacent system sizes.Source: §3.2 · pp. 24, 26
4 Spectral gaps for random quantum circuits
The section develops spectral-gap bounds for local and brickwork random quantum circuits by relating local circuits to structured walks. It establishes a t-independent Ω(n^-3) gap for brickwork circuits when t ≤ Θ(2^(n/2)) and uses spectral-gap bootstrapping to prove Corollary 1.6.
4 Spectral gaps for random quantum circuits
- For t ≤ Θ(2^(n/2)), the brickwork random-circuit moment operator has norm at most 1 − Ω(n^-3) away from the Haar moment operator.The section also states that both all-to-all and brickwork models have t-independent inverse-polynomial gaps.Source: §4 · p. 26
4.1 Gap for CPFPC ensemble
- The CPFPC ensemble is self-adjoint, and its Clifford factors can be replaced by depth-O(n) brickwork circuits forming approximate unitary 2-designs.The resulting CPFPC construction is used as the foundation for the section's gap analysis.Source: §4.1 · p. 27
4.2 Simulating random phases using permutations
- For t ≤ N − 2, alternating- and symmetric-group permutation moments coincide; conjugated first-qubit Z phases have essential norm at most 8t^2/2^n.The phase bound is stated for permutations drawn uniformly from Alt(2^n).Source: §4.2 · pp. 27–28
- The alternating-group construction yields a unitary-design gap in the regime t ≤ Θ(2^(n/2)).The proof approximates random phases using the alternating-group permutation ensemble and relates it to CPFPC.Source: §4.2 · p. 30
4.3 All roads lead to local random quantum circuits
- A gap for k-local subgroup circuits transfers to 2-local all-to-all circuits, then to brickwork circuits, with the first reduction's loss depending only on k.This machinery reduces quantum-circuit gaps to distributions approximable by polynomial-size circuits whose gates are independently drawn from subgroups.Source: §4.3 · pp. 30, 31, 34
- For every t ≥ 1, the brickwork-ordered adjacent-SWAP walk has a spectral gap of Ω(n^-2).The bound applies to the convolution of the adjacent SWAP distributions in brickwork order.Source: §4.3 · p. 33
- The section reduces all-to-all random quantum circuits to local brickwork circuits and gives gap-transfer propositions for connected architectures.The reduction uses sequences of local subgroups; the propositions cover quantum circuits and classical reversible circuits.Source: §4.3 · pp. 34–35
4.4 Proof of Theorem 1.5 and Corollary 1.6
- The proof constructs O(n^3) 3-qubit unitary subgroups, with the stated result applying for t ≤ c2^(n/2).The argument uses these subgroups to establish the local spectral-gap estimate.Source: §4.4 · pp. 35–36
- 1−g(νLRQC,t)=Ω(n^-6/log n) and 1−g(νBRQC,t)=Ω(n^-5/log n).The proof combines Kassabov-generator circuit implementation, the design gap given the full alternating group, and detectability lemmas.Source: §4.4 · pp. 35–36
- Bootstrapping from log-sized patches and all-to-all connectivity yields Corollary 1.6 by applying the two bootstrapping lemmas to Theorem 1.5.The supplied passages give the range t ≤ Θ(2^(2n/5)) for both bootstrapping lemmas.Source: §4.4 · pp. 36–37
5 Efficient reversible circuits generating Alt(2n)
This section develops small, explicit generating sets for alternating groups and elementary matrix groups, culminating in ancilla-free reversible-circuit implementations of Kassabov’s alternating-group generators. It builds these constructions through structured permutation actions and generators over free rings, including groups involving SL(3s;F2).
5 Efficient reversible circuits generating Alt(2n)
- For every n, a k-element generating set for Alt(2^n) has Kazhdan constant at least ε, with each generator an ancilla-free, strongly explicit reversible circuit using O(n) gates and O(1) gates per bit.The gates are NOT, control-NOT, and Toffoli; the circuit description can be produced in poly(n) time.Source: §5 · p. 37
5.1 Review of Kassabov’s generators
- Kassabov’s construction represents Alt(K^6) as even permutations of a six-dimensional hypercube whose coordinate lines each contain K=2^(3s)-1 points.Each line is identified with the nonzero vectors of F_2^(3s), which are permuted by SL(3s;F_2).Source: §5.1 · p. 38
5.1.1 A large generating set for Alt((23s −1)6)
- Six embeddings of a product of K^5 copies of SL(3s;F_2) act on the hypercube’s coordinate directions, and their combined action generates Alt(K^6).The argument establishes double transitivity and uses a group-order lower bound to show the generated group contains Alt(K^6).Source: §5.1.1 · pp. 38–39
5.1.2 Product of many matrix rings
- A quotient polynomial ring over F_p is isomorphic to a product of p copies of F_p, enabling products of matrix groups to be handled through a single elementary matrix group.The section further shows that products of up to p^(km^2) copies of Mat(m;F_p) are generated by k+2 elements.Source: §5.1.2 · pp. 40–41
5.1.3 Generating elementary matrix groups
- Surjective ring maps induce surjective group maps between elementary matrix groups, providing the bridge from the product-ring generators toward alternating-group generators.Lemma 5.10 supplies an equality used in this chain of maps, though its formula is not present in the supplied passage.Source: §5.1.3 · p. 42
- An elementary matrix group over a free ring with l generators is generated by 4l + 6 elements and their inverses.The listed generators suffice for every elementary matrix over the free ring: multiplication encodes addition and multiplication of ring elements.Source: §5.1.3 · p. 43
5.1.4 A small generating set for SL(3s;F2)×215s
- For k = 1 and s ≥ 15, 18 generators suffice; for k = 3 and s ≥ 7, 26 suffice, as in [Kas07a, Corollary 3.1].The construction gives generators for a larger group involving SL(3s;F2) and a direct product of 2^15s copies.Source: §5.1.4 · p. 43
5.2 Circuits
This section implements generators of the alternating-group construction as reversible circuits. It describes both depth-O(n) and depth-1 implementations, with controlled actions on the bit registers.
5.2 Circuits
- The generators for EL(3s;F2)×2^15s act on 3s data bits, with the other 15s bits selecting one of 2^15s factors.The construction implements one embedding directly; the other five are obtained by permuting sets of 3s bits.Source: §5.2.1 · pp. 44–45
5.2.1 Depth-O(n) circuits
- Constant-function generators have depth-1 CNOT networks, while the controlled generators use exactly 15s Toffoli gates.In the controlled implementation, each Toffoli is controlled by x_a,b and y_b and targets y_s+a.Source: §5.2.1 · pp. 45–46
5.2.2 Depth-1 circuits
- The z_c-controlled generators use s Toffoli gates on nonoverlapping triples, so those gates have depth 1.For each c, the controls are x_c,a and y_a, and the target is y_s+a.Source: §5.2.2 · p. 47
5.3 The action outside Ks
The discussion shifts from the interior of K_s to its exterior and notes that the generating set preserves each component K(w).
5.3 The action outside K_s
- Kassabov’s generating set preserves each component K(w), as the section turns from the interior of K_s to its exterior.The passage identifies the exterior as important for the reversible-circuit construction.Source: §5.3 · p. 47
2 Alt(K(w)) ∼= ×w∈F6
This section develops efficient generation results for alternating groups on bit-string spaces and uses them to establish constant lower bounds on Kazhdan constants. It combines embedded alternating subgroups with bounded-length generation and recursive reduction.
2 Alt(K(w)) ∼= ×w∈F6
- For s ≥ 15, a constant-size generating set for Alt(K(16)) has O(n)-gate elements and a Kazhdan constant uniformly bounded away from zero.The canonical projection from the circuit-generated group onto Alt(K(16)) is surjective.Source: §2 · p. 47
5.3.1 Trivializing the action on the exterior points
- The modified circuits generate Alt(K(16)) while acting trivially outside K(16), using O(n) gates per generator and O(1) gates per bit.The generating set has O(1) elements, each comprising Toffoli and CNOT gates.Source: §5.3.1 · pp. 48–49
5.4.1 Conjugations and commutators in permutation groups
- For N ≥ 5, every element of Alt(N) is a product of three commutators; related lemmas bound products by four conjugates or three subgroup elements.The conjugate bound applies when |B| ≥ |A| + 6 ≥ 8, and the subgroup-product bound when |B| ≥ |C|.Source: §5.4.1 · pp. 51–52
5.4.2 From (23s −1)6 to 218s
- Every element of Alt(F_2^18s) is a product of 3^6 elements from the generating set, using 2^6 embedded copies of Alt(Ks).The embeddings are obtained by toggling the six registers with bit flips.Source: §5.4.2 · p. 53
5.4.3 From 218s to 2n
- To handle n not divisible by 18, the section sets up generation of Alt(F_2^n) from two alternating subgroups acting on n−1 bits and leaving one bit intact.Source: §5.4.3 · p. 54
- Every element of Alt(F_2^(n+1)) is a product of 2592 elements from the two embedded Alt(F_2^n) subgroups.The embeddings act on one coordinate block while leaving the other bit intact.Source: §5.4.3 · p. 54
5.5 Proof of Theorem 5.2
- Theorem 5.2 has a constant lower bound on its Kazhdan constant for all n, using Proposition 5.19 when n is a sufficiently large multiple of 18 and Proposition 5.20 recursively otherwise.The recursive reduction is needed at most 17 times when n is not a multiple of 18 or n < 270.Source: §5.5 · p. 55
6 Circuit complexity and generalizations of Shannon’s argument
The section uses counting arguments, building on Shannon’s approach, to relate approximate designs to circuit complexity. It establishes complexity growth for random reversible and quantum circuits and extends the counting argument to richer gate families.
Counting argument
- Shannon’s Boolean-function count motivates the approach, and the reversible complexity measure counts 3-bit-gate circuits computing even permutations.The even-permutation condition is necessary and sufficient because each 3-bit reversible gate on n≥4 bits is even.Source: §6 · pp. 55–56
- The proof adapts Shannon’s counting argument: approximate t-designs spread probability mass across many operations, while circuits with R gates have only exponentially many possibilities.For unitaries, the argument discretizes the space with δ-nets.Source: §6 · p. 55
Reversible circuit complexity
- R=Ω(L/(n^3 log n)) with probability at least 1−2^−Ω(L/n^3) for random reversible circuits with L=O(2^n) gates.This follows from their approximate permutation t-design property at t=Ω(L/n^4).Source: §6 · p. 56
Quantum circuit complexity
- The quantum lower bound applies even to the stronger state-preparation notion: no small circuit can approximate the target state on a single input.The paper defines robust unitary complexity using approximation within a fixed constant δ.Source: §6 · pp. 56–57
- For δ∈(0,1/2), random-circuit state-preparation complexity grows linearly for L≤O(2^{n/2}), with probability at least 1−e^−Ω(L/n^3).The probability bound’s big-Ω absorbs dependence on δ.Source: §6 · p. 57
- For quantum circuits with L=O(2^{n/2}) gates, approximate unitary t-designs at t=Ω(L/n^4) yield complexity R=Ω(L/n^4) with probability at least 1−2^−Ω(L/n^3).The design statement is for constant multiplicative error.Source: §6 · p. 58
Generalizations
- The counting argument extends to modestly sized local gate choices, including local quantum channels and nonreversible classical gates with ancillas.It also yields a linear-in-L depth lower bound for arbitrary local tensors whose Frobenius norms are bounded by a constant.Source: §6 · p. 58
A Overlap Theorem for Permutations
When the overlap region is at least polynomial in t, products of permutations on overlapping subsystems can emulate a permutation acting jointly on the larger system. The finite-overlap proof interpolates from the infinite-overlap limit using a low-degree polynomial and Markov’s other inequality.
A Overlap Theorem for Permutations
- An overlap region of size |B| ≥ poly(t) lets permutations on A×B and B×C emulate a permutation acting jointly on A×B×C.The passage identifies this phenomenon as central to obtaining linear n-dependence for random quantum circuit gaps.Source: A Overlap Theorem for Permutations · p. 64
- The finite-|B| argument uses the infinite-overlap limit and the low-degree dependence on 1/|B| to control the overlap expression.It avoids fine-grained combinatorics of set partitions.Source: A Overlap Theorem for Permutations · p. 64
- Markov’s other inequality bounds how quickly a bounded, low-degree polynomial can change, supporting the interpolation from the limit to finite overlap.The passage also notes this inequality’s use in the polynomial method in query complexity.Source: A Overlap Theorem for Permutations · pp. 64–65
A.1 Partitions and eigenvectors
The appendix represents the permutation-average +1 eigenspace using states indexed by partitions of [t]. Partition-based inclusion-exclusion connects the orthogonal and nonorthogonal state families, with the basis results stated in the stable range N ≥ t.
A.1 Partitions and eigenvectors
- A partition Π of [t] divides the indices into blocks, and refinement splits blocks while increasing or preserving the number of blocks.The text writes refinement as Π₁ ⪯ Π₂ when every pair equivalent under Π₁ is also equivalent under Π₂.Source: §A.1 · p. 65
- M_Π groups tuples whose entries agree within each block; M′_Π additionally requires entries from different blocks to be distinct.The associated unnormalized states span the +1 eigenspace.Source: §A.1 · p. 65
- For N ≥ t, states indexed by partitions Π of [t] form a nonorthogonal basis for the +1 eigenspace of the permutation moment operator.The cited lemma identifies the basis as {|Õ_Π⟩}.Source: §A.1 · p. 66
- A generalized inclusion-exclusion principle switches between orthogonal and nonorthogonal partition states.The change-of-basis matrix is upper triangular with diagonal entries 1, so its inverse is integral and upper triangular.Source: §A.1 · p. 66
- The change-of-basis matrix K and its inverse depend on t, not N; K⁻¹ is the Möbius inversion associated with the partition partial order.The cited combinatorial-bounds lemma bounds entries of K⁻¹.Source: §A.1 · p. 66
- When N − |Π| + 1 ≤ 0, M′_Π vanishes, and the appendix does not use that regime.Source: §A.1 · p. 66
A.2 Infinite B limit
As the overlap dimension tends to infinity, partition-indexed states become orthogonal, yielding an asymptotic overlap lemma. The section cautions that this limiting orthogonality does not describe finite dimensions, where the states can remain far from orthogonal.
A.2 Infinite B limit
- As |B| tends to infinity for fixed t, the partition-indexed states become orthogonal, enabling the asymptotic overlap lemma.The argument invokes the resulting asymptotic orthogonality and the partition-state expansion of the permutation average.Source: §A.2 · p. 67
- The infinite-overlap calculation alone does not control finite |B|; the section explicitly warns that the partition states can be far from orthogonal even for small t.Source: §A.2 · p. 67
- The finite-dimensional nonorthogonality contrasts with the unitary case discussed in [BHH16].Source: §A.2 · p. 67
A.3 Polynomial interpolation
The proof treats inverse overlap size as a variable and constructs an interpolating function for the finite-overlap expression. It approximates that function by a low-degree polynomial and uses Markov’s other inequality to control the return from the infinite-overlap limit to finite overlap.
A.3 Polynomial interpolation
- Markov’s other inequality controls the polynomial’s change from the limiting value to the target finite-overlap value.The proof concludes by applying the resulting bound to complete Theorem A.1.Source: §A.3 · pp. 68, 72
- The interpolating function is expanded in partition-indexed states, with coefficients independent of N′ and norm terms carrying the N′-dependence.The proof uses bounds on the number and coefficients of these terms.Source: §A.3 · pp. 68, 70
- The proof bounds the operator difference by studying an interpolating function in which x = 1/N′ varies while the other subsystem choices are held fixed.The value at x = 0 corresponds to the infinite-overlap limit, where the difference norm vanishes.Source: §A.3 · p. 68
- Taylor approximation supplies low-degree polynomial approximations to the N′-dependent terms, with the stated regime N′ ≥ t for the norm formulas.The text says the approximation error depends on the total number of factors, including numerator and denominator factors.Source: §A.3 · pp. 70–71
- Combining the approximations yields a polynomial of degree q + O(t) for all N′ ≥ t.The proof then chooses q = Θ(t log t + log N), giving degree Θ(t log t + log N).Source: §A.3 · pp. 71–72
A.4 Deferred proofs
These deferred lemmas control Taylor-approximation errors and show how polynomial bounds on a dense sample set can bound values over the full interval.
A.4 Deferred proofs
- The Taylor-series coefficients are bounded in magnitude by 1, so both expansions are dominated by the geometric series 1, y, y^2, ... for y in [0,1).Their sum is 1/(1-y).Source: §A.4 · p. 72
- The target function’s Taylor series is dominated by that of (1-x)^-p, so its truncation error is bounded by the latter’s.The passage invokes Taylor’s theorem for the truncation bound.Source: §A.4 · pp. 72–73
- If every point in [0,1] lies within Δ < 1/(2q^2) of a sample set U, polynomial bounds on U can control the maximum over the interval.The proof compares a maximizing point with its nearest point in U.Source: §A.4 · p. 73
B Permutation t-designs with multiplicative error 𝜀in circuit depth O(nt + log(1/𝜀))
This section proves a linear-depth construction of permutation t-designs with multiplicative error. An explicit constant-depth gate set achieves depth O(nt + log(1/ε)) in the stated t regime.
B Permutation t-designs with multiplicative error ε in circuit depth O(nt + log(1/ε))
- The depth O(nt + log(1/ε)) permutation-design result was claimed informally in, but the authors report that no proof had appeared.The authors provide a proof because the result may be independently interesting.Source: B Permutation t-designs with… · p. 74
- For t ≤ O(2^(n/6.1)), an explicit set of constant-depth reversible circuits yields a multiplicative-error permutation t-design after O(nt + log(1/ε)) steps.The set elements use NOT, CNOT, and Toffoli gates with all-to-all connectivity.Source: B Permutation t-designs with… · p. 74
- The direct Kassabov-generator construction reaches only a subgroup mapping onto a smaller alternating group, so the proof adds random bit flips and uses an overlap lemma.The subgroup maps onto Alt((2^(3s) − 1)^6); the extension handles arbitrary n.Source: B Permutation t-designs with… · p. 74
B.1 Extending almost full alternating groups with random bit flips
This section uses random bit flips to extend the action of Kassabov generators on a “good” subset of bit strings. The resulting walk has a constant spectral gap in the stated t regime.
B.1 Extending almost full alternating groups with random bit flips
- Each Kassabov generator preserves the good-string subspace, so bit flips supply permutations that do not commute with its projector.The good subspace is spanned by strings in Ks.Source: §B.1 · p. 74
- The proof recasts permutation actions on t-tuples as channels on diagonal matrices, enabling an operator-norm bound for the walk.The diagonal representation identifies vector norm with Schatten 2-norm.Source: §B.1 · pp. 74–75
- Random bit flips bring a bit string into the “good” subspace almost always, helping extend the action beyond the subset preserved by the generators.The bit flips are drawn from the group PX of bit-flip operators.Source: §B.1 · pp. 74–75
- The walk formed by random bit flips around the alternating-group walk on Ks has a constant spectral gap when t is sufficiently below 2^(n/6).The passage states that the gap is constant as long as t ≪ 2^(n/6).Source: §B.1 · p. 75
B.2 Composting Kassabov’s generators
This section composes Kassabov generators with random bit flips to obtain constant-depth reversible circuits and a constant gap in the specified t regime. It then extends the construction to arbitrary n.
B.2 Composting Kassabov’s generators
- Kassabov’s fixed-size generating set uses O(n) nonoverlapping CNOT and Toffoli gates per generator, giving depth 1 with all-to-all connectivity while preserving Ks.Each gate commutes with the projector onto the good-string subspace.Source: §B.2 · p. 77
- The construction composes two random bit flips with a Kassabov generator; each resulting circuit has constant depth using NOT, CNOT, and Toffoli gates.The set is S = {xyz : x,z ∈ PX, y ∈ S0}.Source: §B.2 · p. 77
- To handle arbitrary n, the proof partitions bits into overlapping AB and BC blocks and extends the result from n = 18s using the overlap lemma.The two block walks are induced by applying a uniformly random gate from S to each block.Source: §B.2 · pp. 77–78
- For t = O(2^(n/6.1)), where 6.1 > 6 is arbitrarily chosen, sufficiently large constant k makes the overall essential norm of ν∗k_BC at most 3/4, so the gap is constant.Source: §B.2 · p. 78
C Other efficient generators for permutation groups
The section presents Caprace–Kassabov generators as expanders and describes extending them to permutation groups of arbitrary size. It also discusses their circuit implementation and the limitation posed by circuits without ancillas.
C Other efficient generators for permutation groups
- Generators for dense sizes extend via Lemma 5.18 to generators for Alt(N) for every N [CK23].The dense sequence has a constant-factor bound on the gap between successive sizes.Source: C Other efficient generators for… · p. 78
- It remains unclear how to adapt these generators to very efficient circuits without ancillas for approximate permutation designs; with ancillas, such circuits follow easily and have been used [CK23] [MPSY24] [CBB+24].Source: C Other efficient generators for… · p. 78
- σ, α, and β generate Alt(p^3−1), with a Kazhdan constant bounded below uniformly over odd primes p [CK23].Their Cayley graphs are ε′-expanders of degree 6.Source: C Other efficient generators for… · p. 79
- Adding a transposition extends the generators to Sym(p^3−1), whose Kazhdan constant is at least ε/2.Source: C Other efficient generators for… · p. 79
- For Sym(2^n), the construction uses fewer than 910 generators and degrades the Kazhdan constant by at most a factor independent of n.It extends the generators from Sym(p^3−1) through embedded symmetric groups.Source: C Other efficient generators for… · p. 79
- The seven generator actions have reversible-circuit complexity Õ(n), using interval selection and finite-field arithmetic [CK23].A suitable odd prime can be found with high probability in O(n) random trials using efficient primality testing [AKS04].Source: C Other efficient generators for… · p. 79