# Pseudorandom Permutations from Random Reversible Circuits

William He∗ Ryan O’Donnell Computer Science Department, Carnegie Mellon
University<EMAIL_ADDRESS>Supported in part by ARO grant
W911NF2110001.

###### Abstract

We study pseudorandomness properties of permutations on $\\{0,1\\}^{n}$
computed by random circuits made from reversible $3$-bit gates (permutations
on $\\{0,1\\}^{3}$). Our main result is that a random circuit of depth
$n\cdot\widetilde{O}(k^{2})$, with each layer consisting of $\approx n/3$
random gates in a fixed nearest-neighbor architecture, yields almost $k$-wise
independent permutations. The main technical component is showing that the
Markov chain on $k$-tuples of $n$-bit strings induced by a single random
$3$-bit nearest-neighbor gate has spectral gap at least
$1/n\cdot\widetilde{O}(k)$. This improves on the original work of Gowers
[Gow96], who showed a gap of $1/\mathrm{poly}(n,k)$ for one random gate (with
non-neighboring inputs); and, on subsequent work [HMMR05, BH08] improving the
gap to $\Omega(1/n^{2}k)$ in the same setting.

From the perspective of cryptography, our result can be seen as a particularly
simple/practical block cipher construction that gives provable statistical
security against attackers with access to $k$ input-output pairs within few
rounds. We also show that the Luby–Rackoff construction of pseudorandom
permutations from pseudorandom functions can be implemented with reversible
circuits. From this, we make progress on the complexity of the Minimum
_Reversible_ Circuit Size Problem (MRCSP), showing that block ciphers of fixed
polynomial size are computationally secure against arbitrary polynomial-time
adversaries, assuming the existence of one-way functions (OWFs).

##  1 Introduction

Motivated by questions in the analysis of practical cryptosystems (block
ciphers), derandomization, and spectral graph theory, we study
pseudorandomness properties of random reversible circuits.111These have even
been studied as toy models for black holes [HP07, Section 2]. That is, we
study the indistinguishability of truly random permutations on $\\{0,1\\}^{n}$
versus permutations computed by small, randomly chosen reversible circuits.

Our main results concern the extent to which small random reversible circuits
compute _almost $k$-wise independent_ permutations. This corresponds to
_statistical security_ against adversaries that get $k$ input-output pairs
from the permutation. We also study _computational security_ , showing that it
can hold (assuming OWFs exist) even for adversaries running in time
significantly exceeding the size of the reversible circuit.

###  1.1 Basic definitions

We start by defining reversible computation, which was initially studied with
a motivation from physics [Lan, Lec63, Ben73, Tof80, FT82], and subsequently
played an important role in the foundations of quantum computing.

######  Definition 1.

A Boolean circuit is called _reversible_ if it has $n$ wires (hence $n$ inputs
and outputs), and each gate operates on some $c\ll n$ wires, computing a
permutation on $\\{0,1\\}^{c}$. We say such a gate is of type222This concept
has many names: Feistel, Toffoli, “width-$(c-1)$”, “standard quantum oracle
for $f$”…The terminology $\mathrm{DES}[c-1]$ refers to the use of such
permutations in the DES/AES block ciphers; we are following [Cle90]’s
notation. $\mathrm{DES}[c-1]$ if (up to ordering the $c$ bits) it is of the
form $(x,b)\mapsto(x,b\oplus f(x))$ for some $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{c-1}\to\\{0,1\\}$. The _size_ of the circuit is the
number of gates, and the _depth_ is the maximum number of gates through which
any wire passes.

We focus on $\mathrm{DES}[2]$ gates, as they are universal for reversible
computation:

######  Theorem 2.

([CG75], cf. [EG83].) Any permutation in $\mathfrak{A}_{\\{0,1\\}^{n}}$ is
computable by a reversible circuit with $\mathrm{DES}[2]$ gates. (Here
$\mathfrak{A}_{N}$ denotes the alternating group of even permutations on $N$
elements, and $\mathfrak{S}_{N}$ is the full permutation group.333The reader
is advised that the technical distinction between
$\mathfrak{A}_{\\{0,1\\}^{n}}$ and $\mathfrak{S}_{\\{0,1\\}^{n}}$ never plays
an important role in this work.)

Of course, by a simple counting argument, almost all even permutations require
reversible circuits of size $\widetilde{\Omega}(2^{n})$

An important focus of attention in cryptography is on having super-efficient
pseudorandom permutations (block ciphers) that are implementable in hardware.
We introduce here some particularly simple kinds of circuits:

######  Definition 3.

A reversible circuit has _(1D) nearest-neighbor gates_ if each gate operates
on $c$  _consecutive_ wires from $[n]$. The circuit is called _( $3$-bit)
brickwork_ if it has the following architecture: There are $\ell$  _layers_ of
gates, each layer having depth $3$ and size (slightly less than) $n$. Within
each layer with probability 1/2 there are $\lfloor n/3\rfloor$ gates on wires
$\\{1,2,3\\}$, $\\{4,5,6\\},\dots$; with probability 1/2 there are
$\lfloor(n-1)/3\rfloor$ gates on wires $\\{2,3,4\\}$, $\\{5,6,7\\},\dots$ (See
Figure 1.)

######  Remark 4.

We emphasize that a $\mathrm{DES}[2]$-brickwork circuit is determined only by
the parameters $\ell$, $n$, the $\mathrm{DES}[2]$-permutations used at each
gate, and the “parity” of the layers.

Figure 1: The first circuit is an example of a circuit with generic 3-bit
gates. The second is an example of a circuit with 1D nearest-neighbor 3-bit
gates. The third is an example of a brickwork circuit with 3 layers.

Brickwork circuits would be very desirable for block ciphers, as they
potentially have small depth and their nearest-neighbor gates are much easier
to implement. These design considerations have motivated substitution-
permutation networks (SPNs) used in practice, such as AES.

We now define a notion of statistical indistinguishability for permutations:

######  Definition 5.

Let $1\leq k\leq N-2$, and let $\mathcal{P}$ be a probability distribution on
$\mathfrak{S}_{N}$. We say that $\mathcal{P}$ is an _$\varepsilon$
-approximate $k$-design_ for $\mathfrak{S}_{N}$444One may check that $k\leq
N-2$ implies that it doesn’t matter if we write $\mathfrak{A}_{N}$ here. if

$\displaystyle\mathinner{\\!\left\lVert\mathop{{\bf
E}\/}_{\mathbf{g}\sim\mathcal{P}}{\left[\mathbf{g}^{\otimes
k}\right]}-\mathop{{\bf
E}\/}_{\mathbf{g}\sim\mathrm{Unif}(\mathfrak{S}_{N})}{\left[\mathbf{g}^{\otimes
k}\right]}\right\rVert}_{\mathrm{op}}\leq\varepsilon.$

Here $g^{\otimes k}$ denotes the $k$-fold Kronecker product of $g$ when viewed
as a permutation matrix.

######  Remark 6.

The above definition is a rather minimal way to say that a
$\mathcal{P}$-random permutation looks random when restricted to its action on
size-$k$ subsets of $[N]$. For applications, one may wish for a stricter
matrix norm than operator norm; e.g., the $1$-norm. As all $N^{k}$-dimensional
norms are equivalent up to factors of $N^{O(k)}$, one can pass to different
norms by targeting designs with $\varepsilon\ll N^{-O(k)}$, which is
$2^{-O(nk)}$ in our setting of $\mathfrak{S}_{\\{0,1\\}^{n}}$.

A slight variant of this definition is popular in the pseudorandomness
literature:

######  Definition 7.

$\mathcal{P}$ is said to be _$\delta$ -approximate $k$-wise independent_ if
for all distinct $x_{1},\dots,x_{k}\in[N]$, the distribution of
$(\bm{g}(x_{1}),\dots,\bm{g}(x_{k}))$ for $\bm{g}\sim\mathcal{P}$ has total
variation distance at most $\delta$ from the uniform distribution on distinct
$k$-tuples from $[N]$.

######  Remark 8.

As there are $N^{k}$ distinct $k$-tuples on $[N]$, the above definition is not
especially strong unless $\delta\ll N^{-k}$. Also, per Remark 6, if
$\mathcal{P}$ is a $\delta N^{-O(k)}$-approximate $k$-design, then it is
$\delta$-approximate $k$-wise independent. Thus the two notions are not very
different in the typical error parameter setting of $N^{-O(k)}=2^{-O(nk)}$.

Approximate $k$-wise independent permutation distributions $\mathcal{P}$ have
many applications outside of cryptography; derandomization, for example
[MOP20]. In such applications, another important parameter is the number of
truly random “seed” bits needed to generate a draw from $\mathcal{P}$. By
using techniques such as derandomized squaring, one can generally reduce the
seed length to $O(nk)$ for any construction; see [KNR09]. This is true for the
results in our paper, and we don’t discuss this angle further. We are
generally focused on the circuit complexity of our permutations.

###  1.2 Our results on $k$-wise independence

Our main work is to demonstrate that random reversible circuits with not too
many gates are $\varepsilon$-approximate $k$-designs. Perhaps our main result
is the following, which shows that with the very simple/practical architecture
of $\mathrm{DES}[2]$-brickwork circuits, one can achieve good pseudorandomness
even after just $O(n)$ random layers. Note that $\Omega(n)$ layers is
obviously minimal, as otherwise the $1$st and $n$th bits in the circuit do not
interact.

######  Theorem 9.

For $1\leq k\leq 2^{n}-2$, fix the architecture of $n$-bit
$\mathrm{DES}[2]$-brickwork reversible circuits of depth
$n\cdot\widetilde{O}(k^{2})$ (and hence size
$n^{2}\cdot\widetilde{O}(k^{2})$). Then if the $\mathrm{DES}[2]$-gates are
chosen uniformly at random, the resulting permutations on $\\{0,1\\}^{n}$ are
$2^{-O(nk)}$-approximate $k$-wise independent. More generally, they are
$\varepsilon$-approximate $k$-wise independent for depth
$(nk+\log(1/\varepsilon))\cdot\widetilde{O}(k)$.

We are not aware of any such prior work on brickwork or nearest-neighbor gates
for implementing permutations, although this has been studied in the quantum
setting of random unitary circuits. The best prior result was the following
theorem of Brodsky and Hoory for general (non-nearest-neighbor) reversible
architecture:

######  Theorem 10.

([BH08].) Consider the permutation on $\\{0,1\\}^{n}$ computed by a reversible
circuit of $O(n^{3}k^{2})$ randomly chosen $\mathrm{DES}[2]$-gates (meaning in
particular that each gate’s $3$ fan-in wires are randomly chosen). This is
$2^{-O(nk)}$-approximate $k$-wise independent. More generally, such circuits
of size $O(n^{2}k)\cdot(nk+\log(1/\varepsilon))$ suffices for
$\varepsilon$-approximate $k$-wise independence.

There is a simple reduction from general gates to nearest-neighbor gates that
incurs factor-$\Omega(n)$ size blowup. Plugging this into Theorem 10 would
yield $2^{-O(nk)}$-approximate $k$-wise independent permutations formed from
nearest-neighbor reversible circuits of size $O(n^{4}k^{2})$. Besides being
non-brickwork, this is worse than our Theorem 9 by a factor of about $n^{2}$.
We should note that Brodsky and Hoory also prove the following:

######  Theorem 11.

([BH08].) If $k\leq 2^{n/50}$, then Theorem 10 also holds for random
reversible circuits of size $\widetilde{O}(n^{2}k^{2}\log(1/\varepsilon))$.

The improved dependence on $n$ in this theorem, namely $\widetilde{O}(n^{2})$,
is good, but one should caution that the dependence on $\log(1/\varepsilon)$
is _multiplicative_. Thus except in the rather weak case when $\varepsilon\gg
2^{-nk}$, this term introduces a factor of at least $nk$ back into the bound,
making it worse than Theorem 10.

All of the difficulty in our main result Theorem 9 comes from analyzing the
_spectral gap_ of the natural random walk on $k$-tuples of strings arising
from picking _one_ random nearest-neighbor gate. We prove:

######  Theorem 12.

Let $\mathcal{P}$ be the distribution on $\mathfrak{S}_{\\{0,1\\}^{n}}$ given
by choosing one random nearest-neighbor $\mathrm{DES}[2]$ gate. Then
$\mathcal{P}$ is a $(1-\delta)$-approximate $k$-design for $\delta\geq
1/(n\cdot\widetilde{O}(k))$.

Given this result, Theorem 9 follows almost directly by using the
detectability lemma from Hamiltonian complexity theory [AALV09], as in
analogous results for unitary designs due to [BHH16]. The intermediate step is
again proving the one-step spectral gap lower bound.

######  Theorem 13.

Let $\mathcal{P}$ be the distribution on $\mathfrak{S}_{\\{0,1\\}^{n}}$ given
by choosing one layer of brickwork gates. Then $\mathcal{P}$ is a
$(1-\eta)$-approximate $k$-design for $\eta\geq 1/\widetilde{O}(k)$.

We also prove an analogous result to Theorem 12 in the case of non-nearest-
neighbor gates:

######  Theorem 14.

Let $\mathcal{P}$ be the distribution on $\mathfrak{S}_{\\{0,1\\}^{n}}$ given
by choosing one random $\mathrm{DES}[2]$ gate. Then $\mathcal{P}$ is a
$(1-\eta)$-approximate $k$-design for $\eta\geq\Omega(1/(nk\cdot\log k))$.

Although it may look like this result is conceptually dominated by Theorem 12,
we include it as it has improved $\log k$ factors, and its proof reveals some
of the ideas we use in our proof of Theorem 12.

###  1.3 Techniques and comparison with previous work

Prior work in this area also proceeded by bounding the spectral gap of the
random walk on $k$-tuples induced by a single random $\mathrm{DES}[2]$ gate.
The first such result was due to Gowers [Gow96], who established a version of
our Theorem 14 with spectral gap $1/\mathrm{poly}(n,k)$. This was later
improved by Hoory, Magen, Myers, and Rackoff [HMMR05] to
$1/\widetilde{O}(n^{2}k^{2})$, and by Brodsky and Hoory [BH08] to
$1/O(n^{2}k)$. A result with gap $\eta$ immediately translates into
$\varepsilon$-approximate $k$-wise independence of random reversible circuits
with $O(1/\eta)\cdot(nk+\log(1/\varepsilon))$ gates; e.g., the Brodsky–Hoory
gap immediately gives their Theorem 10.

These earlier works bounded the spectral gap using the canonical paths method
([Gow96, HMMR05]) or multicommodity flows and the comparison method ([BH08]).
We depart from these methods and use techniques from the physics literature
concerned with the extent to which random _quantum_ circuits are _unitary_
$k$-designs. Specifically, for Theorem 14 we use the induction-on-$n$
technique developed in [HHJ21], and for our main Theorem 12 we employ the more
sophisticated Nachtergaele method [Nac96] as in the work of Brandão, Harrow,
and Horodecki [BHH16]. These analyses use Fourier and spectral graph theory
methods. In both cases, the inductive technique only begins to work for
$n\geq\Theta(\log k)$, and for smaller $n$ we need to base our argument on
[BH08]; in the case of nearest-neighbor gates, this requires a further
comparison-method based argument.

One can also interpret our result as the construction of a Cayley graph on
$\mathfrak{A}_{2^{n}}$ with spectral gap $\Omega{\left(1/n2^{n}\right)}$ and
degree $O(n)$. Previous work on this by Kassabov [Kas07] constructed constant-
degree expanders out of Cayley graphs on $\mathfrak{A}_{2^{n}}$, but it is not
clear if this random walk can be implemented by short circuits. Especially for
the cryptographic applications of this work, it is important that our random
walks have low circuit complexity.

###  1.4 Cryptographic results

Besides applications to derandomization, a lot of the motivation for studying
$\varepsilon$-approximate $k$-wise independent permutation distributions
$\mathcal{P}$ has come from cryptography. (See, e.g., recent analysis of the
security properties of SPNs due to Liu, Pelecanos, Tessaro, and Vaikuntanathan
[LTV21, LPTV23].) By definition, such distributions are statistically secure
(up to advantage $\varepsilon$) against an adversary that gets access to any
$k$ input-output pairs, chosen nonadaptively. We also note that Maurer and
Pietrzak [MP04] have shown that this can easily be upgraded to security
against _adaptively_ queries by composing two draws from the pseudorandom
permutation (the second inverted). The focus in cryptography is on
distributions $\mathcal{P}$ computable by size-$S$ circuits, $S$ a fixed
polynomial in $n$, which are _computationally_ indistinguishable from random.
By this it is meant that an adversary running in time $T$ (possibly much
larger than $S$), having black-box query access to the permutation, cannot
distinguish the pseudorandom permutation from a truly random one except with
negligible advantage.

In cryptography, significant attention is paid to the designing simple and
efficient block ciphers, and this motivates the question of whether reversible
circuits of the type studied in this paper could be cryptographically secure
pseudorandom permutations. This question was an original motivation for
Gowers’s work on random reversible circuits [Gow96]. Indeed, Gowers
additionally asked (cf. [Gow]) if the following general problem was hard:
Suppose one is given _all_ $(2^{n})$ input-output pairs (the “truth table”) of
a permutation on $\\{0,1\\}^{n}$. Is it computationally hard to determine if
these pairs are consistent with some reversible circuit (with
$\mathrm{DES}[2]$ gates) of size at most $S=n^{5}$ (say)? This is precisely
the permutation analogue of the Minimum Circuit Size Problem (MCSP) (see
[KC00]), and we refer to it as the _Minimum Reversible Circuit Size Problem
(MRCSP)_.

Towards resolving the complexity of MRCSP, we establish it is hard (under a
minimal cryptographic assumption) if the adversary can see any polynomial
number of input-output pairs:

######  Theorem 15.

Fix any constant $d\geq 3$. If one-way functions exist, then there is no
deterministic $\mathrm{poly}(n)$-time algorithm that — given black-box access
to a permutation $\pi$ on $\\{0,1\\}^{n}$ — decides whether $\pi$ is
computable by a reversible circuit of size at most $n^{d}$. (If
subexponentially secure OWFs exist, then we can also rule out subexponential-
time algorithms.)

We prove Theorem 15 as Corollary 76 in Section 7 by following the technique of
Kabanets and Cai [KC00], who showed hardness of MCSP under OWFs. The key new
thing we need to prove is a “reversibilized” version of the Luby–Rackoff
[LR88] construction of (cryptographic) pseudorandom permutations from
pseudorandom function generators. This was done much earlier by Cleve [Cle90]
under the assumption that the pseudorandom function generator is computable in
$\mathrm{NC}^{1}$. We extend this to the case of any any poly-size circuit.

##  2 Preliminaries

###  2.1 The Main Characters: Some Linear Operators

