# Explicit orthogonal and unitary designs

Ryan O’Donnell${~{}}^{\tiny{ⓡ}}$ Computer Science Department, Carnegie Mellon
University. Rocco A. Servedio${~{}}^{\tiny{ⓡ}}$ Department of Computer
Science, Columbia University. Pedro Paredes${~{}}^{\tiny{ⓡ}}$
Department of Computer Science, Princeton University. ${~{}}^{\tiny{ⓡ}}$Author
ordering randomized.

###### Abstract

We give a strongly explicit construction of $\epsilon$-approximate $k$-designs
for the orthogonal group $\mathrm{O}(N)$ and the unitary group
$\mathrm{U}(N)$, for $N=2^{n}$. Our designs are of cardinality
$\operatorname{poly}(N^{k}/\epsilon)$ (equivalently, they have seed length
$O(nk+\log(1/\epsilon)))$; up to the polynomial, this matches the number of
design elements used by the construction consisting of completely random
matrices.

##  1 Introduction

The main new result in our work is the following:

######  Theorem 1.1.

Let $N=2^{n}$ and let $\mathrm{G}(n)$ denote either the orthogonal group
$\mathrm{O}(N)$ or the unitary group $\mathrm{U}(N)$. Then for any $k=k(n)$,
there is an explicit $\epsilon$-approximate $k$-design for $\mathrm{G}(n)$ of
cardinality $\operatorname{poly}(N^{k}/\epsilon)$; i.e., samplable using a
seed of just $O(nk+\log(1/\epsilon))$ truly random bits. Moreover, these
designs are strongly explicit in the following sense: (i) each output matrix
is given by an $n$-qubit circuit consisting of
$S=\operatorname{poly}(nk)\log(1/\epsilon)$ gates, each gate being either
$\mathrm{CNOT}$ or one of a few fixed and explicitly specified $1$-qubit
gates; (ii) the algorithm that takes as input a seed and outputs the
associated circuit runs in deterministic $\operatorname{poly}(S)$ time.

In the unitary case, similar results in the literature only discuss the regime
$k\leq\operatorname{poly}(n)$ [HL09, Sen18], or have polynomially worse seed
length [BHH16, Haf22]. In contrast, our result holds for all $k$ (even
exponentially large as a function of $n$, or larger), and achieves a seed
length which matches, up to constant factors, that of a random construction. A
significant motivation for our work was the orthogonal case, where the only
prior works we know of are [KM15, HHJ21], which we discuss below. Our Theorem
1.1 provides the efficient orthogonal designs needed for Kothari and Meka’s
near-optimal pseudorandom generators for spherical caps [KM15].

Let us now discuss the general context for our result.

##### Derandomization.

Let $\mathcal{G}$ be a class of objects, and assume informally that each
object has “size” $N^{\Theta(1)}$ (think, e.g., of strings of length $N$, or
$N\times N$ matrices). To choose an object from the uniform probability
distribution on $\mathcal{G}$ typically requires using $\Omega(N)$ truly
random bits. A broad goal in derandomization is to identify a useful notion of
“pseudorandomness” for probability distributions on $\mathcal{G}$, and then to
show that one can sample from such a distribution using just $r\ll N$ truly
random bits.111In this introduction, we refer to sampling uniformly from a set
of size $R$ as “using $\log_{2}R$ truly random bits”. An additional goal is
for the sampling algorithm to be _efficient_ ; i.e., the sampled object should
be produced by a deterministic $\operatorname{poly}(r)$-time algorithm, given
the truly random seed of length $r$. In this case, since the sampler has only
$2^{r}$ possible outcomes yet the total number of objects is exponential in
$N$, it must be the case that the sampler represents the output objects in a
“succinct” way. Informally, if it is possible to efficiently compute with
objects represented in this succinct way, the sampler is said to be “strongly
explicit”.

##### Exact $k$-wise independence.

One of the most common and useful notions of pseudorandomness is that of
_bounded independence_. For random objects with $N^{\Theta(1)}$ “entries”
(“coordinates”/“dimensions”), it often suffices for applications if the
objects are merely “$k$-wise independent” for some $k\ll N$. This means that
the object looks truly random whenever only $k$ entries are inspected. In this
case one may hope that the object can be sampled using a random seed of length
just $O(k\log N)$ bits.

The paradigmatic example of this comes from $k$-wise independent length-$N$
Boolean strings. Using results from coding theory [ABI86], it has long been
known that $O(k\log N)$ random bits suffice to efficiently sample a precisely
$k$-wise independent string ${\boldsymbol{x}}\in\\{0,1\\}^{N}$ (meaning that
$({\boldsymbol{x}}_{i_{1}},\dots,{\boldsymbol{x}}_{i_{k}})$ is perfectly
uniformly distributed on $\\{0,1\\}^{k}$ for any $i_{1},\dots,i_{k}$).

For other kinds of random objects, obtaining _exact_ $k$-wise independence
seems extremely difficult. Take the case of random permutations, where
$\boldsymbol{\pi}\in S_{N}$ is said to be $k$-wise independent if
$(\boldsymbol{\pi}(i_{1}),\dots,\boldsymbol{\pi}(i_{k}))$ is uniformly
distributed on $\binom{[N]}{k}$ for any distinct $i_{1},\dots,i_{k}$. While
simple efficient methods for generating $2$\- and $3$-wise independent
permutations using $O(\log N)$ random bits are known, for any constant $k\geq
4$ the best known efficient construction uses $\Theta(N)$ random bits [FPY15].
The situation is similar for random unitary matrices, where
$\boldsymbol{U}\in\mathrm{U}(N)$ is said to be drawn from a $k$-design if
$\operatorname*{\mathbf{E}}[\boldsymbol{U}_{i_{1}j_{1}}\cdots\boldsymbol{U}_{i_{k}j_{k}}]$
is equal to what it would be if $\boldsymbol{U}$ were Haar-distributed on
$\mathrm{U}(N)$ (and similarly if any subset of the entries
$\boldsymbol{U}_{i_{t}j_{t}}$ in the product were replaced with their complex
conjugates). Here it is known how to efficiently construct exact $2$-designs
using $O(\log N)$ bits [DLT02], and exact $3$-designs using $O(\log^{2}N)$
bits [Web16], but good constructions of exact $k$-designs for $k\geq 4$ are
lacking (see, e.g., [BNZZ19]).

##### Approximate $k$-wise independence.

Given these issues, it is natural to seek _$\epsilon$ -approximate_ $k$-wise
independence ($k$-designs). Here it is important to carefully define the
precise notion of “approximate”, as different natural notions are often only
equivalent if one is willing to change $\epsilon$ by a factor that is
exponential in $k$. For example, in the context of Boolean strings in $\\{\pm
1\\}^{N}$, a weak notion of $(\epsilon,k)$-wise independence is that
$\lvert\operatorname*{\mathbf{E}}[{\boldsymbol{x}}_{i_{1}}\cdots{\boldsymbol{x}}_{i_{k}}]\rvert\leq\epsilon$
for all $k$-tuples of distinct values $i_{1},\dots,i_{k}$. Naor and Naor
[NN93] showed that $O(\log(nk/\epsilon))$ random bits suffice to explicitly
generate such a distribution, where we write $n=\log_{2}N$. However, to get
the stronger guarantee that every $k$ bit positions are $\epsilon$-close to
the uniform distribution in statistical distance, one needs $(\epsilon
2^{-k},k)$-wise independence (see, e.g., [AGHP92]), and hence the number of
random bits used in known constructions is $O(k+\log(n/\epsilon))$. In
general, for $q$-ary rather than $2$-ary (Boolean) strings, the seed-length
penalty becomes $O(k\log q)$. So if, e.g., one wants a distribution on
$\mathbbm{Z}_{N}^{N}$ in which every $k$ coordinates have statistical
difference $\epsilon$ from uniform where $N=2^{n}$,222Cf. achieving
$\epsilon$-approximate $k$-wise independent permutations from $S_{N}$. then
the best known explicit constructions use $O(kn+\log(1/\epsilon))$ random
bits.

In this work, we give a common framework for randomness-efficient generation
of approximately $k$-wise independent distributions over _groups_ ,
particularly subgroups of the unitary group. Our framework applies to, e.g.,
the group of $q$-ary strings $\mathbbm{Z}_{q}^{N}$ (realized as diagonal
matrices with $q$th roots of unity as the diagonal entries), the permutation
group $S_{N}$ (realized as $N\times N$ permutation matrices), the orthogonal
group $\mathrm{O}(N)$, and the unitary group $\mathrm{U}(N)$ (with $N=2^{n}$).
We will not discuss strings further in this work, as they are already very
well studied. We first describe prior work on the other three groups, and then
explain our new general method.

##### Permutations.

Explicit approximate $k$-wise independent permutations have found a wide
variety of applications; e.g., in cryptography [KNR09], hashing/dimensionality
reduction [LK10, KN14], and explicit constructions of expanders [MOP22]. One
method for creating them was initiated by Gowers [Gow96], who showed that a
random $n$-qubit circuit composed of
$\operatorname{poly}(n,k)\log(1/\epsilon)$ “classical” $3$-qubit gates (i.e.,
permutations on $\\{0,1\\}^{3}$) yields an $\epsilon$-approximate $k$-wise
independent permutation on $S_{2^{n}}$. (Note that since the circuit size is
polynomial rather than linear in $nk$, the randomness-efficiency of [Gow96] is
polynomially worse than the $O(nk+\log(1/\epsilon))$ random bits needed by a
non-explicit random construction.) Gowers’s technique was to lower-bound the
spectral gap of the random walk on a related graph by
$1/\operatorname{poly}(n,k)$. (See [HMMR05, BH08] for improvement of the
spectral gap to $1/\widetilde{O}(k^{2}n^{2})$.) Subsequently, using techniques
related to space-bounded walks in graphs [Rei08], Kaplan–Naor–Reingold [KNR09]
derandomized this “truly random walk” to achieve efficient
$\epsilon$-approximate $k$-wise independent permutations on $S_{2^{n}}$ with
seed length $O(kn+\log(1/\epsilon))$, matching the (inexplicit) random bound.
Around the same time, Kassabov [Kas07] got the same seed length (without
requiring $N$ to be a power of $2$) via a sophisticated construction of a
constant-size generating set for any $S_{N}$ that makes the resulting Cayley
graph an expander.

##### Unitary matrices.

Introduced to the quantum computing literature in [DCEL09], explicit
$\epsilon$-approximate $k$-designs for the unitary group have had a wide
variety of applications, from randomized benchmarking of quantum gate sets
[ZZP17], to efficient state and process tomography [HKOT23], to understanding
quantum state and unitary complexity [RY17, BCHJ+21]. Previously, works on
constructing approximate unitary designs have chiefly focused on achieving
“strong explicitness” rather than on randomness-efficiency. In particular, the
goal has been to show that a _truly_ random $n$-qubit quantum circuit composed
of $S=\operatorname{poly}(n,k)\log(1/\epsilon)$ gates (i.e. each gate is a
Haar random unitary operator on a constant number of uniformly randomly chosen
qubits) constitutes an $\epsilon$-approximate $k$-design for
$\mathrm{U}(2^{n})$. The breakthrough in this area came from the work of
Brandão, Harrow, and Horodecki [BHH16], who showed that
$S=O(n^{2}k^{10.5}\log(1/\epsilon))$ suffices for $k\leq 2^{\Omega(n)}$. (See
also [HL09] for an earlier construction using
$\operatorname{poly}(n,k)\log(1/\epsilon)$ gates when $k=O(n/\log n)$, and
[Sen18] for a construction in the $k=\operatorname{poly}(n)$ regime.) Further
work has been done on improving the circuit depth and the exponent on $k$; see
[Haf22]. Ours is the first work to derandomize these results and achieve a
seed length that is _linear_ rather than polynomial in $n$ and $k$, and that
works for all $k$, thus matching the non-explicit random construction. As an
example application of our result for unitary matrices, by applying [BCHJ+21]
we get an efficient deterministic procedure for outputting $2^{O(nk)}$ many
$n$-qubit unitary circuits of $\operatorname{poly}(nk)$ gates such that at
least $2^{\Omega(nk)}$ of them (a polynomially large fraction) have strong
quantum circuit complexity $\Omega(\frac{n}{\log n}k)$ (provided $k\leq
2^{\Omega(n)}$).

##### Orthogonal Matrices.

It is natural to think that designs for $\mathrm{O}(N)$ and $\mathrm{U}(N)$
should be related (and indeed orthogonal designs have played a role in
randomized benchmarking for quantum circuits [HFGW18]). However there is no
obvious reduction between the tasks of constructing $\epsilon$-approximate
$k$-designs for the two groups. The first paper we are aware of that attempts
to explicitly construct approximate orthogonal designs is [KM15]. That work
used explicit orthogonal designs with $O(kn+\log(1/\epsilon))$ seed length as
the core pseudorandom object underlying its state-of-the-art pseudorandom
generator for linear threshold functions on $\mathbb{S}^{n-1}$. Unfortunately,
there was an error in their construction of these designs.333The error is in
the interpretation of the main result of [BG12] that is used to establish
Corollary 6.1 of [KM15]. Corollary 6.1 claims that the spectral gap
established by [BG12] for $\mathrm{SU}(N)$ is independent of $N$, but this is
in error [Kot22]; indeed, as noted in [BHH16] after their Corollary 7, “the
proof [in [BG12]] does not give any estimate of the dependency of the spectral
gap on $N$.” Fixing this error was a key motivation for the present work, and
indeed our Theorem 1.1 provides the crucial ingredient needed for the
pseudorandom generators of [KM15].

Some of our technical ideas for handling the orthogonal group are drawn from
the work of Haferkamp and Hunter-Jones, who showed (Theorem 9 of [HHJ21]) that
truly random local orthogonal $n$-qudit circuits of size
$\operatorname{poly}(n,k)\log(q/\epsilon)$ constitute $\epsilon$-approximate
$k$-designs for $\mathrm{O}(q^{n})$, provided $q\geq 8k^{2}$. This result has
suboptimal randomness complexity because of the polynomial rather than linear
dependence on $n$ and $k$, and only gives approximate $k$-designs for small
values of $k$.

###  1.1 Our framework

As stated earlier, we are interested in $k$-wise independent distributions
over groups, particularly the symmetric, orthogonal, and unitary groups. For
each such group $\mathrm{G}$, the notion of “$k$-wise independence” is defined
through a certain _representation_ $\rho^{k}$ of the group. Informally, we say
a distribution $\mathcal{P}$ on $\mathrm{G}$ is approximately $k$-wise
independent if

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathcal{P}}[\rho^{k}(\boldsymbol{g})]\approx\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}}[\rho^{k}(\boldsymbol{g})],$
(1)

where on the right-hand side $\boldsymbol{g}$ is drawn from the Haar
distribution on $\mathrm{G}$.444Here and throughout, whenever $\mathrm{G}$ is
a compact Lie group we write $\boldsymbol{g}\sim\mathrm{G}$ to denote that
$\boldsymbol{g}$ is drawn according to the Haar distribution; in particular,
this is the uniform distribution if $\mathrm{G}$ is finite.

Let us consider our three example groups $\mathrm{G}$, starting with the
orthogonal group $\mathrm{O}(N)$. In this case, the associated representation
$\rho^{k}$ is on $(\mathbbm{C}^{N})^{\otimes k}$, and it maps
$R\in\mathrm{O}(N)$ to $R^{\otimes k}$. In other words, specialized to the
orthogonal group, Equation 1 asserts that $\mathcal{P}$ is an approximate
$k$-design on $\mathrm{O}(N)$ provided

$\operatorname*{\mathbf{E}}_{\boldsymbol{R}\sim\mathcal{P}}[\boldsymbol{R}^{\otimes
k}]\approx\operatorname*{\mathbf{E}}_{\boldsymbol{R}\sim\mathrm{O}(N)}[\boldsymbol{R}^{\otimes
k}].$ (2)

As matrices, the entries of $\rho^{k}(\boldsymbol{R})=\boldsymbol{R}^{\otimes
k}$ are degree-$k$ monomials in the entries of $\boldsymbol{R}$, and thus
Equation 1 (qualitatively) implies that any degree-$k$ polynomial in the
entries of $\boldsymbol{R}$ has approximately the same expectation under
$\mathcal{P}$ as it has under the Haar distribution. This is the usual meaning
of approximate $k$-wise independence in theoretical computer science, and is
often how the notion is used in applications. For the unitary matrices $U$ we
wish to consider polynomials in both the entries of $U$ and their complex
conjugates; thus the appropriate representation of $\mathrm{U}(N)$ is
$\rho^{k,k}$ on $(\mathbbm{C}^{N})^{\otimes 2k}$ defined by

$\rho^{k,k}(U)=U^{\otimes k}\otimes\overline{U}^{\otimes k}.$ (3)

Actually, to unify notation we will work with $\rho^{k,k}$ even when studying
the orthogonal group $\mathrm{O}(N)\leq\mathrm{U}(N)$; in this case of course
$\rho^{k,k}$ is equivalent to $\rho^{2k}$, and we won’t be concerned with the
difference between $k$ and $2k$. (Note that if $k$ is odd then the expectation
of any degree-$k$ monomial in the entries of $\boldsymbol{R}$,
$\boldsymbol{R}\sim\mathrm{O}(N)$, is trivially 0.) Finally, for the symmetric
group $S_{N}\leq\mathrm{U}(N)$ we could again use $\rho^{k,k}$, but previous
work has (implicitly) used an alternative representation, which we’ll call
$\mathcal{W}^{k}$. To define it, let $[N]_{(k)}$ denote the set of sequences
of distinct indices $i_{1},\dots,i_{k}\in[N]$ and let
$\mathbbm{C}^{[N]_{(k)}}$ denote the (complex) vector space with orthonormal
basis vectors $\ket{i_{1}\cdots i_{k}}$. Then the representation
$\mathcal{W}^{k}$ is defined on $\pi\in S_{N}$ via
$\mathcal{W}^{k}(\pi)\ket{i_{1}\cdots
i_{k}}=\ket{\pi(i_{1})\cdots\pi(i_{k})}$. This representation
$\mathcal{W}^{k}$ is the one usually associated to $k$-wise independence on
$S_{N}$, with the analogue of Equation 1 asserting that
$\operatorname*{\mathbf{E}}_{\boldsymbol{\pi}\sim\mathcal{P}}[(\boldsymbol{\pi}(i_{1}),\dots,\boldsymbol{\pi}(i_{k}))]$
is close to being uniformly distributed on $[N]_{(k)}$ for each
$(i_{1},\dots,i_{k})\in[N]_{(k)}$.

A first way to try to achieve approximate $k$-wise independence on
$\mathrm{G}\in\\{S_{N},\mathrm{O}(N),\mathrm{U}(N)\\}$ is through a Markov
chain. Suppose $P\subset\mathrm{G}$ is a set (closed under inverses) of size
$\operatorname{poly}(n)$, where $n=\log_{2}N$. Consider the random walk on
$\mathrm{G}$ that starts at $\mathbbm{1}$ and multiplies by a uniformly random
element of $P$ at each step. We may hope that after, say,
$\operatorname{poly}(nk)\log(1/\epsilon)$ steps, the resulting distribution
$\mathcal{P}$ on $\mathrm{G}$ is close enough to the Haar distribution on
$\mathrm{G}$ that Equation 1 holds. As alluded to earlier, results of this
form were previously shown for $\mathrm{G}=S_{2^{n}}$ (starting with [Gow96])
and for $\mathrm{G}=\mathrm{U}(2^{n})$ (starting with [BHH16]). One
significant contribution of the present work is to generalize the latter to
apply also to $\mathrm{O}(2^{n})$ (or, more precisely and essentially
equivalently, its connected subgroup $\mathrm{SO}(2^{n})$). Specifically, in
Sections 3, 4 and 5, our goal will essentially be to show the following:

######  Theorem 1.2.