We switch from $\\{0,1\\}$ notation to $\\{\pm 1\\}$ notation to facilitate
later Fourier analysis. We will regard elements of $\\{\pm 1\\}^{nk}$ as
tuples $(X^{1},\dots,X^{k})$, where each $X^{i}\in\\{\pm 1\\}^{n}$. If
$X^{i}\in\\{\pm 1\\}^{n}$, let $X^{i}_{S}$ denote the vector $X^{i}$
restricted to indices in $S$, so that if $S=\\{a_{1},\dots,a_{|S|}\\}$ with
$a_{1}<\dots<a_{|S|}$ then $X^{i}_{S}=(X^{i}_{a_{1}},\dots,X^{i}_{a_{|S|}})$.
For two vectors $x,y\in\\{\pm 1\\}^{n}$, define
$\Delta(x,y)=\\{a\in[n]\mathrel{\mathop{\mathchar 58\relax}}x_{a}\neq
y_{a}\\}$. Unless otherwise specified, $\log$ is $\log_{2}$. For positive
integers $a\leq b$ denote $[a,b]=\\{a,a+1,\cdots,b-1,b\\}$ and let
$[a]=[1,a]$. Let $\mathbf{1}$ be the all 1s vector, with length determined by
context. When $L$ is a self-adjoint operator let $\lambda_{2}(L)$ be its
second-smallest distinct eigenvalue. If
$g\in\mathfrak{S}_{\\{0,1\\}^{\gamma}}$ is a permutation and $S\subseteq[n]$
has $|S|=\gamma$ then define $g^{S}\in\mathfrak{S}_{\\{0,1\\}^{n}}$ by setting
$(g^{S}x)_{S}=g(x_{S})$, where coordinates are interpreted to be in
lexicographic order, and $(g^{S}x)_{[n]\setminus S}=x_{[n]\setminus S}$.

When $U$ is a set, we let $\mathbb{R}^{\mathcal{U}}$ denote the vector space
of all functions $\mathcal{U}\to\mathbb{R}$. We equip this space with the
inner product $\left\langle\cdot,\cdot\right\rangle$ given by

$\displaystyle\left\langle f,g\right\rangle=$ $\displaystyle\mathop{{\bf
E}\/}_{\mathbf{x}\in\mathcal{U}}{\left[f(\mathbf{x})g(\mathbf{x})\right]}$

for $f,g\mathrel{\mathop{\mathchar 58\relax}}\mathcal{U}\to\mathbb{R}$. Also
define the norm by $\mathinner{\\!\left\lVert
f\right\rVert}_{2}=\sqrt{\left\langle f,f\right\rangle}$.

######  Definition 16.

Let $n,k$ be positive integers and let $S\subseteq[n]$.

  * •

For every $X\in\\{\pm 1\\}^{nk}$ define the following distribution
$\mathcal{D}_{X}^{n,S,k}$ on $\\{\pm 1\\}^{nk}$. To sample
$\mathbf{Y}\sim\mathcal{D}_{X}^{n,S,k}$, let
$\bm{\sigma}\in\mathfrak{A}_{\\{\pm 1\\}^{|S|}}$ be drawn uniformly at random
and set $\mathbf{Y}^{i}=\bm{\sigma}^{S}X^{i}$ for all $i\in[k]$. Define the
operator $R_{n,S,k}$ on $\mathbb{R}^{\\{\pm 1\\}^{nk}}$ by defining for
$f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{nk}\to\mathbb{R}$ the new
function $R_{n,m,k}f$ by

$\displaystyle(R_{n,S,k}f)(X)=$ $\displaystyle\operatorname{{\bf
E}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{n,S,k}}{\left[f(\mathbf{Y})\right]}.$

  * •

For an integer $m\leq n$ define $\mathcal{D}_{X}^{n,m,k}$ as follows. To
sample $\mathbf{Y}$ from $\mathcal{D}_{X}^{n,m,k}$ sample
$\mathbf{S}\in\binom{[n]}{m}$ uniformly at random and drawn
$\mathbf{Y}\sim\mathcal{D}_{X}^{n,\mathbf{S},k}$. Define the operator
$R_{n,m,k}$ on $\mathbb{R}^{\\{\pm 1\\}^{nk}}$ by defining for
$f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{nk}\to\mathbb{R}$ the new
function $R_{n,m,k}f$ by

$\displaystyle(R_{n,m,k}f)(X)=$ $\displaystyle\operatorname{{\bf
E}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{n,m,k}}{\left[f(\mathbf{Y})\right]}.$

  * •

For a set $I\subseteq[n-\gamma]$ and a constant $\gamma$ define
$\mathcal{D}_{X}^{n,I,k,\gamma\text{-NN}}$ as follows. To sample $\mathbf{Y}$
from $\mathcal{D}_{X}^{n,I,k,\gamma\text{-NN}}$ sample $\mathbf{a}\in I$
uniformly at random and drawn
$\mathbf{Y}\sim\mathcal{D}_{X}^{n,\\{\mathbf{a},\dots,\mathbf{a}+\gamma-1\\},k}$.
Define the operator $R^{\gamma\text{-NN}}_{n,I,k}$ on $\mathbb{R}^{\\{\pm
1\\}^{nk}}$ by defining for $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm
1\\}^{nk}\to\mathbb{R}$ the new function $R^{\gamma\text{-NN}}_{n,I,k}f$ by

$\displaystyle(R^{\gamma\text{-NN}}_{n,I,k}f)(X)=$
$\displaystyle\operatorname{{\bf
E}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{n,I,k,\gamma\text{-NN}}}{\left[f(\mathbf{Y})\right]}.$

  * •

Define the distribution $\mathcal{D}_{X}^{n,k,\mathrm{brickwork}}$ as follows.
To sample $\mathbf{Y}$ from $\mathcal{D}_{X}^{n,k,\mathrm{brickwork}}$ with
probability 1/2 sample $\mathbf{Y}$ by sampling ${\left\lfloor
n/3\right\rfloor}$ random permutations
$\bm{\sigma}_{1},\dots,\bm{\sigma}_{{\left\lfloor n/3\right\rfloor}}$ from
$\mathfrak{A}_{\\{\pm 1\\}^{3}}$ and setting
$\mathbf{Y}^{i}=\bm{\sigma}_{{\left\lfloor
n/3\right\rfloor}}^{\\{n{\left\lfloor n/3\right\rfloor},n{\left\lfloor
n/3\right\rfloor}+1,n{\left\lfloor
n/3\right\rfloor}+2\\}}\cdots\bm{\sigma}_{1}^{\\{1,2,3\\}}X^{i}$ for all
$i\in[k]$. Otherwise, draw
$\bm{\sigma}_{1},\dots,\bm{\sigma}_{{\left\lfloor(n-1)/3\right\rfloor}}\in\mathfrak{A}_{\\{\pm
1\\}^{3}}$ and set
$\mathbf{Y}^{i}=\bm{\sigma}_{{\left\lfloor(n-1)/3\right\rfloor}}^{\\{n{\left\lfloor(n-1)/3\right\rfloor}+1,n{\left\lfloor(n-1)/3\right\rfloor}+2,n{\left\lfloor(n-1)/3\right\rfloor}+3\\}}\cdots\bm{\sigma}_{1}^{\\{2,3,4\\}}X^{i}$
for all $i\in[k]$. Define the operator $R^{\mathrm{brickwork}}_{n,k}$ on
$\mathbb{R}^{\\{\pm 1\\}^{nk}}$ by defining for $f\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{nk}\to\mathbb{R}$ the new function
$R^{\mathrm{brickwork}}_{n,k}f$ by

$\displaystyle(R^{\mathrm{brickwork}}_{n,k}f)(X)=$
$\displaystyle\operatorname{{\bf
E}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{n,k,\mathrm{brickwork}}}{\left[f(\mathbf{Y})\right]}.$

That is, the operator $R_{n,m,k}$ is essentially the transition matrix of the
random walk on $\\{\pm 1\\}^{nk}$ given by randomizing a random subset of $m$
bits. Similarly, the operator $R^{\gamma\text{-NN}}_{n,I,k}$ is essentially
the transition matrix of the random walk on $\\{\pm 1\\}^{nk}$ given by
randomizing a contiguous subset of $\gamma$ bits. The operator
$R^{\mathrm{brickwork}}_{n,k}$ is the transition matrix of the random walk on
$\\{\pm 1\\}^{nk}$ given by randomizing in the brickwork model.

######  Fact 17.

All $R_{n,S,k}$ are projectors. For any $n$, $m\leq n$, and $k$, we have

$\displaystyle\mathinner{\\!\left\lVert
R_{n,m,k}-R_{n,n,k}\right\rVert}_{\mathrm{op}}\geq 0.$

###### Proof.

All $R_{n,S,k}$ are PSD because they are projectors. $R_{n,n,k}=R_{n,[n],k}$
is a projector to a subspace of vectors, all of which are eigenvectors of
$R_{n,m,k}$ with eigenvalue 1. ∎

######  Fact 18.

For any $n,S,k$ we have that $R_{n,S,k}$ is self-adjoint.

###### Proof.

As a matrix, $R_{n,S,k}$ is a stochastic symmetric matrix, which can be seen
by evaluating transition probabilities. ∎

######  Fact 19.

For any $S\subseteq[n]$ we have $R_{n,S,k}\mathbf{1}=\mathbf{1}$ ($\mathbf{1}$
is the all 1s vector). Consequently, $R_{n,m,k}\mathbf{1}=\mathbf{1}$ and
$R^{\gamma\text{-NN}}_{n,I,k}\mathbf{1}=\mathbf{1}$ for all $m$, $\gamma$, and
intervals $I$.

###### Proof.

As a matrix, $R_{n,S,k}$ is doubly stochastic, as per 18. ∎

In some contexts it is easier to work with the Laplacians of these operators:

######  Definition 20.

For any operator $R$ on a vector space $V$ let $L(R)$ denote its Laplacian
$\mathrm{Id}_{V}-R$. In the case where $R=R_{n,m,k}$ for integers $n,m,k$
define $L_{n,m,k}=L(R_{n,m,k})$. In the case where
$R=R_{n,I,k}^{\gamma\text{-NN}}$ define
$L_{n,I,k}^{\gamma\text{-NN}}=L(R_{n,I,k}^{\gamma\text{-NN}})$. In the case
where $R=R_{n,k}^{\text{brickwork}}$ define
$L_{n,k}^{\text{brickwork}}=L(R_{n,I,k}^{\text{brickwork}})$.

###  2.2 Fourier Analysis of Boolean Functions

######  Definition 21.

Let $S_{1},\dots,S_{k}\subseteq[n]$. Then define the function
$\chi_{S_{1},\dots,S_{k}}$ by defining for $X\in\\{\pm 1\\}^{nk}$,

$\displaystyle\chi_{S_{1},\dots,S_{k}}(X)=$
$\displaystyle\prod_{i\in[k]}\prod_{a\in S_{i}}X^{i}_{a}.$

######  Fact 22 ([O’D14]).

The functions $\chi_{S_{1},\dots,S_{k}}$ for $S_{1},\dots,S_{k}\subseteq[n]$
form an orthonormal basis of $\mathbb{R}^{\\{\pm 1\\}^{nk}}$.

##  3 Spectral Gaps

###  3.1 Fully Random Gates

Throughout this section let $n$ be a fixed positive integer. In this section
we prove Theorem 14 by building on the previously-mentioned following result
of Brodsky and Hoory:

######  Theorem 23 ([BH08], Theorem 2).

Given $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{nk}\to\mathbb{R}$,
we have for any $m\leq n$ that

$\displaystyle{\left|\left\langle
f,(R_{m,3,k}-R_{m,m,k})f\right\rangle\right|}\leq
1-\Omega{\left(\frac{1}{m^{2}k}\right)}.$

Our main contribution is a finer analysis in the case when $k$ is small
relative to $m$, which results in the following theorem.

######  Theorem 24.

Assume that $m\geq 100$ and $k\leq 2^{m/3}$. Given
$f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$, we have

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}\leq{\left(\frac{1}{m}+\frac{k^{2}}{2^{m/3}}\right)}\left\langle
f,f\right\rangle.$

Theorem 24 is proven as Theorem 45 in Section 5.

The following lemma allows us to combine Theorem 24 with the previously-known
Theorem 23 to bring the quadratic dependence on the number of wires ($n$) to
linear.

######  Lemma 25 ([OSP23], Lemma 3.2).

Fix a positive integer $n_{0}\geq 4$. For each $k$ and $m_{1}\geq m_{2}$ let
$\tau_{m_{1},m_{2},k}$ be some real number such that

$\displaystyle L_{m_{1},m_{2},k}\geq\tau_{m_{1},m_{2},k}L_{m_{1},m_{1},k}.$

Then for any sequence $n_{0}=m_{0}\leq m_{1}\leq\dots\leq m_{t-1}\leq m_{t}=n$
we have

$\displaystyle
L_{n,n_{0},k}\geq{\left(\prod_{i\in[t-1]}\tau_{m,k}\right)}L_{m_{i},m_{i+1},k}.$

Together, Theorem 23, Theorem 24, and Lemma 25 yield the following initial
spectral gap.

######  Corollary 26.

For any $n$ and $k\leq 2^{n/3}$, we have

$\displaystyle L_{n,3,k}\geq\Omega{\left(\frac{1}{nk\cdot\log
k}\right)}L_{n,n,k}.$

###### Proof.

Theorem 24 shows that for all $m\geq 4\log(k)$ we have $\tau_{m,k}\geq
1-\frac{1}{m}-\frac{1}{2^{m/3}}$. By Lemma 25 applied with $n_{0}=4\log k$, we
have

$\displaystyle L_{n,4\log k,k}\geq\prod_{m=4\log
k}^{n}{\left(1-\frac{1}{m}-\frac{1}{2^{m/3}}\right)}L_{n,n,k}\geq\frac{\log
k}{n}L_{n,n,k}.$

Finally, Theorem 23 shows that

$\displaystyle L_{4\log
k,3,k}\geq\Omega{\left(\frac{1}{k\cdot\log^{2}(k)}\right)}L_{4\log k,4\log
k,k}$

Combining these two inequalities using Lemma 25 produces the result. ∎

We leverage the initial spectral gap from Corollary 26 to produce our designs
by sequentially composing many copies of this pseudorandom permutation. This
is akin to showing that the second largest eigenvalue of the square of a graph
is quadratically smaller than that of the original graph.

######  Corollary 27.

Let $\bm{\sigma}_{1},\dots,\bm{\sigma}_{t}$ be drawn by drawing a random set
from $\binom{[n]}{3}$ and setting each $\bm{\sigma}_{i}$ to be the permutation
computed by a random 3-bit gate on the 3 wires corresponding to the random set
drawn. Let $\bm{\pi}=\bm{\sigma}_{t}{\dots}\bm{\sigma}_{1}$, and say that
$\bm{\pi}$ was drawn from the distribution $\mathrm{Ckt}_{t}$. Then

$\displaystyle\mathinner{\\!\left\lVert\mathop{{\bf
E}\/}_{\bm{\pi}\sim\mathrm{Ckt}_{t}}{\left[\rho^{k}(\bm{\pi})\right]}-\mathop{{\bf
E}\/}_{\pi\sim\mathrm{Unif}(\mathfrak{A}_{N})}{\left[\rho^{k}(\bm{\pi})\right]}\right\rVert}_{\mathrm{op}}\leq{\left(1-\frac{1}{nk\cdot\log
k}\right)}^{\Omega(t)}$

###### Proof.

For any $g\in\mathfrak{A}_{N}$, we have $\rho^{k}(g)\mathop{{\bf
E}\/}_{\pi\sim\mathrm{Unif}(\mathfrak{A}_{N})}{\left[\rho^{k}(\bm{\pi})\right]}=\mathop{{\bf
E}\/}_{\pi\sim\mathrm{Unif}(\mathfrak{A}_{N})}{\left[\rho^{k}(\bm{\pi})\right]}$.
Note also that $\mathop{{\bf
E}\/}_{\pi\sim\mathrm{Unif}(\mathfrak{A}_{N})}{\left[\rho^{k}(\bm{\pi})\right]}=R_{m,m,k}$.
Therefore,

$\displaystyle{\left(R_{m,3,k}-R_{m,m,k}\right)}^{t}=R_{m,3,k}^{t}-R_{m,m,k}^{t}=R_{m,3,k}^{t}-R_{m,m,k}.$

Using this, we find that

$\displaystyle\mathinner{\\!\left\lVert\mathop{{\bf
E}\/}_{\bm{\pi}\sim\mathrm{Ckt}_{t}}{\left[\rho^{k}(\bm{\pi})\right]}-\mathop{{\bf
E}\/}_{\pi\sim\mathrm{Unif}(\mathfrak{A}_{N})}{\left[\rho^{k}(\bm{\pi})\right]}\right\rVert}_{\mathrm{op}}=\mathinner{\\!\left\lVert
R_{m,3,k}^{t}-R_{m,m,k}\right\rVert}_{\mathrm{op}}$ $\displaystyle=$
$\displaystyle\mathinner{\\!\left\lVert{\left(R_{m,3,k}-R_{m,m,k}\right)}^{t}\right\rVert}_{\mathrm{op}}\leq\mathinner{\\!\left\lVert
R_{m,3,k}-R_{m,m,k}\right\rVert}_{\mathrm{op}}^{t}\leq{\left(1-\Omega{\left(\frac{1}{nk\cdot\log
k}\right)}\right)}^{t}$ $\displaystyle\leq$
$\displaystyle{\left(1-\frac{1}{nk\cdot\log k}\right)}^{\Omega(t)}.$

Here we used the bound proved in Corollary 26. ∎

Theorem 14 follows directly from Corollary 27 (with $t=\Theta(nk\cdot\log k)$)
and Section 3.3.

###  3.2 Nearest-Neighbor Random Gates

####  3.2.1 Reduction to the Large $k$ Case

One step in a random reversible circuit with 1D-nearest-neighbor gates is
described by the operator $R_{n,[n-2],k}^{3\text{-NN}}$. Note that we can
write

$\displaystyle R_{n,[n-2],k}^{3\text{-NN}}=$ $\displaystyle\mathop{{\bf
E}\/}_{\mathbf{a}\in[n-2]}{\left[R_{n,\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\},k}\right]}.$

Because the local terms $R_{n,\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\},k}$
are projectors, to analyze such an operator we can use the following theorem
of Nachtergaele.

######  Theorem 28 ([Nac96], Theorem 3).

Let $\\{h_{a,a+1,a+2}\\}_{a\in[n-2]}$ be projectors acting on
$(\mathbb{R}^{2})^{\otimes d}$ such that each $h_{\\{a,a+1,a+2\\}}$ only acts
on the $a,a+1,a+2$th tensor factors. For $I=[a,b]\subseteq[n]$ define the
subspace

$\displaystyle\mathcal{G}_{I}=$
$\displaystyle{\left\\{f\in(\mathbb{R}^{2})^{\otimes
d}\mathrel{\mathop{\mathchar
58\relax}}\sum_{a^{\prime}\in[a,b-2]}h_{a^{\prime},a^{\prime}+1,a^{\prime}+2}f=0\right\\}}.$

Let $G_{I}$ be the projector to $\mathcal{G}_{I}$.

Now suppose there exists $\ell$ and $n_{\ell}$ and
$\varepsilon_{\ell}\leq\frac{1}{\sqrt{\ell}}$ such that for all $n_{\ell}\leq
m\leq n$,