Fix $n\geq 4$ and let $P_{n}\subset\mathrm{SO}(2^{n})$ denote the
$O(n^{2}$)-sized multiset of all $n$-qubit, $1$-gates circuits consisting of
either $\mathrm{CNOT}$ (on some $2$ qubits) or
$\mathrm{Q}=\begin{bmatrix}3/5&-4/5\\\ 4/5&\phantom{-}3/5\\\ \end{bmatrix}$ on
some $1$ qubit, and then closed under negation and inverses. Then for any
$k\geq 1$,

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim
P_{n}}[\rho^{k,k}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{SO}(2^{n})}[\rho^{k,k}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq
1-\frac{1}{n\cdot\operatorname{poly}(k)}.$ (4)

A similar statement holds for $\mathrm{SU}(2^{n})$ with the $1$-qubit
$\mathrm{H}$, $\mathrm{S}$, and $\mathrm{T}$ gates replacing $\mathrm{Q}$.

(See Theorem 3.1 for more details. In Section 2 we will pass from
$\mathrm{SO}(2^{n})$ and $\mathrm{SU}(2^{n})$ to $\mathrm{O}(2^{n})$ and
$\mathrm{U}(2^{n})$; our analysis in Sections 3, 4 and 5 is carried out in the
“special” versions of these groups for technical reasons that will become
clear in Section 3, specifically Section 3.1.) As we discuss in Section 3.1,
the high-level approach we take to establish Theorem 1.2 extends an approach
from [HHJ21].

Given the above theorem, we could improve its right-hand side to
$\epsilon/2^{nk}$ by forming $\boldsymbol{g}$ as a product of
$n\cdot\operatorname{poly}(k)\cdot\log(2^{nk}/\epsilon)=\operatorname{poly}(nk)\cdot\log(1/\epsilon)$
uniformly randomly elements from $P_{n}$. (See Definition 2.2, where we give a
precise definition of “$\epsilon$-approximate $k$-design”, for a discussion of
why $\epsilon/2^{nk}$ is the correct bound for the right-hand side.) The
resulting distribution on $\mathrm{O}(2^{n})$ would be an
$\epsilon$-approximate $k$-design, but unfortunately, drawing from this
distribution would require a seed of
$\operatorname{poly}(nk)\cdot\log(1/\epsilon)$ truly random bits, which leaves
something to be desired from the standpoint of randomness-efficiency.

To improve this and match the randomness-efficiency of the random
construction, one may attempt to apply the method of “pseudorandom walks on
consistently labeled graphs” from [Rei08, RTV06], or “derandomized squaring”
from [RV05]. This is the approach taken in [KNR09] for the symmetric group,
where the evolving value of $\mathcal{W}^{k}(\boldsymbol{\pi})\ket{i_{1}\cdots
i_{k}}$ can be thought of as a random walk on a graph with vertex set
$[N]_{(k)}$. In the setting of Theorem 1.2 there is no graph. Nevertheless, in
Section 6 we will show how derandomized squaring can be slightly generalized
to obtain the following result (a similar generalization appeared recently in
[JMRW22]):

######  Theorem 1.3.

(Abbreviated version of Theorem 6.21.) Given $c,\delta,\epsilon$, there is a
strongly explicit deterministic algorithm that outputs a sequence
$\mathcal{P}$ of $O(c/\operatorname{poly}(\delta\epsilon))$ “monomials” over
the symbols $u_{1},\dots,u_{c},u_{1}^{\dagger},\dots,u_{c}^{\dagger}$, each of
length $O(\log(1/\epsilon)/\operatorname{poly}(\delta))$, such that
$\left\lVert\textnormal{avg}_{\boldsymbol{m}\in\mathcal{P}}\\{\boldsymbol{m}(\mathcal{U})\\}\right\rVert_{\mathrm{op}}\leq\epsilon$
whenever $\mathcal{U}=(U_{1},\dots,U_{c})$ is a sequence of unitaries with
$\left\lVert\textnormal{avg}_{i\in[c]}\\{U_{i}\\}\right\rVert_{\mathrm{op}}\leq
1-\delta$. (Here $m(\mathcal{U})$ denotes the product of $U_{i}$’s and
$U_{i}^{\dagger}$’s obtained by substituting $u_{i}=U_{i}$ in $m$.)

Taking the $\delta$ of Theorem 1.3 to be the $1/\operatorname{poly}(nk)$ of
Theorem 1.2, and the unitaries $\mathcal{U}=(U_{1},\dots,U_{c})$ to correspond
to the 1-gate circuits of Theorem 1.2, we obtain strongly explicit
$\epsilon$-approximate $k$-designs as described in Theorem 1.1 for the special
orthogonal and special unitary groups. A simple modification gives
corresponding designs for the unitary and orthogonal groups, thus yielding
Theorem 1.1.

###  1.2 Organization of this paper

In Section 2 we give the detailed argument explaining how an initial spectral
gap of the sort given by Theorem 1.2 and the generalized “derandomized
squaring” result given by Theorem 1.3 together yield efficient explicit
approximate designs for the orthogonal and unitary groups. The rest of the
paper is devoted to establishing the two necessary ingredients Theorem 1.2 and
Theorem 1.3. Section 3 gives our general framework for establishing the
initial spectral gap for the special unitary and special orthogonal groups; as
we explain there, a crucial step in this framework is establishing a spectral
gap for a certain “auxiliary” $m$-qubit random walk which was inspired by the
analysis of [HHJ21]. Similar to [HHJ21], it turns out that to analyze this
auxiliary random walk, two quite different technical arguments are required
depending on whether the tensor power $k$ is “large” or “small” compared to
the number of qubits $m$; we give these two arguments in Section 4 and Section
5 respectively. Finally, we provide the necessary analysis of the generalized
“derandomized pseudorandom walks” in Section 6.

###  1.3 Notation and preliminaries

To give our constructions it is convenient to use the language of quantum
computing, even when the group involved is the orthogonal or symmetric group.
We will generally consider operators on $\mathbbm{C}^{N}$, where $N=2^{n}$ for
some $n\in\mathbbm{N}^{+}$. We identify
$\mathbbm{C}^{N}=(\mathbbm{C}^{2})^{\otimes n}$ and think of the tensor
factors as corresponding to $n$ qubits.

######  Notation 1.4.

Let $g\in\mathrm{U}(2^{\ell})$, thought of as an $\ell$-qubit “gate” and let
$e=(i_{1},\dots,i_{\ell})$ be a sequence of $\ell$ distinct elements of $[n]$,
i.e. $e\in[n]_{\ell}$. (Here $\ell$ should be thought of as “much less than
$n$”, in particular we will be interested in constant $\ell$.) We use the
notation $g_{e}$ for the operator in $\mathrm{U}(N)$ defined by applying $g$
on qubits (i.e., tensor factors) $i_{1},\dots,i_{\ell}$ (in that order) and
applying the identity operator on the remaining $n-\ell$ qubits. When
$e\in\binom{[n]}{\ell}$ is a set rather than a sequence, we assume the
increasing order on its elements.

We write $A^{\dagger}$ to denote the conjugate transpose of a complex matrix
$A$, $\left\lVert A\right\rVert_{\mathrm{op}}$ to denote the operator norm,
and $\lVert A\rVert_{1}$ to denote its Schatten $1$-norm. We use bold font to
denote random variables.

##  2 A general framework: Explicit $k$-wise independent permutations,
orthogonal designs, and unitary designs

Let $\mathrm{G}(n)$ be a subgroup of $\mathrm{U}(n)$ (the key examples to keep
in mind are the group of permutations on $2^{n}$ elements, the
$2^{n}$-dimensional orthogonal group, the $2^{n}$-dimensional unitary group
itself, and the “special” versions of the latter two). In light of Theorem
1.3, given a probability distribution on a subset of $\mathrm{G}(n)$, we would
like to understand how fast the associated random walk mixes vis-a-vis a
particular representation, namely the $k$-wise tensor product representation
(since that representation corresponds to $k$-wise independence).

Let $\mathcal{P}$ be a probability distribution on $\mathrm{G}(n)$ that is
symmetric (meaning that $\boldsymbol{g}^{-1}=\boldsymbol{g}^{\dagger}$ is
distributed as $\mathcal{P}$ when $\boldsymbol{g}$ is), and let $\rho$ be a
unitary representation of $\mathrm{G}(n)$. Note that since $\rho$ is unitary,
$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim{\cal
P}}[\rho(\boldsymbol{g})]$ is a Hermitian operator with real eigenvalues lying
in $[-1,1]$. Since our goal is $k$-wise independence, the representations that
are of interest to us are $k$-wise tensor product representations:

######  Notation 2.1 ($k$-wise tensor product representations).

For any $k\in\mathbbm{N}^{+}$, we will write $\rho^{k,k}_{2^{n}}$ for the
(complex) representation of $\mathrm{G}(n)$ defined by

$\rho^{k,k}_{2^{n}}(g)=g^{\otimes k,k}\coloneqq g^{\otimes
k}\otimes\overline{g}^{\otimes k},$ (5)

where $\overline{g}$ denotes the complex conjugation of matrix $g$.

There are several different definitions of $\epsilon$-approximate $k$-designs
in the literature, all of which are equivalent if one is willing to lose
factors of $2^{nk}$ on $\epsilon$. For definiteness, we choose the $1$-norm
definition from [HL09]. (One could also equivalently use the notion from
Kothari–Meka [KM15], again up to $2^{nk}$ factors.)

######  Definition 2.2.

A distribution ${\cal P}$ on a finite subset of matrices from $\mathrm{G}(n)$
is an _$\epsilon$ -approximate $k$-design for $\mathrm{G}(n)$_ if

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\cal
P}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]\right\rVert_{1}\leq\epsilon$
(6)

(where $\left\lVert\cdot\right\rVert_{1}$ denotes the Schatten $1$-norm). We
remark that the above condition is implied by the following operator-norm
bound:

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\cal
P}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq\epsilon/2^{nk},$
(7)

and indeed we will establish our approximate design results by going through
the operator norm.

Often we will study the operator
$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathcal{P}}[\rho^{k}(\boldsymbol{g})]$
through its “Laplacian”, which we define as follows:

######  Definition 2.3.

We define the “Laplacian”

$L_{\mathcal{P}}(\rho)=\mathbbm{1}-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathcal{P}}[\rho(\boldsymbol{g})],$
(8)

a self-adjoint (since $\mathcal{P}$ is symmetric) operator satisfying the
following inequalities (in the PSD order):

$0\leq L_{\mathcal{P}}(\rho)\leq 2\cdot\mathbbm{1}.$ (9)

######  Notation 2.4.

In the preceding definition, we abuse notation as follows: In place of
$\mathcal{P}$ we may write a finite (multi)set $P\subset\mathrm{G}(n)$, in
which case the uniform distribution on $P$ is understood. We may also write
“$\mathrm{G}(n)$” in place of $\mathcal{P}$, in which case the uniform (Haar)
distribution is understood. Finally, if $\mathcal{P}$ now denotes a
distribution on $\mathrm{G}(\ell)$, and $E\subseteq[n]_{\ell}$, we write
$\mathcal{P}\times E$ for the distribution on $\mathrm{G}(n)$ given by
choosing $\boldsymbol{g}\sim\mathcal{P}$, independently choosing
$\boldsymbol{e}\sim E$ (uniformly), and finally forming
$\boldsymbol{g}_{\boldsymbol{e}}$.

######  Definition 2.5.

Given a symmetric probability distribution $\mathcal{P}$ as in Definition 2.3,
we define its “lazy” version, $\widetilde{\cal P}$, to be the distribution
which is an equal mixture of ${\cal P}$ and the point distribution supported
on the identity element $\mathbbm{1}$ (note that $\widetilde{\cal P}$ is also
a symmetric distribution). Similar to Definition 2.3, we have that
$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\widetilde{\cal
P}}[\rho(\boldsymbol{g})]$ is a Hermitian operator but now with real
eigenvalues lying in $[0,1]$, and we have the PSD inequalities

$0\leq L_{\widetilde{\mathcal{P}}}(\rho)\leq\mathbbm{1}.$ (10)

######  Fact 2.6.

In the setting of Definitions 2.3 and 2.5, $L_{\mathrm{G}(n)}(\rho)$ is an
orthogonal projection operator, and for any symmetric $\mathcal{P}$ we have
that

$\ker L_{\mathrm{G}(n)}(\rho)\subseteq\ker L_{\mathcal{P}}(\rho)$ (11)

always holds (because for _every_ $g_{0}$ in the support of $\mathcal{P}$ we
have $\rho(g_{0})\Pi=\Pi$, where
$\Pi=\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]$).
From this, and Equations 9 and 10, we also get

$L_{\mathrm{G}(n)}(\rho)\geq\tfrac{1}{2}\cdot L_{\mathcal{P}}(\rho),$ (12)
$L_{\mathrm{G}(n)}(\rho)\geq L_{\widetilde{\mathcal{P}}}(\rho).$ (13)

As Equations 12 and 13 contain a surfeit of symbols, one may wish to read them
respectively as

$\text{``(randomizing $n$
qubits)}\geq\tfrac{1}{2}\cdot\text{($\mathcal{P}$-pseudorandomizing $n$
qubits)}\quad\text{[vis-a-vis~{}$\rho$]''},$ (14) $\text{``(randomizing $n$
qubits)}\geq\text{($\widetilde{\mathcal{P}}$-pseudorandomizing $n$
qubits)}\quad\text{[vis-a-vis~{}$\rho$]''},$ (15)

with the “”$\geq\frac{1}{2}\cdot$” part pronounced “is at least $\frac{1}{2}$
as good as”.

It will be convenient to use the Laplacian operator in some of the steps in
the following sections, even though we ultimately want statements about the
expectation operator. To convert between the two we will use the following:

######  Fact 2.7.

For any unitary representation $\rho$, $L_{\mathcal{P}}(\rho)\leq\epsilon\cdot
L_{\mathrm{G}(n)}(\rho)$ is equivalent to

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\cal
P}[\rho(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq\epsilon.$
(16)

###  2.1 Initial spectral gaps for $S_{N}$, $\mathrm{SO}(N)$ and
$\mathrm{SU}(N)$

Here we summarize all of the non-trivial spectral gaps that we will amplify
using Theorem 1.3.

######  Theorem 2.8 ([BH08]).

For any $k\geq 1$, there is a (multi)set $P_{S_{2^{n}}}$ of cardinality
$O(n^{3})$ such that

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim
P_{S_{2^{n}}}}[\mathcal{W}^{k}_{2^{n}}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim
S_{2^{n}}}[\mathcal{W}^{k}_{2^{n}}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq
1-\frac{1}{\widetilde{O}(k^{2}n^{2})}.$ (17)

Recall that the representation $\mathcal{W}^{k}_{2^{n}}$ is defined on $g\in
S_{2^{n}}$ via $\mathcal{W}^{k}_{2^{n}}(g)\ket{i_{1}\cdots
i_{k}}=\ket{g(i_{1})\cdots g(i_{k})}$. The set $P_{S_{2^{n}}}$ mentioned above
is the set of “simple 3-bit permutations”. This is the set of permutations
$f_{i,j_{1},j_{2},h}$, where $i,j_{1},j_{2}\in[n]$ are all distinct, and $h$
is a Boolean function on $\\{0,1\\}^{2}$, which maps
$(x_{1},\ldots,x_{n})\in\\{0,1\\}^{n}$ to $(x_{1},\ldots,x_{i-1},x_{i}\oplus
h(x_{j_{1}},x_{j_{2}}),x_{i+1}\ldots,x_{n})$.

We establish the following in Sections 3, 4 and 5.

######  Theorem 2.9 (Theorem 3.1 restated).

For $\mathrm{G}(n)\in\\{\mathrm{SO}(2^{n}),\mathrm{SU}(2^{n})\\}$, and any
$k\geq 1$, there is a (multi)set $P_{G}$ of cardinality $O(n^{2})$ such that

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim
P_{G}}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq
1-\frac{1}{n\cdot\operatorname{poly}(k)}.$ (18)

The sets $P_{G}$ for $\mathrm{SO}(2^{n})$ and $\mathrm{SU}(2^{n})$ are
described in Section 3.4.1.

Our proof of Theorem 2.9 is itself a general framework that could potentially
be used to obtain similar results for other subgroups of the unitary group
(for example, the sympletic group), even though we only carry out the
calculations for $\mathrm{SO}(2^{n})$ and $\mathrm{SU}(2^{n})$.

###  2.2 Explicit $k$-wise independent permutations, orthogonal designs, and
unitary designs

We can finally apply Theorem 1.3, so let’s write our above results in the
notation of this theorem. Fix $k\geq 1$ and consider any of the $P$
(multi)sets described in Theorems 2.8 and 2.9.

Let ${\cal
U}=(\rho(g)-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]:g\in
P)$ be a sequence of unitaries, where $\rho$ is the appropriate unitary
representation ($\mathcal{W}^{k}_{2^{n}}$ for $S_{2^{n}}$ and
$\rho^{k,k}_{2^{n}}$ for $\mathrm{SO}(2^{n})$ and $\mathrm{SU}(2^{n})$). For
this choice of ${\cal U}$ we have $c=|P|=\operatorname{poly}(n)$. Notice that
$\left\lVert\textnormal{avg}_{i\in[c]}\\{U_{i}\\}\right\rVert_{\mathrm{op}}$
is exactly the left hand side of the equations in Theorems 2.8 and 2.9, so we
know that this average is at most $1-\delta$ for
$\delta=1/\operatorname{poly}(n,k)$ (as observed, this is actually
$1/\widetilde{O}(k^{2}n^{2})$ for $S_{2^{n}}$ and
$1/(n\operatorname{poly}(k))$ for $\mathrm{SO}(2^{n})$ and
$\mathrm{SU}(2^{n})$). Given $\epsilon>0$, applying Theorem 1.3 (with its
“$\epsilon$” parameter set to $\epsilon/2^{nk}$) we obtain a sequence ${\cal
P}$ of cardinality $\operatorname{poly}(2^{nk}/\epsilon)$ that satisfies
$\left\lVert\textnormal{avg}_{U\in{\cal
P}}\\{U\\}\right\rVert_{\mathrm{op}}\leq\epsilon$. Additionally, $U\in{\cal
P}$ is a product of at most $\operatorname{poly}(nk)\log(1/\epsilon)$ elements
of ${\cal U}$, and so it can be written as
$\rho(g)-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]$,
where $g$ is a product of at most $\operatorname{poly}(nk)\log(1/\epsilon)$
elements of $P$. This follows since for any $g,g^{\prime}\in P$,

$\left\lparen\rho(g)-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]\right\rparen\left\lparen\rho(g^{\prime})-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]\right\rparen=\left\lparen\rho(g\cdot
g^{\prime})-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]\right\rparen,$
(19)

where we use the fact that
$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho(\boldsymbol{g})]$
is an orthogonal projection operator, and that $\rho$ is a representation. We
combine all of this in the following theorems:

######  Theorem 2.10.