$\displaystyle\mathinner{\\!\left\lVert
G_{[m-\ell-1,m]}{\left(G_{[m-1]}-G_{[m]}\right)}\right\rVert}_{\mathrm{op}}\leq\varepsilon_{\ell}.$

Then

$\displaystyle\lambda_{2}{\left(\sum_{a\in[n-2]}h_{\\{{a},{a}+1,{a}+2\\}}\right)}$
$\displaystyle\geq\frac{{\left(1-\varepsilon_{\ell}\sqrt{\ell}\right)}^{2}}{\ell-2}\lambda_{2}{\left(\sum_{a\in[\ell]}h_{\\{{a},{a}+1,{a}+2\\}}\right)}.$

Recall $\lambda_{2}(h)$ denotes the second-smallest distinct eigenvalue of the
operator $h$.

######  Theorem 29.

Fix any $m\geq 100$ and $k\leq 2^{m}-2$ and set $\ell=10\log k$. Then we have

$\displaystyle\mathinner{\\!\left\lVert
R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}\right\rVert}_{\mathrm{op}}\leq\frac{1}{\ell}.$

Theorem 29 is established in Section 6 as Theorem 61.

######  Corollary 30.

We have for $k\geq 3$ that

$\displaystyle\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN}}\right)}\geq\frac{1}{2n}\lambda_{2}{\left(L_{10\log
k+2,[10\log k-2],k}^{3\text{-NN}}\right)}$

###### Proof.

Setting $h_{a,a+1,a+2}=\mathrm{Id}-R_{n,\\{a,a+1,a+2\\},k}$ for each
$a\in[n]$, we see that the projections $G$ (as in the statement of Theorem 28)
are given by $G_{[a]}=R_{n,[\min\\{n,a+2\\}],k}$ for any $a\in[n]$. To see
this, note first that $R_{n,[\min\\{n,a+2\\}],k}$ is indeed a projection. Now
let $f$ be such that $R_{n,[\min\\{n,a+2\\}],k}f=f$. For every
$\sigma\in\mathfrak{S}_{\\{\pm 1\\}^{n}}$ define $f^{\sigma}$ by
$f^{\sigma}(X)=f(\sigma X)$ for all $X\in\\{\pm 1\\}^{nk}$. Then by invariance
of $R_{n,[\min\\{n,a+2\\}],k}$ under a permutation applied to bits in
$[\min\\{n,a+2\\}]$ we have

$\displaystyle
f^{\sigma}=R_{n,[\min\\{n,a+2\\}],k}f^{\sigma}=R_{n,[\min\\{n,a+2\\}],k}f=f.$

for any $\sigma\in\mathfrak{S}_{\\{\pm 1\\}^{[\min\\{n,a+2\\}]}}$. The
converse of this holds as well by a similar argument. Therefore,
$f^{\sigma^{\\{a^{\prime},a^{\prime}+1,a^{\prime}+2\\}}}=f$ for any
$\sigma\in\mathfrak{S}_{\\{0,1\\}^{8}}$ for $a^{\prime}\leq a$, proving that
such an $f$ is truly in the ground space of
$R_{n,\\{a^{\prime},a^{\prime}+1,a^{\prime}+2\\},k}$ for any $a^{\prime}\leq
a$. The converse of this holds as well, because the permutations of the form
$\sigma^{\\{a^{\prime},a^{\prime}+1,a^{\prime}+2\\}}$ with $a^{\prime}\leq a$
generate the group of permutations of the form $\rho^{\\{a,b,c\\}}$ for
$\\{a,b,c\\}\in\binom{[\min\\{n,a+2\\}]}{3}$. Such an argument also proves the
converse, so the $R$ operators are serve as the projections from Theorem 28.

Therefore, by Theorem 29 we have that the hypotheses of Theorem 28 are
satisfied with $\ell=10\log k$ and $\varepsilon_{\ell}=\frac{1}{\ell}$. That
is, for any $m\leq n$ we have

$\displaystyle\mathinner{\\!\left\lVert
G_{[m-\ell-1,m]}{\left(G_{[m-1]}-G_{[m]}\right)}\right\rVert}_{\mathrm{op}}=\mathinner{\\!\left\lVert
R_{n,[m-\ell-1,m],k}{\left(R_{n,[m-1],k}-R_{n,[m],k}\right)}\right\rVert}_{\mathrm{op}}$
$\displaystyle=$
$\displaystyle\mathinner{\\!\left\lVert{\left(R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}\right)}\otimes\mathrm{Id}_{[m+1,n]}\right\rVert}_{\mathrm{op}}\leq\frac{1}{\ell}.$

Therefore the conclusion of Theorem 28 is that

$\displaystyle\lambda_{2}{\left((n-2)L_{n,[n-2],k}^{3\text{-NN}}\right)}\geq\frac{{\left(1-\frac{1}{\sqrt{\ell}}\right)}^{2}}{\ell-2}\lambda_{2}{\left(\ell
L_{\ell+2,[\ell-2],k}^{3\text{-NN}}\right)}\geq\frac{1}{2}\lambda_{2}{\left(L_{\ell+2,[\ell-2],k}^{3\text{-NN}}\right)}.$

Recalling our setting of $\ell$ completes the proof. ∎

####  3.2.2 Comparison Method for the Large $k$ Case

We can use the spectral gap proved in Theorem 23 for the random walk induced
by completely random 3-bit gates to show a spectral gap for the random walk
induced by random 3-bit gates, where the three bits on which the gate acts on
are $a,a+1,a+2$ for some $a\in[n]$. Our proof is a simple application of the
comparison method applied to random walks on multigraphs.

We take the following definition of (multi)graphs. A graph is a pair of sets
$(V,E)$ such that there is a partition $E=\bigcup_{(x,y)\in V^{2}}E_{x,y}$. If
$e\in E_{x,y}$ then we say that $e$ connects the vertex $x$ to the vertex $y$,
and we define $u(e)=x$ and $v(e)=y$. The degree $\deg(x)$ of a vertex $x\in V$
is the number of edges originating at $e$, or $\sum_{y\in V}|E_{x,y}|$. We say
that a graph is regular if $\deg(x)=\deg(y)$ for all $x,y\in V$.

The random walk on a graph $(V,E)$ beginning at a vertex $x\in V$ consists of
the Markov chain $\\{\bm{x}_{i}\\}_{i\geq 0}$ on state space $V$ such that
$\bm{x}_{0}=x$ with probability 1, and to draw $\bm{x}_{i+1}$ given
$\bm{x}_{i}$ we sample a uniform random edge $\bm{e}$ from $\bigcup_{y\in
V}E_{x,y}$. We set $\bm{x}_{i+1}$ equal to the unique $y\in V$ such that
$\bm{e}\in E_{x,y}$.

A Schreier graph is a graph with vertices $V$ such that some group
$\mathfrak{G}$ acts on $V$. Let $S\subseteq\mathfrak{G}$ be some subset of
group elements. The edge set consists of elements of the form $(X,\sigma)$
($\sigma\in S$), so that $(X,\sigma)\in E_{X,\sigma X}$. We call the resulting
graph $\mathrm{Sch}(V,S)$.

######  Definition 31.

Let $S$ and $\widetilde{S}$ be subsets of a group acting on a set $V$. For
each ${\sigma}\in{S}$ let $\Gamma({\sigma})$ be a sequence
$(\widetilde{\sigma}_{1},\dots,{\widetilde{\sigma}}_{t})$ of elements of
$\widetilde{S}$ such that $\sigma
v=\widetilde{\sigma}_{t}\dots\widetilde{\sigma}_{1}v$ for all $v\in V$, so we
regard $\Gamma$ as a map from $S$ to sets of paths using edges in
$\widetilde{S}$. Define the congestion ratio of $\Gamma$ to be

$\displaystyle B({\Gamma})=$
$\displaystyle\max_{\widetilde{\sigma}\in\widetilde{S}}{\left\\{|\widetilde{S}|\mathop{{\bf
E}\/}_{\sigma\in
S}{\left[{N(\widetilde{\sigma},\Gamma(\sigma))|\Gamma({\sigma})|}\right]}\right\\}},$

where $N(\widetilde{\sigma},\Gamma(\sigma))$ is the number of times
$\widetilde{\sigma}$ appears in the sequence $\Gamma(\sigma)$.

######  Lemma 32.

Let $G=\mathrm{Sch}(V,S)$ and $\widetilde{G}=\mathrm{Sch}(V,\widetilde{S})$ be
the connected Schreier graphs of the action of a group. Let $L$ and
$\widetilde{L}$ be the Laplacian operators for the non-lazy random walks on
$G$ and $\widetilde{G}$, respectively. Suppose there exists a $\Gamma$ as in
Definition 31. Then

$\displaystyle\lambda_{2}(L)\geq{\left(\max_{v\in
V}\frac{\pi(v)}{\widetilde{\pi}(v)}\right)}B({\Gamma})\lambda_{2}(\widetilde{L}).$

Here $\pi$ and $\widetilde{\pi}$ are the stationary distributions for $G$ and
$\widetilde{G}$, respectively.

We prove this in Appendix A. It is essentially a reformulation of a standard
result about comparisons on general Markov chains in [WLP09].

######  Lemma 33.

For any $n,k$ we have

$\displaystyle\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN}}\right)}\geq\frac{1}{100000n^{3}}\lambda_{2}{\left(L_{n,3,k}\right)}.$

###### Proof.

Note that $L_{n,3,k}$ and $L_{n,[n-2],k}^{3\text{-NN}}$ are simply the
Laplacians of random walks on Schreier graphs with $\mathfrak{S}_{\\{\pm
1\\}^{n}}$ acting on $\\{\pm 1\\}^{nk}$ by
$e(X^{1},\dots,X^{k})=(eX^{1},\dots,eX^{k})$. In the case of $L_{n,3,k}$ the
edges are given by elements of the form $h^{\\{a,b,c\\}}$ for
$h\in\mathfrak{S}_{\\{\pm 1\\}^{3}}$ and $\\{a,b,c\\}\in\binom{[n]}{3}$. In
the case of $L_{n,[n-3],k}^{3\text{-NN}}$ the edges are given by elements of
the form $g^{\\{a,a+1,a+2\\}}$ for $g\in\mathfrak{S}_{\\{\pm 1\\}^{3}}$ and
$a\in[n-2]$. We deal with each connected component separately. Note that every
connected component is isomorphic to
$\\{(X^{1},\dots,X^{k^{\prime}})\mathrel{\mathop{\mathchar 58\relax}}X^{i}\neq
X^{j}\iff i\neq j\\}$ for $k^{\prime}\leq k$, so we bound the spectral gap for
the walk on $\\{(X^{1},\dots,X^{k})\mathrel{\mathop{\mathchar
58\relax}}X^{i}\neq X^{j}\iff i\neq j\\}$.

We provide a map $\Gamma$ from $\\{h^{\\{a,b,c\\}}\mathrel{\mathop{\mathchar
58\relax}}h\in\mathfrak{S}_{\\{0,1\\}^{3}},a,b,c\in[n]\\}$ to sequences of
elements of the form $g^{\\{a,a+1,a+2\\}}$ for $a\in[n-2]$ such that for any
$h^{\\{a,b,c\\}}$ the sequence
$\Gamma(h^{\\{a,b,c\\}})=(g_{1}^{\\{a_{1},a_{1}+1,a_{1}+2\\}},\dots,g_{t}^{\\{a_{t},a_{t}+1,a_{t}+2\\}})$
satisfies $h^{\\{a,b,c\\}}=g_{t}^{\\{a_{t},a_{t}+1,a_{t}+2\\}}\dots
g_{1}^{\\{a_{1},a_{1}+1,a_{1}+2\\}}$.

The hope is to construct $\Gamma$ such that $B(\Gamma)$ is small and then to
apply Lemma 32. To this end we define $\Gamma$ as follows. Assume $a<b<c$. Fix
$h\in\mathfrak{S}_{8},a\in[n-2]$. Let $d\in[n-2]$ be arbitrary. Then write

$\displaystyle h^{\\{a,b,c\\}}=\mathsf{Sort}^{-1}\cdot
g^{\\{d,d+1,d+2\\}}\cdot\mathsf{Sort},$

Here $\mathsf{Sort}$ sends the $a$th coordinate to the $d$th coordinate, the
$b$th to the $d+1$th, and the $c$th to the $d+2$th. The permutations
$\mathsf{Sort}$ and $\mathsf{Sort}^{-1}$ can each be implemented using at most
$3n$ gates of the form $g^{\\{a^{\prime}-1,a^{\prime},a^{\prime}+1\\}}$ and
$g^{\\{a^{\prime}+1,a^{\prime}+2,a^{\prime}+3\\}}$ where each $g$ swaps
coordinates; this is just by a standard partial sorting algorithm. Write
$\mathsf{Sort}=g_{3n}^{\\{a_{3n},a_{3n}+1,a_{3n}+2\\}}\dots
g_{1}^{\\{a_{1},a_{1}+1,a_{1}+2\\}}$. Then set

$\displaystyle\Gamma(h^{\\{a,b,c\\}})={\left(g_{1}^{\\{a_{1},a_{1}+1,a_{1}+2\\}},\dots,g_{3n}^{\\{a_{3n},a_{3n}+1,a_{3n}+2\\}},h^{(d,d+1,d+2)},\dots,{\left(g_{1}^{\\{a_{1},a_{1}+1,a_{1}+2\\}}\right)}^{-1}\right)}.$

We have $B(\Gamma)\leq 100000n^{3}$ trivially, so we have proved the result by
applying Lemma 32 and the fact that the stationary distributions for both
chains are uniform. ∎

######  Corollary 34.

For any $n,k$ we have

$\displaystyle\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN}}\right)}\geq\Omega{\left(\frac{1}{nk\cdot\log^{5}(k)}\right)}.$

###### Proof.

Lemma 33 shows that
$\lambda_{2}{\left(L_{\ell+2,[\ell],k^{\prime}}^{3\text{-NN}}\right)}\geq\frac{1}{\ell^{3}}\lambda_{2}{\left(L_{\ell+2,3,k^{\prime}}\right)}$
for all $\ell$ and $k^{\prime}$. Theorem 23 states that
$\lambda_{2}{\left(L_{\ell+2,3,k^{\prime}}\right)}\geq\frac{1}{(\ell+2)^{2}k^{\prime}}$
for all $\ell$ and $k^{\prime}$. If we set $\ell=10\log k$ and use Corollary
30 then we get

$\displaystyle\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN}}\right)}\geq\frac{1}{2n}\cdot\lambda_{2}{\left(L_{10\log
k+2,[10\log
k],k}^{3\text{-NN}}\right)}\geq\frac{1}{2n}\cdot\frac{1}{100000k\log^{5}(k)}.$

This implies the result. ∎

As in the case for fully random gates, Theorem 12 follows from Corollary 34
and Section 3.3.

###  3.3 Restricting the Gate Set

So far all of our results have dealt with random circuits with arbitrary gates
acting on 3 bits. However, for practical applications we are often in further
restricting the type of 3-bit gates. However, as long as the arbitrary gate
set is universal on 3 bits, we lose just a constant factor in the mixing time
when we restrict our random circuits to use that gate set, by a standard
application of the comparison method. We prove that we can perform this
conversion before proving our results about brickwork circuits in Section 3.4
because it is somewhat easier to prove for the case of single gates acting at
a time.

######  Lemma 35.

We have

$\displaystyle\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN},\mathrm{DES}[2]}\right)}\geq\Omega{\left(\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN}}\right)}\right)}$

###### Proof.

We compare the Markov chains given by these two Laplacians by providing a way
to write edges in the one induced by arbitrary 3-bit nearest-neighbor gates as
paths in the one induced by 3-bit nearest-neighbor gates with generators
$\mathcal{G}$. Again we focus on the connected component
$\\{(X^{1},\dots,X^{k})\mathrel{\mathop{\mathchar 58\relax}}X^{i}\neq
X^{j}\iff i\neq j\\}$.

For each $g^{S}$ for $g\in\mathfrak{S}_{8}$ and $S\in\binom{[n]}{3}$ let
$\Gamma(g^{S})={\left(g_{i_{1}}^{S},\dots,g_{i_{8!}}^{S}\right)}$ where we
have fixed an arbitrary expansion of $g=g_{i_{1}}\dots g_{i_{8!}}$, and each
$g_{i_{j}}$ is of type $\mathrm{DES}[2]$. Then in the notation of Lemma 32 we
have that

$\displaystyle B(\Gamma)=$
$\displaystyle\max_{g\in\mathcal{G},a\in[n-2]}{\left\\{{\left|\mathcal{G}\right|}(n-2)\mathop{{\bf
E}\/}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[N{\left(g^{\\{a,a+1,a+2\\}},\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right)}{\left|\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right|}\right]}\right\\}}$
$\displaystyle\leq$
$\displaystyle\max_{g\in\mathcal{G},a\in[n-2]}{\left\\{8!n\mathop{{\bf
E}\/}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[8!N{\left(g^{\\{a,a+1,a+2\\}},\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right)}\right]}\right\\}}$
$\displaystyle\leq$
$\displaystyle\max_{g\in\mathcal{G},a\in[n-2]}{\left\\{(8!)^{3}n\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[g^{\\{a,a+1,a+2\\}}\in\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right]}\right\\}}$
$\displaystyle\leq$
$\displaystyle\max_{g\in\mathcal{G},a\in[n-2]}{\left\\{(8!)^{3}n\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[a=\mathbf{a}\right]}\right\\}}$
$\displaystyle\leq$ $\displaystyle(8!)^{3}.$

Applying Lemma 32 completes the proof. ∎

This shows that the random walk given by applying random gates on 3 bits of
type $\mathrm{DES}[2]$ has spectral gap
$\widetilde{\Omega}{\left(1/nk\right)}$, by combining with Corollary 34. A
similar proof essentially shows the same result for the random circuit models
where gates on arbitrary sets of 3 bits.

###  3.4 Brickwork Circuits

The spectral gap for brickwork circuits follows almost directly from the
spectral gap for circuits with nearest-neighbor gates (Corollary 34), as in
[BHH16]. First we show that the random walk induced by 3-bit nearest neighbor
$\mathrm{DES}[2]$ gates, where the 3 bits on which gates act on are of the
form $\\{a,a+1,a+2\\}$ for any $a\in[n-2]$, has approximately the same
spectral gap as that in which the random gates are of the form
$\\{a,a+1,a+2\\}$ for $a\in[n-2]$ but with the restriction that $a\neq 0$ mod
3. Use the notation $L_{n,[n-2],k}^{3\text{-NN},\mathrm{DES}[2]}$ and
$L_{n,\\{a\in[n-2],a=1,2\text{ mod }3\\},k}^{3\text{-NN},\mathrm{DES}[2]}$ for
the Laplacians of these random walks. Assume that $n=0$ mod 3; the other cases
follow similarly.

######  Lemma 36.

For any $n,k$ we have

$\displaystyle\lambda_{2}{\left(L_{n,\\{a\in[n-2],a=1,2\text{ mod
}3\\},k}^{3\text{-NN},\mathrm{DES}[2]}\right)}\geq\Omega{\left(\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN}}\right)}\right)}.$

###### Proof.

By Lemma 35, it suffices to show

$\displaystyle\lambda_{2}{\left(L_{n,\\{a\in[n-2],a=1,2\text{ mod
}3\\},k}^{3\text{-NN},\mathrm{DES}[2]}\right)}\geq\Omega{\left(\lambda_{2}{\left(L_{n,[n-2],k}^{3\text{-NN},\mathrm{DES}[2]}\right)}\right)}.$

We use the comparison method. Again we focus on the connected component
$\\{(X^{1},\dots,X^{k})\mathrel{\mathop{\mathchar 58\relax}}X^{i}\neq
X^{j}\iff i\neq j\\}$. For each
$g\in\mathfrak{S}_{\\{0,1\\}^{3}}\cong\mathfrak{S}_{8}$ of type
$\mathrm{DES}[2]$ and $a\in[n-2]$ we provide a sequence
$\Gamma(g^{\\{a,a+1,a+2\\}})$ of permutations multiplying to
$g^{\\{a,a+1,a+2\\}}$ using only permutations of the form
$h^{\\{b,b+1,b+2\\}}$ with $b\neq 0$ mod 3 such that the resulting congestion
$B(\Gamma)$ is small.

We define $\Gamma$ as follows. Fix $g\in\mathfrak{S}_{8},a\in[n-2]$ where $g$
is of type $\mathrm{DES}[2]$. If $a\neq 0$ mod 3 then simply set
$\Gamma(g^{\\{a,a+1,a+2\\}})=(g^{\\{a,a+1,a+2\\}})$. Otherwise $a=0$ mod 3.
Then there exists a sequence of 64! permutations of the form
$g_{i}^{\\{b_{i},b_{i}+1,b_{i}+2\\}}$ with each $b_{i}\in\\{a-1,a+1\\}$ such
that $g=g_{1}^{\\{b_{1},b_{1}+1,b_{1}+2\\}}\cdots
g_{1}^{\\{b_{64!},\dots,b_{64!}+1,\dots,b_{64!}+2\\}}$. This is because we can
implement the gate $g^{\\{a,a+1,a+2\\}}$ as

$\displaystyle g^{\\{a,a+1,a+2\\}}=\mathsf{Sort}^{-1}\cdot
g^{\\{a-1,a,a+1\\}}\cdot\mathsf{Sort},$

where $\mathsf{Sort}$ sends
$(x_{1},\dots,x_{a-1},x_{a},x_{a+1},x_{a+2},\dots,x_{n})\to(x_{1},\dots,x_{a},x_{a+1},x_{a+2},x_{a-1},\dots,x_{n})$.
The permutations $\mathsf{Sort}$ and $\mathsf{Sort}^{-1}$ can each be
implemented as the product of at most $32!$ permutations of the form
$h^{\\{a-1,a,a+1\\}}$ and $h^{\\{a+1,a+2,a+3\\}}$ where each $h$ is of type
$\mathrm{DES}[2]$. This gives the implementation of $g^{\\{a,a+1,a+2\\}}$ as
the product of at most $64!$ elements of the form $g^{\\{a-1,a,a+1\\}}$ or
$g^{\\{a,a+1,a+2\\}}$, and this defines $\Gamma(g^{\\{a,a+1,a+2\\}})$ for such
$g$ and $a$.

In the notation of Lemma 32, the congestion of $\Gamma$ is bounded:

$\displaystyle B(\Gamma)\leq$ $\displaystyle\max_{g\in\mathcal{G},a=1,2\text{
mod 3}}{\left\\{\frac{8!\cdot 2n}{3}\mathop{{\bf
E}\/}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[N{\left(g^{\\{a,a+1,a+2\\}},\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right)}{\left|\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right|}\right]}\right\\}}$
$\displaystyle\leq$ $\displaystyle 70!\max_{g\in\mathcal{G},a=1,2\text{ mod
3}}{\left\\{n\mathop{{\bf
E}\/}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[N{\left(g^{\\{a,a+1,a+2\\}},\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right)}\right]}\right\\}}$
$\displaystyle\leq$ $\displaystyle 70!\max_{g\in\mathcal{G},a=1,2\text{ mod
3}}{\left\\{n\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[g^{\\{a,a+1,a+2\\}}\in\Gamma(\mathbf{g}^{\\{\mathbf{a},\mathbf{a}+1,\mathbf{a}+2\\}})\right]}\right\\}}$
$\displaystyle\leq$ $\displaystyle 70!\max_{g\in\mathcal{G},a=1,2\text{ mod
3}}{\left\\{n\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{8},\mathbf{a}\in[n-2]}{\left[a\in\\{\mathbf{a}-1,\mathbf{a},\mathbf{a}+1\\}\right]}\right\\}}$
$\displaystyle\leq$ $\displaystyle 71!.$

Here we used that ${\left|\Gamma(g^{\\{a,a+1,a+2\\}})\right|}\leq 64!$ always.
Applying Lemma 32 completes the proof. ∎

######  Lemma 37 ([BHH16], Section 4.A).

For any $n,k$ we have

$\displaystyle\lambda_{2}{\left(L_{n,k}^{\mathrm{brickwork},\mathrm{DES}[2]}\right)}\geq
n\Omega{\left(\lambda_{2}{\left(L_{n,\\{a\in[n-2],a=1,2\text{ mod
}3\\},k}^{3\text{-NN},\mathrm{DES}[2]}\right)}\right)}.$

The idea is to write

$\displaystyle
R_{n,k}^{\text{brickwork},\mathrm{DES}[2]}=\frac{1}{2}P_{\mathrm{odd}}+\frac{1}{2}P_{\mathrm{even}}$
$\displaystyle=$
$\displaystyle\frac{1}{2}R_{n,\\{1,2,3\\},k}^{\mathrm{DES}[2]}R_{n,\\{4,5,6\\},k}^{\mathrm{DES}[2]}\cdots
R_{n,\\{n-2,n-1,n\\},k}^{\mathrm{DES}[2]}+\frac{1}{2}R_{n,\\{2,3,4\\},k}^{\mathrm{DES}[2]}R_{n,\\{5,6,7\\},k}^{\mathrm{DES}[2]}\cdots
R_{n,\\{n-4,n-3,n-2\\},k}^{\mathrm{DES}[2]}.$

Here the operator $R_{n,S,k}^{\mathrm{DES}[2]}$ is the transition operator for
the Markov chain that is similar to $R_{n,S,k}$ but with the restriction that
each step is induced by a gate of type $\mathrm{DES}[2]$. Then we note that
each individual factors in each of the two products all commute. So this
operator is the sum of two projections. Then we can use the inequality
$\mathinner{\\!\left\lVert P+Q\right\rVert}\leq 1+\mathinner{\\!\left\lVert
PQ\right\rVert}$. When we take $P=R_{n,n,k}-P_{\mathrm{odd}}$ and
$Q=R_{n,n,k}-P_{\mathrm{even}}$ we get the inequality

$\displaystyle\mathinner{\\!\left\lVert
P_{\mathrm{odd}}+P_{\mathrm{even}}-2P_{\mathrm{all}}\right\rVert}\leq
1+\mathinner{\\!\left\lVert
P_{\mathrm{odd}}P_{\mathrm{even}}-P_{\mathrm{all}}\right\rVert}.$

Here $P_{\mathrm{all}}$ is the projector to the intersection of the images of
$P_{\mathrm{odd}}$ and $P_{\mathrm{even}}$. The quantity on the LHS is
directly related to the spectral gap we are trying to bound. The detectability
lemma [AALV09] bounds the quantity on the RHS.

######  Corollary 38.

For any $n,k$ we have

$\displaystyle\lambda_{2}{\left(L_{n,k}^{\mathrm{brickwork},\mathrm{DES}[2]}\right)}\geq\Omega{\left(\frac{1}{k\cdot\operatorname{polylog}(k)}\right)}.$

As in the case for fully random gates and nearest-neighbor random gates,
Theorem 13 follows from Corollary 38.

##  4 Proof Overview and Some Helpful Facts

The proof of Theorem 24 follows from directly analyzing the spectrum of the
operator $R_{m,m-1,k}$. We view this operator as noise operators or transition
matrices on the space $\mathbb{R}^{\\{\pm 1\\}^{mk}}$. The issue is that the
$R$ matrices are not a “nice” kind of noise. In particular as transition
matrices the transition probabilities aren’t products of transition
probabilities for each element in the $k$-tuple. In some sense, the Markov
chain that they govern is determined by a process that is essentially
resampling certain coordinates without replacement from $\\{\pm 1\\}^{m}$.

##### Moving to a Nicer Noise Model.

However, we notice that in the case where $k$ is significantly smaller than
$2^{m/2}$, the process of sampling with replacement from $\\{\pm 1\\}^{m}$ is
very similar to the process of sampling without replacement. Thus, we can
essentially pass to this nicer noise model of sampling with replacement,
represented by the $Q$ operators we introduce in Section 5, which guarantees
independence and allows the use of Fourier-analytic techniques to bound the
spectral norms of $Q$ (which are close to $R$). Essentially, we move to
analyzing a nicer noise model. The following lemmas help us formalize this
connection between closeness of Markov chains and linear-algebraic quantities
we deal with.

######  Lemma 39.

Suppose $A$ and $B$ are self-adjoint random walk matrices on a domain
$\mathcal{U}$. That is, for every $X\in\mathcal{U}$ there are distributions
$\mathcal{C}_{X},\mathcal{D}_{X}$ such that for any
$f\mathrel{\mathop{\mathchar 58\relax}}\mathcal{U}\to\mathbb{R}$,

$\displaystyle(Af)(X)=$ $\displaystyle\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{X}}{\left[f(\mathbf{Y})\right]},$
$\displaystyle(Bf)(X)=$ $\displaystyle\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{C}_{X}}{\left[f(\mathbf{Y})\right]}.$

Let $\mathrm{Supp}\subseteq\mathcal{U}$. Then for any
$f,g\mathrel{\mathop{\mathchar 58\relax}}\mathcal{Y}\to\mathbb{R}$ with
$\mathrm{Supp}(f)=\mathrm{Supp}(g)=\mathrm{Supp}$ we have

$\displaystyle{\left|\left\langle f,(A-B)f\right\rangle\right|}$
$\displaystyle\leq\sqrt{\sum_{X\in\mathrm{Supp}}f(X)^{2}\sum_{Y\in\mathrm{Supp}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}\sqrt{\sum_{X\in\mathrm{Supp}}g(X)^{2}\sum_{Y\in\mathrm{Supp}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}.$

where $p_{0}(X,Y)=\frac{1}{|\mathcal{U}|}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}}{\left[\mathbf{Y}=Y\right]}$ and
$p_{1}(X,Y)=\frac{1}{|\mathcal{U}|}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}_{X}}{\left[\mathbf{Y}=Y\right]}$.

In particular, when $f=g$ we get

$\displaystyle{\left|\left\langle
f,(A-B)f\right\rangle\right|}\leq\sum_{X,Y\in\mathrm{Supp}(f)}f(X)^{2}\sum_{Y\in\mathrm{Supp}(f)}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|},$

###### Proof.

We directly compute

$\displaystyle{\left|\left\langle f,(A-B)g\right\rangle\right|}$
$\displaystyle=$ $\displaystyle{\left|\mathop{{\bf E}\/}_{\mathbf{X}\in\\{\pm
1\\}^{mk}}{\left[f(\mathbf{X}){\left((Ag)(\mathbf{X})-(Bg)(\mathbf{X})\right)}\right]}\right|}$
$\displaystyle=$ $\displaystyle{\left|\mathop{{\bf E}\/}_{\mathbf{X}\in\\{\pm
1\\}^{mk}}{\left[f(\mathbf{X}){\left(\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})\right]}-\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{C}_{\mathbf{X}}}{\left[g(\mathbf{Y})\right]}\right)}\right]}\right|}$
$\displaystyle=$ $\displaystyle{\left|\mathop{{\bf E}\/}_{\mathbf{X}\in\\{\pm
1\\}^{mk}}{\left[f(\mathbf{X})\sum_{\mathbf{Y}\in\\{\pm
1\\}^{mk}}g(\mathbf{Y}){\left(\operatorname{{\bf
Pr}}_{\mathcal{D}_{\mathbf{X}}}{\left[\mathbf{Y}\right]}-\operatorname{{\bf
Pr}}_{\mathcal{C}_{\mathbf{X}}}{\left[\mathbf{Y}\right]}\right)}\right]}\right|}$
$\displaystyle=$ $\displaystyle{\left|\sum_{{X},{Y}\in\\{\pm
1\\}^{mk}}f({X})g(Y){\left(\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{X}\sim\mathrm{Unif}(\\{\pm 1\\}^{mk})\\\
\mathbf{Y}\sim\mathcal{D}_{X}\end{subarray}}{\left[\mathbf{X}=X,\mathbf{Y}=Y\right]}-\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{X}\sim\mathrm{Unif}(\\{\pm 1\\}^{mk})\\\
\mathbf{Y}\sim\mathcal{C}_{X}\end{subarray}}{\left[\mathbf{X}=X,\mathbf{Y}=Y\right]}\right)}\right|}$
$\displaystyle\leq$
$\displaystyle\sum_{X,Y\in\mathrm{Supp}}{\left|f({X})\right|}{\left|g(Y)\right|}{\left|\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{X}\sim\mathrm{Unif}(\\{\pm 1\\}^{mk})\\\
\mathbf{Y}\sim\mathcal{D}_{X}\end{subarray}}{\left[\mathbf{X}=X,\mathbf{Y}=Y\right]}-\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{X}\sim\mathrm{Unif}(\\{\pm 1\\}^{mk})\\\
\mathbf{Y}\sim\mathcal{C}_{X}\end{subarray}}{\left[\mathbf{X}=X,\mathbf{Y}=Y\right]}\right|}$
(Support of $f$) $\displaystyle\leq$
$\displaystyle\sum_{X,Y\in\mathrm{Supp}}{\left|f({X})\right|}{\left|g(Y)\right|}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}$
(Define $p_{0},p_{1}$ for notational convenience.) $\displaystyle\leq$
$\displaystyle\sqrt{\sum_{X,Y\in\mathrm{Supp}}f(X)^{2}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}\sqrt{\sum_{X,Y\in\mathrm{Supp}}g(Y)^{2}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}$
$\displaystyle=$
$\displaystyle\sqrt{\sum_{X,Y\in\mathrm{Supp}}f(X)^{2}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}\sqrt{\sum_{X,Y\in\mathrm{Supp}}g(Y)^{2}{\left|p_{0}(Y,X)-p_{1}(Y,X)\right|}}$
(Self-adjointness of $A$ and $B$) $\displaystyle=$
$\displaystyle\sqrt{\sum_{X\in\mathrm{Supp}}f(X)^{2}\sum_{Y\in\mathrm{Supp}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}\sqrt{\sum_{X\in\mathrm{Supp}}g(X)^{2}\sum_{Y\in\mathrm{Supp}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}.\qed$

To employ this comparison bound for similar matrices, we use the following
fact to formally show that when $k$ is not too large, sampling $k$ elements
without replacement is similar to sampling $k$ elements with replacement.

######  Fact 40.

If $k\leq\sqrt{N}$ then

$\displaystyle\prod_{i=0}^{k-1}\frac{N}{N-i}\leq 1+\frac{k^{2}}{N}.$

###### Proof.

We prove by induction on $i$. If $i=0$ then the result is trivially true. Now
assume that $\prod_{i=0}^{k-2}\frac{N}{N-i}\leq 1+\frac{(k-1)^{2}}{N}$. Then

$\displaystyle\prod_{i=0}^{k-1}\frac{N}{N-i}\leq{\left(1+\frac{(k-1)^{2}}{N}\right)}{\left(1+\frac{k-1}{N-k+1}\right)}\leq{\left(1+\frac{(k-1)^{2}}{N}\right)}{\left(1+\frac{k}{N}\right)}\leq{\left(1+\frac{k^{2}}{N}\right)}.$

The inequalities follow because $k\leq\sqrt{N}$. ∎

##### The Badly-Behaved Region.

There is one issue: resampling some set of $m-1$ coordinates with replacement
and without replacement are actually quite different when restricted to the
domain of $X\in\\{\pm 1\\}^{mk}$ such that $X^{i}$ and $X^{j}$ are only
Hamming distance 1 apart. We use a different tool to handle this “badly
behaved” region of the domain $\\{\pm 1\\}^{mk}$. The intuition is in this
region of the graph, we can almost directly show that expansion is good by
analyzing the escape probabilities from this region, so that the contribution
of functions supported on this badly-behaved region to the spectral gap of
$R_{m,m-1,k}$ is already small.

Formally, the following lemma relates the escape probabilities from a region
of the Markov chain to the quadratic form induced by its transition operator.

######  Lemma 41.

Suppose $A$ is a random walk matrix on a domain $\mathcal{U}$ such that the
uniform distribution on $\mathcal{U}$ is a stationary distribution for $A$.
That is, for every $X\in\mathcal{U}$ there is a distribution $\mathcal{D}_{X}$
such that for any $f\mathrel{\mathop{\mathchar
58\relax}}\mathcal{U}\to\mathbb{R}$,

$\displaystyle(Af)(X)=$ $\displaystyle\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{X}}{\left[f(\mathbf{Y})\right]},$

and $A\mathbf{1}=\mathbf{1}$, where $\mathbf{1}$ is the constant 1s vector.

Let $f,g\mathrel{\mathop{\mathchar 58\relax}}\mathcal{U}\to\mathbb{R}$ be such
that for any $X\in\mathrm{Supp}(f)$,

$\displaystyle\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}$
$\displaystyle\leq\varepsilon.$

Then

$\displaystyle{\left|\left\langle
f,Ag\right\rangle\right|}\leq\varepsilon\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

###### Proof.

We directly compute:

$\displaystyle{\left|\left\langle f,Ag\right\rangle\right|}$ $\displaystyle=$
$\displaystyle{\left|\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U},\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[f(\mathbf{X})g(\mathbf{Y})\right]}\right|}$
$\displaystyle=$ $\displaystyle{\left|\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U},\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[f(\mathbf{X})\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}g(\mathbf{Y})\mathbf{1}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}\right]}\right|}$
$\displaystyle=$ $\displaystyle{\left|\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U}}{\left[f(\mathbf{X})\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})\mathbf{1}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}\right]}\right]}\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\mathinner{\\!\left\lVert
f\right\rVert}_{2}\sqrt{\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U}}{\left[\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}^{2}\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})\mathbf{1}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}\right]}^{2}\right]}}\right|}$
(Cauchy-Schwarz) $\displaystyle\leq$
$\displaystyle{\left|\mathinner{\\!\left\lVert
f\right\rVert}_{2}\sqrt{\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U}}{\left[\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}^{2}{\left(\sqrt{\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})^{2}\right]}\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[\mathbf{1}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}^{2}\right]}}\right)}^{2}\right]}}\right|}$
(Cauchy-Schwarz) $\displaystyle=$
$\displaystyle{\left|\mathinner{\\!\left\lVert
f\right\rVert}_{2}\sqrt{\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U}}{\left[\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}^{2}\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})^{2}\right]}\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[\mathbf{1}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}^{2}\right]}\right]}}\right|}$
$\displaystyle=$ $\displaystyle{\left|\mathinner{\\!\left\lVert
f\right\rVert}_{2}\sqrt{\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U}}{\left[\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})^{2}\right]}\right]}}\right|}.$