Let $\epsilon>0$. Then for any $k=k(n)$, there is a set ${\cal P}_{S_{2^{n}}}$
that satisfies:

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim{\cal
P}_{S_{2^{n}}}}[\mathcal{W}^{k}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim{S_{2^{n}}}}[\mathcal{W}^{k}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq\epsilon/2^{nk}.$
(20)

Additionally, this set satisfies the following properties:

  * •

Its cardinality is $\operatorname{poly}(2^{nk}/\epsilon)$.

  * •

Each element of ${\cal P}_{S_{2^{n}}}$ is given by an $n$-qubit circuit
consisting of $S=\operatorname{poly}(nk)\log(1/\epsilon)$ gates, which are
elements of $P_{G}$.

  * •

The algorithm that takes as input a seed and outputs the associated circuit
runs in deterministic $\operatorname{poly}(S)$ time.

######  Theorem 2.11.

Let $\mathrm{G}(n)\in\\{\mathrm{SO}(2^{n}),\mathrm{SU}(2^{n})\\}$ and
$\epsilon>0$. Then for any $k=k(n)$, there is a set ${\cal P}_{G}$ that
satisfies:

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim{\cal
P}_{G}}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n)}[\rho_{2^{n}}^{k,k}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq\epsilon/2^{nk}.$
(21)

Additionally, this set satisfies the following properties:

  * •

Its cardinality is $\operatorname{poly}(2^{nk}/\epsilon)$.

  * •

Each element of ${\cal P}_{G}$ is given by an $n$-qubit circuit consisting of
$S=\operatorname{poly}(nk)\log(1/\epsilon)$ gates, which are elements of
$P_{G}$.

  * •

The algorithm that takes as input a seed and outputs the associated circuit
runs in deterministic $\operatorname{poly}(S)$ time.

Ultimately we want designs for $\mathrm{O}(2^{n})$ and $\mathrm{U}(2^{n})$; we
obtain them from the above via the following simple corollary.

######  Corollary 2.12 (Theorem 1.1 restated).

Let $\mathrm{G}(n)\in\\{\mathrm{O}(2^{n}),\mathrm{U}(2^{n})\\}$ and
$\epsilon>0$. Then for any $k=k(n)$, there is a set ${\cal P}_{G}$ that
satisfies the conditions of Theorem 2.11.

###### Proof.

To obtain the result for $\mathrm{O}(2^{n})$, after sampling from ${\cal
P}_{\mathrm{SO}}$ one samples $\boldsymbol{b}$ as a uniformly random $\pm 1$
and multiplies the first column of the sampled matrix by $\boldsymbol{b}$
(which only changes the cardinality of the resulting ${\cal P}_{\mathrm{O}}$
by a factor of $2$).

For $\mathrm{U}(2^{n})$, no augmentation of ${\cal P}_{\mathrm{SU}}$ is
required; i.e., we can simply take ${\cal P}_{\mathrm{U}}={\cal
P}_{\mathrm{SU}}$.555We thank an anonymous reviewer for this observation. To
see this, first recall that the representations $\rho^{k,k}_{2^{n}}$ of
$\mathrm{U}(2^{n})$ and of $\mathrm{SU}(2^{n})$ respectively have kernels
$K_{\mathrm{U}}=\\{e^{i\alpha}\mathbbm{1}\ :\ \alpha\in[0,2\pi)\\}$ and
$K_{\mathrm{SU}}\\{-\mathbbm{1},\mathbbm{1}\\}$. Next, recall that
$\mathrm{U}(2^{n})/K_{1}\cong\mathrm{SU}(2^{n})/K_{2}$, since both of these
are isomorphic to the projective unitary group $\mathrm{PU}(2^{n})$ (see e.g.
[Wik23]). Now, since the push-forward of the Haar measure of a compact group
$G$ to a factor group $G/H$ is exactly the Haar measure on $G/H$, it follows
that the set ${\cal P}_{\mathrm{SU}}$ of unitaries in $\mathrm{SU}(2^{n})$
that forms an $\epsilon$-approximate $k$-design of $\mathrm{SU}(2^{n})$ is
also an $\epsilon$-approximate $k$-design of $\mathrm{U}(2^{n})$. ∎

It is of note that we can apply the framework of this section, through Theorem
1.3, to obtain explicit designs of any subgroup of the unitary group using any
unitary representation, as long as one establishes an initial gap first, like
in Section 2.1.

##  3 Establishing an initial spectral gap for special orthogonal and unitary
groups

In the rest of the paper we consider a sequence of groups
$(\mathrm{G}(n))_{n\geq 1}$ which is either $(\mathrm{SO}(2^{n}))_{n\geq 1}$
or $(\mathrm{SU}(2^{n}))_{n\geq 1}$. We recall (see e.g. [Mec19, Section 1.3])
that these groups have associated Lie algebras $\mathfrak{g}_{n}$, where

$\displaystyle\text{for~{}}\mathrm{G}(n)=\mathrm{SO}(2^{n}),\
\mathfrak{g}_{n}$ $\displaystyle=\\{H\in\mathbbm{R}^{2^{n}\times
2^{n}}:H\text{ skew-symmetric}\\},$ (22)
$\displaystyle\text{for~{}}\mathrm{G}(n)=\mathrm{SU}(2^{n}),\
\mathfrak{g}_{n}$ $\displaystyle=\\{H\in\mathbbm{C}^{2^{n}\times
2^{n}}:H\text{ skew-Hermitian},\operatorname{tr}(H)=0\\}.$ (23)

When we need to specialize our discussion to a particular one of these two
cases, we will do so explicitly; most of our arguments go through for both
settings (and many go through for the more general setting in which
$\mathrm{G}(n)$ is any compact connected Lie group).

As discussed in Section 2, given Theorem 6.21, in order to construct an
explicit $k$-design for $\mathrm{G}(n)$ it suffices to construct an explicit
sequence $\mathcal{U}=(U_{1},\dots,U_{c})$ of $2^{n}\times 2^{n}$ matrices
from $\mathrm{G}(n)$ satisfying
$\left\lVert\rho^{k,k}_{2^{n}}(U_{i})\right\rVert_{\mathrm{op}}\leq 1$ for all
$i$ and
$\left\lVert\textnormal{avg}(\rho^{k,k}_{2^{n}}(\mathcal{U}))\right\rVert_{\mathrm{op}}\leq
1-{\frac{1}{n\cdot\operatorname{poly}(k)}}$ (in fact, a spectral gap of
$\operatorname{poly}(n,k)$ would also be sufficient). Constructing such a
sequence for $\mathrm{G}(n)$ as described above is the main goal of this
section and is accomplished in the following theorem:

######  Theorem 3.1.

Let $(\mathrm{G}(n))_{n\geq 1}\in\\{(\mathrm{SO}(2^{n}))_{n\geq
1},(\mathrm{SU}(2^{n}))_{n\geq 1}\\}$. There is a fixed positive integer
$n_{0}=4$ and a finite multiset $P_{n_{0}}\subset\mathrm{G}(n_{0})$ such that
for all sufficiently large $n$ and all $k\geq 1$, we have

$\forall k\in\mathbbm{N}^{+},\quad
L_{\widetilde{P}_{n_{0}}\times\binom{[n]}{n_{0}}}(\rho^{k,k}_{2^{n}})\geq{\frac{1}{n\cdot\operatorname{poly}(k)}}\cdot
L_{\mathrm{G}(n)}(\rho^{k,k}_{2^{n}}).$ (24)

(We note that even without using the “pseudorandom walks” machinery of Section
6, as discussed in Section 1.1, since Theorem 3.1 establishes an initial
spectral gap of $1-{\frac{1}{n\cdot\operatorname{poly}(k)}}$, simply taking a
product of $n\cdot\operatorname{poly}(k)\cdot\log(2^{nk}/\epsilon)$ uniform
random draws from $\widetilde{P}_{n_{0}}$ would yield an
$\epsilon$-approximate $k$-design for $\mathrm{G}(n)$ with seed length
$\operatorname{poly}(n,k)\cdot\log(1/\epsilon)$. By combining Theorem 3.1 with
Theorem 6.21 (i.e. using pseudorandom walks) we are able to improve this to
seed length $O(nk+\log(1/\epsilon))$, thus matching the random construction.)

###  3.1 Overview of the proof of Theorem 3.1

Our proof of Theorem 3.1 refines and extends an approach from [HHJ21], and
combines it with arguments from [BHH16]. In this subsection we give a high-
level overview of the structure of the proof, and in the next subsection we
give (a modular version of) the actual proof. Establishing the various modular
pieces will comprise the rest of the paper after Section 3.2.

In Theorem 4 of [HHJ21], Haferkamp and Hunter-Jones establish a spectral gap
for non-local random quantum circuits with truly (Haar) random two-qudit
unitary gates over the unitary group. This is done by analyzing Haar random
unitary gates over $m-1$ randomly chosen qubits from an $m$-qubit system; this
enables them to establish a recurrence relation which lets them bound the
spectral gap of $k$-qudit Haar random unitary gates in terms of the spectral
gap of $(k+1)$-qudit Haar random unitary gates. Our Lemma 3.2 below is a
generalization and rephrasing of their recurrence relation for the
special666At the end of this subsection we explain why, even though our
ultimate goal is to obtain results for the orthogonal and unitary groups, we
need to work with the special versions of these groups at this point in the
argument. unitary and special orthogonal groups; it essentially says that if
truly randomizing (a randomly chosen) $m-1$ out of $m$ qubits is “not too much
worse” than truly randomizing all $m$ qubits, then truly randomizing only a
constant number of (randomly chosen) qubits out of $m$ qubits is also not too
much worse than truly randomizing all $m$ qubits. Given this, the remaining
tasks are (1) to show that indeed truly randomizing (a randomly chosen) $m-1$
out of $m$ qubits is “not too much worse” than truly randomizing all $m$
qubits; and (2) to show that at the bottom level of the argument, it suffices
to _pseudorandomize_ a constant number of (randomly chosen) qubits out of $m$
qubits.

Task (1) requires a significant amount of technical work and is the subject of
Section 4 and Section 5. We follow the high-level approach of [HHJ21] by
breaking the analysis into two sub-cases (Theorem 3.3 and Theorem 3.4)
depending on the relative sizes of $k$ and $m$. In each of these sub-cases we
adapt and generalize the analysis of [HHJ21] (we note that the “small-$m$”
case of [HHJ21], for the unitary group, was based in turn on [BHH16]) in a way
which permits a unified treatment of both the special orthogonal group and the
special unitary group.

Task (2) is necessary because our ultimate goal statement, Theorem 3.1,
requires the randomly chosen non-local gates to be drawn from a _finite_
ensemble of gates rather than being Haar random (“truly random”) gates over
$n_{0}$ qubits. For this step (made formal in Lemma 3.6), following [BHH16] we
use a deep result of Bourgain and Gamburd (subsequently generalized by
Benoiste and de Saxcé [BdS16]) to pass from the Haar distribution over
$\mathrm{G}(n_{0})$ to a uniform distribution over an explicit finite ensemble
of $n_{0}$-qubit gates; see Section 3.4. The [BdS16] results require that the
Lie groups in question be compact and simple; this requirement is why we need
to work with the special versions of the unitary and orthogonal groups
(indeed, in the special orthogonal case we need to further pass to the
projective special orthogonal group; see the proof of Corollary 3.10).

###  3.2 Proof of Theorem 3.1

In order to establish the lower bound of Equation 24 we will need to chain
together some statements that go in the opposite direction from Equation 14
and Equation 15. We do this via the following lemma, which we prove in Section
3.3.

######  Lemma 3.2.

Fix a positive integer constant $n_{0}\geq 4$. Suppose that for $n_{0}<m\leq
n$ we have

$\forall k\in\mathbbm{N}^{+},\quad
L_{\mathrm{G}(m-1)\times\binom{[m]}{m-1}}(\rho^{k,k}_{2^{m}})\geq\tau_{k,m}\cdot
L_{\mathrm{G}(m)}(\rho^{k,k}_{2^{m}}).$ (25)

Then

$\forall k\in\mathbbm{N}^{+},\quad
L_{\mathrm{G}(n_{0})\times\binom{[n]}{n_{0}}}(\rho^{k,k}_{2^{n}})\geq\left\lparen\prod_{n_{0}<m\leq
n}\tau_{k,{m}}\right\rparen\cdot L_{\mathrm{G}(n)}(\rho^{k,k}_{2^{n}}).$ (26)

We remark that Lemma 3.2 only deals with “truly” (Haar) random gates; later we
will move from $n_{0}$-arity “truly random” gates to “pseudorandom” gates,
which are drawn uniformly at random from a finite multiset. It may be helpful
to think of the lemma’s conclusion (Equation 26) as intuitively saying that
truly randomizing only constantly many (randomly chosen) qubits is “not too
much worse” than truly randomizing all $n$ qubits, vis-a-vis the $k$-wise
tensor product representation.

With the above lemma in hand, proving Theorem 3.1 breaks down naturally into
two steps.

First step: Passing from truly random $m$-qubit gates to truly random
$(m-1)$-qubit gates. In other words, lower-bounding $\tau_{k,m}$ for
$m=n_{0}+1,\dots,n$. This is the main technical task where the bulk of our
work is required. The analysis is done separately for “large $m$” and “small
$m$” cases, similar to Lemmas 6 and 7 of [HHJ21], respectively.

Section 4 lower bounds $\tau_{k,m}$ for “large $m$”:

######  Theorem 3.3.

For all $k\leq\frac{1}{\sqrt{10}m^{2}}2^{m/2}$ we have that Equation 25 holds
with $\tau_{k,m}\geq 1-{\frac{1}{m}}-{\frac{\sqrt{10}km}{2^{m/2}}}$.

Section 5 gives a lower bound on $\tau_{k,m}$ which will be useful for “small
$m$”:

######  Theorem 3.4.

For all $m\geq 4$ and all $k\in\mathbbm{N}^{+}$, we have that Equation 25
holds with $\tau_{k,m}\geq.04.$

(We note that Theorem 3.4’s requirement that $m\geq 4$ is why we take
$n_{0}=4$ in Theorem 3.1.)

Given Theorem 3.3 and Theorem 3.4, we get the desired lower bound on
$\tau_{k,n_{0}+1}\cdots\tau_{k,n}$ from a routine computation:

######  Lemma 3.5.

For any constant $n_{0}\geq 4$, for all $n$ and all $k\in\mathbbm{N}^{+}$ we
have
$\tau_{k,n_{0}+1}\cdots\tau_{k,n}\geq{\frac{1}{n\cdot\operatorname{poly}(k)}}.$

###### Proof.

Fix $n_{0}\geq 4$ and take any $n,k\geq 1$. Defining $\ell=\lfloor
4\log_{2}(60k)\rfloor\geq 20$, by Theorem 3.4 we have

$\tau_{k,n_{0}+1}\cdots\tau_{k,\ell}\geq(.04)^{\ell}=(.04)^{O(\log
k)}\geq\frac{1}{\operatorname{poly}(k)}.$ (27)

This proves the result if $n\leq\ell$. Otherwise, it remains to show that

$\tau_{k,\ell+1}\cdots\tau_{k,n}\geq 1/n.$ (28)

For $m\geq\ell+1$ we have
$k\leq\frac{1}{60}2^{m/4}\leq\frac{1}{\sqrt{10}m^{2}}2^{m/2}$, so we are
eligible to use the bound from Theorem 3.3. Then using

$\frac{\sqrt{10}km}{2^{m/2}}\leq\frac{\sqrt{10}m}{60\cdot 2^{m/4}}\leq
2^{-m/5},\quad 1-\frac{1}{m}-2^{-m/5}\geq\left\lparen
1-\frac{1}{m}\right\rparen\exp(-2^{1-m/5})$ (29)

(the last inequality using $m\geq\ell\geq 20$), we conclude

$\tau_{k,\ell+1}\cdots\tau_{k,n}\geq\prod_{m=\ell+1}^{n}\left\lparen
1-\frac{1}{m}\right\rparen\exp(-2^{1-m/5})=\frac{\ell}{n}\exp\left\lparen-\sum_{m=\ell+1}^{n}2^{1-m/5}\right\rparen\geq\frac{1}{n}$
(30)

(using $\ell\geq 20$), confirming Equation 28. ∎

Second step: From “truly random” non-local $n_{0}$-qubit gates to
“pseudorandom” non-local $n_{0}$-qubit gates. The next lemma, proved in
Section 3.4, may be viewed as saying that (suitably) _pseudo_ -randomizing
constantly many randomly chosen qubits is “not much worse” than _truly_
randomizing those qubits.

######  Lemma 3.6.

There is an absolute constant $n_{0}=4$ such that for $n\geq n_{0}+1$, we have

$\forall k\in\mathbbm{N}^{+},\quad
L_{\widetilde{P}_{n_{0}}\times\binom{[n]}{n_{0}}}(\rho^{k,k}_{2^{n}})\geq\kappa_{n_{0}}\cdot
L_{\mathrm{G}(n_{0})\times\binom{[n]}{n_{0}}}(\rho^{k,k}_{2^{n}}),$

where $\kappa_{n_{0}}$ is an absolute constant (depending only on $n_{0}$).

Theorem 3.1 follows from Lemma 3.2, Lemma 3.5 and Lemma 3.6.

###  3.3 Proof of Lemma 3.2

######  Lemma 3.7 (Restatement of Lemma 3.2).

Fix a positive integer $n_{0}\geq 4$. Suppose that for $n_{0}<m\leq n$ we have

$\forall k\in\mathbbm{N}^{+},\quad
L_{\mathrm{G}(m-1)\times\binom{[m]}{m-1}}(\rho^{k,k}_{2^{m}})\geq\tau_{k,m}\cdot
L_{\mathrm{G}(m)}(\rho^{k,k}_{2^{m}}).$ (31)

Then

$\forall k\in\mathbbm{N}^{+},\quad
L_{\mathrm{G}(n_{0})\times\binom{[n]}{n_{0}}}(\rho^{k,k}_{2^{n}})\geq\left\lparen\prod_{n_{0}<m\leq
n}\tau_{k,{m}}\right\rparen\cdot L_{\mathrm{G}(n)}(\rho^{k,k}_{2^{n}}).$ (32)

###### Proof.

For readability we simply write $\tau_{i}$ in this proof to stand for
$\tau_{k,i}$. Also for readability we express the lemma as

(randomizing $m-1$ out of $m$ qubits)
$\displaystyle\geq\tau_{m}\cdot\textnormal{(randomizing all $m$
qubits)}\quad\forall\ n_{0}<m\leq n$ (33)
$\displaystyle\implies\quad\textnormal{(randomizing $n_{0}$ out of $n$
qubits)}$
$\displaystyle\geq\tau_{n_{0}+1}\cdots\tau_{n}\cdot\textnormal{(randomizing
all $n$ qubits),}$

with the modifier “vis-as-vis all $\rho^{k,k}_{2^{m}}$” being implied. The
$m=n_{0}+1$ case of Equation 33 is

$\textnormal{(randomizing $n_{0}$ out of $n_{0}+1$
qubits)}\geq\tau_{n_{0}+1}\cdot\textnormal{(randomizing all $n_{0}+1$
qubits)}.$ (34)

From this, by adding an ignored $(n_{0}+2)$th qubit, we are able to conclude

$\textnormal{(randomizing $n_{0}$ out of the first $n_{0}+1$ of $n_{0}+2$
qubits)}\\\ \geq\tau_{n_{0}+1}\cdot\textnormal{(randomizing the first
$n_{0}+1$ of $n_{0}+2$ qubits)}.$ (35)

To derive this implication more formally, start with Equation 34, which says
that for all $k\in\mathbbm{N}^{+}$,

$\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{g}\sim\mathrm{G}(n_{0})\\\
\boldsymbol{e}\sim\binom{[n_{0}+1]}{n_{0}}\end{subarray}}[\mathbbm{1}-\boldsymbol{g}_{\boldsymbol{e}}^{\otimes
k,k}]\geq\tau_{n_{0}+1}\cdot\operatorname*{\mathbf{E}}_{\boldsymbol{h}\sim\mathrm{G}(n_{0}+1)}[\mathbbm{1}-\boldsymbol{h}^{\otimes
k,k}].$ (36)

We now consider tacking on a $(n_{0}+2)$th tensor factor that is ignored by
both $\boldsymbol{g}_{e}$ and by $\boldsymbol{h}$. Since $A\geq B\implies
A\otimes\mathbbm{1}\geq B\otimes\mathbbm{1}$, we can tensor-product both sides
of Equation 36 by $\mathbbm{1}^{\otimes k,k}$ (where $\mathbbm{1}$ denotes the
$2\times 2$ identity matrix) to conclude

$\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{g}\sim\mathrm{G}(n_{0})\\\
\boldsymbol{e}\sim\binom{[n_{0}+1]}{n_{0}}\in[n_{0}+2]_{n_{0}}\end{subarray}}[\mathbbm{1}-\boldsymbol{g}_{\boldsymbol{e}}^{\otimes
k,k}]\geq\tau_{n_{0}+1}\cdot\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{h}\sim\mathrm{G}(n_{0}+1)\\\
f\coloneqq[n_{0}+1]\in[n_{0}+2]_{n_{0}+1}\end{subarray}}[\mathbbm{1}-\boldsymbol{h}_{f}^{\otimes
k,k}],$ (37)

and this is the meaning of Equation 35. Indeed, we can insert the ignored
$(n_{0}+2)$th qubit at any position, not just the last one; i.e., for any
$j\in[n_{0}+2]$,

$\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{g}\sim\mathrm{G}(n_{0})\\\
\boldsymbol{e}\sim\binom{[n_{0}+2]\setminus
j}{n_{0}}\end{subarray}}[\mathbbm{1}-\boldsymbol{g}_{\boldsymbol{e}}^{\otimes
k,k}]\geq\tau_{n_{0}+1}\cdot\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{h}\sim\mathrm{G}(n_{0}+1)\\\
f\coloneqq[n_{0}+2]\setminus
j\end{subarray}}[\mathbbm{1}-\boldsymbol{h}_{f}^{\otimes k,k}.]$ (38)

If we now average the above (PSD-order) inequality over
$\boldsymbol{j}\sim[n_{0}+2]$ we get

$\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{g}\sim\mathrm{G}(n_{0})\\\
\boldsymbol{e}\sim\binom{[n_{0}+2]}{n_{0}}\end{subarray}}[\mathbbm{1}-\boldsymbol{g}_{\boldsymbol{e}}^{\otimes
k,k}]\geq\tau_{n_{0}+1}\cdot\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{h}\sim\mathrm{G}(n_{0}+1)\\\
\boldsymbol{f}\sim\binom{[n_{0}+2]}{n_{0}+1}\end{subarray}}[\mathbbm{1}-\boldsymbol{h}_{\boldsymbol{f}}^{\otimes
k,k}],$ (39)

which we would express as

$\textnormal{(randomizing $n_{0}$ out of $n_{0}+2$ qubits)}\\\
\geq\tau_{n_{0}+1}\cdot\textnormal{(randomizing $n_{0}+1$ out of $n_{0}+2$
qubits)}.$ (40)

But the $m=n_{0}+2$ case of our hypothesis Equation 33 is

$\textnormal{(randomizing $n_{0}+1$ out of $n_{0}+2$
qubits)}\geq\tau_{n_{0}+2}\cdot\textnormal{(randomizing all $n_{0}+2$
qubits)},$ (41)

so chaining this together with Equation 40 (using the PSD-ordering fact $A\geq
B$, $B\geq C\implies A\geq C$) gives

$\textnormal{(randomizing $n_{0}$ out of $n_{0}+2$ qubits)}\\\
\geq\tau_{n_{0}+1}\cdot\tau_{n_{0}+2}\cdot\textnormal{(randomizing all
$n_{0}+2$ qubits)}.$ (42)