Now, consider each possible value that $\mathbf{X}$ may take. If
$\mathbf{X}\in\mathrm{Supp}(f)$ then by the assumption, we have that
$\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}\leq\varepsilon$.
Otherwise if $\mathbf{X}\not\in\mathrm{Supp}(f)$ we have that
$\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}=0$. In either case, we
have $\mathbf{1}{\left[\mathbf{X}\in\mathrm{Supp}(f)\right]}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[\mathbf{Y}\in\mathrm{Supp}(g)\right]}\leq\varepsilon$.
Continuing with our calculation, we find that

$\displaystyle{\left|\left\langle
f,Ag\right\rangle\right|}\leq\mathinner{\\!\left\lVert
f\right\rVert}_{2}{\left|\sqrt{\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U},\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[\varepsilon\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})^{2}\right]}\right]}}\right|}=\varepsilon\mathinner{\\!\left\lVert
f\right\rVert}_{2}{\left|\sqrt{\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U},\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}}{\left[g(\mathbf{Y})^{2}\right]}}\right|}.$

At this point, we note that sampling $\mathbf{X}$ uniformly at random and then
sampling $\mathbf{Y}\sim\mathcal{D}_{\mathbf{X}}$ gives the same distribution
as sampling $\mathbf{Y}$ uniformly by stationarity of the uniform
distribution. This completes the proof by the following:

$\displaystyle{\left|\left\langle f,Ag\right\rangle\right|}\leq$
$\displaystyle\varepsilon\mathinner{\\!\left\lVert
f\right\rVert}_{2}{\left|\sqrt{\mathop{{\bf
E}\/}_{\mathbf{X}\in\mathcal{U}}{\left[g(\mathbf{X})^{2}\right]}}\right|}=\varepsilon\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.\qed$

The proof of Theorem 29 follows a similar principle, except that we choose a
different way to partition our domain into a “well-behaved” region and a
“badly-behaved” region.

##  5 Proof of Theorem 24

Throughout this section fix $m\geq 3$. Our goal in this section is to
establish Theorem 24, which states that $R_{m,m-1,k}-R_{m,m,k}$ has small
spectral norm. Informally, we show that completely randomizing $m-1$ out of
$m$ wires in a reversible circuit is very similar to randomizing all $m$
wires. Recall that $R_{m,m-1,k}$ is defined via the distributions
$\mathcal{D}_{X}^{m,m-1,k}$ for $X\in\\{\pm 1\\}^{mk}$, from which one samples
by sampling a random set $\mathbf{S}\subseteq[m]$ with $|\mathbf{S}|=1$ (so
really $\mathbf{S}=\\{\mathbf{a}\\}$, where $\mathbf{a}$ is a random element
of $[m]$), “fixes” the entries $X^{i}_{\mathbf{a}}$, and applies a random
permutation to the coordinates not equal to $\mathbf{a}$. We use this notation
and terminology of a “fixed” coordinate $\mathbf{a}$ throughout this section.

As alluded to in Section 4, our proof will decompose the space
$\mathbb{R}^{\\{\pm 1\\}^{mk}}$ on which these operators act into three
orthogonal components, to be defined in Section 5.1. Then Section 5.1, Section
5.2, and Section 5.4 will bound the contributions from vectors lying in these
orthogonal components and their cross terms.

###  5.1 An Orthogonal Decomposition

######  Definition 42.

Regard elements of $\\{\pm 1\\}^{mk}$ as $k$-by-$m$ matrices, so that the
$i$th row of $X$ is $X^{i}$, and the $a$th column of $X$ is $X_{a}$. Define

$\displaystyle B_{\geq 2}$ $\displaystyle={\left\\{X\in\\{\pm
1\\}^{mk}\mathrel{\mathop{\mathchar 58\relax}}\forall i\neq
j\in[k],d{\left(X^{i},X^{j}\right)}\geq 2\right\\}},$ $\displaystyle B_{=1}$
$\displaystyle={\left\\{X\in\\{\pm 1\\}^{mk}\mathrel{\mathop{\mathchar
58\relax}}\forall i\neq j\in[k],d{\left(X^{i},X^{j}\right)}\geq
1\right\\}}\setminus B_{\geq 2},$ $\displaystyle B_{=0}$
$\displaystyle={\left\\{X\in\\{\pm 1\\}^{mk}\mathrel{\mathop{\mathchar
58\relax}}\exists i\neq j\in[k],d{\left(X^{i},X^{j}\right)}=0\right\\}}.$

Our proof that $R_{m,m-1,k}-R_{m,m,k}$ has small spectral norm will go by
induction on $k$. Lemma 43 helps to connect the cases of $k-1$ and $k$ in the
proof. In particular, it shows that we can pass those functions supported on
$B_{=0}$ into the induction.

######  Lemma 43.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ be
supported on $B_{=0}$. Then for any $S_{1},\dots,S_{t}\subseteq[m]$ and
$c_{1},\dots,c_{t}\in\mathbb{R}$ we have

$\displaystyle{\left|\left\langle
f,\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f\right\rangle\right|}\leq\mathinner{\\!\left\lVert\sum_{s=1}^{t}c_{s}R_{m,S_{s},k-1}\right\rVert}_{\mathrm{op}}.$

###### Proof.

For any map $\varphi\mathrel{\mathop{\mathchar 58\relax}}[k]\to[k-1]$ (viewed
as a coloring of $[k]$ with $k-1$ colors) define the set

$\displaystyle\mathcal{J}_{\varphi}={\left\\{{\left(X^{1},\dots,X^{k}\right)}\mathrel{\mathop{\mathchar
58\relax}}X^{i}=X^{j}\iff\varphi(i)=\varphi(j)\right\\}}.$

These sets $\mathcal{J}_{\varphi}$ partition $B_{=0}$. Thus, for every $f$
supported on $B_{=0}$ we have a decomposition $f=\sum_{\varphi}f_{\varphi}$,
where each $f_{\varphi}$ is supported on $\mathcal{J}_{\varphi}$.

Now, for each $\varphi$ define a map
$\mathrm{Res}_{\varphi}\mathrel{\mathop{\mathchar
58\relax}}{\left\\{f\mathrel{\mathop{\mathchar 58\relax}}{\\{\pm
1\\}^{mk}}\to\mathbb{R}\mathrel{\mathop{\mathchar 58\relax}}f\text{ supported
on }\mathcal{J}_{\varphi}\right\\}}\to\mathbb{R}^{\\{\pm 1\\}^{m(k-1)}}$ by
arbitrarily choosing $i,j\in[k]$ such that $\varphi(i)=\varphi(j)$ and
defining for $f_{\varphi}\mathrel{\mathop{\mathchar 58\relax}}\\{\pm
1\\}^{mk}\to\mathbb{R}$ supported on $\mathcal{J}_{\varphi}$ the new function
$\mathrm{Res}_{\varphi}f_{\varphi}\mathrel{\mathop{\mathchar 58\relax}}\\{\pm
1\\}^{m(k-1)}\to\mathbb{R}$ by defining for $X^{\prime}\in\\{\pm
1\\}^{m(k-1)}$

$\displaystyle\mathrm{Res}_{\varphi}f_{\varphi}(X^{\prime})=$
$\displaystyle\frac{f(\mathrm{Res}_{\varphi}^{*}(X^{\prime}))}{2^{m/2}}.$

where $\mathrm{Res}_{\varphi}^{*}(X^{\prime})$ is the unique element of
$\mathcal{J}_{\varphi}$ such that
$(\mathrm{Res}_{\varphi}^{*}(X^{\prime}))^{[k]\setminus\\{j\\}}=X^{\prime}$.
Note this is well-defined because $f_{\varphi}$ is supported on
$\mathcal{J}_{\varphi}$.

######  Claim 44.

For any $f_{\varphi}\mathrel{\mathop{\mathchar 58\relax}}{\\{\pm
1\\}^{mk}}\to\mathbb{R}$ supported on $\mathcal{J}_{\varphi}$ we have
$\mathinner{\\!\left\lVert
f_{\varphi}\right\rVert}_{2}=\mathinner{\\!\left\lVert\mathrm{Res}_{\varphi}f_{\varphi}\right\rVert}_{2}$
and for any $S\subseteq[m]$,

$\displaystyle\left\langle
f_{\varphi},R_{m,S,k}f_{\varphi}\right\rangle=\left\langle\mathrm{Res}_{\varphi}f_{\varphi},R_{m,S,k}\mathrm{Res}_{\varphi}f_{\varphi}\right\rangle.$

We prove the claim later, and for now use it to compute

$\displaystyle\left\langle f,\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f\right\rangle$
$\displaystyle=$ $\displaystyle\sum_{\varphi,\varphi^{\prime}}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi^{\prime}}\right\rangle$
$\displaystyle=$ $\displaystyle\sum_{\varphi}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi}\right\rangle+\sum_{\varphi\neq\varphi^{\prime}}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi^{\prime}}\right\rangle$
$\displaystyle=$
$\displaystyle\sum_{\varphi}\left\langle\mathrm{Res}_{\varphi}f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}\mathrm{Res}_{\varphi}f_{\varphi}\right\rangle+\sum_{\varphi\neq\varphi^{\prime}}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi^{\prime}}\right\rangle$
(44) $\displaystyle\leq$
$\displaystyle\sum_{\varphi}\mathinner{\\!\left\lVert\sum_{s=1}^{t}c_{s}R_{m,S_{s},k-1}\right\rVert}^{2}_{\mathrm{op}}\mathinner{\\!\left\lVert\mathrm{Res}_{\varphi}f_{\varphi}\right\rVert}_{2}^{2}+\sum_{\varphi\neq\varphi^{\prime}}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi^{\prime}}\right\rangle$
$\displaystyle=$
$\displaystyle\mathinner{\\!\left\lVert\sum_{s=1}^{t}c_{s}R_{m,S_{s},k-1}\right\rVert}^{2}_{\mathrm{op}}\sum_{\varphi}\mathinner{\\!\left\lVert
f_{\varphi}\right\rVert}_{2}^{2}+\sum_{\varphi\neq\varphi^{\prime}}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi^{\prime}}\right\rangle$
$\displaystyle=$
$\displaystyle\mathinner{\\!\left\lVert\sum_{s=1}^{t}c_{s}R_{m,S_{s},k-1}\right\rVert}^{2}_{\mathrm{op}}\left\langle
f,f\right\rangle+\sum_{\varphi\neq\varphi^{\prime}}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi^{\prime}}\right\rangle.$

The last equality follows from orthogonality of the $f_{\varphi}$.

To take care of the cross terms, we observe that for any
$X\in\mathcal{J}_{\varphi}$ and $S\subseteq[n]$, we have $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,S,k}}{\left[\mathbf{Y}\in\mathcal{J}_{\varphi^{\prime}}\right]}=\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,S,k}}{\left[\mathbf{Y}\in\mathcal{J}_{\varphi^{\prime}}\right]}=0$
for any $\varphi^{\prime}\neq\varphi$. Then by Lemma 41 we have

$\displaystyle\sum_{\varphi\neq\varphi^{\prime}}\left\langle
f_{\varphi},\sum_{s=1}^{t}c_{s}R_{m,S_{s},k}f_{\varphi^{\prime}}\right\rangle=0.\qed$

###### Proof of 44.

Without loss of generality assume that $\varphi(k-1)=\varphi(k)$ so we can
regard $\mathrm{Res}_{\varphi}f_{\varphi}$ as a real function on $\\{\pm
1\\}^{m(k-1)}$. Then

$\displaystyle\left\langle f_{\varphi},f_{\varphi}\right\rangle=\mathop{{\bf
E}\/}_{\mathbf{X}\in\\{\pm
1\\}^{mk}}{\left[f_{\varphi}(\mathbf{X})^{2}\right]}=\frac{1}{2^{mk}}\sum_{X\in\\{\pm
1\\}^{mk}}f_{\varphi}(X)^{2}=\frac{1}{2^{m(k-1)}}\sum_{X\in\mathcal{J}_{\varphi}}{\left(\frac{f_{\varphi}(X)}{2^{m/2}}\right)}^{2}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{m(k-1)}}\sum_{X^{\prime}\in\\{\pm
1\\}^{m(k-1)}}\left(\mathrm{Res}_{\varphi}f(X^{\prime})\right)^{2}=\left\langle\mathrm{Res}_{\varphi}f_{\varphi},\mathrm{Res}_{\varphi}f_{\varphi}\right\rangle.$

To prove the second statement, we compute

$\displaystyle\left\langle f_{\varphi},R_{m,S,k}f_{\varphi}\right\rangle$
$\displaystyle=$ $\displaystyle\mathop{{\bf E}\/}_{\mathbf{X}\in\\{\pm
1\\}^{mk}}{\left[f_{\varphi}(\mathbf{X})\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}^{m,S,k}_{X}}{\left[f_{\varphi}(\mathbf{Y})\right]}\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{mk}}\sum_{X\in\\{\pm
1\\}^{mk}}f_{\varphi}(X)\sum_{Y\in\\{\pm
1\\}^{mk}}f_{\varphi}(Y)\operatorname{{\bf
Pr}}_{\mathcal{D}_{X}^{m,S,k}}{\left[\mathbf{Y}=Y\right]}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{mk}}\sum_{X\in\mathcal{J}_{\varphi}}f_{\varphi}(X)\sum_{Y\in\mathcal{J}_{\varphi}}f_{\varphi}(Y)\operatorname{{\bf
Pr}}_{\mathcal{D}_{X}^{m,S,k}}{\left[\mathbf{Y}=Y\right]}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{m(k-1)}}\sum_{X\in\mathcal{J}_{\varphi}}f_{\varphi}(X)\sum_{Y\in\mathcal{J}_{\varphi}}f_{\varphi}(Y)\operatorname{{\bf
Pr}}_{\mathcal{D}_{X}^{m,S,k}}{\left[\mathbf{Y}=Y\right]}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{m(k-1)}}\sum_{X^{\prime}\in\\{\pm
1\\}^{m(k-1)}}\mathrm{Res}_{\varphi}f_{\varphi}(X^{\prime})\sum_{Y^{\prime}\in\\{\pm
1\\}^{m(k-1)}}\mathrm{Res}_{\varphi}f_{\varphi}(Y^{\prime})\operatorname{{\bf
Pr}}_{\mathcal{D}_{X^{\prime}}^{m,S,k-1}}{\left[\mathbf{Y}=Y^{\prime}\right]}$
$\displaystyle=$
$\displaystyle\left\langle\mathrm{Res}_{\varphi}f_{\varphi},R_{m,S,k}\mathrm{Res}_{\varphi}f_{\varphi}\right\rangle.$

The second-to-last equality follows because the corresponding $X,Y$ are in
$\mathcal{J}_{\varphi}$. ∎

We now prove Theorem 24, deferring proofs of the remaining needed auxiliary
results to Section 5.2 and Section 5.4.

######  Theorem 45 (Theorem 24 restated).

Let $m\geq 100$ and assume that $k\leq 2^{m/3}$. Given any
$f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$, we have

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}\leq{\left(\frac{1}{m}+\frac{k^{2}}{2^{m/3}}\right)}\left\langle
f,f\right\rangle.$

###### Proof.

We prove by induction on $k$. In the base case $k=1$ and the result holds by
the following argument when we write $f=f_{2}$. Now assume that the result
holds for real functions on $\\{\pm 1\\}^{m(k-1)}$.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$.
Write $f=f_{0}+f_{1}+f_{2}$ where $f_{0}$ is supported on $B_{=0}$, $f_{1}$ is
supported on $B_{=1}$, and $f_{2}$ is supported on $B_{\geq 2}$. By Lemma 53
applied with both $R_{m,m-1,k}$ and $R_{m,m,k}$ and $B_{=0}$ and $\\{\pm
1\\}^{mk}\setminus B_{=0}=B_{=1}\cup B_{\geq 2}$, the other cross terms
vanish, and we have

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle{\left|\left\langle
f_{0},(R_{m,m-1,k}-R_{m,m,k})f_{0}\right\rangle\right|}+{\left|\left\langle
f_{1},(R_{m,m-1,k}-R_{m,m,k})f_{1}\right\rangle\right|}$
$\displaystyle\;\;\;\;\;\;+{\left|\left\langle
f_{2},(R_{m,m-1,k}-R_{m,m,k})f_{2}\right\rangle\right|}+{\left|2\left\langle
f_{1},(R_{m,m-1,k}-R_{m,m,k})f_{2}\right\rangle\right|}$ (Self-adjointness
(18)) $\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{(k-1)^{2}}{2^{m/2}}\right)}\left\langle
f_{0},f_{0}\right\rangle+{\left(\frac{1}{m}+\frac{k^{2}m^{5}}{2^{m-2}}\right)}\left\langle
f_{1},f_{1}\right\rangle+{\left(\frac{1}{m}+\frac{k^{2}}{2^{m/2}}\right)}\left\langle
f_{2},f_{2}\right\rangle+\frac{2k^{2}m}{2^{m-3}}\mathinner{\\!\left\lVert
f_{1}\right\rVert}_{2}\mathinner{\\!\left\lVert f_{2}\right\rVert}_{2}$ (Lemma
43 \+ induction, Corollary 51, Proposition 60, Lemma 52, in that order)
$\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{k^{2}}{2^{m/2}}\right)}\left\langle
f,f\right\rangle+\frac{2k^{2}m^{5}}{2^{m-3}}\mathinner{\\!\left\lVert
f_{1}\right\rVert}_{2}\mathinner{\\!\left\lVert f_{2}\right\rVert}_{2}$
$\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{k^{2}}{2^{m/2}}\right)}\left\langle
f,f\right\rangle+\frac{k^{2}}{2^{m-20}}\left\langle f,f\right\rangle$
$\displaystyle=$
$\displaystyle{\left(\frac{1}{m}+\frac{k^{2}}{2^{m/3}}\right)}\left\langle
f,f\right\rangle.\qed$

###  5.2 $f$ Supported on $B_{=1}$

We now use Lemma 41 to bound ${\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}\leq{\left|\left\langle
f,R_{m,m-1,k}f\right\rangle\right|}$ when $f$ is supported only on $B_{=1}$
and the cross terms contributed. We first define a partition of $B_{=1}$, and
apply Lemma 41 to these different parts. One of our main observations to bound
$f$ supported on $B_{=1}$ is the observation that when $k$ is small, it is
highly unlikely that two vectors out of any $k$ are close to each other. Thus,
a random walk beginning in $B_{=1}$ and obeying the transition probabilities
given by $B_{m,m-1,k}$ will rarely remain in $B_{=1}$. Formally, Lemma 41
bounds the contributions to the spectral norm by these transition
probabilities.