Iterating this argument completes the proof of the lemma. ∎

###  3.4 Proof of Lemma 3.6

An ingredient we need for Lemma 3.6 is the existence of a suitable finite
“gate set” with useful properties. This is provided by the following lemma,
which follows from known universality results in quantum computing (see
Section 3.4.1):

######  Lemma 3.8.

There is an absolute constant $n_{0}=4$ for which there is a finite multiset
$P_{n_{0}}\subset\mathrm{SO}(2^{n_{0}})$, closed under negations and inverses,
with two properties:

  * (A)

(There is a basis in which) every matrix in $P_{n_{0}}$ has algebraic entries.

  * (B)

Finite products of elements of $P_{n_{0}}$ are dense in
$\mathrm{SO}(2^{n_{0}})$.

The same statement is true for $\mathrm{SU}(2^{n_{0}})$ (also with $n_{0}=4$).

Lemma 3.8 allows us to use a deep result of Benoist and de Saxcé [BdS16],
which extended earlier work of Bourgain–Gamburd [BG12] (for the case of the
special unitary group) to a broader range of groups. The main result of
[BdS16] is as follows:

######  Theorem 3.9.

([BdS16, Consequence of Theorem 1.2].) For $n\geq 1$ let
$\mathrm{G}(n)\subseteq\mathrm{SU}(2^{n})$ be a connected compact simple Lie
group. Fix a positive integer $n_{0}$ and suppose that
$P_{n_{0}}\subset\mathrm{G}(n_{0})$ satisfies properties (A) and (B) of Lemma
3.8. Then there exists a constant $\kappa>0$ such that

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\widetilde{P_{n_{0}}}}[\mathrm{reg}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n_{0})}[\mathrm{reg}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq
1-\kappa,$ (43)

where $\mathrm{reg}$ denotes the regular representation of
$\mathrm{G}(n_{0})$. Equivalently,
$L_{\widetilde{P_{n_{0}}}}(\mathrm{reg})\geq\kappa\cdot
L_{\mathrm{G}(n_{0})}(\mathrm{reg}),$ or

$\textnormal{($\widetilde{P_{n_{0}}}$-pseudorandomizing in $2^{n_{0}}$
dimensions)}\geq\kappa\cdot\textnormal{(randomizing $2^{n_{0}}$
dimensions)}\quad\textnormal{[vis-a-vis~{}$\mathrm{reg}$]}.$ (44)

We remark that (as noted by [BHH16]) a weaker form of Equation 43, with the
$k$-wise tensor product representation in place of the regular representation
and $\kappa$ depending on $k$, has been known at least since [AK63]; however,
the stronger quantitative bound of Equation 43 is essential for our purposes.

Theorem 3.9 yields the following useful corollary:

######  Corollary 3.10.

For $n_{0}=4$, $\mathrm{G}(n_{0})=\mathrm{SO}(2^{n_{0}})$, and
$P_{n_{0}}\subset\mathrm{G}(n_{0})$ satisfying properties (A) and (B) of Lemma
3.8, there is a constant $\kappa>0$ such that for all $k\in\mathbbm{N}^{+}$ we
have
$L_{\widetilde{P_{n_{0}}}}(\mathrm{\rho}^{k,k}_{2^{n_{0}}})\geq\kappa\cdot
L_{\mathrm{G}(n_{0})}(\mathrm{\rho}^{k,k}_{2^{n_{0}}}).$ That is, vis-a-vis
any $\rho^{k,k}_{2^{n_{0}}}$, we have

$\textnormal{($\widetilde{P_{n_{0}}}$-pseudorandomizing $n_{0}$
qubits)}\geq\kappa\cdot\textnormal{($\mathrm{G}(n_{0})$-randomizing $n_{0}$
qubits)}.$ (45)

The same is true for $n_{0}=4$, $\mathrm{G}(n_{0})=\mathrm{SU}(2^{n_{0}})$.

###### Proof.

We first note that since all irreducible representations appear in the regular
representation777For a concrete proof in the case of
$\mathrm{G}(\ell)=\mathrm{SO}(2^{\ell})$, see e.g. [KM15, Lem. 6.1]., the
conclusion of Theorem 3.9 also holds for any $\rho^{k,k}_{2^{\ell}}$
representation. Since the special unitary group is connected, compact, and
simple888Recall that the Lie algebra of the special unitary group is simple,
and that Benoiste and de Saxcé remark, following their Theorem 1.2 in [BdS16],
that “ _For us, a compact simple Lie group will be a compact real Lie group
whose Lie algebra is simple._ ”, this immediately gives Corollary 3.10 in the
case $\mathrm{G}(n_{0})=\mathrm{SU}(2^{n_{0}})$.

For the special orthogonal case, while
$\mathrm{G}(n_{0})=\mathrm{SO}(2^{n_{0}})$ is not simple, the projective
special orthogonal group
$\mathrm{PSO}(2^{n_{0}})=\mathrm{SO}(2^{n_{0}})/\\{\pm 1\\}$ is a connected
compact simple Lie group. Writing $P^{\prime}_{n_{0}}$ to denote the multiset
of elements of $\mathrm{PSO}(2^{n_{0}})$ corresponding to $P_{n_{0}}$, Theorem
3.9 gives us that

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\widetilde{P^{\prime}_{n_{0}}}}[\rho^{k,k}_{2^{n_{0}}}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{PSO}(2^{n_{0}})}[\rho^{k,k}_{2^{n_{0}}}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq
1-\kappa.$ (46)

Now recalling that $\rho^{k,k}_{2^{n_{0}}}(g)=g^{\otimes k}\otimes g^{\otimes
k}$, since $P_{n_{0}}$ is closed under negation there is no need to
distinguish between $\mathrm{PSO}(2^{n_{0}})$ and $\mathrm{SO}(2^{n_{0}})$ in
either of the expectations appearing in Equation 46, i.e. we have

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\widetilde{P^{\prime}_{n_{0}}}}[\rho^{k,k}_{2^{n_{0}}}(\boldsymbol{g})]=\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\widetilde{P_{n_{0}}}}[\rho^{k,k}_{2^{n_{0}}}(\boldsymbol{g})],\quad\quad\quad\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{PSO}(2^{n_{0}})}[\rho^{k,k}_{2^{n_{0}}}(\boldsymbol{g})]=\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{SO}(2^{n_{0}})}[\rho^{k,k}_{2^{n_{0}}}(\boldsymbol{g})],$
(47)

which gives Corollary 3.10 for the case
$\mathrm{G}(n_{0})=\mathrm{SO}(2^{n_{0}})$. ∎

With Corollary 3.10 in hand, now we are ready to prove Lemma 3.6:

_Proof of Lemma 3.6._ By Corollary 3.10, we have
$L_{\widetilde{P_{n_{0}}}}(\mathrm{\rho}^{k,k}_{2^{n_{0}}})\geq\kappa_{n_{0}}\cdot
L_{\mathrm{G}(n_{0})}(\mathrm{\rho}^{k,k}_{2^{n_{0}}})$, i.e.

$\mathbbm{1}-\operatorname*{\mathbf{E}}_{\boldsymbol{h}\sim\widetilde{P_{n_{0}}}}[\rho(\boldsymbol{h})]\geq\kappa_{n_{0}}\left(\mathbbm{1}-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n_{0})}[\rho(\boldsymbol{g})]\right).$
(48)

We consider tacking on $n-{n_{0}}$ tensor factors that are ignored by both
$\boldsymbol{g}$ and by $\boldsymbol{h}$. Since $A\geq B\implies
A\otimes\mathbbm{1}\geq B\otimes\mathbbm{1}$, we can tensor-product both sides
of Equation 48 by the identity to conclude

$\mathbbm{1}-\operatorname*{\mathbf{E}}_{\boldsymbol{h}\sim\widetilde{P_{n_{0}}}}[\rho(\boldsymbol{h}_{[n_{0}]})]\geq\kappa_{n_{0}}\left(\mathbbm{1}-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n_{0})}[\rho(\boldsymbol{g}_{[n_{0}]})]\right).$
(49)

We can insert the ignored $n-n_{0}$ qubits at any positions, not just the last
one; averaging the resulting inequalities, we get

$\displaystyle{\frac{1}{{n\choose n-n_{0}}}}\sum_{1\leq
i_{1}<\cdots<i_{n_{0}}\leq
n}\left(\mathbbm{1}-\operatorname*{\mathbf{E}}_{\boldsymbol{h}\sim\widetilde{P_{n_{0}}}}[\rho(\boldsymbol{h}_{(i_{1},\dots,i_{n_{0}})})]\right)$
$\displaystyle\geq\kappa_{n_{0}}\cdot{\frac{1}{{n\choose n-n_{0}}}}\sum_{1\leq
i_{1}<\cdots<i_{n_{0}}\leq
n}\left(\mathbbm{1}-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(n_{0})}[\rho(\boldsymbol{g}_{(i_{1},\dots,i_{n_{0}})})]\right),$
(50)

which is what Lemma 3.6 asserts. ∎

####  3.4.1 Proof of Lemma 3.8

We first consider $\mathrm{SO}(2^{4})$; so we must show that there is a finite
multiset $P_{4}\subset\mathrm{SO}(2^{4})$, closed under inverses, that
satisfies conditions (A) and (B) of Lemma 3.8.

Define the 1- and 2-qubit gates

$\mathrm{Q}\coloneqq\begin{bmatrix}3/5&-4/5\\\ 4/5&\phantom{-}3/5\\\
\end{bmatrix}\quad\text{and}\quad\mathrm{CNOT}\coloneqq\begin{bmatrix}1&0\\\
0&0\end{bmatrix}\otimes\begin{bmatrix}1&0\\\
0&1\end{bmatrix}+\begin{bmatrix}0&0\\\
0&1\end{bmatrix}\otimes\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},$ (51)

and let $P_{4}$ be the following finite subset999Recall that
$\mathrm{CNOT}\not\in\mathrm{SO}(2^{2})$, but
$\mathrm{CNOT}\otimes\mathbbm{1}_{4\times 4}\in\mathrm{SO}(16)$. of
$\mathrm{SO}(2^{4})$:

$P_{4}:={\text{the closure
of~{}}\\{\mathrm{Q}_{(j)}:j\in[4]\\}\cup\\{\mathrm{CNOT}_{(i,j)}:i,j\in[4],i\neq
j\\}\text{~{}under inverses and negations}}.$ (52)

Clearly $P_{4}$ satisfies (A), and (B) follows from the following result from
[Shi02, Thm. 3.1]:

######  Fact 3.11.

The $1$\- and $2$-qubit gates

$\mathrm{Q}\coloneqq\begin{bmatrix}3/5&-4/5\\\ 4/5&\phantom{-}3/5\\\
\end{bmatrix}\quad\text{and}\quad\mathrm{CNOT}\coloneqq\begin{bmatrix}1&0\\\
0&0\end{bmatrix}\otimes\begin{bmatrix}1&0\\\
0&1\end{bmatrix}+\begin{bmatrix}0&0\\\
0&1\end{bmatrix}\otimes\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ (53)

are together universal for quantum computing with real amplitudes. More
precisely, recalling Equation 52, we have that finite products of elements of
$P_{4}$ are dense in $\mathrm{SO}(2^{4})$.

Next we turn to $\mathrm{SU}(2^{4})$. Define the $1$-qubit Hadamard gate
(denoted $\mathrm{H}$), phase gate (denoted $\mathrm{S}$), and “$\pi/8$ gate”
(denoted $\mathrm{T}$) respectively as

$\mathrm{H}\coloneqq{\frac{1}{\sqrt{2}}}\begin{bmatrix}1&\phantom{+}1\\\
1&-1\\\
\end{bmatrix},\quad\mathrm{S}\coloneqq{\frac{1}{\sqrt{2}}}\begin{bmatrix}1&\phantom{+}1\\\
1&-1\\\
\end{bmatrix},\quad\quad\text{and}\quad\mathrm{T}\coloneqq\begin{bmatrix}1&0\\\
0&e^{i\pi/4}\\\ \end{bmatrix},$ (54)

and recall the definition of $\mathrm{CNOT}$ from Equation 51. Now let
$P^{\prime}_{4}$ be the closure of
$\\{\mathrm{H}_{(j)}:j\in[4]\\}\cup\\{\mathrm{S}_{(j)}:j\in[4]\\}\cup\\{\mathrm{T}_{(j)}:j\in[4]\\}\cup\\{\mathrm{CNOT}_{(i,j)}:i,j\in[4],i\neq
j\\}$ under inverses and negations. It is clear that $P^{\prime}_{4}$ is a
finite set of elements of $\mathrm{U}(2^{4})$, closed under inverses,
satisfying (A). The fact that $P^{\prime}_{4}$ satisfies (B) follows from the
well-known fact (see, e.g., [NC10, Sec. 4.5.3]) that $\mathrm{H}$,
$\mathrm{S},$ $\mathrm{T}$ and $\mathrm{CNOT}$ together are universal for
quantum computing. Finally, we obtain the desired set of elements
$P_{4}\subset\mathrm{SU}(2^{4})$ by multiplying elements of $P^{\prime}_{4}$
by suitable complex values of unit norm to have determinant one.

##  4 Lower bounding $\tau_{m}$ for large $m$

In this section we prove Theorem 3.3, restated below, using simplifications of
techniques introduced in [HHJ21]:

######  Theorem 4.1 (Restatement of Theorem 3.3).

Let the sequence of groups $(\mathrm{G}(n))_{n\geq 1}$ be either
$(\mathrm{SO}(2^{n}))_{n\geq 1}$ or $(\mathrm{SU}(2^{n}))_{n\geq 1}$. Define
the following operators on $(\mathbbm{C}^{2^{m}})^{\otimes 2k}$:

$\Pi^{(m)}=\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m)}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})],\quad\Pi_{[m]\setminus
i}\otimes\mathbbm{1}_{i}=\textnormal{($\mathbbm{1}_{2k\times 2k}$ on the $i$th
tensor factor, $\Pi^{(m-1)}$ on the remainder)}.$ (55)

Then for all $k\leq\frac{1}{\sqrt{10}m^{2}}2^{m/2}$ we have

$\left\lVert\mathop{\textnormal{avg}}_{i=1}^{m}\\{\Pi_{[m]\setminus
i}\otimes\mathbbm{1}_{i}\\}-\Pi^{(m)}\right\rVert_{\mathrm{op}}\leq\frac{1}{m}+\frac{\sqrt{10}km}{2^{m/2}};$
(56)

equivalently, in the notation of Theorem 3.3, $\tau_{m}\geq
1-(\frac{1}{m}+\frac{\sqrt{10}km}{2^{m/2}})$.

We observe:

######  Fact 4.2.

$\operatorname{\textnormal{Im}}\Pi^{(m)}$ is a subspace of
$\operatorname{\textnormal{Im}}(\Pi_{[m]\setminus i}\otimes\mathbbm{1}_{i})$
for all $i$.

###  4.1 Identifying the projectors

To prove Theorem 4.1, we will need to have a description of the projection
operator $\Pi^{(m)}$; luckily, this is provided by known representation
theory. To state the results we need some notation.

######  Notation 4.3.

If $X\in\mathbbm{C}^{r\times r}$ is a matrix, we write
$\mathrm{vec}(X)\in\mathbbm{C}^{r}\otimes\mathbbm{C}^{r}$ for its
vectorization; here $\mathrm{vec}$ is the linear map that takes
$\ket{i}\\!\bra{j}$ to $\ket{ij}$.

######  Fact 4.4.

For matrices $R_{0},R_{1},S\in\mathbbm{C}^{r\times r}$ it holds that
$(R_{0}\otimes R_{1})\mathrm{vec}(S)=\mathrm{vec}(R_{0}SR_{1}^{\top})$.

######  Notation 4.5.

Having fixed some $D=2^{m}\in\mathbbm{N}^{+}$, we write

$\ket{\Phi}=D^{-1/2}\sum_{a=1}^{D}\ket{a}\otimes\ket{a}=D^{-1/2}\mathrm{vec}(\mathbbm{1}_{D\times
D})$ (57)

for the maximally entangled state on $\mathbbm{C}^{D}\otimes\mathbbm{C}^{D}$.

######  Notation 4.6.

For $k\in\mathbbm{N}^{+}$, let $\mathcal{M}_{2k}$ denote the set of all
perfect matchings on $[2k]$, and let $\mathcal{M}_{2k}^{\textrm{bip}}$ denote
the subset of all “bipartite” perfect matchings, meaning that each pair in the
matching can be written as $\\{i,j\\}$ with $i\leq k$ and $j>k$.

######  Notation 4.7.

For $M\in\mathcal{M}_{2k}$, we introduce the unit vector

$\ket{\Phi_{M}}=\bigotimes_{\\{i,j\\}\in
M}\ket{\Phi}_{ij}\in(\mathbbm{C}^{D})^{\otimes 2k},$ (58)

where we abuse notation slightly by writing $\ket{\Phi}_{ij}$ for the
maximally entangled state on the $i$th and $j$th tensor components.

Let us give two examples. First, with $k=3$:

$M=\\{\\{1,2\\},\\{3,6\\},\\{4,5\\}\\}\implies\ket{\Phi_{M}}=D^{-k/2}\sum_{a,b,c=1}^{D}\ket{aabccb}=D^{-k/2}\cdot\sum_{\begin{subarray}{c}\chi:[2k]\to[D]\\\
\text{all edges of $M$ monochromatic}\\\ \text{for vertex-coloring
$\chi$}\end{subarray}}\ket{\chi}.$ (59)

As a second example, with general $k$:

$M_{0}=\\{\\{1,k+1\\},\\{2,k+2\\},\dots,\\{k,2k\\}\\}\implies\ket{\Phi_{M_{0}}}=D^{-k/2}\mathrm{vec}(\mathbbm{1}_{D^{k}\times
D^{k}}).$ (60)

It is not hard to show that every $\ket{\Phi_{M}}$ with $M\in\mathcal{M}_{2k}$
(respectively, $M\in\mathcal{M}^{\text{bip}}_{2k}$) is fixed by every
$\rho_{D}^{k,k}(g)$ for $g\in\mathrm{SO}(D)$ (respectively,
$g\in\mathrm{SU}(D)$). To illustrate this for the particular
$M_{0}\in\mathcal{M}^{\text{bip}}_{2k}\subseteq\mathcal{M}_{2k}$ from Equation
60, we have that for $g\in\mathrm{SO}(D)\leq\mathrm{SU}(D)$,

$g^{\otimes k}\otimes\overline{g}^{\otimes
k}\ket{\Phi_{M_{0}}}={\frac{g^{\otimes k}\otimes\overline{g}^{\otimes
k}\mathrm{vec}(\mathbbm{1}_{D^{k}\times
D^{k}})}{D^{k/2}}}={\frac{\mathrm{vec}(g^{\otimes
k}\mathrm{vec}(\mathbbm{1}_{D^{k}\times D^{k}})(\overline{g}^{\otimes
k})^{\top})}{D^{k/2}}}={\frac{\mathrm{vec}(\mathbbm{1}_{D^{k}\times
D^{k}})}{D^{k/2}}}=\ket{\Phi_{M_{0}}},$ (61)

where we used Fact 4.4 and $\overline{g}^{\top}=g^{\dagger}=g^{-1}$. Given
this fact, each $\ket{\Phi_{M}}$ must be fixed by the average representation
$\Pi^{(m)}$, and thus be in $\mathop{\mathrm{Im}}\Pi^{(m)}$. On the other
hand, it is elementary to show (e.g., [BC20, Prop. 1]) that
$\mathop{\mathrm{Im}}\Pi^{(m)}$ is _precisely_ the set of vectors fixed by
every operator in $\\{\rho_{D}^{k,k}(g):g\in\mathrm{G}(m)\\}$ (recall that
$D=2^{m}$). In turn, these are precisely the vectorizations of all matrices in
the _commutant_ (centralizer) of $\mathcal{A}=\\{g^{\otimes
k}:g\in\mathrm{G}(m)\\}.$ Finally, the commutants of tensor product
representations of our groups have been identified under the umbrella of
_Schur–Weyl duality_.

######  Theorem 4.8.

By Schur–Weyl duality for $\mathrm{U}(D)$ [Sch01, Wey39, Yua12], $D=2^{m}$,
when $\mathrm{G}(m)=\mathrm{U}(2^{m})$ the projector $\Pi^{(m)}$ has image
equal to the span of $\ket{\Phi_{M}}$ for
$M\in\mathcal{M}_{2k}^{\mathrm{bip}}$. The same is true when
$\mathrm{G}(m)=\mathrm{SU}(2^{m})$, since $\Pi^{(m)}$ is unchanged in this
case.101010Observe that because of the conjugation in the definition of
$\rho^{k,k}_{2^{n}}$, the expectation $\Pi^{(m)}$ is the same whether the
expectation is taken over $\boldsymbol{g}\sim\mathrm{G}(n)=\mathrm{SU}(2^{n})$
or $\boldsymbol{g}\sim\mathrm{G}(n)=\mathrm{U}(2^{n})$.