######  Definition 46.

For $S\subseteq[m]$ define the set $\mathcal{I}_{S}\subseteq\\{\pm 1\\}^{mk}$
by

$\displaystyle\mathcal{I}_{S}={\left\\{X\in B_{=1}\mathrel{\mathop{\mathchar
58\relax}}\forall a\in S,\exists i,j\in[k]\mathrel{\mathop{\mathchar
58\relax}}\Delta{\left(X^{i},X^{j}\right)}=\\{a\\}\right\\}}.$

Unfortunately, the sets $\mathcal{I}_{S}$ for different $S\subseteq[m]$ do not
form a partition of $B_{=1}$, since there is overlap between $\mathcal{I}_{S}$
and $\mathcal{I}_{T}$ for $S\neq T$. However, we can artificially make this
into a partition.

######  Definition 47.

For $S\subseteq[m]$ with $|S|=1$ (so $S=\\{a\\}$ for some $a\in[m]$) define
the set $\widetilde{\mathcal{I}}_{S}\subseteq\\{\pm 1\\}^{nk}$ by

$\displaystyle\widetilde{\mathcal{I}}_{S}=\mathcal{I}_{S}\setminus\bigcup_{a^{\prime}\neq
a}\mathcal{I}_{\\{a^{\prime}\\}}.$

Now place an arbitrary ordering $\preceq$ on the set
$\\{S\subseteq[m]\mathrel{\mathop{\mathchar 58\relax}}|S|=2\\}$ and define

$\displaystyle\widetilde{\mathcal{I}}_{S}=\mathcal{I}_{S}\setminus{\left(\bigcup_{S^{\prime}\subseteq[m]\mathrel{\mathop{\mathchar
58\relax}}|S^{\prime}|=2,S^{\prime}\preceq
S}\mathcal{I}_{S^{\prime}}\right)}.$

######  Observation 48.

The collection of sets
$\\{\widetilde{\mathcal{I}}_{S}\mathrel{\mathop{\mathchar
58\relax}}S\subseteq[m],|S|\leq 2\\}$ forms a partition of $B_{=1}$.

######  Lemma 49.

Let $S\subseteq[m]$ be such that $|S|\leq 2$. If $k\geq 2$ and
$f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ is
supported on $\widetilde{\mathcal{I}}_{S}$ then

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}\leq{\left(\frac{1}{m}+\frac{mk^{2}}{2^{m-1}}\right)}\left\langle
f,f\right\rangle.$

###### Proof.

We bound ${\left|\left\langle
f,R_{m,m-1,k}f\right\rangle\right|}\leq{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}$. This inequality is true
because $R_{m,m,k}$ and $R_{m,m-1,k}-R_{m,m,k}$ are PSD by 17. Suppose first
that $|S|=1$ so that $S=\\{a\\}$ for some $a\in[m]$. Let
$X\in\widetilde{\mathcal{I}}_{S}$. Then

$\displaystyle\operatorname{{\bf
Pr}}{\left[R_{m,m-1,k}X\in\widetilde{\mathcal{I}}_{S}\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{m}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in\widetilde{\mathcal{I}}_{\\{a\\}}|\mathbf{a}=a\right]}+\frac{m-1}{m}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in\widetilde{\mathcal{I}}_{\\{a\\}}|\mathbf{a}\neq
a\right]}$ (Recall $\mathbf{a}$ is the “fixed” coordinate.)
$\displaystyle\leq$ $\displaystyle\frac{1}{m}+\frac{m-1}{m}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in\widetilde{\mathcal{I}}_{\\{a\\}}|\mathbf{a}\neq
a\right]}$ $\displaystyle\leq$
$\displaystyle\frac{1}{m}+\sum_{i,j\in[k]}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[d{\left(\mathbf{Y}^{i},\mathbf{Y}^{j}\right)}\leq
1|\mathbf{a}\neq a\right]}$ $\displaystyle\leq$
$\displaystyle\frac{1}{m}+\binom{k}{2}\frac{m-1}{2^{m-1}-1}$
$\displaystyle\leq$ $\displaystyle\frac{1}{m}+\frac{mk^{2}}{2^{m-1}}.$

Then applying Lemma 41, while noticing that any $R_{m,m^{\prime},k}$ has the
uniform distribution over $\\{\pm 1\\}^{mk}$ as a stationary distribution
(19), completes the proof.

A similar calculation shows that if $|S|=2$ and
$X\in\widetilde{\mathcal{I}}_{S}$ then $\operatorname{{\bf
Pr}}{\left[R_{m,m-1,k}X\in\widetilde{\mathcal{I}}_{S}\right]}\leq\frac{mk^{2}}{2^{m-1}}\leq\frac{1}{m}+\frac{mk^{2}}{2^{m-1}}$,
and again Lemma 41 completes the proof. ∎

######  Lemma 50.

Let $S\neq T\subseteq[m]$ be such that $|S|,|T|\leq 2$. If $k\geq 2$ and
$f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ is
supported on $\widetilde{\mathcal{I}}_{S}$ and $g\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ is supported on
$\widetilde{\mathcal{I}}_{T}$ then

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})g\right\rangle\right|}\leq\frac{mk^{2}}{2^{m-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

###### Proof.

Let $X\in\widetilde{\mathcal{I}}_{S}$. Let $a\in T\setminus S$ be such that
there does not exist $i,j\in[k]$ such that $X\in\mathcal{I}_{\\{a\\}}$. Then

$\displaystyle\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in\widetilde{\mathcal{I}}_{T}\right]}\leq\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in\widetilde{\mathcal{I}}_{\\{a\\}}\right]}\leq\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in{\mathcal{I}}_{\\{a\\}}\right]}$
$\displaystyle\leq$ $\displaystyle\sum_{i,j\in[k]}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[d{\left(\mathbf{Y}^{i},\mathbf{Y}^{j}\right)}=1\right]}\leq\binom{k}{2}\frac{m-1}{2^{m-1}-1}.$
($X\not\in\mathcal{I}_{\\{a\\}}$)

Then applying Lemma 41 gives

$\displaystyle{\left|\left\langle
f,R_{m,m-1,k}g\right\rangle\right|}\leq\frac{mk^{2}}{2^{m-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

A similar calculation shows that $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m,k}}{\left[\mathbf{Y}\in\widetilde{\mathcal{I}}_{T}\right]}\leq\frac{k^{2}}{2^{m}}$.
Then Lemma 41 gives

$\displaystyle{\left|\left\langle
f,R_{m,m,k}g\right\rangle\right|}\leq\frac{k^{2}}{2^{m}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

Applying the triangle inequaltiy completes the proof. ∎

######  Corollary 51.

Assume $k\geq 2$. Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm
1\\}^{mk}\to\mathbb{R}$ be supported on $B_{=1}$. Then

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}\leq{\left(\frac{1}{m}+\frac{k^{2}m^{5}}{2^{m-1}}\right)}\left\langle
f,f\right\rangle.$

###### Proof.

Write $f=\sum_{S\subseteq[m]\mathrel{\mathop{\mathchar 58\relax}}|S|\leq
2}f_{S}$ where each $f_{S}$ is supported on $\mathcal{I}_{S}$. Then

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k}f)\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle{\left|\left\langle f,R_{m,m-1,k}f\right\rangle\right|}$
($R_{m,m,k}$ and $R_{m,m-1,k}-R_{m,m,k}$ both PSD 17) $\displaystyle=$
$\displaystyle\sum_{S,T\subseteq[m]\mathrel{\mathop{\mathchar
58\relax}}|S|,|T|\leq 2}{\left|\left\langle
f_{S},R_{m,m-1,k}f_{T}\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle\sum_{S\subseteq[m]\mathrel{\mathop{\mathchar 58\relax}}|S|\leq
2}{\left|\left\langle f_{S},R_{m,m-1,k}f_{S}\right\rangle\right|}+\sum_{S\neq
T\subseteq[m]\mathrel{\mathop{\mathchar 58\relax}}|S|,|T|\leq
2}{\left|\left\langle f_{S},R_{m,m-1,k}f_{T}\right\rangle\right|}$
$\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{mk^{2}}{2^{m-1}}\right)}\sum_{S\subseteq[m]\mathrel{\mathop{\mathchar
58\relax}}|S|\leq 2}\left\langle
f_{S},f_{S}\right\rangle+\frac{mk^{2}}{2^{m-1}}\sum_{S\neq
T\subseteq[m]\mathrel{\mathop{\mathchar 58\relax}}|S|,|T|\leq
2}\mathinner{\\!\left\lVert f_{S}\right\rVert}_{2}\mathinner{\\!\left\lVert
f_{T}\right\rVert}_{2}$ (Lemma 49, Lemma 50) $\displaystyle=$
$\displaystyle{\left(\frac{1}{m}+\frac{mk^{2}}{2^{m-1}}\right)}\left\langle
f,f\right\rangle+\frac{mk^{2}}{2^{m-1}}\sum_{S\neq
T\subseteq[m]\mathrel{\mathop{\mathchar 58\relax}}|S|,|T|\leq
2}\mathinner{\\!\left\lVert f_{S}\right\rVert}_{2}\mathinner{\\!\left\lVert
f_{T}\right\rVert}_{2}$ $\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{mk^{2}}{2^{m-1}}\right)}\left\langle
f,f\right\rangle+\frac{mk^{2}}{2^{m-1}}\sum_{S\neq
T\subseteq[m]\mathrel{\mathop{\mathchar 58\relax}}|S|,|T|\leq 2}\left\langle
f,f\right\rangle$ $\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{mk^{2}}{2^{m-1}}\right)}\left\langle
f,f\right\rangle+\frac{m^{5}k^{2}}{2^{m-1}}\left\langle f,f\right\rangle$
$\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{m^{5}k^{2}}{2^{m-1}}\right)}\left\langle
f,f\right\rangle.$

Note that we can apply Lemma 49 and Lemma 50 because $k\geq 2$. ∎

###  5.3 Cross Terms

We can use the same idea to bound the contributions from the cross terms.

######  Lemma 52.

Let $f_{1}\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$
be supported on $B_{=1}$ and let $f_{2}\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ be supported on $B_{\geq 2}$. Then

$\displaystyle{\left|\left\langle
f_{1},(R_{m,m-1,k}-R_{m,m,k})f_{2}\right\rangle\right|}\leq\frac{k^{2}m}{2^{m-2}}\mathinner{\\!\left\lVert
f_{1}\right\rVert}_{2}\mathinner{\\!\left\lVert f_{2}\right\rVert}_{2}.$

###### Proof.

For $X\in B_{\geq 2}$ we have $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in
B_{=1}\right]}\leq\frac{k^{2}m}{2^{m-1}}$. Apply Lemma 41 to find that

$\displaystyle{\left|\left\langle
f_{1},R_{m,m-1,k}f_{2}\right\rangle\right|}\leq\frac{k^{2}m}{2^{m-1}}\mathinner{\\!\left\lVert
f_{1}\right\rVert}_{2}\mathinner{\\!\left\lVert f_{2}\right\rVert}_{2}.$

For $X\in B_{\geq 2}$ we have $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m,k}}{\left[\mathbf{Y}\in
B_{=1}\right]}\leq\frac{k^{2}}{2^{m}}$. Apply Lemma 41 to find that

$\displaystyle{\left|\left\langle
f_{1},R_{m,m,k}f_{2}\right\rangle\right|}\leq\frac{k^{2}}{2^{m}}\mathinner{\\!\left\lVert
f_{1}\right\rVert}_{2}\mathinner{\\!\left\lVert f_{2}\right\rVert}_{2}.$

Applying the triangle inequality completes the proof. ∎

######  Lemma 53.

Let $f_{0}\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$
be supported on $B_{=0}$ and let $f_{1}\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ be supported on $B_{=1}\cup B_{\geq
2}$. Then

$\displaystyle{\left|\left\langle
f_{0},(R_{m,m-1,k}-R_{m,m,k})f_{1}\right\rangle\right|}\leq 0.$

###### Proof.

For $X\in B_{\geq 2}\cup B_{=1}$ we have $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m-1,k}}{\left[\mathbf{Y}\in
B_{=0}\right]}=\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,m,k}}{\left[\mathbf{Y}\in
B_{=0}\right]}=0$. Apply Lemma 41 to bound

$\displaystyle{\left|\left\langle
f_{0},(R_{m,m-1,k}-R_{m,m,k})f_{1}\right\rangle\right|}\leq{\left|\left\langle
f_{0},R_{m,m-1,k}f_{1}\right\rangle\right|}+{\left|\left\langle
f_{0},R_{m,m,k}f_{1}\right\rangle\right|}\leq 0.\qed$

###  5.4 A Hybrid Argument for $f$ supported on $B_{\geq 2}$

In this section we bound the square terms $\left\langle
f_{2},(R_{m,m-1,k}-R_{m,m,k})f_{2}\right\rangle$ for $f_{2}$ supported on
$B_{\geq 2}$. As mentioned in Section 4, our key idea is that when $k$ is
small compared to $m$, the fraction of $X\in\\{\pm 1\\}^{mk}$ with two
identical columns is so small that applying the noise by randomly permuting
the rows is almost the same as randomly replacing the rows with completely
random rows. That is, sampling without replacement resembles sampling with
replacement closely.

This observation allows us to pass from the random walk described by
$R_{m,m-1,k}$ to a different random walk described by a nicer noise model
described by operators we will call $Q_{m,m-1,k}$. The key tool we use is the
bound given by Lemma 39 for relating total-variation distances between Markov
chain transition probabilities to a more linear-algebraic notion of closeness,
stated in terms of their transition matrices. Fourier-analytic techniques will
then be useful to bound the spectral norm of these $Q$-operators.

######  Definition 54.

We define four operators777$R_{m,m-1,k}$ and $R_{m,m,k}$ have already been
defined, but we define them again here for ease of comparison. $R_{m,m-1,k}$,
$Q_{m,m-1,k}$, $R_{m,m,k}$, and $Q_{m,m,k}$ on $\mathbb{R}^{\\{\pm
1\\}^{mk}}$.

  * •

Define

$\displaystyle(R_{m,m-1,k}f)(X)$
$\displaystyle=\underset{\mathbf{Y}\sim\mathcal{D}^{m,m-1,k}_{X}}{\operatorname{{\bf
E}}}{\left[f(\mathbf{Y})\right]}.$

  * •

To define $Q_{m,m-1,k}$, for any $X\in{\left\\{\pm 1\right\\}}^{mk}$ we define
the distribution $\mathcal{C}^{m,m-1,k}_{X}$ as follows. To sample
$\mathbf{X}$ from $\mathcal{C}^{m,m-1,k}_{X}$, we sample $\mathbf{a}\in[m]$
uniformly randomly and set $\mathbf{X}^{i}_{\mathbf{a}}=X^{i}_{\mathbf{a}}$
for all $i\in[k]$. Then set $\mathbf{X}^{i}_{a}$ uniformly randomly for
$a\neq\mathbf{a}$. Then

$\displaystyle(Q_{m,m-1,k}f)(X)$
$\displaystyle=\underset{\mathbf{Y}\sim\mathcal{C}^{m,m-1,k}_{X}}{\operatorname{{\bf
E}}}{\left[f(\mathbf{Y})\right]}.$

  * •

Define

$\displaystyle(R_{m,m,k}f)(X)$ $\displaystyle=\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathcal{D}^{m,m,k}_{X}}{\left[f(\mathbf{Y})\right]}.$

  * •

The operator $Q_{m,m,k}$ is defined by setting for each
$f\mathrel{\mathop{\mathchar 58\relax}}{\left\\{\pm
1\right\\}}^{mk}\to\mathbb{R}$

$\displaystyle(Q_{m,m,k}f)(X)$ $\displaystyle=\mathop{{\bf
E}\/}_{\mathbf{Y}\sim\mathrm{Unif}{\left({\left\\{\pm
1\right\\}}^{mk}\right)}}{\left[f(\mathbf{Y})\right]}.$

######  Fact 55.

The matrices $Q_{m,m-1,k}$ and $Q_{m,m,k}$ are self-adjoint and PSD for any
$m,k$.

We intend to show that ${\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}$ is small for $f$ supported on
$B_{\geq 2}$. We do so by a hybrid argument. In the following inequality, the
first (and last) term on the RHS will be bounded by a simple bound on the
total variation distance between the distribution $\mathcal{C}_{X}^{m,m-1,k}$
and $\mathcal{D}_{X}^{m,m-1,k}$ ($\mathcal{C}_{X}^{m,m,k}$ and
$\mathcal{D}_{X}^{m,m,k}$). As mentioned before, the second term on the RHS
will be bounded using Fourier analysis.

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle{\left|\left\langle
f,{\left(R_{m,m-1,k}-Q_{m,m-1,k}\right)}f\right\rangle\right|}+{\left|\left\langle
f,{\left(Q_{m,m,k}-Q_{m,m-1,k}\right)}f\right\rangle\right|}+{\left|\left\langle
f,{\left(R_{m,m,k}-Q_{m,m,k}\right)}f\right\rangle\right|}.$

####  5.4.1 The First Hybrid: $R_{m,m-1,k}$ to $Q_{m,m-1,k}$

######  Lemma 56.

Assume that $k\leq 2^{m/3}$. For any $f\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ supported on $B_{\geq 2}$ and we have
that

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-Q_{m,m-1,k})f\right\rangle\right|}\leq\frac{k^{2}}{2^{m-1}}\left\langle
f,f\right\rangle.$

###### Proof.

We directly compute (using the appropriate definitions of $p_{0}$ and $p_{1}$
given in Lemma 39):

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-Q_{m,m-1,k})f\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle\sum_{X\in B_{\geq 2}}f(X)^{2}\sum_{Y\in B_{\geq
2}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}$ (Lemma 39 \+ self-adjointness (18,
55)) $\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\cdot\frac{k^{2}}{2^{m-1}}\sum_{X\in B_{\geq
2}}f(X)^{2}$ (Equation 1 below) $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{m-1}}\left\langle f,f\right\rangle.$

It suffices to establish Equation 1. Assume that $X\in B_{\geq 2}$. Then