By Schur–Weyl duality for $\mathrm{SO}(D)$ [Bra37, Gro99], $D=2^{m}$, when
$\mathrm{G}(m)=\mathrm{SO}(2^{m})$ and $k<2^{m-1}$ the projector $\Pi^{(m)}$
has image equal to the span of $\ket{\Phi_{M}}$ for $M\in\mathcal{M}_{2k}$.

######  Remark 4.9.

The condition $k<2^{m-1}$ in the previous theorem cannot be dropped. For
example,

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{O}(2)}[\rho^{1,1}_{2}(\boldsymbol{g})]=\text{projection
onto }\tfrac{1}{\sqrt{2}}(\ket{00}+\ket{11}),$ (62)

but

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{SO}(2)}[\rho^{1,1}_{2}(\boldsymbol{g})]=\text{projection
onto
}\operatorname{span}\\{\tfrac{1}{\sqrt{2}}(\ket{00}+\ket{11}),\tfrac{1}{\sqrt{2}}(\ket{01}-\ket{10})\\}.$
(63)

We have now identified a spanning set for $\mathop{\text{Im}}\Pi^{(m)}$, but
working with it is complicated by the fact that it is not an orthonormal
basis. It is, however, relatively “close” to being so, as we now show
(following and simplifying some arguments from [BHH16, Lem. 17] and [HHJ21,
Lem. 9]). First, an elementary lemma in linear algebra:

######  Lemma 4.10.

Let $W\in\mathbbm{C}^{d\times t}$ have unit vector columns
$\ket{w_{1}},\dots,\ket{w_{t}}$, and suppose their Gram matrix
$W^{\dagger}W\in\mathbbm{C}^{t\times t}$ is close to the identity, in the
sense that $E=W^{\dagger}W-\mathbbm{1}$ has $\left\lVert
E\right\rVert_{\mathrm{op}}\leq\kappa<1$. (For example, this would hold if

$\lVert E\rVert_{1\mapsto 1}=\max_{j\in[t]}\sum_{i\neq
j}\lvert\braket{w_{i}}{w_{j}}\rvert\leq\kappa,$ (64)

since generally $\lVert E\rVert_{1\mapsto 1}\geq\rho(E)=\left\lVert
E\right\rVert_{\mathrm{op}}$, as $E$ is Hermitian.) Then
$WW^{\dagger}=\sum_{i}\ket{w_{i}}\\!\bra{w_{i}}$ satisfies

$WW^{\dagger}\mathop{\approx}^{\kappa}\Pi_{T},$ (65)

where $\Pi_{T}$ is the projector onto
$T=\operatorname{span}\\{\ket{w_{1}},\dots,\ket{w_{t}}\\}$, and
$X\mathop{\approx}^{\kappa}Y$ denotes $\left\lVert
X-Y\right\rVert_{\mathrm{op}}\leq\kappa$.

###### Proof.

By hypothesis, all eigenvalues $\lambda$ of $W^{\dagger}W$ satisfy
$|\lambda-1|\leq\kappa<1$. Hence $WW^{\dagger}$ also has these $t$ (nonzero)
$\lambda$’s within $\kappa$ of $1$ as eigenvalues (associated to eigenvectors
in $T$), plus possibly additional eigenvalues of $0$ (outside $T$). This
confirms Equation 65. ∎

######  Theorem 4.11.

In the setting of $\mathrm{G}(m)=\mathrm{SO}(D)$, $D=2^{m}$ and provided
$k^{2}\leq\frac{1}{9}D$, we have

$\sum_{M\in\mathcal{M}_{2k}}\ket{\Phi_{M}}\\!\bra{\Phi_{M}}\
\mathop{\approx}^{\kappa_{m}}\ \Pi^{(m)},$ (66)

where $\kappa_{m}\coloneqq\tfrac{10}{9}\frac{k^{2}}{D}$. In the setting of
$\mathrm{G}(m)=\mathrm{SU}(2^{m})$, the same is true with $\mathcal{M}_{2k}$
replaced by $\mathcal{M}_{2k}^{\textnormal{bip}}$ (and one could replace
$\kappa_{m}$ by $\tfrac{5}{9}\frac{k^{2}}{D}$, but we won’t).

###### Proof.

The result for $\mathrm{U}(2^{m})$ (hence $\mathrm{SU}(2^{m})$) appears in
[BHH16], and for $\mathrm{O}(2^{m})$ in [HHJ21], but we present here a
representation theory-free proof, focusing on the $\mathrm{SO}(2^{m})$ case.

We will employ Lemma 4.10, with the $\ket{w_{i}}$’s being the
$\ket{\Phi_{M}}$’s, $M\in\mathcal{M}_{2k}$. In particular, we will establish
the premise in Equation 64 with $\kappa=\kappa_{m}$. By symmetry of all
matchings in $\mathcal{M}$, the quantity inside the maximum is the same for
every “$\ket{w_{j}}$”; thus, we need only bound it for one particular choice,
say the $M_{0}$ from Equation 60. Thus we need to establish

$\sum_{M\in\mathcal{M}_{2k}}\lvert\braket{\Phi_{M}}{\Phi_{M_{0}}}\rvert=1+\sum_{M\neq
M_{0}}\lvert\braket{\Phi_{M}}{\Phi_{M_{0}}}\rvert\leq 1+\kappa_{m}.$ (67)

In computing $\braket{\Phi_{M}}{\Phi_{M_{0}}}$, it is easy to see (e.g., from
Equation 59) we get a contribution of $D^{-k}$ from every vertex-coloring
$\chi:[2k]\to[D]$ that makes all edges of $M$ and $M_{0}$ monochromatic. Since
$M\cup M_{0}$ is a union of cycles, this is equivalent to a contribution of
$D^{\text{cc}(M\cup M_{0})}$, where $\text{cc}(\cdot)$ denotes the number of
connected components. Thus (cf. [HHJ21, (B10)])

$D^{k}\cdot\sum_{\text{matchings
}M}\lvert\braket{\Phi_{M}}{\Phi_{M_{0}}}\rvert=D^{k}\cdot\sum_{\text{matchings
}M}\braket{\Phi_{M}}{\Phi_{M_{0}}}=\sum_{M}D^{\text{cc}(M\cup M_{0})}.$ (68)

The summation on the right is just the generating function (with
“indeterminate” $D$) for the number of connected components obtained when
placing a matching (initially: $M$) onto the endpoints of $k$ labeled paths
(initially: $M_{0}$). But this is a very simple exercise. Take the first
labeled path, with endpoints $x,y$, and consider the vertex $z$ to which $x$
is matched. There are $2k-1$ possibilities for $z$, with one of them ($z=y$)
increasing the component count by $1$, and the other $2k-2$ increasing the
count by $0$. Thus the generating function picks up a factor of
$(D^{1}+(2k-2)\cdot D^{0})$, and we reduce $k$ to $k-2$. We conclude that (cf.
[HHJ21, (B12)])

$\sum_{M}D^{\text{cc}(M\cup M_{0})}=(D+(2k-2))(D+(2k-4))\cdots(D+2)D$ (69)

and hence

$\sum_{M}\lvert\braket{\Phi_{M}}{\Phi_{M_{0}}}\rvert=(1)\left\lparen
1+\tfrac{2}{D}\right\rparen\left\lparen
1+\tfrac{4}{D}\right\rparen\cdots\left\lparen
1+\tfrac{2k-2}{D}\right\rparen\leq\exp(\tfrac{k(k-1)}{D})\leq
1+\tfrac{10}{9}\tfrac{k^{2}}{D}=1+\kappa_{m},$ (70)

the last inequality holding because we have assumed $k^{2}\leq\frac{1}{9}D$.
Thus we have indeed verified Equation 67.

The case of $\mathrm{G}(m)=\mathrm{U}(2^{m})$ is similar; we just need to
compute the generating function for bipartite matchings, meaning
$\mathcal{M}_{2k}^{\text{bip}}$ replaces $\mathcal{M}$. The bound for
$\kappa_{m}$ becomes
$(1)(1+\frac{1}{D})(1+\frac{2}{D})\cdots(1+\frac{k-1}{D})-1$, which is only
smaller (by a factor of about $\frac{1}{2}$). ∎

###  4.2 Proof of Theorem 4.1

In this section we establish Theorem 4.1. We begin by proving some general
facts about projectors that are nearly orthogonal to each other.

######  Lemma 4.12.

Let $P_{1},\dots,P_{m}$ be orthogonal projections, and write
$A=\mathop{\textnormal{avg}}_{i=1}^{m}\\{P_{i}\\}$. Then

$\left\lVert P_{i}P_{j}\right\rVert_{\mathrm{op}}\leq\epsilon\ \ \forall\
i\neq j\quad\implies\quad\left\lVert
A\right\rVert_{\mathrm{op}}\leq\tfrac{1}{m}+\min\\{\sqrt{\epsilon},m\epsilon\\}.$
(71)

###### Proof.

We have

$A^{2}=\frac{1}{m}A+\frac{1}{m^{2}}\sum_{i\neq
j}P_{i}P_{j};\quad\implies\quad\left\lVert
A\right\rVert_{\mathrm{op}}^{2}\leq\frac{1}{m}\left\lVert
A\right\rVert_{\mathrm{op}}+\frac{m(m-1)}{m^{2}}\epsilon\leq\frac{1}{m}\left\lVert
A\right\rVert_{\mathrm{op}}+\epsilon.$ (72)

Solving the quadratic inequality yields $\left\lVert
A\right\rVert_{\mathrm{op}}\leq\frac{1}{2m}+\sqrt{\frac{1}{4m^{2}}+\epsilon}$,
from which the result follows. ∎

######  Corollary 4.13.

In the setting of Lemma 4.12, let $P$ be an orthogonal projection with
$\operatorname{\textnormal{Im}}P\leq\operatorname{\textnormal{Im}}P_{i}$ for
all $i$. Then Equation 71 holds with each instance of $P_{i}$ replaced by
$\widetilde{P}_{i}=P_{i}-P$.

###### Proof.

It suffices to note that $\widetilde{P}_{i}^{2}=\widetilde{P}_{i}$, since
$P_{i}\cdot P=P\cdot P_{i}=P$. ∎

######  Remark 4.14.

The identity used in the proof easily extends to
$\widetilde{P}_{i_{1}}\widetilde{P}_{i_{2}}\cdots\widetilde{P}_{i_{k}}=P_{i_{1}}P_{i_{2}}\cdots
P_{i_{k}}-P$. Also, this identity remains true if any set of tildes is removed
from the LHS (except for the set of all $k$).

Let us now study the particular orthogonal projectors involved in Theorem 4.1.
We wish to employ Corollary 4.13 with

$P_{i}\coloneqq\Pi_{[m]\setminus i}\otimes\mathbbm{1}_{i},\quad i=1\dots
m,\qquad P\coloneqq\Pi^{(m)}.$ (73)

Fact 4.2 tells us Corollary 4.13’s hypothesis is satisfied. We thus obtain

$\left\lVert\mathop{\textnormal{avg}}_{i=1}^{m}\\{P_{i}\\}-\Pi^{(m)}\right\rVert_{\mathrm{op}}\leq\frac{1}{m}+\min\\{\sqrt{\epsilon},m\epsilon\\},\quad\text{for
}\epsilon=\max_{i\neq
j}\left\\{\left\lVert\widetilde{P}_{i}\widetilde{P}_{j}\right\rVert_{\mathrm{op}}\right\\}.$
(74)

By symmetry of the $m$ tensor factors, we have
$\epsilon=\left\lVert\widetilde{P}_{1}\widetilde{P}_{m}\right\rVert_{\mathrm{op}}$,
and hence

$\epsilon^{2}=\left\lVert(\widetilde{P}_{1}\widetilde{P}_{m})^{\dagger}(\widetilde{P}_{1}\widetilde{P}_{m})\right\rVert_{\mathrm{op}}=\left\lVert
P_{m}\widetilde{P}_{1}P_{m}\right\rVert_{\mathrm{op}},$ (75)

where we used Remark 4.14 to get
$\widetilde{P}_{m}\widetilde{P}_{1}\widetilde{P}_{1}\widetilde{P}_{m}=P_{m}\widetilde{P}_{1}P_{m}$.

Our goal will be to use Theorem 4.11 (recall its $\kappa_{m}$ notation) to
establish the following:

$\displaystyle\textbf{Claim: }\quad\epsilon^{2}=\left\lVert
P_{m}\widetilde{P}_{1}P_{m}\right\rVert_{\mathrm{op}}$
$\displaystyle\leq\kappa_{m-2}+2\kappa_{m-1}+\kappa_{m}$ (76)
$\displaystyle=\tfrac{10}{9}k^{2}(2^{2-m}+2\cdot 2^{1-m}\cdot
2^{-m})=10k^{2}2^{-m}\eqqcolon\delta.$ (77)

We will apply Theorem 4.11 for $m-2,m-1,m$; its hypothesis will be satisfied
even for $m-2$, since we have $k^{2}\leq\frac{1}{9}2^{m-2}$ by virtue of the
assumption $k^{2}\leq\frac{1}{10m^{4}}2^{m}$ in the theorem we’re proving.
Moreover, this assumption implies that $\delta^{1/4}\leq 1/m$, meaning that
Equation 74 gives us the bound

$\left\lVert\mathop{\textnormal{avg}}_{i=1}^{m}\\{P_{i}\\}-\Pi^{(m)}\right\rVert_{\mathrm{op}}\leq\frac{1}{m}+\min\\{\delta^{1/4},m\delta^{1/2}\\}=\frac{1}{m}+m\delta^{1/2}=\frac{1}{m}+\frac{\sqrt{10}km}{2^{m/2}},$
(78)

verifying Equation 56 and completing the proof of Theorem 4.1. Thus it remains
to establish Equation 76.

To establish the claim, let us write $\mathcal{M}$ for either
$\mathcal{M}_{2k}$ or $\mathcal{M}_{2k}^{\text{bip}}$ (depending on
$\mathrm{G}(m)$); and, for $M\in\mathcal{M}$ let us write

$J_{M}=\ket{\phi_{M}}\\!\bra{\phi_{M}},\quad\text{where $\ket{\phi_{M}}$ is
the $D=2$ case of $\ket{\Phi_{M}}$ from
\lx@cref{creftypepluralcap~refnum}{not:1} and~\lx@cref{refnum}{not:2}}.$ (79)

Then (up to tensor factoring reordering) we Have $J_{M}^{\otimes
m}=\ket{\Phi_{M}}$, and hence Theorem 4.11 tells us

$\sum_{M\in\mathcal{M}}J_{M}^{\otimes
m}\mathop{\approx}^{\kappa_{m}}\Pi^{(m)}.$ (80)

We will also use this to derive

$\sum_{M\in\mathcal{M}}J_{M}^{\otimes(m-1)}\mathop{\approx}^{\kappa_{m-1}}\Pi^{(m-1)}\quad\implies\quad\sum_{M\in\mathcal{M}}\mathbbm{1}_{1}\otimes
J_{M}^{\otimes(m-1)}\mathop{\approx}^{\kappa_{m-1}}P_{1},$ (81)

where the implication is by tensoring with $\mathbbm{1}_{1}$ (which doesn’t
change operator norm differences). Using Equation 80 again, and the triangle
inequality, we reach

$\widetilde{P}_{1}=P_{1}-P\mathop{\approx}^{\kappa_{m-1}+\kappa_{m}}\sum_{M\in\mathcal{M}}\mathbbm{1}_{1}\otimes
J_{M}^{\otimes(m-1)}-\sum_{M\in\mathcal{M}}J_{M}^{\otimes
m}=\sum_{M\in\mathcal{M}}\overline{J}_{M}\otimes J_{M}^{\otimes(m-1)},$ (82)

where $\overline{J}_{M}\coloneqq\mathbbm{1}-J_{M}$. Since $\left\lVert
P_{m}\right\rVert_{\mathrm{op}}\leq 1$, we can further conclude

$\displaystyle P_{m}\widetilde{P}_{1}P_{m}$
$\displaystyle\mathop{\approx}^{\kappa_{m-1}+\kappa_{m}}P_{m}\left\lparen\sum_{M\in\mathcal{M}}\overline{J}_{M}\otimes
J_{M}^{\otimes(m-1)}\right\rparen P_{m}$ (83)
$\displaystyle=(\Pi^{(m-1)}\otimes\mathbbm{1}_{m})\left\lparen\sum_{M\in\mathcal{M}}\overline{J}_{M}\otimes
J_{M}^{\otimes(m-2)}\otimes
J_{M}\right\rparen(\Pi^{(m-1)}\otimes\mathbbm{1}_{m})$ (84)
$\displaystyle=\sum_{M\in\mathcal{M}}\left\lparen\Pi^{(m-1)}(\overline{J}_{M}\otimes
J_{M}^{\otimes(m-2)})\Pi^{(m-1)}\right\rparen\otimes J_{M}.$ (85)

Writing

$Z_{M}\coloneqq\Pi^{(m-1)}(\overline{J}_{M}\otimes
J_{M}^{\otimes(m-2)})\Pi^{(m-1)},$ (86)

we can put Equation 85 into Equation 75 to obtain

$\epsilon^{2}\leq\kappa_{m-1}+\kappa_{m}+\left\lVert\sum_{M\in\mathcal{M}}Z_{M}\otimes
J_{M}\right\rVert_{\mathrm{op}}.$ (87)

Now $Z_{M}$ is PSD, being a conjugation (by $\Pi^{(m-1)})$ of a PSD matrix:
the tensor product of projections $J_{M}$ and $\overline{J}_{M}$. Since $0\leq
J_{M}\leq\mathbbm{1}$, we therefore conclude $0\leq Z_{M}\otimes J_{M}\leq
Z_{M}\otimes\mathbbm{1}_{m}$. Summing this over $M$ yields

$0\leq\sum_{M\in\mathcal{M}}Z_{M}\otimes
J_{M}\leq\sum_{M\in\mathcal{M}}Z_{M}\otimes\mathbbm{1}_{m}=\left\lparen\sum_{M\in\mathcal{M}}Z_{M}\right\rparen\otimes\mathbbm{1}_{m},$
(88)

and hence (from Equation 87)

$\epsilon^{2}\leq\kappa_{m-1}+\kappa_{m}+\left\lVert\sum_{M\in\mathcal{M}}Z_{M}\right\rVert_{\mathrm{op}}=\kappa_{m-1}+\kappa_{m}+\left\lVert\Pi^{(m-1)}\left\lparen\sum_{M\in\cal
M}\overline{J}_{M}\otimes
J_{M}^{\otimes(m-2)}\right\rparen\Pi^{(m-1)}\right\rVert_{\mathrm{op}}.$ (89)

We have effectively now reduced from $m$ tensor components to $m-1$. Indeed,
suppose we had defined the “$m-1$” analogues of $P_{1},P_{2},\dots$ and $P$,
calling them $P_{1}^{(m-1)},P_{2}^{(m-1)},\dots$ and $P^{(m-1)}=\Pi^{(m-1)}$.
Then Equation 82 would tell us

$\widetilde{P}_{1}^{(m-1)}=P^{(m-1)}_{1}-P^{(m-1)}\mathop{\approx}^{\kappa_{m-2}+\kappa_{m-1}}\sum_{M\in\cal
M}\overline{J}_{M}\otimes J_{M}^{\otimes(m-2)},$ (90)

and putting this into Equation 89 (using $\left\lVert
P^{(m-1)}\right\rVert_{\mathrm{op}}\leq 1$) yields

$\epsilon^{2}\leq\kappa_{m-2}+2\kappa_{m-1}+\kappa_{m}+\left\lVert
P^{(m-1)}\widetilde{P}_{1}^{(m-1)}P^{(m-1)}\right\rVert_{\mathrm{op}}.$ (91)

But $P^{(m-1)}\widetilde{P}_{1}^{(m-1)}P^{(m-1)}$ is in fact $0$! (In the
notation of Corollary 4.13 this would be “$P\cdot\widetilde{P}_{1}\cdot
P=0$”.) Thus we have established the claim, Equation 76.

##  5 Lower bounding $\tau_{m}$ for small $m$

In this section we prove Theorem 3.4, restated below:

######  Theorem 5.1 (Restatement of Theorem 3.4).

Let the sequence of groups $(\mathrm{G}(n))_{n\geq 1}$ be either
$(\mathrm{SO}(2^{n}))_{n\geq 1}$ or $(\mathrm{SU}(2^{n}))_{n\geq 1}$. For any
$m\geq 4$ we have that