$\displaystyle\sum_{Y\in B_{\geq 2}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}$
$\displaystyle=$ $\displaystyle\sum_{Y\in B_{\geq
2}}{\left|\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y\right]}-\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y\right]}\right|}$
$\displaystyle=$ $\displaystyle\frac{1}{m}\sum_{a\in[m]}\sum_{Y\in B_{\geq
2}}{\left|\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y|a\text{
fixed}\right]}-\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y|a\text{
fixed}\right]}\right|}$ $\displaystyle=$
$\displaystyle\frac{1}{m}\sum_{a\in[m]}\sum_{Y\in B_{\geq
2},Y_{a}=X_{a}}{\left|\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y|a\text{
fixed}\right]}-\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y|a\text{
fixed}\right]}\right|}$ $\displaystyle=$
$\displaystyle\frac{1}{m2^{mk}}\sum_{a\in[m]}\sum_{Y\in B_{\geq
2},Y_{a}=X_{a}}{\left|\prod_{i=0}^{k-1}\frac{1}{2^{m-1}-i}-\frac{1}{2^{(m-1)k}}\right|}$
($k\leq 2^{m/3}\leq 2^{m}-2$ and $X\in B_{\geq 2}$) $\displaystyle\leq$
$\displaystyle\frac{1}{m2^{mk}}\sum_{a\in[m]}\sum_{Y\in B_{\geq
2},Y_{a}=X_{a}}{\left|\frac{1}{2^{(m-1)k}}{\left(\prod_{i=0}^{k-1}\frac{2^{m-1}}{2^{m-1}-i}-1\right)}\right|}$
$\displaystyle\leq$ $\displaystyle\frac{1}{m2^{mk}}\sum_{a\in[m]}\sum_{Y\in
B_{\geq
2},Y_{a}=X_{a}}{\left|\frac{1}{2^{(m-1)k}}{\left(1+\frac{k^{2}}{2^{m-1}}-1\right)}\right|}$
($k\leq 2^{m/3}$, 40) $\displaystyle=$
$\displaystyle\frac{1}{m2^{mk}}\sum_{a\in[m]}\sum_{Y\in B_{\geq
2},Y_{a}=X_{a}}\frac{k^{2}}{2^{m-1}2^{(m-1)k}}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{mk}}\sum_{Y\in B_{\geq
2},Y_{1}=X_{1}}\frac{k^{2}}{2^{m-1}2^{(m-1)k}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\cdot\frac{2^{mk}}{2^{k}}\cdot\frac{k^{2}}{2^{m-1}2^{(m-1)k}}$
$\displaystyle=$ $\displaystyle\frac{k^{2}}{2^{m-1}2^{mk}}.$ (1)

Note that our computations for $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y|a\text{
fixed}\right]}$ and $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}^{m,m-1,k}_{X}}{\left[\mathbf{Y}=Y|a\text{
fixed}\right]}$ relied on the fact that $Y\in B_{\geq 2}$. ∎

####  5.4.2 The Second Hybrid: $Q_{m,m-1,k}$ to $Q_{m,m,k}$

We use Fourier analysis to analyze the spectrum of the operator
$Q_{m,m-1,k}-Q_{m,m,k}$, which will prove that $\mathinner{\\!\left\lVert
Q_{m,m-1,k}-Q_{m,m,k}\right\rVert}_{\mathrm{op}}$ is small. We use the Fourier
characters as an eigenbasis for $Q_{m,m-1,k}-Q_{m,m,k}$.

######  Fact 57.

Fix $S_{1},\dots,S_{k}\subseteq[n]$. Then

$\displaystyle{\left((Q_{m,m-1,k}-Q_{m,m,k})\chi_{S_{1},\dots,S_{k}}\right)}=$
$\displaystyle\begin{cases}\frac{1}{m}\chi_{S_{1},\dots,S_{k}}&\text{ if
}S_{1}\cup\dots\cup S_{k}=\\{a\\}\text{ for some $a\in[m]$}.\\\ 0&\text{
otherwise.}\end{cases}$

###### Proof.

If ${\left|\bigcup_{i}S_{i}\right|}=1$ then $S_{1}=\dots=S_{k}=\emptyset$ and
it is clear that

$\displaystyle
Q_{m,m-1,k}\chi_{S_{1},\dots,S_{k}}=1=Q_{m,m,k}\chi_{S_{1},\dots,S_{k}}.$

Now assume ${\left|\bigcup_{i}S_{i}\right|}\geq 2$. Then for any
$X=(X^{1},\dots,X^{k})\in\\{\pm 1\\}^{mk}$,

$\displaystyle Q_{m,m-1,k}\chi_{S_{1},\dots,S_{k}}(X^{1},\dots,X^{k})$
$\displaystyle=$ $\displaystyle\mathop{{\bf
E}\/}_{(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}}{\left[\chi_{S_{1},\dots,S_{k}}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{m}\sum_{a^{\prime}\in[m]}\mathop{{\bf
E}\/}_{\begin{subarray}{c}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}\\\
\mathbf{a}=a^{\prime}\end{subarray}}{\left[\chi_{S_{1},\dots,S_{k}}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{m}\sum_{a^{\prime}\in[m]}\mathop{{\bf
E}\/}_{\begin{subarray}{c}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}\\\
\mathbf{a}=a^{\prime}\end{subarray}}{\left[\prod_{i\in[k]}\prod_{a\in
S_{i}}\mathbf{Y}^{i}_{a}\right]}$ $\displaystyle=$
$\displaystyle\frac{1}{m}\sum_{a^{\prime}\in[m]}\mathop{{\bf
E}\/}_{\begin{subarray}{c}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}\\\
\mathbf{a}=a^{\prime}\end{subarray}}{\left[{\left(\prod_{\begin{subarray}{c}i\in[k]\\\
a^{\prime}\in
S_{i}\end{subarray}}\mathbf{Y}^{i}_{a^{\prime}}\right)}{\left(\prod_{i\in[k]}\prod_{a\in
S_{i}\setminus\\{a^{\prime}\\}}\mathbf{Y}^{i}_{a}\right)}\right]}$
$\displaystyle=$
$\displaystyle\frac{1}{m}\sum_{a^{\prime}\in[m]}{\left(\prod_{\begin{subarray}{c}i\in[k]\\\
a^{\prime}\in
S_{i}\end{subarray}}\mathbf{Y}^{i}_{a^{\prime}}\right)}\mathop{{\bf
E}\/}_{\begin{subarray}{c}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}\\\
\mathbf{a}=a^{\prime}\end{subarray}}{\left[\prod_{i\in[k]}\prod_{a\in
S_{i}\setminus\\{a^{\prime}\\}}\mathbf{Y}^{i}_{a}\right]}$ $\displaystyle=$
$\displaystyle\frac{1}{m}\sum_{a^{\prime}\in[m]}{\left(\prod_{\begin{subarray}{c}i\in[k]\\\
a^{\prime}\in
S_{i}\end{subarray}}\mathbf{Y}^{i}_{a^{\prime}}\right)}\mathop{{\bf
E}\/}_{(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\in{\left(\\{\pm
1\\}^{n}\right)}^{[k]\setminus\\{a^{\prime}\\}}}{\left[\chi_{S_{1}\setminus\\{a^{\prime}\\},\dots,S_{k}\setminus\\{a^{\prime}\\}}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\right]}$
$\displaystyle=$ $\displaystyle 0.$ (since at least one of the
$S_{i}\setminus\\{a^{\prime}\\}$ is nonempty)

It is easy to see that $Q_{m,m,k}\chi_{S_{1},\dots,S_{k}}=0$, since
$S_{1}\cup\dots\cup S_{k}\neq\emptyset$.

Now assume that $\bigcup_{i}S_{i}=\\{a^{\prime}\\}$ for some
$a^{\prime}\in[m]$. Then it is clear that
$Q_{m,m,k}\chi_{S_{1},\dots,S_{k}}=0$, since $S_{1}\cup\dots\cup
S_{k}\neq\emptyset$. We now compute

$\displaystyle Q_{m,m-1,k}\chi_{S_{1},\dots,S_{k}}(X^{1},\dots,X^{k})$
$\displaystyle=$ $\displaystyle\mathop{{\bf
E}\/}_{(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}}{\left[\chi_{S_{1},\dots,S_{k}}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{m}\sum_{a\in[m]}\mathop{{\bf
E}\/}_{\begin{subarray}{c}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}\\\
\mathbf{a}=a\end{subarray}}{\left[\prod_{\begin{subarray}{c}i\in[k]\\\
S_{i}=\\{a^{\prime}\\}\end{subarray}}\mathbf{Y}^{k}_{a^{\prime}}\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{m}\mathop{{\bf
E}\/}_{\begin{subarray}{c}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}\\\
\mathbf{a}=a^{\prime}\end{subarray}}{\left[\prod_{\begin{subarray}{c}i\in[k]\\\
S_{i}=\\{a^{\prime}\\}\end{subarray}}\mathbf{Y}^{k}_{a^{\prime}}\right]}$ (If
$\mathbf{a}\neq a^{\prime}$ then the $\mathbf{Y}^{i}_{a^{\prime}}$ are
uniformly random.) $\displaystyle=$ $\displaystyle\frac{1}{m}\mathop{{\bf
E}\/}_{\begin{subarray}{c}(\mathbf{Y}^{1},\dots,\mathbf{Y}^{k})\sim\mathcal{C}^{m,m-1,k}_{X}\\\
\mathbf{a}=a^{\prime}\end{subarray}}{\left[\prod_{\begin{subarray}{c}i\in[k]\\\
S_{i}=\\{a^{\prime}\\}\end{subarray}}X^{k}_{a^{\prime}}\right]}$
$\displaystyle=$
$\displaystyle\frac{1}{m}\chi_{S_{1},\dots,S_{k}}(X^{1},\dots,X^{k}).$

Therefore
${\left(Q_{m,m-1,k}-Q_{m,m,k}\right)}\chi_{S_{1},\dots,S_{k}}=\frac{1}{m}\chi_{S_{1},\dots,S_{k}}(X^{1},\dots,X^{k})-0=\frac{1}{m}\chi_{S_{1},\dots,S_{k}}(X^{1},\dots,X^{k})$.
∎

######  Corollary 58.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$.
Then

$\displaystyle{\left|\left\langle
f,(Q_{m,m-1,k}-Q_{m,m,k})f\right\rangle\right|}\leq\frac{1}{m}\left\langle
f,f\right\rangle.$

###### Proof.

The $\chi_{S_{1},\dots,S_{k}}$ form an orthonormal eigenbasis (22) for
$Q_{m,m-1,k}-Q_{m,m,k}$, and by 57 each basis element has eigenvalue with
absolute value at most $\frac{1}{m}$. ∎

####  5.4.3 The Third Hybrid: $Q_{m,m,k}$ to $R_{m,m,k}$

######  Lemma 59.

Assume that $k\leq 2^{m/3}$. For any $f\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ supported on $B_{\geq 2}$ we have

$\displaystyle{\left|\left\langle
f,(R_{m,m,k}-Q_{m,m,k})f\right\rangle\right|}\leq\frac{k^{2}}{2^{m}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}.$

###### Proof.

As in the proof of Lemma 56 we find that (with the appropriate definitions of
$p_{0}$ and $p_{1}$ for use of Lemma 39,

$\displaystyle{\left|\left\langle
f,(R_{m,m,k}-Q_{m,m,k})f\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle\sum_{X\in B_{\geq 2}}f(X)^{2}\sum_{Y\in B_{\geq
2}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}$ (Lemma 39 \+ self-adjointness (18,
55)) $\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\cdot\frac{k^{2}}{2^{m}}\sum_{X\in B_{\geq
2}}f(X)^{2}$ (Equation 2 below) $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{m}}\left\langle f,f\right\rangle.$

It remains to prove Equation 2:

$\displaystyle\sum_{Y\in B_{\geq 2}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}$
$\displaystyle=$ $\displaystyle\sum_{Y\in B_{\geq
2}}{\left|\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}^{m,m,k}_{X}}{\left[\mathbf{Y}=Y\right]}-\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}^{m,m,k}_{X}}{\left[\mathbf{Y}=Y\right]}\right|}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{mk}}\sum_{Y\in B_{\geq
2}}{\left|\prod_{i=0}^{k-1}\frac{1}{2^{m}-i}-\frac{1}{2^{mk}}\right|}$ ($k\leq
2^{m/3}\leq 2^{m}-2$ and $X\in B_{\geq 2}$) $\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\sum_{Y\in B_{\geq
2}}{\left|\frac{1}{2^{mk}}{\left(\prod_{i=0}^{k-1}\frac{2^{m}}{2^{m}-i}-1\right)}\right|}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2^{mk}}\sum_{Y\in B_{\geq
2}}{\left|\frac{1}{2^{mk}}{\left(1+\frac{k^{2}}{2^{m}}-1\right)}\right|}$
($k\leq 2^{m/3}$, 40) $\displaystyle=$
$\displaystyle\frac{1}{2^{mk}}\sum_{Y\in B_{\geq 2}}\frac{k^{2}}{2^{m}2^{mk}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\cdot{2^{mk}}\cdot\frac{k^{2}}{2^{m}2^{mk}}$
$\displaystyle=$ $\displaystyle\frac{k^{2}}{2^{m}}.$ (2)

Note that our computations relied on the fact that $Y\in B_{\geq 2}$. ∎

####  5.4.4 Putting Hybrids Together

######  Proposition 60.

Assume that $k\leq 2^{m/3}$. For any $f\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$ supported on $B_{\geq 2}$, we have

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}\leq{\left(\frac{1}{m}+\frac{k^{2}}{2^{m/2}}\right)}\left\langle
f,f\right\rangle$

###### Proof.

By the triangle inequality,

$\displaystyle{\left|\left\langle
f,(R_{m,m-1,k}-R_{m,m,k})f\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle{\left|\left\langle
f,{\left(R_{m,m-1,k}-Q_{m,m-1,k}\right)}f\right\rangle\right|}+{\left|\left\langle
f,{\left(Q_{m,m,k}-Q_{m,m-1,k}\right)}f\right\rangle\right|}+{\left|\left\langle
f,{\left(R_{m,m,k}-Q_{m,m,k}\right)}f\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle\frac{k^{2}}{2^{m-1}}\left\langle
f,f\right\rangle+\frac{1}{m}\left\langle
f,f\right\rangle+\frac{k^{2}}{2^{m}}\left\langle f,f\right\rangle$ (Lemma 56,
Corollary 58, Lemma 59) $\displaystyle\leq$
$\displaystyle{\left(\frac{1}{m}+\frac{k^{2}}{2^{m-2}}\right)}\left\langle
f,f\right\rangle.$

Note we can apply Lemma 56 and Lemma 59 because $f$ is supported on $B_{\geq
2}$. ∎

##  6 Proof of Theorem 29

In this section let $m$ and $k\leq 2^{m}-2$ be fixed positive integers. As in
the proof of Theorem 24 (via its restatement Theorem 45) we will break
$\mathbb{R}^{\\{\pm 1\\}^{mk}}$ into orthogonal components and bound the
contributions of each of these cross terms to evaluation on the quadratic form
given by $R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}$.

Define the following subsets of $\\{\pm 1\\}^{mk}$:

  * •

$B_{=0}={\left\\{X\in\\{\pm 1\\}^{mk}\mathrel{\mathop{\mathchar
58\relax}}\exists i\neq j\in[k],X^{i}=X^{j}\right\\}}$.888$B_{=0}$ was already
defined in Section 5 but we define it again here for convenience.

  * •

$B_{\geq 1}^{\mathrm{coll}}={\left\\{X\in\\{\pm 1\\}^{mk}\setminus
B_{=0}\mathrel{\mathop{\mathchar 58\relax}}\exists i\neq
j\in[k],X^{i}_{[m-\ell-1,m-1]}=X^{j}_{[m-\ell-1,m-1]}\right\\}}$.

  * •

$B_{\geq 1}^{\mathrm{safe}}={\left\\{X\in\\{\pm
1\\}^{mk}\mathrel{\mathop{\mathchar 58\relax}}\forall i\neq
j\in[k],X^{i}_{[m-\ell-1,m-1]}\neq X^{j}_{[m-\ell-1,m-1]}\right\\}}$.

Note that these sets form a partition of $\\{\pm 1\\}^{mk}$.

As in the proof of Theorem 24, the contribution from the parts of functions
supported on $B_{=0}$ will be bounded by induction. The component $B_{\geq
1}^{\mathrm{safe}}$ will play the role that $B_{\geq 2}$ did: the part of the
domain on which the noise model induced by random permutations (sampling
without replacement) to the bits in $[m-\ell-1,m-1]$ is close to the noise
model induced by completely random replacement of bits (sampling with
replacement). $B_{\geq 1}^{\mathrm{coll}}$ is the component on which these two
noise models are not similar, but as in the case of $B_{=1}$, this set will
already show good expansion.

######  Theorem 61 (Theorem 29 restated).

Fix any $m\geq 100$ and set $100\leq\ell\leq m$. Suppose $k\leq 2^{\ell/10}$.
Then we have for any $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm
1\\}^{mk}\to\mathbb{R}$ that

$\displaystyle{\left|\left\langle
f,R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}\leq\frac{k^{3}}{2^{\ell/2-20}}\left\langle
f,f\right\rangle\leq\frac{1}{\ell}\left\langle f,f\right\rangle.$

###### Proof.

We prove by induction on $k$. In the base case $k=1$ and the result holds by
the following argument when we write $f=f_{2}$. Now assume that the result
holds for real functions on $\\{\pm 1\\}^{m(k-1)}$.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}$.
Write $f=f_{0}+f_{1}+f_{2}$ where $f_{0}$ is supported on $B_{=0}$, $f_{1}$ is
supported on $B_{\geq 1}^{\mathrm{coll}}$, and $f_{2}$ is supported on
$B_{\geq 1}^{\mathrm{safe}}$. By Lemma 53 applied with $R_{m,[m-\ell-1,m],k}$,
$R_{m,[m-1],k}$ and $R_{m,[m],k}$ and $B_{=0}$ and $\\{\pm 1\\}^{mk}\setminus
B_{=0}=B_{\geq 1}^{\mathrm{coll}}\cup B_{\geq 1}^{\mathrm{safe}}$, the other
cross terms vanish, and we have