$\forall
k\in\mathbbm{N}^{+},\quad\quad\quad\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)\times\binom{[m]}{m-1}}[\rho_{2^{m}}^{k,k}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m)}[\rho_{2^{m}}^{k,k}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq\left\lparen
1-(1-\tfrac{1}{m})\tfrac{1-2^{2-m}}{4-2^{3-m}}\right\rparen^{1/4}\leq.96;$
(92)

equivalently, in the notation of Theorem 3.4, $\tau_{m}\geq.04$.

###  5.1 Metrics

As discussed in Section 3, for $\mathrm{G}(m)=\mathrm{SO}(2^{m})$ or
$\mathrm{G}(m)=\mathrm{SU}(2^{m})$ we have that
$\mathrm{G}(m)\subseteq\mathrm{U}(2^{m})$ is a compact connected Lie group
with associated Lie algebra $\mathfrak{g}_{m}$, where

$\displaystyle\text{for~{}}\mathrm{G}(m)=\mathrm{SO}(2^{m}),\
\mathfrak{g}_{m}$ $\displaystyle=\\{H\in\mathbbm{R}^{2^{m}\times
2^{m}}:H\text{ skew-symmetric}\\},$ (93)
$\displaystyle\text{for~{}}\mathrm{G}(m)=\mathrm{SU}(2^{m}),\
\mathfrak{g}_{m}$ $\displaystyle=\\{H\in\mathbbm{C}^{2^{m}\times
2^{m}}:H\text{ skew-Hermitian},\ \operatorname{tr}H=0\\}.$ (94)

As per [Tao14, Prop. 2.11.1], $\mathrm{G}(m)$ can be given the structure of a
Riemannian manifold with a bi-invariant metric. Moreover, $\mathrm{G}(m)$ is
totally geodesic within $\mathrm{U}(2^{m})$, hence the exponential map
$\exp:\mathfrak{g}_{m}\to\mathrm{G}(m)$ is surjective and Riemannian distance
$d_{\textnormal{Rie}}$ within $\mathrm{G}(m)$ coincides with Riemannian
distance within $\mathrm{U}(2^{m})$. This distance can be computed
straightforwardly (see, e.g., [Mec19, within Lem. 1.3]), as follows:

  * •

The Riemannian distance is bi-invariant, so
$d_{\textnormal{Rie}}(X,Y)=d_{\textnormal{Rie}}(\mathbbm{1},Z)$ for
$Z=YX^{-1}$.

  * •

Given $Z\in\mathrm{G}(m)$, we can choose a unique $H\in\mathfrak{g}_{m}$ with
$\exp(H)=Z$ such that the eigenvalues of $H$ are of the form
$\mathrm{i}\theta_{j}$ for $\theta_{j}\in(-\pi,\pi]$. We write $H=\log Z$ for
this choice of $H$.

  * •

Then
$d_{\textnormal{Rie}}(\mathbbm{1},Z)=\|H\|_{\mathrm{Fro}}=(\sum_{j}\theta_{j}^{2})^{1/2}$.

In other words,

$d_{\textnormal{Rie}}(X,Y)=\|\log(YX^{-1})\|_{\mathrm{Fro}}.$ (95)

For the sake of computation it will be convenient to work not just with the
Riemannian distance $d_{\textnormal{Rie}}$ on $\mathrm{G}(m)$, but also the
(very similar) Frobenius distance $d_{\mathrm{Fro}}$, where
$d_{\mathrm{Fro}}(X,Y)$ denotes $\|X-Y\|_{\mathrm{Fro}}$. In the above setup,
now using bi-invariance of $d_{\mathrm{Fro}}$, we evidently have

$d_{\mathrm{Fro}}(X,Y)=\|\mathbbm{1}-Z\|_{\mathrm{Fro}}=\left\lparen{\operatorname{{\textstyle\sum}}}_{j}|1-\exp(\mathrm{i}\theta_{j})|^{2}\right\rparen^{1/2}=\left\lparen{\operatorname{{\textstyle\sum}}}_{j}(2\sin(\theta_{j}/2))^{2}\right\rparen^{1/2}.$
(96)

For some constant $c<.4\leq 1$ we have the following numerical inequality (for
$|\theta|\leq\pi$):

$(2\sin(\theta/2))^{2}\leq\theta^{2}\leq(2\sin(\theta/2))^{2}+c(2\sin(\theta/2))^{4}.$
(97)

Using just $c\leq 1$, we may conclude111111Here we are clarifying slightly the
deduction of [BHH16, eq. (112a)].

$d_{\mathrm{Fro}}(X,Y)^{2}\leq d_{\textnormal{Rie}}(X,Y)^{2}\leq
d_{\mathrm{Fro}}(X,Y)^{2}+d_{\mathrm{Fro}}(X,Y)^{4}.$ (98)

Finally, we will also use the operator-norm distance,
$d_{\mathrm{op}}(X,Y)=\left\lVert X-Y\right\rVert_{\mathrm{op}}$, which
satisfies $d_{\mathrm{op}}(X,Y)\leq d_{\mathrm{Fro}}(X,Y)$.

We now move on to considering (Borel) probability measures on metric spaces
(always assumed to be complete and separable). First we recall some basic
definitions:

######  Definition 5.2.

A pair of jointly distributed random variables
$(\boldsymbol{X},\boldsymbol{Y})$ is a _coupling_ of probability distributions
$\nu_{1},\nu_{2}$ if $\boldsymbol{X}$ (respectively, $\boldsymbol{Y}$) has
marginal distribution $\nu_{1}$ (respectively, $\nu_{2}$).

######  Definition 5.3.

On the metric space $(M,d)$, the _$L^{p}$ -Wasserstein distance_ between two
measures $\nu_{1}$ and $\nu_{2}$ is

$W_{d,p}(\nu_{1},\nu_{2})=\inf\left\\{\operatorname*{\mathbf{E}}[d(\boldsymbol{X},\boldsymbol{Y})^{p}]^{1/p}\
:\ (\boldsymbol{X},\boldsymbol{Y})\text{~{}is a coupling
of~{}}(\nu_{1},\nu_{2})\right\\}.$ (99)

######  Notation 5.4.

If $\nu$ is a probability measure on metric space $M$ and $K$ is a Markov
transition kernel on $M$, we write $K^{\ell}\nu$ for the probability measure
on $M$ resulting from starting with probability measure $\nu$ and taking
$\ell\in\mathbbm{N}$ steps according to $K$.

###  5.2 Oliveira’s theorem and its consequences

We now state a key result of Oliveira [Oli09] that says that on any _length
space_ (see e.g. [BH99]), $L^{2}$-Wasserstein local contraction implies global
contraction. As we only need the result in the particular case of compact,
connected Lie groups (which are finite-diameter complete Riemannian
manifolds), we state it only in this simpler context:

######  Theorem 5.5.

(Implied by [Oli09, Thm. 3].) Let $(M,d)$ be a finite-diameter complete
Riemannian manifold, and let $K$ be a Markov transition kernel on $M$
satisfying the following:

$W_{d,2}(K\delta_{X},K\delta_{Y})\leq(\eta+o(1))d(X,Y),\quad\text{with respect
to $d(X,Y)\to 0$.}$ (100)

(Here $\delta_{Z}$ denotes the measure that puts all of its probability mass
on $Z\in M$.) Then for all probability measures $\nu_{1},\nu_{2}$ on $M$ it
holds that

$W_{d,2}(K\nu_{1},K\nu_{2})\leq\eta\cdot W_{d,2}(\nu_{1},\nu_{2}).$ (101)

Iterating this yields the following:

######  Corollary 5.6.

In the setting of Theorem 5.5, for any $\ell\in\mathbbm{N}^{+}$ we have

$W_{d,2}(K^{\ell}\nu_{1},K^{\ell}\nu_{2})\leq\eta^{\ell}\cdot
W_{d,2}(\nu_{1},\nu_{2})\leq D\eta^{\ell},$ (102)

where $D$ is an upper bound on the diameter of $M$.

We now specialize this corollary to the case where $(M,d)$ is
$(\mathrm{G}(m),d_{\textnormal{Rie}})$; combining it with Definition 5.3 and
using also $W_{{d_{\mathrm{op}}},1}\leq W_{d_{\mathrm{Fro}},1}\leq
W_{d_{\mathrm{Fro}},2}\leq W_{d_{\textnormal{Rie}},2}$, we may conclude:

######  Corollary 5.7.

Let $\mathrm{G}(m)$ be a compact connected Lie group, and let $K$ be a Markov
transition kernel on $\mathrm{G}(m)$ such that Equation 100 holds for
$d_{\textnormal{Rie}}$ with constant $\eta$. Then for any probability measures
$\nu_{1},\nu_{2}$ on $\mathrm{G}(m)$, and any $\ell\in\mathbbm{N}^{+}$, there
is a coupling $(\boldsymbol{X},\boldsymbol{Y})$ of the measures
$K^{\ell}\nu_{1},K^{\ell}\nu_{2}$ under which

$\operatorname*{\mathbf{E}}[\left\lVert\boldsymbol{X}-\boldsymbol{Y}\right\rVert_{\mathrm{op}}]\leq
2D\eta^{\ell}$ (103)

(where $D$ is a bound on the $d_{\textnormal{Rie}}$-diameter of
$\mathrm{G}(m)$, and the factor $2$ accounts for the $\inf$).

Our next step is to get rid of the coupling in Corollary 5.7. To do this, we
first observe that the representation $\rho^{k,k}_{2^{m}}$ is uniformly
continuous on $\mathrm{G}(m)$ with respect to the operator-norm distance.
Concretely, from the identity

$g_{1}\otimes\cdots\otimes g_{K}-h_{1}\otimes\cdots\otimes
h_{K}=\sum_{i=1}^{K}g_{1}\otimes\cdots\otimes
g_{i-1}\otimes(g_{i}-h_{i})\otimes h_{i+1}\otimes\cdots\otimes h_{K}$ (104)

and $\left\lVert
X\right\rVert_{\mathrm{op}},\left\lVert\overline{X}\right\rVert_{\mathrm{op}}=1$
for $X\in\mathrm{G}(m)$, as well as multiplicativity of $d_{\mathrm{op}}$ with
respect to tensor products, we may conclude that

$\left\lVert\rho^{k,k}_{2^{m}}(X)-\rho^{k,k}_{2^{m}}(Y)\right\rVert_{\mathrm{op}}\leq
2k\left\lVert X-Y\right\rVert_{\mathrm{op}}$ (105)

for any $X,Y\in\mathrm{G}(m)$. Using this, as well as the triangle inequality
for $d_{\mathrm{op}}$, in Corollary 5.7 yields:

######  Corollary 5.8.

In the setting of Corollary 5.7,

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{X}\sim
K^{\ell}\nu_{1}}[\rho^{k,k}_{2^{m}}(\boldsymbol{X})]-\operatorname*{\mathbf{E}}_{\boldsymbol{Y}\sim
K^{\ell}\nu_{2}}[\rho^{k,k}_{2^{m}}(\boldsymbol{Y})]\right\rVert_{\mathrm{op}}\leq
4kD\eta^{\ell}.$ (106)

(Note that in contrast with Corollary 5.7, here Corollary 5.8 does not feature
any coupling between $K^{\ell}\nu_{1}$ and $K^{\ell}\nu_{2}$.)

Now we further specialize by taking $\nu_{1}=\delta_{\mathbbm{1}}$ (the
measure with all probability on the identity element
$\mathbbm{1}\in\mathrm{G}(m)$), taking $\nu_{2}$ to be Haar measure, and
specifying that

$K\text{ arises from left-multiplying by a random
$\boldsymbol{g}\sim\mathcal{P}$},$ (107)

where $\mathcal{P}$ is some symmetric probability distribution on
$\mathrm{G}(m)$ as in Definition 2.3. Note that, whatever $\mathcal{P}$ is, we
have $K^{\ell}\nu_{2}=\nu_{2}$ (Haar measure), and

$\operatorname*{\mathbf{E}}_{\boldsymbol{X}\sim
K^{\ell}\nu_{1}}[\rho^{k,k}_{2^{m}}(\boldsymbol{X})]=\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{g}_{1},\dots,\boldsymbol{g}_{\ell}\sim\mathcal{P}\\\
\text{independent}\end{subarray}}[\rho^{k,k}_{2^{m}}(\boldsymbol{g}_{\ell}\cdots\boldsymbol{g}_{1})]=\operatorname*{\mathbf{E}}[\rho^{k,k}_{2^{m}}(\boldsymbol{g}_{\ell})\cdots\rho^{k,k}_{2^{m}}(\boldsymbol{g}_{1})]=\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathcal{P}}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]^{\ell}.$
(108)

From this and Corollary 5.8 we conclude the following:

######  Corollary 5.9.

Let $\mathcal{P}$ be a symmetric probability distribution on $\mathrm{G}(m)$.
Given $X,Y\in\mathrm{G}(m)$, write $\mathcal{P}^{(X)}$ (respectively,
$\mathcal{P}^{(Y)}$) for the distribution of $\boldsymbol{g}X$ (respectively,
$\boldsymbol{g}Y$) when $\boldsymbol{g}\sim\mathcal{P}$. Then supposing

$W_{d_{\textnormal{Rie}},2}(\mathcal{P}^{(X)},\mathcal{P}^{(Y)})\leq(\eta+o(1))d_{\textnormal{Rie}}(X,Y)\quad\text{with
respect to $d_{\textnormal{Rie}}(X,Y)\to 0$,}$ (109)

it follows that for any $\ell,k\in\mathbbm{N}^{+}$ we have

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathcal{P}}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]^{\ell}-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m)}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}\leq
4kD\cdot\eta^{\ell}.$ (110)

Our goal for the next section will be to establish the following:

######  Theorem 5.10.

Let $\nu_{m}$ denote the distribution $\mathrm{G}(m-1)\times\binom{[m]}{m-1}$
on $\mathrm{G}(m)$, thought of as inducing a Markov chain on $\mathrm{G}(m)$
via left-multiplication. Fix any $X,Y\in\mathrm{G}(m)$ with
$d_{\textnormal{Rie}}(X,Y)=\epsilon\leq 1$, and let
$\boldsymbol{X}^{\prime\prime}$ (respectively,
$\boldsymbol{Y}^{\prime\prime}$) denote the result of taking _two_ independent
steps from $X$ (respectively, $Y$) according to $\nu_{m}$. Then there is a
coupling of $\boldsymbol{X}^{\prime\prime},\boldsymbol{Y}^{\prime\prime}$
under which

$\operatorname*{\mathbf{E}}[d_{\textnormal{Rie}}(\boldsymbol{X}^{\prime\prime},\boldsymbol{Y}^{\prime\prime})^{2}]\leq(1-\gamma_{m})\epsilon^{2}+O_{m}(\epsilon^{3}),$
(111)

where $\gamma_{m}=(1-\frac{1}{m})\gamma^{\prime}_{m}$ with
$\gamma^{\prime}_{m}=\frac{1-2^{2-m}}{4-2^{3-m}}$, and the $O_{m}(\cdot)$
hides a constant depending only on $m$.

This theorem establishes the hypothesis of Corollary 5.9 with
$\mathcal{P}=\nu_{m}\ast\nu_{m}$ and $\eta=\sqrt{1-\gamma_{m}}$. We can
therefore easily derive the following (where the equality uses the fact that
$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m)}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]$
is a projection operator):

$\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\nu_{m}}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]^{2\ell}-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m)}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}=\left\lVert\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\nu_{m}}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]-\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m)}[\rho^{k,k}_{2^{m}}(\boldsymbol{g})]\right\rVert_{\mathrm{op}}^{2\ell}\leq
4kD\cdot(1-\gamma_{m})^{\ell/2}.$ (112)

Taking $(2\ell)$th roots and then $\ell\to\infty$ thus yields Theorem 5.1.

###  5.3 Proof of Theorem 5.10

We begin by describing the needed coupling. First, we use the same randomness
to take one step from each of $X,Y$; that is, we define

$\boldsymbol{X}^{\prime}=\boldsymbol{g}_{[m]\setminus\boldsymbol{i}}\cdot
X,\qquad\boldsymbol{Y}^{\prime}=\boldsymbol{g}_{[m]\setminus\boldsymbol{i}}\cdot
Y,$ (113)

where $\boldsymbol{i}\sim[m]$, $\boldsymbol{g}\sim\mathrm{G}(m-1)$ are
uniformly random and independent. To take the second steps, we first draw
$\boldsymbol{j}\sim[m]$. Then, based on the outcomes
$\boldsymbol{i},\boldsymbol{j},\boldsymbol{g}$, we will deterministically
define some

$\boldsymbol{h}=h(\boldsymbol{i},\boldsymbol{j},\boldsymbol{g})\in\mathrm{G}(m-1)$
(114)

and then take

$\boldsymbol{X}^{\prime\prime}=(\widetilde{\boldsymbol{g}}\boldsymbol{h})_{[m]\setminus\boldsymbol{j}}\cdot\boldsymbol{X}^{\prime},\qquad\boldsymbol{Y}^{\prime\prime}=\widetilde{\boldsymbol{g}}_{[m]\setminus\boldsymbol{j}}\cdot\boldsymbol{Y}^{\prime},$
(115)

where $\widetilde{\boldsymbol{g}}\sim\mathrm{G}(m-1)$ is drawn uniformly and
independently of all other random variables. This is a valid coupling, since
for every outcome of $\boldsymbol{i},\boldsymbol{j},\boldsymbol{g}$ the
distributions of $\widetilde{\boldsymbol{g}}\boldsymbol{h}$ and
$\widetilde{\boldsymbol{g}}$ are identical. Then

$d_{\textnormal{Rie}}(\boldsymbol{X}^{\prime\prime},\boldsymbol{Y}^{\prime\prime})=d_{\textnormal{Rie}}(\boldsymbol{h}_{[m]\setminus\boldsymbol{j}}\cdot\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime}),$
(116)

since $d_{\textnormal{Rie}}({\cdot},{\cdot})$ is unitarily invariant. In case
$\boldsymbol{i}=\boldsymbol{j}$, we will “give up” and simply define
$\boldsymbol{h}=\mathbbm{1}$, in which case we get
$d_{\textnormal{Rie}}(\boldsymbol{X}^{\prime\prime},\boldsymbol{Y}^{\prime\prime})=d_{\textnormal{Rie}}(\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime})=d_{\textnormal{Rie}}(X,Y)=\epsilon$.
Thus we have

$\operatorname*{\mathbf{E}}[d_{\textnormal{Rie}}(\boldsymbol{X}^{\prime\prime},\boldsymbol{Y}^{\prime\prime})^{2}]=\frac{1}{m}\epsilon^{2}+\left\lparen
1-\frac{1}{m}\right\rparen\mathop{\textnormal{avg}}_{\boldsymbol{i}\neq\boldsymbol{j}}\left\\{\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}\left[d_{\textnormal{Rie}}\left\lparen\boldsymbol{h}_{[m]\setminus\boldsymbol{j}}\cdot\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime}\right\rparen^{2}\right]\right\\}.$
(117)

To complete the definition of $\boldsymbol{h}$, we specify the function $h$:

$\text{for $i\neq j$, we define }h=h(i,j,g)\text{ to minimize
}d_{\mathrm{Fro}}\left\lparen h_{[m]\setminus j}\cdot g_{[m]\setminus i}\cdot
X,g_{[m]\setminus i}\cdot Y\right\rparen^{2};$ (118)

in other words,
$\boldsymbol{h}=h(\boldsymbol{i},\boldsymbol{j},\boldsymbol{g})$ minimizes
$d_{\mathrm{Fro}}\left\lparen\boldsymbol{h}_{[m]\setminus\boldsymbol{j}}\cdot\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime}\right\rparen$.
With this choice of $h$, note that we have
$d_{\mathrm{Fro}}\left\lparen\boldsymbol{h}_{[m]\setminus\boldsymbol{j}}\cdot\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime}\right\rparen\leq\epsilon\leq
1$ for every outcome of $\boldsymbol{i},\boldsymbol{j},\boldsymbol{g}$, since
$\boldsymbol{h}=\mathbbm{1}$ is always an option (and
$d_{\mathrm{Fro}}(\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime})=d_{\mathrm{Fro}}(X,Y)\leq
d_{\textnormal{Rie}}(X,Y)=\epsilon$). Thus employing Equation 98 we may
conclude

$\operatorname*{\mathbf{E}}[d_{\textnormal{Rie}}(\boldsymbol{X}^{\prime\prime},\boldsymbol{Y}^{\prime\prime})^{2}]\leq\frac{1}{m}\epsilon^{2}+\left\lparen
1-\frac{1}{m}\right\rparen\mathop{\textnormal{avg}}_{\boldsymbol{i}\neq\boldsymbol{j}}\left\\{\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}\left[d_{\mathrm{Fro}}\left\lparen\boldsymbol{h}_{[m]\setminus\boldsymbol{j}}\cdot\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime}\right\rparen^{2}\right]\right\\}+\epsilon^{4}.$
(119)

Thus to complete the proof of Theorem 5.10, it suffices to establish the
following:

$\forall i\neq
j,\qquad\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}\left[\min_{h\in\mathrm{G}(m-1)}\left\\{d_{\mathrm{Fro}}\left\lparen
h_{[m]\setminus
j},\boldsymbol{Y}^{\prime}\cdot(\boldsymbol{X}^{\prime})^{-1}\right\rparen^{2}\right\\}\right]\leq(1-\gamma^{\prime}_{m})\epsilon^{2}+O_{m}(\epsilon^{3}).$
(120)

(Here we used $d_{\mathrm{Fro}}\left\lparen h_{[m]\setminus
j}\cdot\boldsymbol{X}^{\prime},\boldsymbol{Y}^{\prime}\right\rparen=d_{\mathrm{Fro}}\left\lparen
h_{[m]\setminus
j},\boldsymbol{Y}^{\prime}\cdot(\boldsymbol{X}^{\prime})^{-1}\right\rparen$.)
Our proof of this will not have any particular dependence on $i,j$, so without
loss of generality let us fix $i=1$ and $j=m$. We establish Equation 120 via
the below two lemmas. (Here and subsequently the notation
“$\operatorname{tr}_{i}X$” below denotes the partial trace corresponding to
tracing out the $i$th qubit of $X$.)

######  Lemma 5.11.

Fix any $Z\in\mathrm{G}(m)$ with
$d_{\textnormal{Rie}}(\mathbbm{1},Z)=\epsilon$. Then

$\min_{h\in\mathrm{G}(m-1)}\left\\{d_{\mathrm{Fro}}\left\lparen
h\otimes\mathbbm{1},Z\right\rparen^{2}\right\\}\leq(1-\tfrac{1}{2}\lVert\operatorname{tr}_{m}B\rVert_{\mathrm{Fro}}^{2})\epsilon^{2}+O_{m}(\epsilon^{3}),$
(121)

where $B=\tfrac{1}{\epsilon}\log Z\in\mathfrak{g}_{m}$ satisfies
$\|B\|_{\mathrm{Fro}}=1$.

######  Lemma 5.12.

For $m\geq 2$ and any $A\in\mathfrak{g}_{m}$, writing $\delta=2^{2-m}$, we
have

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}[\lVert\operatorname{tr}_{m}((\mathbbm{1}\otimes\boldsymbol{g}_{[m]\setminus
1})A(\mathbbm{1}\otimes\boldsymbol{g}_{[m]\setminus
1}^{\dagger}))\rVert_{\mathrm{Fro}}^{2}]\geq\frac{1-\delta}{2-\delta}\|A\|_{\mathrm{Fro}}^{2}.$
(122)

To see how the above two lemmas imply Equation 120 (in the case $i=1$, $j=m$),
we first apply Lemma 5.11 with $Z$ being the outcome of
$\boldsymbol{Y}^{\prime}\cdot(\boldsymbol{X}^{\prime})^{-1}$. Writing
$\boldsymbol{B}=\frac{1}{\epsilon}\log(\boldsymbol{Y}^{\prime}(\boldsymbol{X}^{\prime})^{-1})$
(recall that from Equation 113 this is a random matrix depending on
$\boldsymbol{g}$), Lemma 5.11 tells us that

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}\left[\min_{h\in\mathrm{G}(m-1)}\left\\{d_{\mathrm{Fro}}\left\lparen
h_{[m]\setminus
j}\otimes\mathbbm{1}_{j},\boldsymbol{Y}^{\prime}\cdot(\boldsymbol{X}^{\prime})^{-1}\right\rparen^{2}\right\\}\right]\leq(1-\tfrac{1}{2}\operatorname*{\mathbf{E}}[\|\operatorname{tr}_{m}\boldsymbol{B}\|_{\mathrm{Fro}}^{2}])\epsilon^{2}+O_{m}(\epsilon^{3}).$
(123)

But, for $\boldsymbol{g}\sim\mathrm{G}(m-1)$, we have

$\boldsymbol{B}=\tfrac{1}{\epsilon}\log\left\lparen(\mathbbm{1}\otimes\boldsymbol{g}_{[m]\setminus
1})YX^{-1}(\mathbbm{1}\otimes\boldsymbol{g}_{[m]\setminus
1}^{\dagger})\right\rparen=(\mathbbm{1}\otimes\boldsymbol{g}_{[m]\setminus
1})\left\lparen\tfrac{1}{\epsilon}\log(YX^{-1})\right\rparen(\mathbbm{1}\otimes\boldsymbol{g}_{[m]\setminus
1}^{\dagger}).$ (124)

The result now follows by applying Lemma 5.12 with
$A=\frac{1}{\epsilon}\log(YX^{-1})$, which has $\|A\|_{\mathrm{Fro}}=1$ since
$d_{\textnormal{Rie}}(X,Y)=\epsilon$.

####  5.3.1 Proof of Lemma 5.11

To prove Lemma 5.11, it suffices to show that the particular choice

$h\coloneqq\exp(-\tfrac{1}{2}\epsilon\operatorname{tr}_{m}B)$ (125)

satisfies Equation 121. We observe that since $\mathrm{G}(m)$ is either
$\mathrm{SO}(2^{m})$ or $\mathrm{SU}(2^{m})$, recalling Equations 93 and 94 we
have that $\operatorname{tr}_{m}B\in\mathfrak{g}_{m-1}$ since
$B\in\mathfrak{g}_{m}$ (note that $\operatorname{tr}B=0$ implies
$\operatorname{tr}(\operatorname{tr}_{m}B)=0$), and hence indeed
$h\in\mathrm{G}(m-1)$ as required. Now we must bound

$d_{\mathrm{Fro}}\left\lparen h\otimes\mathbbm{1},Z\right\rparen^{2}=\langle
h\otimes\mathbbm{1}-Z,h\otimes\mathbbm{1}-Z\rangle=2\operatorname{tr}\mathbbm{1}-\langle
h\otimes\mathbbm{1},Z\rangle-\langle
Z,h\otimes\mathbbm{1}\rangle=2\operatorname{tr}\mathbbm{1}-2\Re\langle
h\otimes\mathbbm{1},Z\rangle.$ (126)

Recalling $Z=\exp(\epsilon B)$ where $\|B\|_{\mathrm{Fro}}=1$, we abuse
notation slightly by writing

$Z=1+\epsilon B+\epsilon^{2}B^{2}/2+O_{m}(\epsilon^{3}),$ (127)

where “$O_{m}(\epsilon^{3})$” stands for some matrix $E$ satisfying
$\|E\|_{\mathrm{Fro}}\leq C\epsilon^{3}$, with $C$ a constant depending only
on $m$ that may change from line to line.

We may similarly expand
$h\otimes\mathbbm{1}=\exp(-\tfrac{1}{2}\epsilon\operatorname{tr}_{m}B)\otimes\mathbbm{1}$,
and upon substituting into Equation 126 and simplifying, we obtain

$\eqref{eqn:whatami}=\Re\operatorname{tr}(T-2B)\epsilon+\Re\operatorname{tr}\left\lparen
TB-\tfrac{1}{4}T^{2}-B^{2}\right\rparen\epsilon^{2}+O_{m}(\epsilon^{3}),\qquad
T\coloneqq(\operatorname{tr}_{m}B)\otimes\mathbbm{1}.$ (128)

Now $B,T$ are both in the Lie algebra for $\mathrm{G}(m)$; i.e., they are
skew-symmetric in the case $\mathrm{G}(m)=\mathrm{SO}(2^{m})$, and traceless
skew-Hermitian in the case $\mathrm{G}(m)=\mathrm{SU}(2^{m})$. Thus both have
purely imaginary trace, meaning $\Re\operatorname{tr}(T-2B)=0$. Moreover, $B$
skew-Hermitian implies
$\operatorname{tr}B^{2}=\operatorname{tr}B(-B^{\dagger})=-\langle
B,B\rangle=-\|B\|_{\mathrm{Fro}}^{2}=-1$, and similarly
$\operatorname{tr}T^{2}=-\|T\|_{\mathrm{Fro}}^{2}=-2\lVert\operatorname{tr}_{m}B\rVert_{\mathrm{Fro}}^{2}$.
Finally,

$\operatorname{tr}(TB)=-\langle
T,B\rangle=-\langle(\operatorname{tr}_{m}B)\otimes\mathbbm{1},B\rangle=-\langle\operatorname{tr}_{m}B,\operatorname{tr}_{m}B\rangle=-\lVert\operatorname{tr}_{m}B\rVert_{\mathrm{Fro}}^{2}.$
(129)

Putting these deductions into Equation 128 yields

$\eqref{eqn:whatami}=(1-\tfrac{1}{2}\lVert\operatorname{tr}_{m}B\rVert_{\mathrm{Fro}}^{2})\epsilon^{2}+O_{m}(\epsilon^{3}),$
(130)

completing the proof of Lemma 5.11.

####  5.3.2 Proof of Lemma 5.12

Given $m$ qubits, we’ll write $L=\\{1,\dots,m-1\\}$ for the system defined by
the first $m-1$ of them, and (slightly abusing notation) write $m$ for the
system defined by the $m$th one. We will also write $L^{\prime}$ and
$m^{\prime}$ for duplicate copies of these systems, and given a subset
$S\subseteq[m]$, we write $\textrm{SWAP}_{S,S^{\prime}}$ to denote the
operator that swaps the qubits in $S$ with the corresponding subset of qubits
$1^{\prime},\dots,m^{\prime}.$ Now for any $(m-1)$-qubit operator $C$ we have

$\lVert
C\rVert_{\mathrm{Fro}}^{2}=\operatorname{tr}(C^{\dagger}C)=\operatorname{tr}((C_{L}^{\dagger}\otimes
C_{L^{\prime}})\cdot\textrm{SWAP}_{L,L^{\prime}}).$ (131)

In turn, if $C=\operatorname{tr}_{m}B$ for some operator $B$ on $m$ qubits, we
conclude

$\lVert\operatorname{tr}_{m}B\rVert_{\mathrm{Fro}}^{2}=\operatorname{tr}(\operatorname{tr}_{m,m^{\prime}}(B^{\dagger}\otimes
B)\cdot\textrm{SWAP}_{L,L^{\prime}})=\operatorname{tr}((B^{\dagger}\otimes
B)\cdot(\textrm{SWAP}_{L,L^{\prime}}\otimes\mathbbm{1}_{m,m^{\prime}})).$
(132)

Next, if $B=HAH^{\dagger}$ for unitary $H$, we may use the cyclic property of
trace to conclude

$\lVert\operatorname{tr}_{m}B\rVert_{\mathrm{Fro}}^{2}=\operatorname{tr}((A^{\dagger}\otimes
A)\cdot W)=\langle A\otimes A^{\dagger},W\rangle,\qquad W\coloneqq(H\otimes
H)(\textrm{SWAP}_{L,L^{\prime}}\otimes\mathbbm{1}_{m,m^{\prime}})(H^{\dagger}\otimes
H^{\dagger}).$ (133)

(The above formula, specialized to $m=3$, essentially appears as [BHH16, Eqn.
(103)].) Finally, suppose $H=\mathbbm{1}\otimes g$ for some $(m-1)$-qubit
unitary $g$. For notational clarity we break up the system $L$ into subsystems
“$1$” and $K=\\{2,\dots,m-1\\}$, writing $H=\mathbbm{1}_{1}\otimes g_{K,m}$
and

$H\otimes H=\mathbbm{1}_{1,1^{\prime}}\otimes(g_{K,m}\otimes
g_{K^{\prime},m^{\prime}}).$ (134)

Putting this into the definition of $W$, we see that the two qubits labeled
$1$ and $1^{\prime}$ are simply swapped by $W$, and we have

$W=\mathrm{SWAP}_{1,1^{\prime}}\cdot\widehat{W},\qquad\widehat{W}\coloneqq(g_{K,m}\otimes
g_{K^{\prime},m^{\prime}})S(g_{K,m}^{\dagger}\otimes
g_{K^{\prime},m^{\prime}}^{\dagger}),\qquad
S\coloneqq(\mathrm{SWAP}_{K,K^{\prime}}\otimes\mathbbm{1}_{m,m^{\prime}}).$
(135)

Recalling Fact 4.4, we see that

$\mathrm{vec}(\widehat{W})=\rho^{2,2}_{2^{m-1}}(g)\cdot\mathrm{vec}(S).$ (136)

In other words, $\widehat{W}$ is the action of $g$ on $S$ under representation
$\rho^{2,2}_{2^{m-1}}$, when we suitably use the “matricized” interpretation
of this representation. Finally, we are interested in the case that
$\boldsymbol{g}\sim\mathrm{G}(m-1)$ is chosen “uniformly” (Haar measure on
$\mathrm{G}(m-1)$); then we conclude from the above equations that

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}[\lVert\operatorname{tr}_{m}((\mathbbm{1}\otimes\boldsymbol{g})A(\mathbbm{1}\otimes\boldsymbol{g}^{\dagger}))\rVert_{\mathrm{Fro}}^{2}]=\langle
A\otimes A^{\dagger},\mathrm{SWAP}_{1,1^{\prime}}\cdot
S_{0}\rangle,\qquad\mathrm{vec}(S_{0})\coloneqq\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}[\rho^{2,2}_{2^{m-1}}(\boldsymbol{g})]\cdot\mathrm{vec}(S).$
(137)

We now compute $S_{0}$ (we note that a similar calculation for
$\mathrm{G}(m-1)=\mathrm{U}(2^{m-1})$ is given in [HHJ21, Eqn. (61)]):

######  Proposition 5.13.

Let $D=2^{m-1}$, and define the following operators acting across systems
$K\cup\\{m\\}$, $K^{\prime}\cup\\{m^{\prime}\\}$:

$Q_{2}=D\cdot\ket{\Phi}\\!\bra{\Phi},\quad Q_{3}=\mathbbm{1},\quad
Q_{4}=\mathrm{SWAP}$ (138)

(where $\ket{\Phi}=D^{-1/2}\sum_{a\in\\{0,1\\}^{m-1}}\ket{a}\otimes\ket{a}$ is
the maximally entangled state). Then

$\displaystyle\mathrm{G}(m-1)$ $\displaystyle=\mathrm{SO}(D)$
$\displaystyle\implies\phantom{Dc_{2}\cdot Q_{2}+{}}S_{0}$
$\displaystyle=c_{2}\cdot Q_{2}+c_{3}\cdot Q_{3}+c_{4}\cdot Q_{4},$ (139)
$\displaystyle\mathrm{G}(m-1)$ $\displaystyle=\mathrm{SU}(D)$
$\displaystyle\implies\phantom{Dc_{2}\cdot Q_{2}+{}}S_{0}$
$\displaystyle=c^{\prime}_{3}\cdot Q_{3}+c^{\prime}_{4}\cdot Q_{4},$ (140)

where the non-negative constants
$c_{2},c_{3},c_{4},c^{\prime}_{3},c^{\prime}_{4}$ are given by

$\displaystyle c_{2}=\frac{D/2-1}{(D-1)(D+2)},\quad
c_{3}=\frac{3D/2+1}{(D-1)(D+2)},\quad c_{4}=\frac{(D/2-1)(D+3)}{(D-1)(D+2)},$
(141) $\displaystyle\quad c^{\prime}_{3}=\frac{3D/2}{(D-1)(D+1)},\quad
c^{\prime}_{4}=\frac{D^{2}/2-2}{(D-1)(D+1)}\geq c_{4}.$ (142)

###### Proof.

We recall from Theorem 4.8 that121212Note that here we are using $m\geq 4$.

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}[\rho^{2,2}_{2^{m-1}}(\boldsymbol{g})]=\text{projection
onto the span of }\\{\ket{\varphi_{M}}:M\in\mathcal{M}\\},$ (143)

where we use the following notation:

$\displaystyle M_{12}=\\{\\{1,2\\},\\{3,4\\}\\},\quad
M_{13}=\\{\\{1,3\\},\\{2,4\\}\\},\quad M_{14}=\\{\\{1,4\\},\\{2,3\\}\\};$
(144)
$\displaystyle\ket{\varphi_{M_{12}}}=\mathrm{vec}(Q_{2})=\sum_{x,y\in\\{0,1\\}^{m-1}}\ket{x,x,y,y},$
(145)
$\displaystyle\ket{\varphi_{M_{13}}}=\mathrm{vec}(Q_{3})=\sum_{x,y}\ket{x,y,x,y},\quad\ket{\varphi_{M_{14}}}=\mathrm{vec}(Q_{4})=\sum_{x,y}\ket{x,y,y,x};$
(146)
$\displaystyle\mathrm{G}(m-1)=\mathrm{SO}(2^{m-1})\implies\mathcal{M}=\\{M_{12},M_{13},M_{14}\\},\qquad\mathrm{G}(m-1)=\mathrm{SU}(2^{m-1})\implies\mathcal{M}=\\{M_{13},M_{14}\\}.$
(147)

Let us further define

$\ket{\psi_{10}}=\sum_{x\in\\{0,1\\}^{m-1}}\ket{x,x,x,x}\quad\text{and}\quad\ket{\psi_{1j}}=\ket{\varphi_{M_{1j}}}-\ket{\psi_{10}},$
(148)

so that the $\ket{\psi_{1j}}$’s are pairwise orthogonal, with
$\braket{\psi_{10}}{\psi_{10}}=D$ and $\braket{\psi_{1j}}{\psi_{1j}}=D(D-1)$
for $j>1$. Then, since from Equation 135 we have

$\mathrm{vec}(S)=\sum_{\begin{subarray}{c}x=(x^{\prime},a)\in\\{0,1\\}^{m-2}\times\\{0,1\\}\\\
y=(y^{\prime},b)\in\\{0,1\\}^{m-2}\times\\{0,1\\}\end{subarray}}\ket{(x^{\prime},a),(y^{\prime},b),(y^{\prime},a),(x^{\prime},b)},$
(149)

we can easily compute

$\bra{\psi_{10}}\mathrm{vec}(S)=D,\quad\bra{\psi_{12}}\mathrm{vec}(S)=0,\quad\bra{\psi_{13}}\mathrm{vec}(S)=D,\quad\bra{\psi_{14}}\mathrm{vec}(S)=D(D/2-1).$
(150)

From this we conclude that the projection of $\mathrm{vec}(S)$ onto the span
of the four $\ket{\psi_{1j}}$’s (which is also the span of $\ket{\psi_{10}}$
and the three $\ket{\varphi_{M_{1j}}}$’s) is

$\ket{\sigma}\coloneqq\ket{\psi_{10}}+\frac{1}{D-1}\ket{\psi_{13}}+\frac{D/2-1}{D-1}\ket{\psi_{14}}.$
(151)

Now one may easily verify that the following vector $\ket{\tau}$ is orthogonal
to each $\ket{\varphi_{M_{1j}}}=\ket{\psi_{10}}+\ket{\psi_{1j}}$:

$\ket{\tau}=-(D-1)\ket{\psi_{10}}+\ket{\psi_{12}}+\ket{\psi_{13}}+\ket{\psi_{14}}.$
(152)

Thus we can bring $\ket{\sigma}$ into the span of the three
$\ket{\varphi_{M_{1j}}}$’s by adding a suitable multiple of $\ket{\tau}$ to
zero out the $\ket{\psi_{10}}$ component as follows:

$\displaystyle\ket{\sigma}+c\ket{\tau}$
$\displaystyle=(1-(D-1)c)\ket{\psi_{10}}+c\ket{\psi_{12}}+\left\lparen\frac{1}{D-1}+c\right\rparen\ket{\psi_{13}}+\left\lparen\frac{D/2-1}{D-1}+c\right\rparen\ket{\psi_{14}}$
(153)
$\displaystyle=\left\lparen\frac{D/2-1}{D-1}-(D+2)c\right\rparen\ket{\psi_{10}}+c\ket{\varphi_{M_{12}}}+\left\lparen\frac{1}{D-1}+c\right\rparen\ket{\varphi_{M_{13}}}+\left\lparen\frac{D/2-1}{D-1}+c\right\rparen\ket{\varphi_{M_{14}}},$
(154)

and taking $c=\frac{D/2-1}{(D-1)(D+2)}$ we finally get that

$\text{the projection of $\mathrm{vec}(S)$ onto the span of
}\ket{\varphi_{M_{12}}},\ket{\varphi_{M_{13}}},\ket{\varphi_{M_{14}}}\text{ is
}c_{2}\ket{\varphi_{M_{12}}}+c_{3}\ket{\varphi_{M_{13}}}+c_{4}\ket{\varphi_{M_{14}}}.$
(155)

One can repeat the above using
$\ket{\tau^{\prime}}=-(D-1)\ket{\psi_{10}}+\ket{\psi_{13}}+\ket{\psi_{14}}$ in
place of $\ket{\tau}$ to similarly deduce

$\text{the projection of $\mathrm{vec}(S)$ onto the span of
}\ket{\varphi_{M_{13}}},\ket{\varphi_{M_{14}}}\text{ is
}c^{\prime}_{3}\ket{\varphi_{M_{13}}}+c^{\prime}_{4}\ket{\varphi_{M_{14}}}.$
(156)