$\displaystyle{\left|\left\langle
f,R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}$
$\displaystyle=$ $\displaystyle{\left|\left\langle f,Af\right\rangle\right|}$
(Defining $A$ for convenience of notation) $\displaystyle\leq$
$\displaystyle{\left|\left\langle
f_{0},Af_{0}\right\rangle\right|}+{\left|\left\langle
f_{2},Af_{2}\right\rangle\right|}+{\left|\left\langle
f_{1},A(f_{1}+f_{2})\right\rangle\right|}+{\left|\left\langle
f_{2},Af_{1}\right\rangle\right|}$ $\displaystyle=$
$\displaystyle{\left|\left\langle
f_{0},Af_{0}\right\rangle\right|}+{\left|\left\langle
f_{2},Af_{2}\right\rangle\right|}+{\left|\left\langle
f_{1},A(f_{1}+f_{2})\right\rangle\right|}+{\left|\left\langle
f_{1},A^{*}f_{2}\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle\frac{(k-1)^{3}}{2^{\ell/2-10}}\left\langle
f_{0},f_{0}\right\rangle+\frac{k^{2}}{2^{\ell/2-20}}\langle
f_{2},f_{2}\rangle+\frac{k^{2}}{2^{\ell-10}}\mathinner{\\!\left\lVert
f_{1}+f_{2}\right\rVert}_{2}\mathinner{\\!\left\lVert
f_{2}\right\rVert}_{2}+\frac{k^{2}}{2^{\ell-10}}\mathinner{\\!\left\lVert
f_{1}\right\rVert}_{2}\mathinner{\\!\left\lVert f_{2}\right\rVert}_{2}$ (Lemma
43 \+ Induction, Corollary 68, Corollary 64, Corollary 65, in that order)
$\displaystyle\leq$ $\displaystyle\frac{k^{3}}{2^{\ell/2-20}}\langle
f,f\rangle.$

In the last step we used that $k\leq 2^{\ell/10}$. ∎

Similar to Section 5.4 we will again argue that because $\ell$ is large,
applying a random permutation to the same indices of all elements of a tuple
of binary strings is similar to replacing those indices with random binary
strings in all elements of a tuple. To model this situation, we similarly use
the matrix $Q_{m,S,k}$ to denote the random walk matrix induced by the
following distribution $\mathcal{C}_{X}^{m,S,k}$ for each $X\in\\{\pm
1\\}^{mk}$. To draw $\mathbf{Y}\sim\mathcal{C}_{X}^{m,S,k}$, set
$\mathbf{Y}^{i}_{[m]\setminus S}=X^{i}_{[m]\setminus S}$ and set
$\mathbf{Y}^{i}_{S}$ uniformly at random for all $i\in[k]$.

###  6.1 $f$ Supported on $B_{\geq 1}^{\mathrm{coll}}$ and Cross Terms

In this section we leverage that $B_{\geq 1}^{\mathrm{coll}}$ is a set in
$\\{\pm 1\\}^{mk}$ with very good expansion. In some sense, $B_{\geq
1}^{\mathrm{coll}}$ plays the role that $B_{=1}$ played in Section 5. The
following lemma formalizes the expansion property that we need.

######  Lemma 62.

For any $X\in B_{\geq 1}^{\mathrm{coll}}\cup B_{\geq 1}^{\mathrm{safe}}$ we
have that for any $I,J\subseteq[m]$ such that $I\cup J=[m]$ and
$I,J\supseteq[m-\ell-1,m-1]$,

$\displaystyle\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}\in
B_{\geq 1}^{\mathrm{coll}}\right]}\leq\frac{k^{2}}{2^{\ell-2}}.$

In fact, this holds with $\mathcal{C}$ replacing $\mathcal{D}$ anywhere in
this inequality.

###### Proof.

We prove this for the case of distributions $\mathcal{D}$ in both drawing
$\mathbf{Y}$ and $\mathbf{Z}$, but the proof translates easily to the case for
$\mathcal{C}$. Fix any $X\in B_{\geq 1}^{\mathrm{coll}}\cup B_{\geq
1}^{\mathrm{safe}}$. Define the following subset of pairs of indices in
$\binom{[k]}{2}$:

$\displaystyle P_{1}=$
$\displaystyle{\left\\{\\{i,j\\}\in\binom{[k]}{2}\mathrel{\mathop{\mathchar
58\relax}}X^{i}_{I}=X^{j}_{I}\right\\}}.$

Assume that $\\{i,j\\}\in P_{1}$. Then $\mathbf{Y}^{i}_{I}=\mathbf{Y}^{j}_{I}$
with probability 1. But now note that $X^{i}_{J}\neq X^{j}_{J}$ since
otherwise $X^{i}=X^{j}$, which contradicts that $X\not\in B_{=0}$. Therefore,

$\displaystyle\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}\right]}$
$\displaystyle=$ $\displaystyle\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Z}\sim\mathcal{D}_{X}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{\ell}-1}.$ (3)

Now assume that $\\{i,j\\}\not\in P_{1}$. Let $E$ be the event that
$\mathbf{Y}^{i}_{[m-\ell-1,m-1]}=\mathbf{Y}^{j}_{[m-\ell-1,m-1]}$. Then

$\displaystyle\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}\right]}$
$\displaystyle=$ $\displaystyle\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}}{\left[E\right]}\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}|E\right]}$
$\displaystyle+\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}}{\left[\overline{E}\right]}\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}|\overline{E}\right]}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2^{\ell}}+\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}|\overline{E}\right]}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{\ell}}+\frac{1}{2^{\ell}-1}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2^{\ell-2}}.$ (4)

To complete the proof, we use a union bound and find

$\displaystyle\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}\in
B_{\geq 1}^{\mathrm{coll}}\right]}$ $\displaystyle\leq$
$\displaystyle\sum_{\\{i,j\\}\in\binom{[k]}{2}}\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}\right]}$
$\displaystyle\leq$ $\displaystyle\sum_{\\{i,j\\}\in P_{1}}\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}\right]}$
$\displaystyle+\sum_{\\{i,j\\}\not\in P_{1}}\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathbf{Y}\sim\mathcal{D}_{X}^{m,I,k}\\\
\mathbf{Z}\sim\mathcal{D}_{\mathbf{Y}}^{m,J,k}\end{subarray}}{\left[\mathbf{Z}^{i}_{[m-\ell-1,m-1]}=\mathbf{Z}^{j}_{[m-\ell-1,m-1]}\right]}$
$\displaystyle\leq$ $\displaystyle\sum_{\\{i,j\\}\in
P_{1}}\frac{1}{2^{\ell}}+\sum_{\\{i,j\\}\not\in P_{1}}\frac{1}{2^{\ell-1}}$
$\displaystyle\leq$
$\displaystyle\sum_{\\{i,j\\}\in\binom{[k]}{2}}\frac{1}{2^{\ell-2}}$
$\displaystyle\leq$ $\displaystyle\frac{k^{2}}{2^{\ell-2}}.\qed$

######  Lemma 63.

Let $k\geq 2$ and $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}$ be
supported on $B_{\geq 1}^{\mathrm{coll}}$ and $g\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}$ be supported on $B_{\geq 1}^{\mathrm{safe}}\cup
B_{\geq 1}^{\mathrm{coll}}$. Let $I$ and $J$ be such that $I\cup J=[m]$. Then

$\displaystyle{\left|\left\langle
f,{R_{m,J,k}R_{m,I,k}}g\right\rangle\right|}\leq\frac{k^{2}}{2^{\ell-2}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

Moreover, this holds with $Q$ in place of $R$ anywhere.

###### Proof.

The inequality directly follows from Lemma 41 and Lemma 62. We can apply Lemma
41 because the uniform distribution on $\\{\pm 1\\}^{mk}$ is indeed a
stationary distribution under $R_{m,S,k}$ for any $S$ (19). The $Q$ case
follows from the fact that Lemma 62 applies for the distributions
$\mathcal{C}$ too. ∎

######  Corollary 64.

Let $k\geq 2$ and $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}$ be
supported on $B_{\geq 1}^{\mathrm{coll}}$ and $g\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}$ be supported on $B_{\geq 1}^{\mathrm{safe}}\cup
B_{\geq 1}^{\mathrm{coll}}$. Then

$\displaystyle{\left|\left\langle
f,R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}g\right\rangle\right|}\leq\frac{k^{2}}{2^{\ell-3}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

###### Proof.

We compute

$\displaystyle{\left|\left\langle
f,R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}g\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,{R_{m,[m-\ell-1,m],k}R_{m,[m-1],k}}g\right\rangle\right|}+{\left|\left\langle
f,{R_{m,[m-\ell-1,m],k}R_{m,[m],k}}g\right\rangle\right|}$ $\displaystyle=$
$\displaystyle{\left|\left\langle
f,{R_{m,[m-\ell-1,m],k}R_{m,[m-1],k}}g\right\rangle\right|}+{\left|\left\langle
f,{R_{m,[m],k}}g\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-2}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert
g\right\rVert}_{2}+\frac{k^{2}}{2^{\ell}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}$ (Lemma 63)
$\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-3}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.\qed$

######  Corollary 65.

Let $k\geq 2$ and $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm 1\\}^{mk}$ be
supported on $B_{\geq 1}^{\mathrm{coll}}$ and $g\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}$ be supported on $B_{\geq 1}^{\mathrm{safe}}\cup
B_{\geq 1}^{\mathrm{coll}}$. Then

$\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}\right)}^{*}g\right\rangle\right|}\leq\frac{k^{2}}{2^{\ell-3}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

###### Proof.

We compute

$\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}\right)}^{*}g\right\rangle\right|}$
$\displaystyle=$ $\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-1],k}R_{m,[m-\ell-1,m],k}-R_{m,[m],k}\right)}g\right\rangle\right|}$
(self-adjointness (18)) $\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,{R_{m,[m-\ell-1,m],k}R_{m,[m-1],k}}g\right\rangle\right|}+{\left|\left\langle
f,{R_{m,[m-\ell-1,m],k}R_{m,[m],k}}g\right\rangle\right|}$ $\displaystyle=$
$\displaystyle{\left|\left\langle
f,{R_{m,[m-\ell-1,m],k}R_{m,[m-1],k}}g\right\rangle\right|}+{\left|\left\langle
f,{R_{m,[m],k}}g\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-2}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert
g\right\rVert}_{2}+\frac{k^{2}}{2^{\ell}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}$ (Lemma 63)
$\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-3}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

Note this is essentially the same proof as Corollary 64. ∎

###  6.2 A Hybrid Argument for $f$ Supported on $B_{\geq 1}^{\mathrm{safe}}$

The role that $B_{\geq 1}^{\mathrm{safe}}$ plays in this section is similar to
the role played by $B_{\geq 2}$ in Section 5. It is the region of $\\{\pm
1\\}^{mk}$ that is “well-behaved” in the sense that the nicer noise model
given by the $Q$ operators is similar to the noise model given by the $R$
operators on this region of $\\{\pm 1\\}^{mk}$.

######  Lemma 66.

Assume that $k\leq 2^{\ell/10}$ and $f,g\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}$ be supported on $B_{\geq 1}^{\mathrm{safe}}$. Then
for any $S\supseteq[m-\ell-1,m-1]$, we have

$\displaystyle{\left|\left\langle
f,{\left(Q_{m,S,k}-R_{m,S,k}\right)}g\right\rangle\right|}\leq\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

###### Proof.

By assumption $f$ and $g$ are supported on $B_{\geq 1}^{\mathsf{safe}}$.
Therefore, by Lemma 39 and self-adjointness of $Q_{m,S,k}$ and $R_{m,S,k}$
(18, 55) we have

$\displaystyle{\left|\left\langle
f,(R_{m,s,k}-Q_{m,S,k})g\right\rangle\right|}$ $\displaystyle\leq$
$\displaystyle\sqrt{\sum_{X\in B_{\geq 1}^{\mathrm{safe}}}f(X)^{2}\sum_{Y\in
B_{\geq
1}^{\mathrm{safe}}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}\sqrt{\sum_{X\in
B_{\geq 1}^{\mathrm{safe}}}g(X)^{2}\sum_{Y\in B_{\geq
1}^{\mathrm{safe}}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\cdot\frac{k^{2}}{2^{\ell-1}}\sqrt{\sum_{X\in
B_{\geq 1}^{\mathrm{safe}}}f(X)^{2}}\sqrt{\sum_{X\in B_{\geq
1}^{\mathrm{safe}}}g(X)^{2}}$ (Equation 5 below) $\displaystyle=$
$\displaystyle\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert g\right\rVert}_{2}.$

Here $p_{0}$ and $p_{1}$ are as used below. Now it suffices to establish
Equation 5. Assume $X\in B_{\geq 1}^{\mathrm{safe}}$. Then because
$S\supseteq[m-\ell-1,m-1]$, we know that for all $i\neq j$ we have
$X^{i}_{S}\neq X^{j}_{S}$.

$\displaystyle\sum_{Y\in B_{\geq
1}^{\mathrm{safe}}}{\left|p_{0}(X,Y)-p_{1}(X,Y)\right|}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}Y\in B_{\geq 1}^{\mathrm{safe}}\\\
\forall i\in[k],a\in[m]\setminus
S,Y^{i}_{a}=X^{i}_{a}\end{subarray}}{\left|\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}^{m,S,k}_{X}}{\left[\mathbf{Y}=Y\right]}-\frac{1}{2^{mk}}\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}^{m,S,k}_{X}}{\left[\mathbf{Y}=Y\right]}\right|}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{mk}}\sum_{\begin{subarray}{c}Y\in
B_{\geq 1}^{\mathrm{safe}}\\\ \forall i\in[k],a\in[m]\setminus
S,Y^{i}_{a}=X^{i}_{a}\end{subarray}}{\left|\prod_{j=0}^{k-1}\frac{1}{2^{|S|}-j}-\frac{1}{2^{|S|k}}\right|}$
($k\leq 2^{m/3}\leq 2^{m}-2$ and $X,Y\in B_{\geq 1}^{\mathrm{safe}}$)
$\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\sum_{\begin{subarray}{c}Y\in B_{\geq
1}^{\mathrm{safe}}\\\ \forall i\in[k],a\in[m]\setminus
S,Y^{i}_{a}=X^{i}_{a}\end{subarray}}{\left|\frac{1}{2^{|S|k}}{\left(\prod_{j=0}^{k-1}\frac{2^{|S|}}{2^{|S|}-j}-1\right)}\right|}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2^{mk}}\sum_{\begin{subarray}{c}Y\in B_{\geq
1}^{\mathrm{safe}}\\\ \forall i\in[k],a\in[m]\setminus
S,Y^{i}_{a}=X^{i}_{a}\end{subarray}}{\left|\frac{1}{2^{|S|k}}{\left(1+\frac{k^{2}}{2^{|S|}}-1\right)}\right|}$
($k^{2}\leq 2^{\ell}\leq 2^{|S|}$, 40) $\displaystyle=$
$\displaystyle\frac{1}{2^{mk}}\sum_{\begin{subarray}{c}Y\in B_{\geq
1}^{\mathrm{safe}}\\\ \forall i\in[k],a\in[m]\setminus
S,Y^{i}_{a}=X^{i}_{a}\end{subarray}}\frac{k^{2}}{2^{|S|}2^{|S|k}}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{mk}}\cdot
2^{|S|k}\cdot\frac{k^{2}}{2^{|S|}2^{|S|k}}$ $\displaystyle=$
$\displaystyle\frac{k^{2}}{2^{|S|}2^{mk}}$ $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{mk}2^{\ell-1}}.$ (5)

The last inequality follows because
$|S|\geq{\left|[m-\ell-1,m-1]\right|}=\ell-1$. Having established Equation 5,
we have completed the proof. ∎

At this point it may seem like we are essentially finished with the proof,
since we should be able to just replace all the $R$ operators in the
expression $\left\langle
f,{R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}}f\right\rangle$
with the corresponding $Q$ operators and finish the proof. However, we don’t
quite show an upper bound on the operator norm of $R-Q$. Rather, we simply
show that they are close on the well-behaved region. A priori, this gives us
no information about how products of these operators may behave, since the
first term in the product may “rotate” vectors into the badly-behaved region.
So a straightforward application of the triangle inequality fails.

However, we observe that we have already shown in Section 6.1 that random
walks starting outside the badly-behaved region rarely transition into it, so
that we almost can pretend as if all of these operators are operators on
$\mathbb{R}^{B_{\geq 1}^{\mathrm{safe}}}$. We formalize this by inserting
projections to the space of functions supported on $B_{\geq
1}^{\mathrm{safe}}$, and showing that this move does very little
quantitatively.

######  Lemma 67.

We have for any $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm
1\\}^{mk}\to\mathbb{R}$ supported on $B_{\geq 1}^{\mathrm{safe}}$ that

$\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}-Q_{m,[m-\ell-1,m],k}\right)}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}\leq\frac{k^{2}}{2^{\ell/2-20}}\langle
f,f\rangle.$

Moreover, we have

$\displaystyle{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}-R_{m,[m],k}+Q_{m,[m],k}\right)}f\right\rangle\right|}\leq\frac{k^{2}}{2^{\ell/2-20}}\langle
f,f\rangle.$

###### Proof.

Let $\Pi_{\mathrm{safe}}$ be the projection to $\\{h\mathrel{\mathop{\mathchar
58\relax}}\\{\pm 1\\}^{mk}\to\mathbb{R}\mathrel{\mathop{\mathchar
58\relax}}h\text{ supported on }B_{\geq 1}^{\mathrm{safe}}\\}$. We directly
compute

$\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}-Q_{m,[m-\ell-1,m],k}\right)}R_{m,[m-1],k}f\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}-Q_{m,[m-\ell-1,m],k}\right)}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rangle\right|}$
$\displaystyle\;\;+{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}-Q_{m,[m-\ell-1,m],k}\right)}\Pi_{\mathrm{safe}}R_{m,[m-1],k}f\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}-Q_{m,[m-\ell-1,m],k}\right)}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rangle\right|}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert\Pi_{\mathrm{safe}}R_{m,[m-1],k}f\right\rVert}_{2}$
(Lemma 66) $\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,R_{m,[m-\ell-1,m],k}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rangle\right|}+{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rangle\right|}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rVert}_{2}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell/2-10}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}.$ (Equation 6 below)

Here our application of the Lemma 66 depended on the fact that
$\mathrm{Supp}(\Pi_{\mathrm{safe}}R_{m,[m-1],k}f)\subseteq B_{\geq
1}^{\mathrm{safe}}$ and
$\mathrm{Supp}((\mathrm{Id}-\Pi_{\mathrm{safe}})R_{m,[m-1],k}f)\subseteq\\{\pm
1\\}^{mk}\setminus B_{\geq 1}^{\mathrm{safe}}$.

To establish Equation 6 we compute

$\displaystyle\mathinner{\\!\left\lVert{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rVert}_{2}^{2}$
$\displaystyle=$
$\displaystyle\left\langle{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f,{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rangle$
$\displaystyle=$ $\displaystyle\left\langle
R_{m,[m-1],k}f,{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}^{2}R_{m,[m-1],k}f\right\rangle$
$\displaystyle=$ $\displaystyle\left\langle
f,R_{m,[m-1],k}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rangle$
(self-adjointness (18)) $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right\rVert}_{2}$
$\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}.$ (6)

The first inequality follows from Lemma 41 the fact that
$\mathrm{Supp}(f)\subseteq B_{\geq 1}^{\mathrm{safe}}$ and for any $X\in
B_{\geq 1}^{\mathrm{safe}}$, we have $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{D}^{m,[m-1],k}_{X}}{\left[\mathbf{Y}\not\in
B_{\geq 1}^{\mathrm{safe}}\right]}\leq\frac{k^{2}}{2^{\ell-1}}$ (using the
same proof as Lemma 62), and that
$\mathrm{Supp}{\left({\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}R_{m,[m-1],k}f\right)}\subseteq\\{\pm
1\\}^{mk}\setminus B_{\geq 1}^{\mathrm{safe}}$.

Bounding the similar quantity but with $R_{m,[m],k}$ instead of
$R_{m,[m-1],k}$ is the same and the final result follows from the triangle
inequality. The second part of the lemma statement follows from the same
argument and an application of the triangle inequality:

$\displaystyle{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}-R_{m,[m],k}+Q_{m,[m],k}\right)}f\right\rangle\right|}$
$\displaystyle=$ $\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}-R_{m,[m],k}+Q_{m,[m],k}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}$
(18, 55) $\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}+{\left|\left\langle
f,{\left(R_{m,[m],k}-Q_{m,[m],k}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}.$
(7)

We show how to bound the first term in this sum:

$\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}\right)}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}$