The proof is complete. ∎

Now we compute:

$\langle A\otimes A^{\dagger},\mathrm{SWAP}_{1,1^{\prime}}\cdot
Q_{4}\rangle=\langle A\otimes
A^{\dagger},\mathrm{SWAP}_{[m],[m]^{\prime}}\rangle=\|A\|_{\mathrm{Fro}}^{2}$
(157)

(similar to Equation 131), and

$\langle A\otimes A^{\dagger},\mathrm{SWAP}_{1,1^{\prime}}\cdot
Q_{3}\rangle=\langle A\otimes
A^{\dagger},\mathrm{SWAP}_{1,1^{\prime}}\cdot\mathbbm{1}_{[m]\setminus
1,[m]^{\prime}\setminus 1^{\prime}}\rangle=\|\operatorname{tr}_{[m]\setminus
1}A\|_{\mathrm{Fro}}^{2}\geq 0$ (158)

(similar to Equation 132). Finally, since (as can be easily verified)

$\mathrm{SWAP}_{1,1^{\prime}}\cdot
Q_{2}=\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}\\\
x,y\in\\{0,1\\}^{m-1}\end{subarray}}\ket{(a,x),(b,x)}\\!\bra{(b,y),(a,y)},$
(159)

we may conclude that

$\langle A\otimes A^{\dagger},\mathrm{SWAP}_{1,1^{\prime}}\cdot
Q_{2}\rangle=\sum_{a,b,x,y}\braket{(b,y)}{A^{\dagger}}{(a,x)}\braket{(a,y)}{A}{(b,x)}\geq-\|A\|_{\mathrm{Fro}}^{2}$
(160)

by Cauchy–Schwarz. Putting these conclusions together with Equation 137 and
Proposition 5.13, we get that for both $\mathrm{G}(m-1)=\mathrm{SO}(2^{m-1})$
and $\mathrm{G}(m-1)=\mathrm{SU}(2^{m-1})$ it holds that

$\operatorname*{\mathbf{E}}_{\boldsymbol{g}\sim\mathrm{G}(m-1)}[\lVert\operatorname{tr}_{m}((\mathbbm{1}\otimes\boldsymbol{g})A(\mathbbm{1}\otimes\boldsymbol{g}^{-1}))\rVert_{\mathrm{Fro}}^{2}]\geq(c_{4}-c_{2})\|A\|_{\mathrm{Fro}}^{2}=\frac{D/2-1}{D-1}\|A\|_{\mathrm{Fro}}^{2}=\frac{1-2^{2-m}}{2-2^{2-m}}\|A\|_{\mathrm{Fro}}^{2},$
(161)

completing the proof of Lemma 5.12.

##  6 Pseudorandom products of operators

In this section we generalize the “derandomized squaring” technique of
Rozenman and Vadhan [RV05] so that it may be applied to random walks on
groups, where the goal is to show rapid mixing of a particular representation.
We remark that the proofs are not really different from those in [RV05], and
that a similar generalization appeared recently in [JMRW22].

######  Notation 6.1.

Throughout we will be considering noncommutative polynomials, with real
coefficients, over symbols
$u_{1},\dots,u_{c},u_{1}^{\dagger},\dots,u_{c}^{\dagger}$. (These symbols will
eventually be substituted by square matrices.) If $p$ is such a polynomial,
its _adjoint_ $p^{\dagger}$ is formed in the natural way (i.e.,
$(u_{i}^{\dagger})^{\dagger}=u_{i}$ and
$(u_{i}u_{j})^{\dagger}=u_{j}^{\dagger}u_{i}^{\dagger}$, etc.), and we call
$p$ _self-adjoint_ if $p^{\dagger}=p$.

######  Notation 6.2.

We will also consider _polynomial sequences_ $S=(s_{1},\dots,s_{m})$, where
each $s_{i}$ is a polynomial in the $u_{j}$’s. (Usually $s_{i}$ will in fact
be a _monomial_.)

######  Notation 6.3.

If $\mathcal{U}=(U_{1},\dots,U_{c})$ is a sequence of matrices, we write
$S(\mathcal{U})=(s_{1}(\mathcal{U}),\dots,s_{m}(\mathcal{U}))$, where
$s_{j}(\mathcal{U})$ is the matrix resulting from substituting $u_{i}=U_{i}$
for each $i\in[c]$.

######  Notation 6.4.

Given a polynomial sequence $S$ we write $\textnormal{avg}(S)$, or
$\textnormal{avg}\circ S$, for the polynomial
$\frac{1}{m}\sum_{j=1}^{m}s_{j}$.

######  Definition 6.5.

If $p$ is a polynomial over $u_{1},\dots,u_{c}$, we define

$\|p\|=\sup_{r}\\{\left\lVert
p(\mathcal{U})\right\rVert_{\mathrm{op}}:\mathcal{U}=(U_{1},\dots,U_{c}),\
U_{j}\in\mathbbm{C}^{r\times r},\ \left\lVert
U_{j}\right\rVert_{\mathrm{op}}\leq 1\ \forall j\\},$ (162)

the largest operator norm that $p$ can achieve when $u_{1},\dots,u_{c}$ are
substituted with square matrices of bounded operator norm. More generally, if
$S=(s_{1},\dots,s_{m})$ is a sequence of polynomials we write
$\|S\|=\max(\|s_{1}\|,\dots,\|s_{m}\|)$.

######  Definition 6.6.

A _directed graph_ $G=(V,E)$ will consist of a finite _sequence_ of vertices
$V$, and a finite _sequence_ of edges $E$ from $V\times V$ (so parallel edges
and self-loops are allowed). Such a graph is _undirected_ if $E$ can be
partitioned into pairs of the form $\\{(i,j),(j,i)\\}$. We say $G$ is _$d$
-out-regular_ if for each $i\in V$ we have exactly $d$ elements of the form
$(i,j)$ in $E$; one can analogously define in-regularity, and the two concepts
are the same for undirected graphs. Note that if $G$ is an undirected
$d$-regular graph, then $|E|=d|V|$ (contrary to usual convention, as $E$ is
still composed of directed edges).

######  Definition 6.7.

Given a graph $G=(V,E)$, where $V=(1,2,\dots,m)$, and given a polynomial
sequence $S=(s_{1},\dots,s_{m})$, we define $q_{G}\circ S$ to be the
polynomial sequence131313One would have hoped for the more natural-looking
ordering $s_{i}^{\dagger}s_{j}$, but alas we are forced to follow standard
conventions: the length-$2$ path $(i,j)$ means “first $i$, then $j$”; but,
with operators acting on the left, $s_{i}^{\dagger}s_{j}$ means “first do
$s_{j}$, then do $s_{i}^{\dagger}$”.

$(s_{j}^{\dagger}s_{i})_{(i,j)\in E}.$ (163)

######  Remark 6.8.

If $G$ is undirected, the polynomial $\textnormal{avg}(q_{G}\circ S)$ is self-
adjoint.

######  Fact 6.9.

We always have $\|q_{G}\circ S\|\leq\|S\|^{2}$, and hence $\|S\|\leq
1\implies\|q_{G}\circ S\|\leq 1$.

######  Definition 6.10.

If $G=(V,E)$ is a $d$-out-regular directed graph with $V=(1,2,\dots,c)$, then
the normalized adjacency matrix of $G$ is

$A_{G}\coloneqq\frac{1}{d}\sum_{(i,j)\in
E}\ket{j}\\!\bra{i}=c\cdot\textnormal{avg}(q_{G}\circ\mathcal{U}),\quad\text{where
}\mathcal{U}=(\bra{1},\dots,\bra{c}).$ (164)

######  Fact 6.11.

Let $G=(V,E)$ be an out-regular directed graph with $V=(1,2,\dots,m)$ and let
$\mathcal{W}=(W_{1},\dots W_{m})$ be a sequence of matrices from
$\mathbbm{C}^{r\times r^{\prime}}$.141414We only really care about
$r^{\prime}=r$, but we allow $r^{\prime}\neq r$ for the sake of comparison
with Equation 164, where $r=1$ and $r^{\prime}=c$. Then

$\textnormal{avg}(q_{G}(\mathcal{W}))=\frac{1}{m}\mathcal{W}^{\dagger}(A_{G}\otimes\mathbbm{1}_{r\times
r})\mathcal{W},$ (165)

where we identify $\mathcal{W}$ with $\sum_{j=1}^{m}\ket{j}\otimes W_{j}$, the
$mr\times r^{\prime}$ matrix formed by stacking the $W_{j}$’s into a column.
(For $r^{\prime}=r$, this identity is essentially the formula
$w^{\dagger}Aw=\sum_{ij}w_{i}^{\dagger}A_{ij}w_{j}$, but with entries from the
ring $\mathbbm{C}^{r\times r}$.)

######  Notation 6.12.

We let $\mathrm{K}_{m}$ denote the complete (regular) undirected graph with
self-loops on $m$ vertices, which has $V=(1,2,\dots,m)$ and
$E=((1,1),(1,2),\dots,(1,m),(2,1),\dots,(m,m))$. We may write $\mathrm{K}$ in
place of $\mathrm{K}_{m}$ if the context is clear.

######  Fact 6.13.

If $S=(s_{1},\dots,s_{m})$ is a polynomial sequence,

$\textnormal{avg}(q_{\mathrm{K}_{m}}\circ
S)=\textnormal{avg}(S)^{\dagger}\textnormal{avg}(S),$ (166)

the Hermitian-square of $\textnormal{avg}(S)$. Hence if $\mathcal{U}$ is a
sequence of matrices, $\left\lVert\textnormal{avg}(q_{\mathrm{K}}\circ
S(\mathcal{U}))\right\rVert_{\mathrm{op}}=\left\lVert\textnormal{avg}(S(\mathcal{U}))\right\rVert_{\mathrm{op}}^{2}$.

######  Definition 6.14.

Recall that a regular undirected graph $G$ is said to be a _(2-sided)
$\mu$-expander_ if $\left\lVert
A_{G}-A_{\mathrm{K}}\right\rVert_{\mathrm{op}}\leq\mu$.

######  Fact 6.15.

Since $A_{\mathrm{K}}$ is the projection onto the $1$-dimensional subspace
spanned by $\sum_{j}\ket{j}$, and since $A_{G}$ also fixes this subspace, $G$
being a $\mu$-expander is equivalent to $\left\lVert
A_{G}-(1-\mu)A_{\mathrm{K}}\right\rVert_{\mathrm{op}}\leq\mu$.

The following result is essentially the same as [RV05, Thm. 4.4]:

######  Proposition 6.16.

Let $G$ be a $\mu$-expander on vertex set $V=(1,2,\dots,m)$, let
$S=(s_{1},\dots,s_{m})$ be a polynomial sequence with $\|S\|\leq 1$, and let
$\mathcal{U}=(U_{1},\dots,U_{c})$ be a sequence of matrices in
$\mathbbm{C}^{r\times r}$ with $\left\lVert
U_{j}\right\rVert_{\mathrm{op}}\leq 1$ for all $j$. Then

$\left\lVert\textnormal{avg}(q_{G}\circ
S(\mathcal{U}))\right\rVert_{\mathrm{op}}\leq(1-\mu)\left\lVert\textnormal{avg}(S(\mathcal{U}))\right\rVert_{\mathrm{op}}^{2}+\mu.$
(167)

###### Proof.

Write $\mathcal{W}=S(\mathcal{U})=(W_{1},\dots,W_{m})$, so $\left\lVert
W_{j}\right\rVert_{\mathrm{op}}\leq 1$ for all $j$. Using Fact 6.11 twice, we
derive

$\left\lVert\textnormal{avg}(q_{G}(\mathcal{W}))-(1-\mu)\textnormal{avg}(q_{\mathrm{K}}(\mathcal{W}))\right\rVert_{\mathrm{op}}=\frac{1}{m}\left\lVert\mathcal{W}^{\dagger}(\Delta\otimes\mathbbm{1}_{r\times
r})\mathcal{W}\right\rVert_{\mathrm{op}},\quad\text{where
}\Delta=A_{G}-(1-\mu)A_{K}.$ (168)

We have $\left\lVert\Delta\right\rVert_{\mathrm{op}}\leq\mu$ by Fact 6.15, and
$\left\lVert\mathcal{W}\right\rVert_{\mathrm{op}}\leq\sqrt{\operatorname{{\textstyle\sum}}_{j}\left\lVert
W_{j}\right\rVert_{\mathrm{op}}}\leq\sqrt{m}$. So by submultiplicativity of
operator norm, the right-hand side above is at most $\mu$, and the proof is
complete from Fact 6.13 and the triangle inequality. ∎

Iterating this, and using Fact 6.9 to conclude that $\lVert
q_{G_{t}}\circ\cdots\circ q_{G_{1}}\circ S\rVert\leq 1$ whenever $\lVert
S\rVert\leq 1$, yields:

######  Proposition 6.17.

Let $S=(s_{1},\dots,s_{m})$ be a polynomial sequence with $\|S\|\leq 1$ and
let $\mathcal{U}=(U_{1},\dots,U_{c})$ be a matrix sequence with $\left\lVert
U_{j}\right\rVert_{\mathrm{op}}\leq 1$ for all $j$. Moreover, let
$G_{1},G_{2},\dots,G_{t}$ be a sequence of regular graphs, where
$G_{i}=(V_{i},E_{i})$ is a $\mu_{i}$-expander with $V_{i+1}=E_{i}$ (and
$V_{1}=(1,2,\dots,m)$). Then

$\left\lVert\textnormal{avg}(q_{G_{t}}\circ q_{G_{t-1}}\circ\cdots\circ
q_{G_{1}}\circ S(\mathcal{U}))\right\rVert_{\mathrm{op}}\leq f_{\mu_{t}}\circ
f_{\mu_{t-1}}\circ\cdots\circ
f_{\mu_{1}}(\left\lVert\textnormal{avg}(S(\mathcal{U}))\right\rVert_{\mathrm{op}}),$
(169)

where $f_{\mu}(\lambda)=(1-\mu)\lambda^{2}+\mu$. In particular, if $m=c$,
$S=(u_{1},\dots,u_{c})$, and we write $Q=q_{G_{t}}\circ\cdots\circ q_{G_{1}}$
and $F_{(\mu_{1},\dots,\mu_{t})}=f_{\mu_{t}}\circ\cdots\circ f_{\mu_{1}}$,
then

$\left\lVert\textnormal{avg}(Q\circ\mathcal{U})\right\rVert_{\mathrm{op}}\leq
F_{(\mu_{1},\dots,\mu_{t})}(\left\lVert\textnormal{avg}(\mathcal{U})\right\rVert_{\mathrm{op}}).$
(170)

The work [RV05] also contains calculations very similar to the following
(wherein the special number $.11$ is chosen due to certain explicit expander
constructions):

######  Proposition 6.18.

For $0<\delta,\epsilon\leq 1$, we have $F_{\vec{\mu}}(1-\delta)\leq\epsilon$
for any sequence $\vec{\mu}$ that entrywise satisfies

$(0,\dots,0)\leq\vec{\mu}\leq(\vec{\mu}^{(1)},\vec{\mu}^{(2)}),\qquad\vec{\mu}^{(1)}\coloneqq(\underbrace{.11,\dots,.11}_{\text{$\ell_{1}$
times}}),\qquad\vec{\mu}^{(2)}\coloneqq\tfrac{1}{4}(2^{-2},2^{-4},2^{-8},\dots,2^{-2^{\ell_{2}}}),$
(171)

where $\ell_{1}\geq\log_{2^{.8}}(1/\delta)+3$ (note: $2^{.8}\approx 1.74$) and
$\ell_{2}\geq\log_{2}\log_{2}(1/\epsilon)$.

###### Proof.

Since $f_{\mu}(\lambda)$ is nondecreasing on $[0,1]$ for both $\mu$ and
$\lambda$, it suffices to analyze all upper bounds as if they were equalities.
It is easy to check that $f_{.11}(1-\delta)\leq 1-2^{.8}\delta$ for all
$0\leq\delta\leq.03$, and hence

$\ell\geq\log_{2^{.8}}(1/\delta)-6\quad\implies\quad
f_{.11}^{\circ\ell}(1-\delta)\leq 1-.03/1.75\leq.985.$ (172)

Also, $f_{.11}^{\circ 9}(.985)\leq 1/4$, and hence
$F_{\vec{\mu}^{(1)}}(1-\delta)\leq 1/4$. The proof is now complete by
observing that $F_{\vec{\mu}^{(2)}}(1/4)\leq\frac{1}{2}2^{-2^{-\ell_{2}}}$. ∎

Regarding explicit construction of expander graphs, taking $p=29$ and $509$ in
[Alo21, Thm. 1.2] and adding a self-loop to every vertex yields:

######  Theorem 6.19.

For $(d,\mu)=(32,.45)$ and also $(d,\mu)=(512,.11)$, there is a strongly
explicit algorithm for constructing $n$-vertex, $d$-regular, $\mu$-expander
graphs (for all sufficiently large $n$).

By repeatedly squaring the $32$-regular graphs above, one can also conclude
the following (in which it is possible that $d=d(n)>n$):

######  Corollary 6.20.

For any easy-to-compute $j=j(n)\in\mathbbm{N}$, there is a strongly explicit
($\operatorname{polylog}(n,d)$ time) algorithm for constructing $n$-vertex,
$d$-regular, $\mu$-expander graphs (for all sufficiently large $n$) where, for
$k=2^{j}$, we have $d=32^{k}$ and
$\mu=\mu(n)=.45^{k}\leq\frac{1}{4}2^{-k}=\frac{1}{4}d^{-1/5}$ (the inequality
holding provided $j\geq 4$).

Putting together Corollary 6.20, Proposition 6.18, and Proposition 6.17 yields
the following:

######  Theorem 6.21.

There is a strongly explicit, space-minimal algorithm with the following
behavior on inputs $c$ and $0<\delta,\epsilon<1$ (where we assume
$c=2^{i_{1}}$, $\delta=16^{-i_{2}}$, and $\epsilon=2^{-2^{i_{3}}}$ for some
$i_{1},i_{2},i_{3}\in\mathbbm{N}$ sufficiently large). The algorithm outputs a
sequence $Q$ of $N=O(c/(\delta^{11.25}\epsilon^{10}))$ monomials over symbols
$u_{1},\dots,u_{c}$ and $u_{1}^{\dagger},\dots,u_{c}^{\dagger}$, each of
length $L=8\log_{2}(1/\epsilon)/\delta^{1.25}$, with the following property:

For any sequence $\mathcal{U}=(U_{1},\dots,U_{c})$ of matrices in
$\mathbbm{C}^{r\times r}$ satisfying $\left\lVert
U_{i}\right\rVert_{\mathrm{op}}\leq 1$ for all $i$ and
$\left\lVert\textnormal{avg}(\mathcal{U})\right\rVert_{\mathrm{op}}\leq
1-\delta$, it holds that
$\left\lVert\textnormal{avg}(Q\circ\mathcal{U})\right\rVert_{\mathrm{op}}\leq\epsilon$.

Here “strongly explicit and space-minimal” means that, given a monomial index
$i\in[N]$ and a monomial position index $j\in[L]$, the algorithm runs in
deterministic $\operatorname{polylog}(c/\delta\epsilon)$ time and
$O(\log(c/\delta\epsilon))$ space and outputs the $j$th symbol of the $i$th
monomial in $Q$.

###### Proof.

Given $c,\delta,\epsilon$, the desired $Q$ is $q_{G_{t}}\circ\cdots\circ
q_{G_{1}}\circ(u_{1},\dots,u_{c})$, where $G_{1},\dots,G_{t}$ is a sequence as
in Proposition 6.17, with:

  * •

$\ell_{1}=\log_{2^{.8}}(1/\delta)+3=\frac{5}{4}\log_{2}(1/\delta)+3$,
$\ell_{2}=\log_{2}\log_{2}(1/\epsilon)$, and $t=\ell_{1}+\ell_{2}$;

  * •

$G_{1},\dots,G_{\ell_{1}}$ are $512$-regular $.11$-expanders, with $G_{j}$ on
$512^{j-1}{c}$ vertices, as in Theorem 6.19;

  * •

$G_{\ell_{1}+1},\dots,G_{\ell_{1}+\ell_{2}}$ are as in Corollary 6.20, with
$G_{\ell_{1}+j}$ being a $32^{k}$-regular, $\tfrac{1}{4}2^{-k}$-expander (for
$k=2^{\min(j,4)}$) on $32^{k+32}N_{0}$ vertices (once $j\geq 4$), where
$N_{0}=512^{\ell_{1}}c$ is $|E(G_{\ell_{1}})|$.

The length of $Q$ is

$N=|E(G_{t})|=32^{2^{\ell_{2}+1}+32}N_{0}=2^{160}\cdot