††thanks: Co-first authors.††thanks: Co-first authors.

# Approximate t-designs in generic circuit architectures

Daniel Belkin  Institute for Condensed Matter Theory and IQUIST and NCSA
Center for Artificial Intelligence Innovation and Department of Physics,
University of Illinois at Urbana-Champaign, IL 61801, USA  James Allen
Institute for Condensed Matter Theory and IQUIST and NCSA Center for
Artificial Intelligence Innovation and Department of Physics, University of
Illinois at Urbana-Champaign, IL 61801, USA  Soumik Ghosh  Department of
Computer Science, The University of Chicago  Christopher Kang  Department of
Computer Science, The University of Chicago  Sophia Lin  Department of
Computer Science, The University of Chicago  James Sud  Department of Computer
Science, The University of Chicago  Fred Chong  Department of Computer
Science, The University of Chicago  Bill Fefferman  Department of Computer
Science, The University of Chicago  Bryan K. Clark<EMAIL_ADDRESS>Institute for Condensed Matter Theory and IQUIST and NCSA Center for
Artificial Intelligence Innovation and Department of Physics, University of
Illinois at Urbana-Champaign, IL 61801, USA

###### Abstract

Unitary $t$-designs are distributions on the unitary group whose first $t$
moments appear maximally random. Previous work has established several upper
bounds on the depths at which certain specific random quantum circuit
ensembles approximate $t$-designs. Here we show that these bounds can be
extended to any fixed architecture of Haar-random two-site gates. This is
accomplished by relating the spectral gaps of such architectures to those of
1D brickwork architectures. Our bound depends on the details of the
architecture only via the typical number of layers needed for a block of the
circuit to form a connected graph over the sites. When this quantity is
independent of width, the circuit forms an approximate $t$-design in linear
depth. We also give an implicit bound for nondeterministic architectures in
terms of properties of the corresponding distribution over fixed
architectures.

††preprint: APS/123-QED

##  I Introduction

Random quantum circuits are an important tool in the study of both natural and
engineered quantum systems. In quantum computing, random circuits have been
suggested for randomized benchmarking [1, 2], security, and state preparation
[3]. Recent claims of quantum supremacy have hinged on the hardness of
classical simulation of random circuits ([4, 5, 6, 7]). Random circuits have
also been proposed as models for information scrambling in black holes [8, 9],
and the more general random tensor networks have been used as an explicit
construction of the holographic duality in ADS/CFT [10]. In quantum
information theory, random circuits are the standard setting in which to study
measurement-induced phase transitions[11], and they are used as an
analytically-tractable model of quantum ergodicity and chaos [12].

Random circuit models often serve as an interesting theoretically tractable
model for more realistic physical systems. Their maximally generic dynamics
are often a valuable source of intuition as to what one should expect in a
“typical” physical system.

One natural question to ask is how the distribution over the unitary group
induced by a circuit architecture evolves with increasing circuit depth. The
Haar measure on the unitary group is clearly a fixed point of any quantum
circuit distribution, since it is invariant under any unitary gate.
Furthermore, the large-depth limit of a random circuit ensemble converges
uniformly to the Haar measure so long as the gate set is universal [13]. This
uniform convergence is very slow, requiring a circuit depth that scales
exponentially with system size. On the other hand, the expected values of
specific observables under certain circuit distributions approach their Haar
values much faster (e.g. in depth $\log N$) [14]. But this fast convergence
depends on specific details of the observables considered and is not
necessarily universal for other quantities of interest.

In this work we focus on a form of convergence weaker than uniform convergence
of measure, but strong enough to guarantee convergence of essentially any
experimentally observable property. In particular, we study the depth at which
random circuits approximate the Haar measure on every polynomial of bounded
degree (known as the approximate t-design depth).

Approximate unitary designs were first introduced in ref. [15], which showed
that sequential random all-to-all architectures on $N$ sites form approximate
2-designs after $O(N^{2})$ gates. Ref. 16 found that circuits of 1D-local
randomized structures form approximate $t$-designs after $O(t^{10}N^{2})$
gates. For more general graphs which admit Hamiltonian paths, ref. 17 shows
that at most $O(t^{9.5}\log^{4}(t)N^{3})$ gates are required.

Certain fixed architectures have also been studied: Ref. 18 showed that
brickwork circuits with 1D geometric locality also form 2-designs in
$O(N^{2})$ gates, corresponding to circuit depth $O(N)$, while ref. 19 later
found a general-$t$ depth of $O(t^{5}N)$ for the same architecture.

Here we extend previous results for special architectures to generic fixed
architectures. Our main goal is to show that any reasonable circuit
architecture forms an approximate $t$-design in linear depth. We will find
that the rate of convergence is controlled by the connectedness of the
architecture.

###  I.1 Summary of results

In this work, we extend previous results for special architectures to generic
architectures. Consider a periodic architecture composed of $\ell$ complete
layers of $2$-site gates on $N$ sites, each with local dimension $q$. For
large $t$, we prove the $\epsilon$-approximate $t$-design depth is at most

$d_{*}=t^{9.5(\ell-1)+o(1)}\left(2Nt\log q+\log\frac{1}{\epsilon}\right)$

with tighter bounds for small $t$ or for $q=2$.

For architectures composed of incomplete111See Definition 2 layers this bound
becomes

$d_{*}=t^{15.2(\ell-1)+o(1)}\left(2Nt\log q+\log\frac{1}{\epsilon}\right)$

For aperiodic architectures, we partition the circuit into blocks of layers
such that the gates in each block form a connected graph over the whole
system. We show such architectures form approximate $t$-designs when

$d\geq t^{15.2(\bar{\ell}-1)+o(1)}(2Nt\log q+\log\frac{1}{\epsilon})$

where $\bar{\ell}$ is the average number of layers per block.222For
architectures without any regular structure, $\bar{\ell}$ may itself depend on
depth, so this is not always an explicit formula for the $t$-design depth.

For nondeterministic architectures we obtain an implicit bound in terms of the
joint distribution of (a) the effective number of layers in the circuit and
(b) the number of connected blocks.

###  I.2 Structure of the proof

We wish to prove that the frame potential of a random circuit ensemble
approaches that of the Haar measure. Following previous work on approximate
t-designs [20], we begin by expressing the frame potential as a tensor network
of single-gate moment operators (Section. II). In Section III, we focus on the
case of periodic complete architectures and show that the $t$-design depth is
determined by the spectral gap of the transfer matrix $T$. (The assumptions of
completeness and periodicity will be relaxed in sections VIIB and C,
respectively.)

We then decompose the transfer matrix into a product of $\ell$ layers of
gates. Each layer is an orthogonal projection operator. We wish to bound the
spectral gap of the transfer matrix in terms of the geometry of the subspaces
to which the layers project. The key insight at this stage is to consider the
way adding a new layer shrinks the unit eigenspace of the product, reducing
the norm of the excluded vectors. In Section IV, we bound the spectral gap in
terms of these norm reductions. The impact of a new layer on the unit
eigenspace can be represented by a graph of nodes and edges, which we term the
cluster-merging picture.

The next step is to simplify the cluster-merging picture at each layer. In
Section V, we show that you can unravel the cluster-merging graph of each
layer into a collection of loops without increasing the spectral gap. This is
useful because each loop is the transfer matrix of a periodic 1D brickwork
architecture. At this stage we have obtained a lower bound on our transfer
matrix spectral gap in terms of the spectral gaps of 1D brickworks.

In Section VI, we proceed to show the 1D brickwork spectral gap itself may be
bounded by previous results on 1D approximate $t$-design depths. Many of these
results were actually originally proven in terms of the spectral gap, but our
argument applies even to bounds obtained by other methods. Together these
steps allow us to turn a bound on the 1D $t$-design depth into a bound for
generic architectures.

We also discuss extensions of our techniques to other architectures. We show
how our bounds can be applied in expectation to architectures in which gate
locations are drawn randomly, giving an implicit bound in terms of properties
of the induced distribution over fixed architectures. We observe that our
techniques may be adapted to give tighter bounds for architectures with
special structure and give an explicit example for the case of higher-
dimensional brickwork architectures.

###  I.3 Definitions

A quantum circuit on $N$ sites of local dimension $q$ corresponds to a unitary
$U_{c}\in U(q^{N})$. A random quantum circuit architecture then induces a
measure $\varepsilon_{C}$ on $U(q^{N})$. Define the associated $t$-fold
channel

$\displaystyle\Phi_{\text{RQC}}(\rho)=\int_{\varepsilon_{C}}U_{C}^{\otimes
t}\rho(U_{C}^{\dagger})^{\otimes t}\text{d}U_{C}$ (4)

######  Definition 1.

An $\epsilon$-approximate unitary $t$-design[16] is a measure
$\varepsilon_{C}$ on $U(q^{N})$ such that the diamond norm distance between
the corresponding $t$-fold channel $\Phi_{\text{RQC}}$ and that of the Haar
measure is at most $\epsilon$:

$\displaystyle||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}\leq\epsilon$
(5)

We will often shorten “$\epsilon$-approximate unitary $t$-design” to
“$(\epsilon,t)$-design”.

######  Definition 2.

We call an $L$-layer random circuit architecture on $N$ sites complete if each
of the $L$ layers consists of $\frac{N}{2}$ Haar-random $2$-site unitary
gates. In other words, exactly one gate acts on each site per layer.

######  Definition 3.

An $\ell$-layer periodic random circuit architecture repeats the layout of its
layers with period $\ell$ as the depth increases. Note that gates themselves
are independently random at every depth; only the spatial arrangement of the
gates is repeated.

######  Definition 4.

A connected $\ell$-block of a circuit architecture on $N$ sites is a
contiguous block of $\ell$ layers such that the gates in the block form a
connected graph over all $N$ sites.

Our most general results are for complete architectures and depend on the
frequency and size of connected $\ell$-blocks. However, we obtain a more
explicit form for the special case of periodic architectures. We obtain each
result by reduction to the well-studied 1D brickwork architecture.

######  Definition 5.

The $N$-site 1D brickwork is a complete $2$-layer periodic random circuit
architecture, equipped with an ordering $1...N$ of the sites, such that the
first layer applies gates on sites $\\{2j,2j+1\mod N\\}$, while the second
layer applies gates on sites $\\{2j-1\mod N,2j\\}$. In this paper, the spatial
boundary conditions are periodic unless otherwise specified.

###  I.4 Main results

######  Theorem 1.

Suppose that the $N$-site 1D brickwork architecture (with either open or
periodic boundary conditions) forms an $\epsilon$-approximate $t$-design after
at most

$\displaystyle
k_{1}=C(N,q,t)\log\frac{1}{\epsilon}+o_{\epsilon}\left(\log\frac{1}{\epsilon}\right)$
(6)

periods. Then arbitrary complete $\ell$-layer periodic architectures form an
$\epsilon$-approximate $t$-design after at most

$\displaystyle k_{*}=\frac{2Nt\log
q+\log\frac{1}{\epsilon}}{\log\frac{1}{s_{*}}}$ (7)

periods, where

$s_{*}=1-\left(1-\exp\left(-\frac{1}{2C(q,t)}\right)\right)^{\ell-1}$

and $C(q,t)=\sup_{N}C(N,q,t)$. We may relax the bound to the more legible

$\displaystyle k_{*}=\big{(}4\overline{C}(q,t)\big{)}^{\ell-1}\left(2Nt\log
q+\log\frac{1}{\epsilon}\right)$ (9)

by defining $\overline{C}(q,t)\equiv\max\big{(}C(q,t),\frac{1}{2}\big{)}$

######  Theorem 2.

If we do not require that the layers be complete, an $\ell$-layer periodic
architecture forms an $\epsilon$-approximate $t$-design after at most

$\displaystyle k_{*}=\frac{2Nt\log
q+\log\frac{1}{\epsilon}}{\log\frac{1}{s_{*}}}$ (10)

periods, where

$s_{*}=1-\left(1-\exp\left(-\frac{1}{2C(\sqrt{q},t)}\right)\right)^{\ell-1}$

and $C(\sqrt{q},t)$ is defined as in Theorem 1.

We also show an alternative result on incomplete layers in Section VII.2 which
depends on $C(q,t)$ instead of $C(\sqrt{q},t)$, but at the cost of multiplying
$\ell$ by a factor $O(\log\log N)$. Section VIII.1 gives a conjecture under
which the extra factor can be removed.

######  Theorem 3.

The results of Theorems 1 and 2 hold even if the architecture is not periodic,
with $\ell$ replaced by an “average connection depth” defined formally in
Theorem 11.

We will begin with a proof of the periodic, complete case. This proof is
simpler and illustrates the essential elements of our strategy. The argument
will then be extended to the incomplete and aperiodic cases.

###  I.5 Known values of $C(q,t)$

Previous works imply the following bounds on $C(q,t)$:

  * •

For general parameters, the best known bound is that of ref. [16] For the case
of 1D brickwork circuits333Note that our bound is based on a fixed 1D
brickwork instead of a random layer ordering. This allows us to tighten the
bound of ref. [16] for parallel local random circuits by a factor of $2$, by
skipping the factor of $\frac{1}{2}$ relaxation of $\lambda_{2}$ in their
Lemma 21.  where $q\geq 2$, the authors give

$\displaystyle
C(q,t)=261500\lceil\log_{q}(4t)\rceil^{2}q^{2}t^{5+\frac{3.1}{\log q}}$ (12)

For arbitrary $q>1$, the more general form is

$C(q,t)=234(q^{2}+1)e^{\frac{2.5\log(4)(1+\log(q^{2}+1))}{\log(q)}+1}\\\
\times\lceil\log_{q}(4t)\rceil^{2}t^{5+\frac{5(1+\log(1+q^{-2}))}{2\log q}}$
(13)

When $q\geq 2$, we can replace the $t$-exponent with $9.5\geq
5+\frac{\log(e(1+q^{2}))}{\log q}$. Similarly, for $q\geq\sqrt{2}$ we have an
exponent of at most $15.2$.

  * •

For $q=2$, Equation 22 of ref. 19 gives the tighter bound:

$k_{1}=\alpha\log^{5}(t)t^{4+\frac{3}{\sqrt{\log_{2}t}}}\left(2Nt+\log_{2}\frac{1}{\epsilon}\right)$

where $\alpha=10^{13}$. This gives

$C(2,t)=\overline{C}(2,t)=\frac{\alpha}{2\log
2}\log^{5}(t)t^{4+\frac{3}{\sqrt{\log_{2}t}}}$

  * •

For $t=2$ and any $q>1$, Equation 27 of ref. 18 gives

$C(q,2)=\left(2\log\frac{q^{2}+1}{2q}\right)^{-1}$

for 1D brickwork circuits with open boundary conditions. We show in Appendix B
that periodic boundary conditions improve the bound to

$C(q,2)=\left(4\log\frac{q^{2}+1}{2q}\right)^{-1}$

  * •

In the limit $q\rightarrow\infty$, Equation 36 of ref. 18 shows that the
leading-order term is $C(q,t)=\left(2\log\frac{q}{2}\right)^{-1}$ with open
boundary conditions. Periodic boundary conditions again tighten444There can be
no single domain wall in periodic boundary conditions, so the leading term is
now given by the two-domain-wall sector. this to

$C(q,t)=\left(4\log\frac{q}{2}\right)^{-1}+o_{q}(\log^{-1}q)$

  * •

The limit of large $t$ is also interesting. The result of ref. 19 gives
$C(2,t)=t^{4+o(1)}$. If we assume the conjecture of ref. 18, we obtain
$C(q,t)=O(1)$.

##  II Approximate $t$-designs and tensor network picture

For a random quantum circuit channel $\Phi_{\text{RQC}}$ formed from a circuit
ensemble $U_{C}\in\varepsilon_{C}$, the diamond norm difference from the Haar
distribution is bounded in terms of the frame potential[18]:

$\displaystyle||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}^{2}\leq
q^{2Nt}\left(\mathcal{F}^{(t)}_{\varepsilon_{C}}-\mathcal{F}^{(t)}_{\text{Haar}}\right)$
(18)
$\displaystyle\mathcal{F}^{(t)}_{\varepsilon_{C}}=\int_{\varepsilon_{C}^{\otimes
2}}|\text{tr}(U_{C}^{\dagger}V_{C})|^{2t}\text{d}U_{C}\text{d}V_{C}.$ (19)

Both the random quantum circuit channel and the frame potential can be written
in terms of the $t$-th moment operator

$\displaystyle\widehat{\Phi}_{\text{RQC}}=\int_{\varepsilon_{C}}U_{C}^{\otimes
t,t}\text{d}U_{C}$

where $U_{C}^{\otimes t,t}\equiv U_{C}^{\otimes t}\otimes(U_{C}^{*})^{\otimes
t}$. This is a matricization of the quantum channel $\Phi_{\text{RQC}}$, i.e.

$\widehat{\Phi}_{\text{RQC}}\left(\text{vec}(\rho)\right)=\text{vec}\left(\Phi_{\text{RQC}}(\rho)\right)$

We also have

$\displaystyle\mathcal{F}^{(t)}_{\varepsilon}$
$\displaystyle=\int_{\varepsilon_{C}^{\otimes
2}}\text{tr}(U_{C}^{\dagger\otimes t,t}V_{C}^{\otimes
t,t})\text{d}U_{C}\text{d}V_{C}$ (21)
$\displaystyle=\text{tr}(\widehat{\Phi}^{\dagger}_{\text{RQC}}\widehat{\Phi}_{\text{RQC}})$
(22)

a)b) Figure 1: (a) Folding all $t$ copies of a specific gate $U_{i}$ and
$U_{i}^{\dagger}$ in the channel $\Phi_{\text{RQC}}$ into a single operator
$U_{i}^{\otimes t,t}$, where $t=2$. The gray dotted region indicates a density
matrix on which the channel acts. This is vectorized in the middle panel,
forming a matricization of the $2t$ copies of $U_{i}$. (b) The reduction of
the $t$-th moment operator $\widehat{\Phi}_{\text{RQC}}$ to a network of
identical projection tensors $G$. Each unitary $U_{i}^{\otimes t,t}$ can be
averaged separately into an independent copy of $G$.

We assume that $U_{C}$ consists of two-site unitary gates $U_{i}$ drawn
independently from the Haar distribution over $U(q^{2})$. Since distinct gates
are independent, we can average over each gate separately (Figure 1). The
averaging joins the $2t$ copies of each gate that appear in $U_{C}^{\otimes
t,t}$ into a single operator $G$. The action of $G$ depends only on $t$ and
the number of sites on which $U_{i}$ acts. $\widehat{\Phi}_{\text{RQC}}$
becomes the contraction of a tensor network in the shape of the original
circuit $U_{C}$, but with each $U_{i}^{\otimes t,t}$ replaced with its average
$G$.

The individual $G$’s can be written in terms of single-site permutation
states. Given a permutation $\sigma\in S_{t}$, we define a particular
maximally-entangled state on $t$ pairs of sites

$\displaystyle|\sigma\rangle=q^{-t/2}\sum_{\vec{i}\in\mathbb{Z}_{q}^{t}}|\vec{i}\rangle|\sigma(\vec{i})\rangle$
(23)

We will call a tensor power of a permutation state on on $m$ sites
$|\sigma\rangle^{\otimes m}=|\sigma\rangle|\sigma\rangle...|\sigma\rangle$ a
uniform permutation state.

######  Theorem 4.

Let $U$ be an $m$-site Haar-random unitary. Let $G$ be the expected value of
the corresponding moment operator $U_{i}^{\otimes t,t}$. Then $G$ is a
projector onto the space spanned by the uniform permutation states
$|\sigma\rangle^{\otimes m}$.

A proof may be found in ref. 20. In particular, we see that the $t$-th moment
operator for the Haar distribution over all $N$ sites is just the orthogonal
projector on to the globally uniform permutation states on all $N$ sites.
Furthermore, these states also span the unit eigenspace of the moment operator
of any architecture:

######  Lemma 1.

If the circuit architecture is connected, the unit eigenspace of
$\widehat{\Phi}_{\text{RQC}}$ is spanned by the globally uniform permutation
states $\ket{\sigma}^{\otimes N}$.

###### Proof.

Suppose we apply $k$ repetitions of the circuit architecture. As
$k\rightarrow\infty$, ref. 13 shows that the induced measure on $U(q^{N})$
converges to the Haar measure. It follows that the corresponding moment
operator $\widehat{\Phi}_{\text{RQC}}^{k}$ converges to that of the Haar
measure, which is the projector onto the span of the cluster-uniform
permutation states. But since $\widehat{\Phi}_{\text{RQC}}$ is norm-
nonincreasing, $\lim_{k\rightarrow\infty}\widehat{\Phi}_{\text{RQC}}^{k}$ is a
projector on to the unit eigenspace of $\widehat{\Phi}_{\text{RQC}}$, so the
unit eigenspace of $\widehat{\Phi}_{\text{RQC}}$ must be the same as that of
$\widehat{\Phi}_{\text{Haar}}$. Theorem 4 completes the argument. ∎

Figure 2: Breaking up $\widehat{\Phi}_{\text{RQC}}$ for a random quantum
circuit (in this case a 1D brickwork) into $k=3$ copies of the transfer matrix
$T$.

##  III Transfer matrix and the spectral gap

We now specialize to the case of $\ell$-layer periodic architectures. In this
case we can define a transfer matrix $T$ by contracting together the
projectors $G_{i},i\in\left\\{1...\frac{\ell N}{2}\right\\}$ of the moment
operator $\widehat{\Phi}_{\text{RQC}}$ corresponding to a single period of the
architecture, as shown in Figure 2. We will show that the approximate
$t$-design time is controlled by the singular value spectrum of $T$. If there
are $k$ periods of the architecture, the moment operator corresponds to the
$k$th power of the transfer matrix, so by Equation 22 the frame potential is

$\displaystyle\mathcal{F}_{\varepsilon}=\text{tr}(T^{\dagger
k}T^{k})=||T^{k}||^{2}_{F}$ (24)

######  Theorem 5.

$\displaystyle\mathcal{F}_{\varepsilon}-\mathcal{F}_{\text{Haar}}\leq
q^{2Nt}s_{*}^{2k}$ (25)

where $s_{*}$ is the largest non-unit singular value of $T$.

###### Proof.

Starting from

$\mathcal{F}_{\varepsilon}=||T^{k}||_{F}^{2}$

we can use Theorem 16, proven in Appendix A to see that

$||T^{k}||_{F}^{2}\leq m_{1}+(d^{2}-m_{1}-m_{0})s_{*}^{2k}$

where $d^{2}$ is the dimension of $T$, $m_{1}$ is the dimesnion of its unit
eigenspace, and $m_{0}$ is the dimension of its zero eigenspace. As long as
the circuit is connected, by Lemma 1, it shares the same unit eigenstates as
the Haar distribution, so $m_{1}=\mathcal{F}_{\text{Haar}}^{(q^{N})}$. The
first layer consists of $2$-site gates, each of which has only
$\mathcal{F}_{\text{Haar}}^{(q^{2})}$ nonzero eigenvalues. A lower bound on
$m_{0}$ is thus $d^{2}-\left(\mathcal{F}_{\text{Haar}}^{(q^{2})}\right)^{N}$.
The total dimension for $T$ is $d^{2}=q^{2Nt}$, so we find

$\displaystyle\mathcal{F}_{\varepsilon}\leq\mathcal{F}_{\text{Haar}}^{(q^{N})}+\left(\left(\mathcal{F}_{\text{Haar}}^{(q^{2})}\right)^{N}-\mathcal{F}_{\text{Haar}}^{(q^{N})}\right)s_{*}^{2k}$
(27)

Of course, $\mathcal{F}_{\text{Haar}}$ is just the dimension of the unit
eigenspace, which is at most $t!$ (since it is spanned by the uniform
permutation states) and also at most $q^{2Nt}$ (since that is the total
dimension of $T$). In addition, it is known to be equal[18] to $t!$ for $t\leq
d$. From Equation 19 it is clear that the frame potential is a monotonically
increasing function of $t$. Together these imply

$\displaystyle\min(t!,d!)\leq\mathcal{F}_{\text{Haar}}^{(d)}\leq\min\left(t!,d^{2t}\right)$
(28)

so that

$\displaystyle\left(\mathcal{F}_{\text{Haar}}^{(q^{2})}\right)^{N}-\mathcal{F}_{\text{Haar}}^{(q^{N})}\leq\min\left(t!,q^{2t}\right)^{N}-\min\left(t!,\left(q^{N}\right)!\right)$

The remaining algebra will be easier if we further relax this to

$\displaystyle\left(\mathcal{F}_{\text{Haar}}^{\left(q^{2}\right)}\right)^{N}-\mathcal{F}_{\text{Haar}}^{\left(q^{N}\right)}\leq
q^{2Nt}$ (29)

Without this relaxation, all of our bounds change by

$2Nt\log
q\rightarrow\log\left(\left(\mathcal{F}_{\text{Haar}}^{\left(q^{2}\right)}\right)^{N}-\mathcal{F}_{\text{Haar}}^{\left(q^{N}\right)}\right)$

This latter is tighter for small $t$, but the former is more convenient to
interpret, so we prefer the simplified form. Equation 27 then becomes

$\displaystyle\mathcal{F}_{\varepsilon}\leq\mathcal{F}_{\text{Haar}}+q^{2Nt}s_{*}^{2k}$
(30)

∎

Substituting Theorem 5 into Equation 18 gives a bound on the rate at which a
random circuit architecture approaches a $t$-design in terms of the subleading
singular value (SSV) of the transfer matrix:

$\displaystyle||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}\leq
q^{2Nt}s_{*}^{k}$ (31)

It follows that the number of periods required to push the diamond-norm error
below $\epsilon$ can be upper-bounded in terms of $s_{*}$ by

$\displaystyle k_{*}=\frac{2Nt\log
q+\log\frac{1}{\epsilon}}{\log\frac{1}{s_{*}}},$ (32)

which is already part of Theorem 1. It remains only to bound $s_{*}$, i.e. the
spectral gap of $T$.

##  IV Bounding the spectral gap

We wish to bound the largest non-unit singular value of a product of
projectors. Because each projector is norm-nonincreasing, any subspace whose
norm is decreased by some large amount by the first few projectors cannot
contain a large singular value. If $P_{i}...P_{1}$ does not have a large
singular value, then any large singular value of $P_{i+1}...P_{1}$ must arise
from vectors that were nearly unit eigenvectors of $P_{i}...P_{1}$, while
still being orthogonal to the unit eigenvectors of $P_{i+1}...P_{1}$. This
allows us to construct an inductive bound based on the relative geometry of
the subspaces to which the $P_{i}$ project.

######  Theorem 6.

Consider some set of subspaces $X_{i},i\in\\{1...n\\}$ of a Hilbert space. Let
$P_{i}$ be the orthogonal projector on to $X_{i}$ and $Q_{i}$ the orthogonal
projector on to $\bigcap_{j=1}^{i}X_{i}$. Define $T=P_{n}...P_{2}P_{1}$ and
let $s_{*}$ be the largest non-unit singular value of $T_{n}$. Then we have
the bound

$\displaystyle s_{*}^{2}\leq 1-\prod_{i=2}^{n}(1-\mathscr{s}_{i}^{2})$ (33)

where $\mathscr{s}_{i}$ is the largest non-unit singular value of
$P_{i}Q_{i-1}$.

The proof of this theorem is given in Appendix A. In our case, the $P_{i}$
will be the layers of the transfer matrix. We will call the $\mathscr{s}_{i}$
the layer-restricted singular values. Our first goal is to characterize the
$Q_{i}$, which we term the intermediate unit eigenspace projectors.

###  IV.1 Cluster-merging picture

To bound the layer-restricted singular values, we first must understand the
intermediate unit eigenspace to which $Q_{i}$ projects. From Theorem 4, we
know that the unit eigenstates of a single gate are the uniform permutation
states $\ket{\sigma}^{\otimes m}$. Moreover, each gate is norm non-increasing,
so a state whose norm is reduced by a gate cannot recover that norm later.
This leads to

######  Lemma 2.

Let $G_{i},i\in\\{1...m\\}$ be some gates within the transfer matrix which
form a connected graph on some cluster of $n$ sites. The unit eigenspace of
the contracted network $M=\prod_{i=1}^{m}G_{i}$ is spanned by the cluster-
uniform permutation states $\\{|\sigma\rangle^{\otimes n},\sigma\in S_{t}\\}$

###### Proof.

We may interpret $M$ as the transfer matrix of a (possibly incomplete) random
quantum circuit architecture with the same layout as the $G_{i}$. Since the
$G_{i}$ are connected, the corresponding quantum circuits are also connected.
We may then apply Lemma 1. ∎

a)

b)

Figure 3: The cluster-merging picture for calculating the 3rd layer-restricted
subleading singular value $\mathscr{s}_{3}$, i.e. the subleading singular
value of $P_{3}Q_{2}$. (a): The first two layers are collected into clusters
(blue) of sites that are connected by the first two layers of gates. The
intermediate unit eigenspace projector $Q_{2}$ is then a tensor product of
projectors on each cluster. (b): (Left) Graphical representation of
$P_{3}Q_{2}$ in the cluster merging picture. Each cluster in $Q_{2}$ becomes a
node labeled by the number of sites it contains. Gates in $P_{3}$ that join
distinct clusters become edges. Gates in $P_{3}$ that join two sites within
the same cluster are ignored. (Right) Each connected component of this graph
is merged into a single cluster of the next intermediate unit eigenspace
projector $Q_{3}$ .

This leads to the cluster-merging picture (Figure 3). Take some sequence of
complete layers $P_{1}...P_{l}$. These layers may connect all the sites, or
they may connect only certain subsets of the sites. Call each subset of sites
which is connected by $P_{1}...P_{l}$ a cluster. Recall that the intermediate
unit eigenspace projector $Q_{l}$ is defined to be the orthogonal projector on
to the unit eigenspace of the product $P_{l}...P_{1}$.

By Lemma 2, the space to which $Q_{l}$ projects is the tensor product of the
spans of the uniform permutation states on each cluster. As we include more
layers by increasing $l$, the clusters merge and the unit eigenspace to which
$Q_{l}$ projects shrinks. Eventually the whole circuit has been connected in
to a single cluster, at which time the unit eigenspace is the span of the
globally uniform permutation states $|\sigma\rangle^{\otimes N}$.

Our goal is to compute $\mathscr{s}_{l}$, which is the largest non-unit
singular value of $P_{l}Q_{l-1}$. This can be accomplished by constructing the
cluster-merging graph which uniquely determines $\mathscr{s}_{l}$. To build
the graph, let each cluster of sites connected by $P_{l-1}...P_{1}$ be a node,
with weight equal to the number of sites in the cluster. Each gate of $P_{l}$
that joins two distinct clusters is mapped to an edge joining the
corresponding nodes. Gates of $P_{l}$ that join two sites within the same
cluster do not influence $\mathscr{s}_{l}$ and can be ignored. The layer-
restricted singular values $\mathscr{s}_{l}$ depend only on the graph topology
and the node weights, not on any other details of the architecture.

##  V Reduction of each layer to 1D brickwork loops

In this section we will give a set of rules for rearranging a cluster-merging
graph into a standard form without decreasing its subleading singular value.

####  V.0.1 Structure of the graph

######  Lemma 3.

For a complete $\ell$-layer periodic architecture, the cluster-merging graph
for each layer above the first has nodes of even weight and even degree.

###### Proof.

We first show that the clusters are of even size. The first layer creates
clusters of size $2$. Subsequent layers create clusters by merging these
size-$2$ clusters together, so later cluster sizes are also even.

We next show that each cluster has an even number of external connections.
Suppose a cluster of size $m$ has $n_{i}$ internal gates and $n_{e}$ external
gates. Since each site is acted on by exactly one two-site gate, we have
$2n_{i}+n_{e}=m$, and so $n_{e}$ is even. The nodes are thus of even degree. ∎

####  V.0.2 Cluster-merging bound

Our goal is to bound $\mathscr{s}_{i}$ for generic cluster-merging graphs in
terms of cluster-merging graphs of some standard form. First consider the unit
eigenspace.

######  Lemma 4.

The unit eigenspace of a connected cluster-merging graph is spanned by the
globally uniform permutation states.

This is just a special case of Lemma 2. We can now show a lower bound:

######  Lemma 5.

Let $A$,$B$ be two nodes of a connected cluster-merging graph. If we merge $A$
and $B$ into a single node $AB$, the subleading singular value of the graph
does not increase.

###### Proof.

Let $\mathscr{s},\mathscr{s}^{\prime}$ be the subleading singular value of the
old and new graphs, respectively. Let $X,X^{\prime}$ be the subspaces
projected to by the nodes of the old and new graphs. Let $P$ be the projector
corresponding to the edges, which are the same for both graphs.

By Lemma 4, the unit eigenspaces of $PQ$ and $PQ^{\prime}$ are the same. Call
this subspace $Z$. We may write

$\mathscr{s}=\max_{\left\\{v\in X|v\perp Z\right\\}}\frac{||Pv||}{||v||}$

and

$\mathscr{s}^{\prime}=\max_{\left\\{v\in X^{\prime}|v\perp
Z\right\\}}\frac{||Pv||}{||v||}$

$X$ is spanned the cluster-uniform states over the old nodes, while
$X^{\prime}$ is spanned by the cluster-uniform states over the new nodes. A
cluster-uniform permutation state on the new node $AB$ is of the form
$\ket{\sigma}^{\otimes(|A|+|B|)}$, which is also cluster-uniform on $A$ and
$B$ individually. In other words, $X^{\prime}\subseteq X$. Since
$\mathscr{s}^{\prime}$ is the maximum of the same function over a smaller
space, we obtain $\mathscr{s}^{\prime}\leq\mathscr{s}$. ∎

If we run our lower bound in reverse, we are led to the following two
rewriting rules that give upper bounds on subleading singular values of
cluster-merging graphs:

######  Lemma 6.

If we split a node and the two sides remain part of the same connected graph,
the subleading singular value does not decrease.

######  Lemma 7.

If we split a node and add a new link to keep the graph connected, the
subleading singular value does not decrease.

###### Proof.

These both correspond to applying 5 backwards. ∎

Note that the number of links connected to a cluster cannot exceed the number
of sites it contains, so we can only apply the latter lemma to clusters with
at least two unoccupied sites. We are now ready to prove the main result of
this section.

Figure 4: Algorithm for bounding a cluster-merging graph by a 1D brickwork
structure. We first use Lemma 6 to split clusters (without joining the halves
with an edge) along an Eulerian circuit in our graph.We then use Lemma 7 to
break up larger clusters (joining the halves with an edge) until all clusters
in the loop have size 2. Each step in this process does not decrease the
subleading singular value of the graph.

######  Theorem 7.

Consider any cluster-merging graph on $n$ sites with SSV $\mathscr{s}$. Let
$s_{\text{1D}}(m)$ be the SSV for a 1D brickwork loop on $m$ sites. We have

$\mathscr{s}\leq\max_{m\leq n}s_{\text{1D}}(m)$

###### Proof.

Our goal is to apply the graph rewriting rules repeatedly to upper-bound a
cluster in a standard form. First suppose that the graph is connected. Since
nodes are of even degree, there exists an Eulerian circuit through the
cluster-merging graph. We can split nodes along this Eulerian circuit using
Lemma 6 until our graph structure is a single loop, again with nodes of even
degree (Figure 4, first process). We can then apply Lemma 7 repeatedly within
each node to split each node into many nodes, each of size $2$ (Figure 4,
second process). When we are done, we have exactly a 1D brickwork loop on $m$
sites. These transformations cannot decrease the SSV, so the brickwork SSV is
an upper bound on the original SSV.

Now consider any disconnected graph. We can apply the argument above to bound
each connected component by a loop graph. The corresponding operator is a
tensor product of loop operators, and the largest singular value of each loop
operator is $1$. The subleading singular value of the whole operator is then
just the largest subleading singular value of any of the connected components.
Each connected component is a brickwork loop of size at most $m\leq n$. ∎

##  VI Spectral gap of 1D Brickwork Loops

In order to extract a useful result from Theorem 7, we need a bound on the
spectral gap of the 1D brickwork architecture. In Section V we showed that the
$t$-design depth is controlled by the spectral gap of the transfer matrix. We
now reverse that argument in order to obtain a bound on the spectral gap in
terms of the $t$-design depth. This will allow us to convert all known results
on 1D brickwork $t$-design depths into bounds on the spectral gap.

######  Theorem 8.

Suppose that the 1D brickwork architecture on $N$ sites (with either open or
periodic boundary conditions) forms an $\epsilon$-approximate $t$-design after

$\displaystyle
k_{1}=C(N,q,t)\log\frac{1}{\epsilon}+o_{\epsilon}\left(\log\frac{1}{\epsilon}\right)$
(37)

periods (corresponding to depth $2k_{1}$), for some function $C(N,q,t)$. Then
the largest non-unit singular value $s_{\text{1D}}$ of the corresponding
transfer matrix $T_{t}$ is bounded by

$s_{\text{1D}}\leq e^{-\frac{1}{2C(q,t)}}$

where $C(q,t)=\sup_{N}C(N,q,t)$

###### Proof.

Define

$\Delta(k,t)=\Phi_{\text{RQC},k,t}-\Phi_{\text{Haar}}$

From the definition of the diamond norm

$||\Delta||_{\diamond}\geq||\Delta||_{1\rightarrow
1}\geq\frac{||\Delta(\rho)||_{1}}{||\rho||_{1}}$

for any operators $\rho$. Let $\lambda$ be the largest eigenvalue of the
$\Delta$ and choose $\rho$ to be the corresponding eigenvector, so that
$\Delta(\rho)=\lambda\rho$. Then we obtain

$||\Delta||_{\diamond}\geq|\lambda|$

Note that the leading eigenvalue of $\Delta$ is exactly the subleading
eigenvalue of $\Phi_{\text{RQC}}$, since the unit eigenspace of
$\Phi_{\text{RQC}}$ is exactly cancelled by $\Phi_{\text{Haar}}$. Furthermore,
$\widehat{\Phi}_{\text{RQC}}=T_{t}^{k}$, so we have

$\lambda=\lambda_{*}^{k}$

where $\lambda_{*}$ is the subleading eigenvalue of $T$. If we choose
$k=k_{1}$ so that

$||\Delta(k_{1},t)||_{\diamond}<\epsilon$

we obtain

$|\lambda_{*}|<\epsilon^{\frac{1}{k_{1}}}$

Inverting equation (12) gives

$\log\frac{1}{\epsilon}=\frac{k_{1}}{C(N,q,t)}+o_{k_{*}}(k_{*})$

or

$\epsilon=e^{-\frac{k_{1}}{C(N,q,t)}+o_{k_{1}}(k_{1})}$

We can now take the limit of small $\epsilon$ or equivalently large $k_{1}$ to
obtain

$\epsilon=\left(e^{-\frac{1}{C(N,q,t)}}\right)^{k_{1}}$

which implies $|\lambda_{*}|\leq e^{-\frac{1}{C(q,t)}}$. Theorem 13 of
Appendix A tells us $s_{\text{1D}}=\sqrt{\lambda_{*}}$, so we find
$s_{\text{1D}}\leq e^{-\frac{1}{2C(q,t)}}$ ∎

######  Theorem 9.

Let $s_{\text{1D,open}}(N)$ be the subleading singular value of the $N$-site
1D brickwork with open boundary conditions, and let
$s_{\text{1D,periodic}}(N)$ be the same for the periodic-boundary-conditions
case. Then $s_{\text{1D,periodic}}(N)\leq s_{\text{1D,open}}(N)$

This result allows us to also use bounds derived for open brickworks in
Theorem 7. It follows directly from the following more general rewriting rule
for cluster-merging graphs.

######  Lemma 8.

Consider a connected cluster-merging graph. If we add a new edge to the graph,
the subleading singular value $\mathscr{s}$ does not increase.

###### Proof.

Let $P$ and $Q$ be the edges and nodes of the original graph, and let $R$ be
the new link. Let $X$ be the unit eigenspace of $Q$ and $Z$ the unit
eigenspace of $PQ$. Since the graph was already connected without $R$, the
unit eigenspace of $R$ includes $Z$, so $Z$ is also the unit eigenspace of the
new graph $RPQ$. The original singular value is

$\mathscr{s}=\max_{\left\\{v\in X|v\perp Z\right\\}}\frac{||Pv||}{||v||}$

while the new singular value is

$\mathscr{s}^{\prime}=\max_{\left\\{v\in X|v\perp
Z\right\\}}\frac{||RPv||}{||v||}$

Since $R$ is an orthogonal projector, $||RPv||\leq||Pv||$, so
$\mathscr{s}^{\prime}\leq\mathscr{s}$. ∎

Given an open-boundary-condition transfer matrix, we can add a link to obtain
the transfer matrix of a periodic-boundary-condition brickwork on the same
number of sites. Adding a link can only decrease $\mathscr{s}$, which
completes the proof of Theorem 9.

##  VII Approximate $t$-design depths

###  VII.1 Complete periodic architectures

We are now ready to prove Theorem 1. Suppose that the $N$-site 1D brickwork
architecture forms an $\epsilon$-approximate $t$-design in depth at most

$\displaystyle
2C(N,q,t)\log\frac{1}{\epsilon}+o_{\epsilon}\left(\log\frac{1}{\epsilon}\right)$
(48)

Define $C(q,t)=\sup_{N}C(N,q,t)$. By Theorem 8 the subleading singular value
of $T_{t}$ for a brickwork loop is upper-bounded by

$\displaystyle s_{\text{1D}}\leq e^{-\frac{1}{2C(q,t)}}$ (49)

From Theorem 7 it follows that the SSV for any cluster-merging graph is
bounded by the same value. Substituting into Theorem 6, we see that the
subleading singular value for a complete $\ell$-layer block is bounded by

$\displaystyle s_{*}\leq 1-\left(1-e^{-\frac{1}{2C(q,t)}}\right)^{\ell-1}$
(50)

We can substitute into Equation 32 to see that the critical period count is
then bounded by

$\displaystyle k_{*}=\frac{2Nt\log
2q+\log\frac{1}{\epsilon}}{\log\left[\left(1-\left(1-e^{-\frac{1}{2C(q,t)}}\right)^{\ell-1}\right)^{-1}\right]}$
(51)

This completes the proof of Theorem 1.

###  VII.2 Incomplete layers

For complete architectures, we have

$\displaystyle s_{*}^{2}\leq 1-(1-s_{\text{1D}}(q))^{\ell-1}$ (52)

by reducing each cluster-merging graph to an Eulerian cycle. If the circuit is
incomplete, the Eulerian cycle is not guaranteed to exist. Instead, an
incomplete circuit with local dimension $q$ has subleading singular bounded by
that of a complete circuit with local dimension $\sqrt{q}$.

We may, without loss of generality, insert single-site gates so that each site
is acted upon by exactly one gate per layer. These single-site gates can be
absorbed into a two-site gate either above or below without changing the Haar
measure over that two-site gate. This takes an incomplete circuit to a
“complete” circuit with a mixture of one-site and two-site gates.

Now suppose that $\sqrt{q}$ is an integer. We can then split each site of
dimension $q$ into a pair of sites of dimension $\sqrt{q}$. This gives us a
complete circuit containing a mixture of $2$\- and $4$-site gates. Suppose we
split each $4$-site gate lengthwise into a pair of $2$-site gates. It seems
intuitive that this operation should decrease the rate of scrambling, not
increase it. And the resulting circuit is a complete circuit of $2$-site gates
with local dimension $\sqrt{q}$, so its cluster-merging graphs have Eulerian
cycles. In Appendix C, we formalize this intuition and show that the same idea
can be applied even in the case where $\sqrt{q}$ is not an integer. The site-
splitting process is illustrated in Fig. 5.

This allows us to reduce a bound on incomplete layers to a 1D brickwork bound
on $\sqrt{q}$, specifically

$\displaystyle s_{*}^{2}\leq 1-(1-s_{\text{1D}}(\sqrt{q}))^{\ell-1}$ (53)

for incomplete architectures.

We may use any proof of $C(q,t)$ if $\sqrt{q}$ is an integer. For non-integer
$\sqrt{q}$, however, the definition of $s_{\text{1D}}$ is trickier. It is not
necessarily true that generic bounds on $C(q,t)$ which have been derived for
integer $q\geq 2$ can be analytically continued to $C(\sqrt{q},t)$. Many of
the proofs in the literature can easily be extended to non-integer $q>1$ (see
Section I.5). However, not all of these proofs can be easily extended, e.g.
ref. 19 which applies only to $q=2$. The bound of ref. 16 can be extended, but
the scaling goes from $\sim t^{10}$ to $\sim t^{16}$. And there may be future
improved strategies for bounding 1D brickwork that work only for integer $q$.
We thus also give the following bound, which gives us a reduction in terms of
$C(q,t)$ instead of $C(\sqrt{q},t)$.

######  Theorem 10.

For an architecture with blocks of $\ell$ layers,

$\displaystyle
k_{*}=\big{(}4\overline{C}(q,t)\big{)}^{x(N)\ell-1}\left(2Nt\log
q+\log\frac{1}{\epsilon}\right)$ (54)

where the expansion coefficient

$\displaystyle x(N)=8\lceil\log_{2}\lfloor\log_{2}(N+1)\rfloor\rceil+2$ (55)

The proof is found in Appendix D.

###  VII.3 Aperiodic architectures

So far we have restricted ourselves to periodic architectures to simplify the
exposition. However, our results generalize quite directly to aperiodic
architectures.

######  Theorem 11.

Define $C(q,t)$ as in Theorem 1. For a not-necessarily-periodic $L$-layer
circuit $U_{C}$, choose a decomposition

$\displaystyle U_{C}=V_{k+1}U_{k}V_{k}U_{k-1}V_{k-1}...U_{1}V_{1}$ (56)

where each $U_{i}$ is a connected $\ell_{i}$-block and each $V_{i}$ is some
contiguous block of layers which may not connect all the sites. The
architecture is an $\epsilon$-approximate $t$-design if

$\displaystyle k\geq\frac{2Nt\log
q+\log\frac{1}{\epsilon}}{\log\frac{1}{s_{*}}}$ (57)

where we have defined the effective averaged singular value

$s_{*}=1-\left(1-e^{-\frac{1}{2C(\sqrt{q},t)}}\right)^{\bar{\ell}-1}$

in terms of the mean block size

$\bar{\ell}=\frac{1}{k}\sum_{i=1}^{k}\ell_{i}$

If we also require that the layers be complete, we can replace $\sqrt{q}$ with
$q$. Notice that $k$ counts the total number of times the circuit is
connected, while $\bar{\ell}$ is the size of the typical connected block. We
see that the $(\epsilon,t)$-design depth is controlled by the frequency and
size of the connected blocks. However, for a aperiodic architecture
$\bar{\ell}$ might depend on depth, so this does not give us any explicit
expression for the critical depth.

###### Proof.

A decomposition of the circuit into blocks of layers induces a decomposition
of the associated $t$-fold channel as

$\hat{\Phi}_{\text{RQC}}=R_{k}T_{k}R_{k-1}T_{k-1}...R_{1}T_{1}$

where the $R_{i}$ are some set of norm-nonincreasing transfer matrices. Let
$s_{*}^{(i)}$ be the subleading singular value of each $T_{i}$. Equation 50
still applies for each $s_{*}^{(i)}$, with $\ell$ replaced by $\ell_{i}$.555We
can further tighten the bound for certain architectures by observing that
$\ell_{i}$ only needs to count layers that merge clusters. Layers consisting
of only internal edges within already-merged clusters need not be counted.
Theorem 15 of Appendix A shows that the $R_{i}$ are essentially irrelevant.
Equation 31 now becomes

$\displaystyle||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}\leq
q^{2Nt}\prod_{i=1}^{k}s_{*}^{(i)}$ (58)

The condition to obtain an $\epsilon$-approximate $t$-design is then

$\displaystyle\epsilon\leq
q^{2Nt}\prod_{i=1}^{k}\left(1-\left(1-s_{\text{1d}}\right)^{\ell_{i}-1}\right)$
(59)

We may rearrange this as

$\displaystyle 2Nt\log
q+\log\frac{1}{\epsilon}\geq-\sum_{i=1}^{k}\log\left(1-\left(1-s_{\text{1d}}\right)^{\ell_{i}-1}\right)$
(60)

Furthermore, $-\log(1-c^{x})$ is convex, so by Jensen’s inequality

$\displaystyle 2Nt\log
q+\log\frac{1}{\epsilon}\geq-k\log\left(1-\left(1-s_{\text{1d}}\right)^{\bar{\ell}-1}\right)$
(61)

∎

This formula implies Theorem 2 as a special case. Furthermore, it is also
simple for regularly-connected architectures for which all of the $\ell_{i}$
are equal.

There is still a question of the choice of decomposition in Equation 56. This
decomposition is not unique; different choices of decomposition will give
different bounds. Note in particular that $V_{i}$ may be empty, which
corresponds to the identity.

Furthermore, the optimal decomposition may depend on $q$ and $t$. For example,
consider an architecture consisting of alternating connected $2$-blocks and
connected $4$-blocks. If we count all the blocks, then $\bar{\ell}=3$ and the
depth is $d=3k$. But if we count only the $2$-blocks and lump the $4$-blocks
into the $V_{i}$, we obtain $\bar{\ell}=2$ and $d=6k$. The former is better
for small $C$ and the latter for large $C$, with a crossover point
$C\left(\sqrt{q},t\right)\approx 1.157$.

##  VIII Further extensions

###  VIII.1 Tighter bound for incomplete layers

We suspect that neither of our currrent incomplete-architecture bounds are
tight. The subleading singular value is essentially determined by how tightly
connected the graph is. Any tree-shaped graph is “more connected” than a
linear graph on the same number of sites, in the sense that distances between
nodes are shorter and degrees of nodes are higher. This leads us to make the
following conjecture:

######  Conjecture 1.

Any cluster-merging tree on $N$ sites has subleading singular value

$\mathscr{s}\leq s_{\text{1D,open}}(q)$

where $s_{\text{1D,open}}(q)$ is the subleading singular value of the open-
boundary-condition 1D brickwork.

Numerical evidence for the conjecture is given in Appendix D. If it holds, our
Theorems 2-3 can be applied directly with $C_{\text{open}}(q,t)$ instead of
$\sqrt{q}$.

For $t=2$, where both values are known exactly, we have

$s_{\text{1D,open}}(q)=\frac{2q}{q^{2}+1}$

and

$s_{\text{1D,closed}}(\sqrt{q})=\frac{4q}{(q+1)^{2}}$

so that $s_{\text{1D,open}}(q)<s_{\text{1D,closed}}(\sqrt{q})$. One can prove
this in general using a site-merging argument analogous to that of Appendix C.
So this bound is also tighter than that of Theorem 2.

###  VIII.2 Nondeterministic architectures

Our theorems focus on deterministic architectures, in which the contents of
the gates are random but their arrangement is fixed. Another interesting class
of ensembles is nondeterministic architectures, in which the locations of the
gates are also random[16]. In this case, the $t$-design property is obtained
by averaging over both the spatial arrangement of the gates and their content.
Bounds on nondeterministic and deterministic architectures can often be
related to each other by the union bound or detectability lemma[21, 19].

We can also show more directly that bounds for particular spatial structures
imply bounds for averages over ensembles of structures. We use the triangle
inequality on $||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}$, where
$\Phi_{\text{RQC}}$ is drawn from some distribution $\rho_{\Phi}$. Then

$\displaystyle||\langle\Phi_{\text{RQC}}\rangle_{\rho_{\Phi}}-\Phi_{\text{Haar}}||_{\diamond}\leq\left\langle||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}\right\rangle_{\rho_{\Phi}}$
(64)

In particular Equation 59 with the right-hand side replaced with its average
over the architecture. We can use Jensen’s inequality again to see

$\displaystyle\log\left\langle||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}\right\rangle_{\rho_{\Phi}}\leq\left\langle\log||\Phi_{\text{RQC}}-\Phi_{\text{Haar}}||_{\diamond}\right\rangle_{\rho_{\Phi}}$
(65)

so we can also apply Equation 61 with the right-hand side replaced by its
average.

The connection count $k$ and mean block size $\bar{\ell}$ will both differ
between realizations, and it is not clear that there is any general strategy
for calculating their distribution. Presumably they are not independent, so we
can’t solve Equation 61 for $\langle k\rangle$. An interesting open question
is whether there exists any simple relationship between the averaged bound and
the distribution from which the circuit structure is drawn.

A commonly-studied example is that of gates which are drawn sequentially from
some a uniform distribution over some set of pairs of sites [16, 19, 17]. In
the worst case, such circuits may require $N-1$ nontrivial layers to connect
all the sites666The upper bound is $N-1$ because we ignore layers with
completely disconnected cluster-merging graphs.. However, typical instances
probably require far fewer distinct layers, perhaps as few as $O(1)$. Further
work may wish to explore the relationship between bounds obtained by this
strategy and known bounds for such architectures [17].

###  VIII.3 Highly-connected architectures

Previous work on random circuits[16, 18, 19, 14] has focused largely on
brickwork architectures. Brickwork architectures are in some sense
exceptionally well-connected, so they should be expected to converge to the
Haar distribution relatively quickly. Indeed, ref. [22] shows that in certain
weak convergence measures, higher-dimensional brickwork circuits approach the
Haar measure at a rate that increases with geometric dimension, which
corresponds to increasing the period $\ell$ of the architecture. Here we
suggest an extension of our techniques to obtain tighter bounds for such
special architectures.

The first observation is that highly-connected cluster-merging graphs give
small $\mathscr{s}_{i}$. Certain families of $N$-site architectures form
clusters of sizes which scale with $N$ after only a few layers. If we join two
$m$-site clusters with $m$ gates, Appendix E shows that the subleading value
is $q^{-\Omega(m)}$ as $m\rightarrow\infty$. In other words, any layers which
only join clusters with an extensive number of edges do not contribute to our
bound.

For the specific case of higher-dimensional brickwork circuits and $t=2$, we
can give a more explicit calculation. The first $D$ (“even”) layers of the
$D$-dimensional brickwork form hypercube clusters of size $2^{D}$. The $D+1$th
layer, which is the first “odd” layer, then connects these hypercubes into
rows of $2^{D}N^{\text{1/D}}$ sites. The remaining odd layers are then highly
connected, so in the limit of large $N$ their contribution can be ignored.
This argument, given in detail in Appendix E, shows that the
$(\epsilon,t=2)$-design depth of the $D$-dimensional brickwork is at most

$\displaystyle d_{*}=2D\frac{4N\log
q+\log\frac{1}{\epsilon}}{\log\left[\left(1-\left(1-\exp\left(-\frac{1}{2C(q,2)}\right)\right)^{2}\right)^{-1}\right]}$
(66)

It seems likely that this argument could be improved to give a bound that
actually decreases with $D$, since the dominant $D+1$th-layer cluster-merging
graph has a relatively simple structure. It also may be possible to extend
such techniques to larger $t$ and for other extensively-connected
architectures.

##  IX Conclusion

We show that bounds on approximate $t$-designs for 1D brickworks imply bounds
for general architectures. This process not only gives us an immediate bound
linear in $N$ for the $t$-th moments of all sufficiently well-connected
architectures, but allows us to convert any improved 1D bounds into bounds on
generic structures. We also show that our bounds can be extended by an
averaging procedure to an implicit bound for nondeterministic architectures.

Any architecture consisting of connected $\ell$-blocks of $O(1)$ depth can be
bounded this way. So our result implies that any sufficiently regularly-
connected circuit ensemble approximates global information scrambling in at
most linear depth.

It is interesting to note that our Theorem 1 gives a bound that loosens as the
period $\ell$ increases. It seems likely that the approximate $t$-design depth
actually decreases[14] with $\ell$ for certain well-connected structures, such
as higher-dimensional brickworks. The scaling of our bound, which is
determined by worst-case architectures, suggests that there may exist other
“tenuously connected” architectures at larger $\ell$. Whether or not such
adversarial examples can actually be found is an interesting open question.

Note added: During the final stages of completing the present manuscript, we
became aware of a related parallel independent work with similar results on
nondeterministic architectures which will appear in the same arXiv posting
[23].

###### Acknowledgements.

We acknowledge useful conversations with Nicholas Hunter-Jones. D.B.
acknowledges Felix Leditzky for suggesting relevant literature. This material
is based upon work supported by the U.S. Department of Energy, Office of
Science, National Quantum Information Science Research Centers. B.F. and S.G.
acknowledge support from AFOSR (FA9550-21-1-0008) and DOE QuantISED grant DE-
SC0020360. This material is based upon work partially supported by the
National Science Foundation under Grant CCF-2044923 (CAREER).

## References

  * [1] Joseph Emerson, Robert Alicki, and Karol Zyczkowski.  Scalable noise estimation with random unitary operators.  Journal of Optics B: Quantum and Semiclassical Optics, 7(10), 2005.
  * [2] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson.  Characterizing quantum gates via randomized benchmarking.  Physical Review A, 85(4):042311, 4 2012.
  * [3] Patrick Hayden, Debbie Leung, Peter W. Shor, and Andreas Winter.  Randomizing quantum states: Constructions and applications.  Communications in Mathematical Physics, 250(2):371–391, 7 2003.
  * [4] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  Nature Physics, page 1, 2018.
  * [5] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani.  On the complexity and verification of quantum random circuit sampling.  Nature Physics, 15(2):159–163, 2019.
  * [6] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  In Ryan O’Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 22:1–22:67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [7] Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu.  Noise and the frontier of quantum supremacy.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1308–1317. IEEE, 2021.
  * [8] Patrick Hayden and John Preskill.  Black holes as mirrors: quantum information in random subsystems.  Journal of High Energy Physics, 2007(09):120, 9 2007.
  * [9] Yasuhiro Sekino and L. Susskind.  Fast scramblers.  Journal of High Energy Physics, 2008(10):065, 10 2008.
  * [10] Patrick Hayden, Sepehr Nezami, Xiao Liang Qi, Nathaniel Thomas, Michael Walter, and Zhao Yang.  Holographic duality from random tensor networks.  Journal of High Energy Physics, 2016(11), 2016.
  * [11] Brian Skinner, Jonathan Ruhman, and Adam Nahum.  Measurement-Induced Phase Transitions in the Dynamics of Entanglement.  Physical Review X, 9(3), 2019.
  * [12] Yunxiang Liao and Victor Galitski.  Effective Field Theory of Random Quantum Circuits.  Entropy, 24(6), 2022.
  * [13] Joseph Emerson, Etera Livine, and Seth Lloyd.  Convergence conditions for random quantum circuits.  Physical Review A - Atomic, Molecular, and Optical Physics, 72(6), 2005.
  * [14] Aram W. Harrow and Richard A. Low.  Random quantum circuits are approximate 2-designs.  Communications in Mathematical Physics, 291(1):257–302, 2009.
  * [15] Andris Ambainis and Joseph Emerson.  Quantum t-designs: T-wise independence in the quantum world.  Proceedings of the Annual IEEE Conference on Computational Complexity, pages 129–140, 2007.
  * [16] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki.  Local Random Quantum Circuits are Approximate Polynomial-Designs.  Communications in Mathematical Physics, 346(2):397–434, 2016.
  * [17] Michał Oszmaniec, Michał Horodecki, and Nicholas Hunter-Jones.  Saturation and recurrence of quantum complexity in random quantum circuits.  arXiv preprint arXiv:2205.09734, 2022.
  * [18] Nicholas Hunter-Jones.  Unitary designs from statistical mechanics in random quantum circuits.  arXiv preprint arXiv:1905.12053, 2019.
  * [19] Jonas Haferkamp.  Random quantum circuits are approximate unitary t-designs in depth O(nt5+o(1)).  Quantum, 6, 2022.
  * [20] Winton G. Brown and Lorenza Viola.  Convergence rates for arbitrary statistical moments of random quantum circuits.  Physical Review Letters, 104(25):250501, 6 2010.
  * [21] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani.  Quantum Hamiltonian complexity and the detectability lemma.  arXiv preprint arXiv:1011.3445, 2010.
  * [22] Aram W. Harrow and Saeed Mehraban.  Approximate Unitary t-Designs by Short Random Quantum Circuits Using Nearest-Neighbor and Long-Range Gates.  Communications in Mathematical Physics, 401(2):1531–1626, 2023.
  * [23] Shivan Mittal and Nicholas Hunter-Jones.  Local random quantum circuits form approximate designs on arbitrary architectures.  2023\.
  * [24] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G.S.L. Brandão.  Random Quantum Circuits Anticoncentrate in Log Depth.  PRX Quantum, 3(1):10333, 2022.

##  Appendix A Properties of projector products

In this section we prove some general results about products of orthogonal
projection operators. Consider some set of subspaces $X_{i},i\in\\{1...n\\}$
of a Hilbert space. Define $P_{i}$ to be the orthogonal projector on to
$X_{i}$ and

$T=P_{n}...P_{2}P_{1}$

In general we are interested in understanding the singular value spectrum of
$T$.

###  A.1 Structure of the unit eigenspace

######  Lemma 9.

The left unit eigenspace, right unit eigenspace, and unit singular value space
of $T$ are all $\bigcap_{i=1}^{n}X_{i}$.

###### Proof.

Let $Y$ be the unit eigenspace of $T$. A projector is norm-nonincreasing (i.e.
$||P_{i}||_{\infty}=1$). Furthermore, it acts as the identity on any vector
whose norm it does not decrease. It follows that a unit eigenvector of $T$
must be a unit eigenvector of each of the $P_{i}$. It’s easy to see that the
converse also holds, so $Y=\bigcap_{i=1}^{n}X_{i}$. This argument works the
same from the left and the right, so the left and right unit eigenspaces are
the same.

Now consider the singular value spaces of $T$. These are the square roots of
the eigenvalues of $T^{\dagger}T$. Since the left and right eigenspaces are
the same, they are in the unit eigenspace of $T^{\dagger}T$. Since both
$T^{\dagger}$ and $T$ are norm-nonincreasing, they must be the whole unit
eigenspace. So the unit singular-value-space of $T$ is exactly the unit
eigenspace. ∎

######  Lemma 10.

The unit eigenspace of $T$ is orthogonal to all other eigenstates of $T$, all
other eigenstates of $T^{\dagger k}T^{k}$, and remains orthogonal no matter
how many factors of $T$ or $T^{\dagger}$ are applied to the other eigenstate.

###### Proof.

From Lemma 9 we know that the left and right unit eigenspaces of $T$ are the
same. Let $u$ be a unit eigenvector and $v$ a right-eigenvector with
eigenvalue $\lambda<1$. We can compute

$u^{\dagger}v=u^{\dagger}Tv=\lambda u^{\dagger}v$

which can hold only if $u^{\dagger}v=0$. So $Y$ is orthogonal to every non-
unit eigenspace of $T$.

Since $T^{\dagger k}T^{k}$ is Hermitian, its eigenstates of different
eigenvalues are automatically orthogonal, so $u^{\dagger}v=0$ for any subunit
eigenstates $v$ of $T^{\dagger k}T^{k}$.

These proofs still hold if we apply extra factors of $T$ or $T^{\dagger}$ to
$v$, because we can freely absorb these extra factors into $u$.

∎

###  A.2 Bound from layer-restricted subleading singular values

######  Theorem 12.

Let $Q_{i}$ to be the orthogonal projector on to $\bigcap_{j=1}^{i}X_{i}$. Let
$\mathscr{s}_{i}$ be the largest non-unit singular value of $P_{i}Q_{i-1}$.
Let $s_{*}$ be the largest non-unit singular value of $T$. Then we have the
bound

$\displaystyle s_{*}^{2}\leq 1-\prod_{i=2}^{n}(1-\mathscr{s}_{i}^{2})$ (68)

###### Proof.

This is Theorem 6 of the main text. We will prove Equation 68 by induction.
Let $T_{i}=P_{i}...P_{1}$ so that $T=T_{n}$. Suppose that $T_{i-1}$ satisfies
equation 68. We will prove that $T_{i}=P_{i}T_{i-1}$ also satisfies 68.
Let $Y_{i}$ be the unit eigenspace of $T_{i}$. Let $v$ be a unit vector such
that $||T_{i}v||=s_{*}(T_{i})$. We may take an orthogonal decomposition
$v=v_{1}+v_{2}$, where $v_{1}\in Y_{i-1}$ and $v_{2}\perp Y_{i-1}$. We wish to
compute

$s_{*}(T_{i})=||P_{i}T_{i-1}v||=||P_{i}(v_{1}+T_{i-1}v_{2})||$

Let $n_{i}=||v_{i}||$ and let $\theta,\phi$ be the angles between $T_{i}v$ and
$v_{1},Mv_{2}$, respectively. Note that $||T_{i-1}v_{2}||\leq
s(T_{i-1})n_{2}$. Then

$\displaystyle||P_{i}(v_{1}+T_{i-1}v_{2})||\leq||v_{1}||\cos\theta+s_{*}(T_{i-1})||v_{2}||\cos\phi$
(69)

We next wish to optimize this bound over $||v_{1}||,||v_{2}||,\theta,\phi$ to
obtain an unconditional bound. Our first constraint is
$||v_{1}||^{2}+||v_{2}||^{2}=1$, so after optimizing over the norms we find

$||P_{i}(v_{1}+Mv_{2})||\leq\sqrt{\cos^{2}\theta+s_{*}(T_{i-1})^{2}\cos^{2}\phi}\equiv
f(\theta,\phi)$

Now we optimize over the angles. By their definition we must have
$0\leq\theta\leq\frac{\pi}{2}$ and likewise for $\phi$. Notice that $f$ is a
monotonically decreasing function of both $\theta$ and $\phi$ in this region,
so the maximum will be attained somewhere on the boundary of the feasible set.

We also have some additional constraints. Since $v_{1}\perp Mv_{2}$, we must
have $\theta+\phi\geq\frac{\pi}{2}$. And we know that the angle between
$v_{1}$ and $P_{i}$ must be at least $\cos^{-1}\mathscr{s}_{i}$ by the
definition of $\mathscr{s}_{i}$.

The Pareto frontier where both $\theta$ and $\phi$ are as small as possible
lies along $\theta+\phi=\frac{\pi}{2}$, so the optimum must be somewhere on
this line. On this line we have $\cos^{2}\phi=1-\cos^{2}\theta$, so

$f(\theta)=\sqrt{(1-s_{*}(T_{i-1})^{2})\cos^{2}\theta+s_{*}(T_{i-1})^{2}}$

Since $s_{*}(T_{i-1})<1$ this is again a decreasing function of $\theta$, so
it attains its maximum when $\theta$ is minimized, i.e.
$\theta=\cos^{-1}\mathscr{s}_{i}$. We thus find

$s_{*}(T_{i})\leq\sqrt{(1-s_{*}(T_{i-1})^{2})\mathscr{s}_{i}^{2}+s_{*}(T_{i-1})^{2}}$

By assumption $s_{*}(T_{i-1})^{2}\leq
1-\prod_{j=2}^{i-1}(1-\mathscr{s}_{j}^{2})$ and so

$\displaystyle s_{*}(T_{i})^{2}$
$\displaystyle\leq\mathscr{s}_{i}^{2}+(1-\mathscr{s}_{i})^{2}\left(1-\prod_{j=2}^{i-1}(1-\mathscr{s}_{j}^{2})\right)$
$\displaystyle\leq 1-\prod_{j=2}^{i}(1-\mathscr{s}_{j}^{2})$ (73)

completing the induction. Finally, for the base case, $T_{1}$ is a single
projector, so $s_{*}(T_{1})=0$. ∎

###  A.3 Other bounds on subleading singular values

######  Lemma 11.

Let $s_{*}$ be the largest non-unit singular value of $T$. Let $\lambda_{*}$
be the non-unit eigenvalue of $T$ with the largest magnitude. Then

$|\lambda_{*}|\leq s_{*}$

###### Proof.

We may write

$s_{*}=\max_{\left\\{v|v\perp Z\right\\}}\frac{||Tv||}{||v||}$

Let $v$ be an eigenvector of $T$ with eigenvalue $\lambda\neq 1$. From before
$v\perp Z$, and clearly $\frac{||Tv||}{||v||}=\lambda$, so we have
$s_{*}\geq\lambda$. The lemma follows immediately. ∎

######  Theorem 13.

Consider two projectors $P_{1},P_{2}$. Let $\lambda_{*}$ be the largest non-
unit eigenvalue of $P_{2}P_{1}$ and let $s_{*}$ be the largest non-unit
singular value. Then

$s_{*}=\sqrt{\lambda_{*}}$

###### Proof.

Any eigenvector $v_{*}$ corresponding to $\lambda_{*}$ must lie in the unit
eigenspace of $P_{2}$. Otherwise, the output $P_{2}P_{1}v_{*}$ will not be
parallel to $v_{*}$. Also, if we take the vector $w_{*}\equiv P_{1}v_{*}$, by
Lemma 10 this vector is orthogonal to the unit eigensapce of $P_{2}P_{1}$, and

$\displaystyle\frac{||P_{2}P_{1}w_{*}||^{2}}{||w_{*}||^{2}}$
$\displaystyle=\frac{v_{*}^{T}P_{1}P_{2}^{2}P_{1}v_{*}}{v_{*}^{T}P_{1}v_{*}}$
$\displaystyle=\frac{\lambda_{*}^{2}}{v_{*}^{T}(P_{2}P_{1}v_{*})}$
$\displaystyle=\lambda_{*}$ (77)

So the subleading singular value of $P_{2}P_{1}$ is at least
$\sqrt{\lambda_{*}}$.

Now, take $w_{*}$ to be the subleading eigenvector of
$(P_{2}P_{1})^{\dagger}(P_{2}P_{1})=P_{1}P_{2}P_{1}$. By definition the
corresponding eigenvalue is $s_{*}^{2}$. Take $v_{*}=P_{2}P_{1}w_{*}$ (still
orthogonal to the unit eigenspace of $P_{2}P_{1}$ by Lemma 10). Then

$\displaystyle P_{2}P_{1}v_{*}$ $\displaystyle=P_{2}P_{1}^{2}P_{2}P_{1}w_{*}$
$\displaystyle=s_{*}^{2}P_{2}P_{1}w_{*}$ $\displaystyle=s_{*}^{2}v_{*}$ (78)

We see that the subleading eigenvalue of $P_{2}P_{1}$ is at least $s_{*}^{2}$.
Combining these two inequalities establishes Theorem 13. ∎

######  Lemma 12.

Let $T_{i},i\in\\{1...k\\}$ be a sequence of projector products that all share
the same unit eigenspace. Let $s_{*}^{(i)}$ be the largest non-unit singular
value of $T_{i}$. Then the largest non-unit singular value of
$\prod_{i=1}^{k}T_{i}$ is at most $\prod_{i}s_{*}^{(i)}$.

###### Proof.

Let $[M]_{1}$ denote the unit singular value space of $M$, and let
$M_{j}=\prod_{i=j}^{k}T_{i}$ We can write the subleading singular value of
$M_{k}$ as

$s(M_{j})=\max_{v\perp\left[M_{j}\right]_{1}}\frac{||M_{j}v||}{||v||}$

Since the $T_{i}$ all share a unit eigenspace, the unit eigenspace of $M_{j}$
is the same as that of each $T_{i}$. But by Lemma 9, the unit eigenspaces and
unit singular value spaces of both $T_{i}$ and $M_{j}$ are the same, so

$\left[M_{j}\right]_{1}=[T_{1}]$

We thus have

$s(M_{j})=\max_{v\perp[T]_{1}}\frac{||M_{j}v||}{||v||}$

Furthermore,

$||M_{j}v||=||M_{j+1}T_{j}v)||\leq S_{j}||M_{j+1}v||$

and so

$s(M_{j})\leq s_{*}^{(j)}s(M_{j+1})$

Induction then gives the desired bound. ∎

###  A.4 Bounds on Frobenius norms

######  Lemma 13.

Let $T$ be a projector product with largest non-unit singular value $s_{*}$.
Let $d$ be the dimension of the space on which $T$ acts, let $m_{1}$ be the
dimension of the unit eigenspace of $T$, and let $m_{0}$ be the dimension of
the zero eigenspace. Then

$||T^{k}||_{F}^{2}\leq m_{1}+(d-m_{1}-m_{0})s_{*}^{2}$

###### Proof.

Let $\sigma_{i}$ be all the singular values of $T$. We have $\sigma_{i}=1$ for
$i\in\\{1...m_{1}\\}$, $\sigma_{j}\leq s_{*}$ for
$i\in\\{m_{1}+1...d-m_{0}\\}$, and $\sigma_{k}=0$ for $i\\{\in
d-m_{0}+1...d\\}$. We compute

$||T||_{F}^{2}=\sum_{i}\sigma_{i}^{2}\leq\sum_{i=1}^{m}1+\sum_{i=m+1}^{d-m_{0}}s_{*}^{2}$

from which the result follows immediately. We can further tighten the bound by
replacing $d$ with the number of nonzero singular values. ∎

######  Theorem 14.

Let $T_{i},i\in\\{1...k\\}$ be a sequence of projector products that all have
the same unit eigenspace. Let $d$ be the dimension of the space on which
$T_{i}$ acts, let $m_{1}$ be the dimension of the unit eigenspace of $T_{i}$,
and let $m_{0}$ be the dimension of the zero eigenspace of any particular
$T_{i}$. Let $s_{*}^{(i)}$ be the largest non-unit singular value of $T_{i}$.
Then

$\displaystyle\left|\left|\prod_{i}T_{i}\right|\right|_{F}^{2}\leq
m_{1}+(d-m_{1}-m_{0})\prod_{i=1}^{k}\left(s_{*}^{(i)}\right)^{2}$ (86)

###### Proof.

This follows directly from the results of lemmas 12 and 13. ∎

######  Theorem 15.

Let $T_{i},s_{*}^{(i)},d,m_{1},m_{0}$ be as in Theorem 14. Let $R_{1}...R_{n}$
be a sequence of projector products such that the unit eigenspace of $T_{1}$
is contained within the unit eigenspace of each $R_{i}$. Let $M$ be the
product of all of the $T_{i}$ and all of the $R_{i}$ in any ordering. Then

$\displaystyle||M||_{F}^{2}\leq
m_{1}+(d-m_{1}-m_{0})\prod_{i=1}^{k}\left(s_{*}^{(i)}\right)^{2}$ (87)

###### Proof.

The $R_{i}$ also preserve the unit eigenspace of $T_{i}$ and are also norm-
nonincreasing, so the proof of Lemma 12 still goes through. We can then again
use Lemma 13 to obtain the final formula. ∎

######  Theorem 16.

Let $T$ be a projector product with largest non-unit singular value $s_{*}$.
Let $d,m_{1},m_{0}$ be as before. Then

$||T^{k}||_{F}^{2}\leq m_{1}+(d-m_{1}-m_{0})s_{*}^{2k}$

###### Proof.

This is an immediate consequence of Theorem 14 in the case where the $T_{i}$
are all the same. ∎

##  Appendix B Proof of the 1D brickwork spectral gap for $t=2$

For a string of $N$ sites which we act a 1D brickwork on, we can consider the
non-orthogonal basis

$\displaystyle|\vec{X}\rangle=\bigotimes_{i}|X_{i}\rangle_{i}$ (89)

where $X_{i}$ means the one of the two $k=2$ permutation states $|I\rangle$
(Identity) or $|S\rangle$ (Swap). This basis is complete on the image of any
layer of the brickwork. We start with

######  Lemma 14.

Take $P_{1}$ to be the projector into the unit eigenspace of $T$. Then there
exists a depth-independent constant $c_{X^{\prime}X}$ such that

$\displaystyle\langle\vec{X^{\prime}}|T^{k}|\vec{X}\rangle\leq\langle\vec{X^{\prime}}|P_{1}|\vec{X}\rangle+c_{X^{\prime}X}\lambda_{1}^{k}$
(90)

for every $k>\frac{\log(N)}{-\log(\lambda_{1})}+1$, where
$\lambda_{1}=\left(\frac{2q}{q^{2}+1}\right)^{4}$

Proof: We use a domain wall trajectory approach[24]. Each gate sends
$|II\rangle\rightarrow|II\rangle$, $|SS\rangle\rightarrow|SS\rangle$, and the
non-uniform $|IS\rangle,|SI\rangle\rightarrow
q/(q^{2}+1)(|II\rangle+|SS\rangle)$. The point is that the transfer matrix
sends each configuration into a sum of other configurations, depending on the
position of the I,S domain walls in the system. If a gate in the transfer
matrix crosses a domain wall (and all domain walls will be crossed by a gate
each layer after the 1st layer), it either moves left with weight
$q/(q^{2}+1)$ or right with weight $q/(q^{2}+1)$. So we can represent the
transfer matrix of $k$ layers as a series of domain wall trajectories with
their accompanying weights. A domain wall trajectory is a sequence of
$\vec{X}^{j}$’s such that $\vec{X}^{0}=\vec{X}$ and
$\vec{X}^{d}=\vec{X}^{\prime}$. Specifically we’re looking out for the domain
walls in each layer $\vec{X}^{j}$, because the total number of domain walls
never increases - each domain wall either moves around or annihilates with a
neighbor, possibly eventually reaching the steady states
$|I\rangle^{N},|S\rangle^{N}$ with no domain walls. We have, for domain wall
trajectories $\gamma$ with final state $F_{\gamma}$ and weight $w(\gamma)$,

$\displaystyle\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle=\sum_{\gamma}w(\gamma)\langle\vec{X}^{\prime}|F_{\gamma}\rangle$
(91)

We can categorize each domain wall trajectory according to which domain walls
annihilate before the end of the circuit and which remain to the end. We can
separate the total domain wall trajectory into the annihilating (“closed”)
domain walls $\gamma_{c}$ from the “open” domain wall trajectories
$\gamma_{o}$ that stay to the end. The weight of the whole domain wall
trajectory is just a product of the two components:

$\displaystyle w(\gamma)=w(\gamma_{o})w(\gamma_{c})$ (92)

Moreover

######  Lemma 15.

The final state $F_{\gamma}$ is determined solely by the open component of the
trajectory.

###### Proof.

If we look at one of the surviving domain walls, the I/S values to the
immediate left or right of the domain wall must remain the same through the
whole trajectory (otherwise the domain wall would be annihilated). Then the
rest of the final configuration can be determined by just flipping the sign
when crossing every other domain wall. Because the signs to the immediate left
and right of the domain wall were fixed by the original configuration
$\vec{X}$, there is no global symmetry ambiguity either. ∎

With this we can separate the sum (91) into a sum over the partitions $p$ that
specify which domain walls are closed and which remain open. The partition in
turn specifies the set of possible open and closed domain wall trajectories,
$\mathcal{O}(p)$ and $\mathcal{C}(p)$:

$\displaystyle\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle$
$\displaystyle=\sum_{p}\sum_{\gamma_{o}\in\mathcal{O}(p)}\sum_{\gamma_{c}\in\mathcal{C}(p)}w(\gamma_{o})w(\gamma_{c})\langle\vec{X}^{\prime}|F_{\gamma}\rangle$
(93)
$\displaystyle=\sum_{p}\sum_{\gamma_{o}\in\mathcal{O}(p)}w(\gamma_{o})\langle\vec{X}^{\prime}|F_{\gamma}\rangle\left(\sum_{\gamma_{c}\in\mathcal{C}(p)}w(\gamma_{c})\right)$
(94)

Now we start to bound things. Firstly,

######  Lemma 16.

$\sum_{\gamma_{c}\in\mathcal{C}(p)}w(\gamma_{c})$ is bounded by the infinite
depth limit, i.e. the sum of all the possible trajectories in an infinite
depth circuit that start at the domain walls specified by $p$ but annihilate
to either the uniform $|I\rangle$ or $|S\rangle$ states.

This is because $\mathcal{C}(p)$ is just a subset of all the possible closed
trajectories, and increasing the depth on a trajectory that’s already closed
doesn’t change its weight. The sum of weights in the infinite depth limit, in
turn, has to be

$\displaystyle\lim_{k\rightarrow\infty}\big{|}T^{k}|\vec{X}_{C}(p)\rangle\big{|}=\big{|}P_{1}|\vec{X}_{C}(p)\rangle\big{|}$
(95)

where $|\vec{X}_{C}(p)\rangle$ is the initial configuration given by only the
closed domain walls, and $P_{1}$ is the unit eigenspace projector. That is,
it’s the component of $|\vec{X}_{C}(p)\rangle$ in the unit eigenspace of $T$,
because the unit eigenspace is all that survives in the infinite depth limit.
Let’s call this infinite depth limit $W(p)$. We also have

######  Lemma 17.

$\displaystyle\sum_{\gamma_{o}\in\mathcal{O}(p)}w(\gamma_{o})\leq\left(\frac{2q}{q^{2}+1}\right)^{2N_{o}(k-1)}$
(96)

where $N_{o}$ is the number of open domain walls.

###### Proof.

We build up $\sum_{\gamma_{o}\in\mathcal{O}(p)}w(\gamma_{o})$ layer by layer.
At each layer beyond the first, each open trajectory $\gamma_{o}$ needs to
move each of its $N_{o}$ domain walls. Each domain wall has at most 2 possible
directions to move in (and could be less than 2 if other domain walls are
blocking the way). No matter the direction, the domain wall acquires a weight
$q/(q^{2}+1)$ by moving. So the total weight of all the possible trajectories
created by adding a layer onto $\gamma_{o}$ is at most
$w(\gamma_{o})\left(\frac{2q}{q^{2}+1}\right)^{N_{o}}$. A transfer matrix is
composed of two layers, so this is an extra factor of
$\left(\frac{2q}{q^{2}+1}\right)^{2N_{o}}$ per transfer matrix applied.
Extrapolating back to the first layer gives us the equation above. ∎

With these two inequalities, we have

$\displaystyle\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle$
$\displaystyle\leq\sum_{p}W(p)\sum_{\gamma_{o}\in\mathcal{O}(p)}w(\gamma_{o})\langle\vec{X}^{\prime}|F_{\gamma_{o}}\rangle$
(97)
$\displaystyle\leq\sum_{p}W(p)x_{F}\sum_{\gamma_{o}\in\mathcal{O}(p)}w(\gamma_{o})$
(98) $\displaystyle\leq\sum_{p}W(p)x_{F}\lambda_{1}^{\frac{1}{2}N_{o}(k-1)}$
(99)

For
$x_{F}\equiv\max_{\gamma_{o}\in\mathcal{O}(p)}\langle\vec{X}^{\prime}|F_{\gamma_{o}}\rangle$
and $\lambda_{1}=\left(\frac{2q}{q^{2}+1}\right)^{4}$. The RHS is now a
weighted sum of terms that are exponential in depth, with base
$\lambda_{1}^{\frac{1}{2}N_{o}}$ dependent on the number of open trajectories
in the partition. The gentlest exponential is the single partition where
$N_{o}=0$ and all the domain walls are closed - in that case $W(p)$ is the
component of $|\vec{X}\rangle$ in the unit eigenspace and
$\left[\max_{\gamma_{o}\in\mathcal{O}(p)}\langle\vec{X}^{\prime}|F_{\gamma_{o}}\rangle\right]$
is the component of $|\vec{X^{\prime}}\rangle$ in the unit eigenspace. This
term is therefore bounded by
$\lim_{k\rightarrow\infty}\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle$, which
by Lemma 2 is the same as $\langle\vec{X}^{\prime}|P_{1}|\vec{X}\rangle$

The rest of the partitions have $N_{o}\geq 2$ in periodic boundary conditions.
Hence they decay at a rate $\lambda_{1}^{k}$ or faster. Specifically, we have

$\displaystyle\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle\leq\langle\vec{X}^{\prime}|P_{1}|\vec{X}\rangle+c_{X^{\prime}X}\lambda_{1}^{k}$
(100)

for some depth-independent constant $c_{X^{\prime}X}$ (note that while
$\max_{\gamma_{o}\in\mathcal{O}(p)}\langle\vec{X}^{\prime}|F_{\gamma_{o}}\rangle$
is depth dependent, it’s bounded above by 1). Now we can prove that
$\lambda_{1}=\left(\frac{2q}{q^{2}+1}\right)^{4}$ genuinely is the subleading
eigenstate of $T$, using

######  Lemma 18.

For a complete basis $|\vec{X}\rangle$, if
$\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle\leq\langle\vec{X}^{\prime}|P_{1}|\vec{X}\rangle+c_{X^{\prime}X}\lambda_{1}^{k}$,
and
$\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle\geq\langle\vec{X}^{\prime}|P_{1}|\vec{X}\rangle$,
then $T^{k}$ has no eigenstate $|\psi_{2}\rangle$ with eigenvalue
$\lambda_{1}<\lambda_{2}<1$.

###### Proof.

Suppose there exists such an eigenstate $|\psi_{2}\rangle$. Then because
$|\vec{X}\rangle$ is complete, there must exist some $\vec{X}$ which has a
nonzero component of $|\psi_{2}\rangle$ in its eigenstate decomposition of $T$

$\displaystyle|\vec{X}\rangle=a_{1}|\psi_{1}\rangle+a_{2}|\psi_{2}\rangle+...,\qquad
a_{2}\neq 0$ (101)

Moreover, there must exist some $\vec{X^{\prime}}$ which has a nonzero overlap
with $|\psi_{2}\rangle$, i.e. $\langle\vec{X^{\prime}}|\psi_{2}\rangle\neq 0$.
Then we have

$\displaystyle\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle$
$\displaystyle=a_{1}1^{k}\langle\vec{X^{\prime}}|\psi_{1}\rangle+a_{2}\lambda_{2}^{k}\langle\vec{X^{\prime}}|\psi_{2}\rangle+...$
(102)
$\displaystyle=1^{k}\langle\vec{X^{\prime}}|P_{1}|\vec{X}\rangle+a_{2}\lambda_{2}^{k}\langle\vec{X^{\prime}}|\psi_{2}\rangle+...$
(103)

In particular, because $\lambda_{2}>\lambda_{1}$, for any constant
$c_{X^{\prime}X}$ there must be some $k$ for which
$\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle>\langle\vec{X}^{\prime}|P_{1}|\vec{X}\rangle+c_{1}\lambda_{1}^{k}$.
This is a contradiction of our assumption, so no such $\lambda_{2}$ can exist.

One caveat is that the eigenstate overlap
$a_{2}\langle\vec{X^{\prime}}|\psi_{2}\rangle$ could be negative instead.
Which is where the lower bound comes in - provided $\lambda_{2}$ is the
largest subleading eigenvalue, there must also exist some $k$ for which
$a_{2}\lambda_{2}^{k}\langle\vec{X^{\prime}}|\psi_{2}\rangle$ overtakes every
nonunit term in the sum and the lower bound is violated instead. This lower
bound is naturally satisfied in our case because $P_{1}$ is the infinite depth
limit of $T^{k}$, but $T$ is contractive, so adding more layers to
$\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle$ always decreases its norm.
Because it’s a sum of positive trajectories, it’s also positive, so the value
of $\langle\vec{X}^{\prime}|T^{k}|\vec{X}\rangle$ cannot increase as it goes
to $P_{1}$. ∎

Once we have $\lambda_{1}=\left(\frac{2q}{q^{2}+1}\right)^{4}$, by Lemma 11,
$s_{*}=\left(\frac{2q}{q^{2}+1}\right)^{2}$. Therefore, our trace decays at a
rate $C(q,2)=\frac{1}{2\log(1/s_{*})}=\frac{1}{4\log\frac{q^{2}+1}{2q}}$.

##  Appendix C Mapping incomplete to complete layers for non-integer
$\sqrt{q}$

If $\sqrt{q}$ is not an integer, we cannot draw Haar-random
$\sqrt{q}\times\sqrt{q}$ unitaries. There is thus no such thing as the 1D
brickwork circuit ensemble. So how can we apply the site-splitting trick used
in the proof of Theorem 2? Instead of defining $s_{\text{1D}}(q)$ to be the
subleading singular value of the transfer matrix corresponding to some
underlying circuit ensemble, we will define the transfer matrix directly.

The first step is to rephrase our site-splitting strategy from something done
in the quantum circuits to something done at the level of transfer matrices.
Consider a set of vector spaces labeled by a positive real-valued $r>1$:

$\displaystyle X_{r}=\text{span}\\{\ket{\sigma}_{r}|\;\sigma\in S_{t}\\}$
(104)

where each vector space is equipped with a basis $|\sigma\rangle_{X_{r}}$ and
an inner product

$\displaystyle\braket{\sigma}{\tau}_{r}=r^{\ell(\sigma\tau^{-1})}$ (105)

Here $\ell(\sigma)$ is the length of the cycle structure of $\sigma$. Now,
consider the mapping $V:X_{r}\rightarrow{X_{\\!\\!\\!\sqrt{r}}}^{\otimes 2}$
defined on basis elements by

$V\ket{\sigma}_{r}=\ket{\sigma}_{\sqrt{r}}^{\otimes 2}$

We first show that $V$ is an isometry. Compute

$\bra{\sigma}V^{\dagger}V\ket{\tau}=\braket{\sigma\sigma}{\tau\tau}_{\sqrt{r}}=\left(\sqrt{r}^{\ell(\sigma\tau^{-1})}\right)^{2}$

and

$\braket{\sigma}{\tau}_{r}=r^{\ell(\sigma\tau^{-1})}$

which are the same.

For each $X_{r}$, let us define the $k$-site gate
$G_{k}^{(X_{r})}:X_{r}^{\otimes k}\rightarrow X_{r}^{\otimes k}$ which is the
orthogonal projector on to the span of $\\{|\sigma\rangle_{r}^{\otimes
k}|\;\sigma\in S_{t}\\}$. We now observe the following:

######  Lemma 19.

If we replace every $G_{k}^{X_{r}}$ in the transfer matrix with
$G_{2k}^{{X_{\\!\\!\\!\sqrt{r}}}}$, the singular values do not change.

###### Proof.

From the definition of $V$, we see

$G_{k}^{X_{r}}=V^{\dagger\otimes k}G_{2k}^{{X_{\\!\\!\\!\sqrt{r}}}}V^{\otimes
k}$

We may thus rewrite the transfer matrix by replacing $G_{k}^{X_{r}}$ with the
above expression for each gate. Furthermore,
$VV^{\dagger}=G_{1}^{{X_{\\!\\!\\!\sqrt{r}}}}$. Factors of $G_{1}$ may be
absorbed into $G_{k}$ from either side, which means in particular

$G_{2k}^{{X_{\\!\\!\\!\sqrt{r}}}}=(VV^{\dagger})^{\otimes
k}G_{2k}^{{X_{\\!\\!\\!\sqrt{r}}}}=G_{2k}^{{X_{\\!\\!\\!\sqrt{r}}}}(VV^{\dagger})^{\otimes
k}$

We may thus pair up the copies of $V$ that appear on internal legs of the
transfer matrix and absorb them into the adjacent
$G_{2k}^{{X_{\\!\\!\\!\sqrt{r}}}}$. Copies of $V$ which appear on external
legs, meanwhile, are isometries and thus do not change the singular values of
the transfer matrix. ∎

If we return to our original transfer matrix, we see that we can identify each
site as a member of $X_{q}$, and each two-site gate as a copy of
$G_{2}^{X_{q}}$. Moreover, we can freely apply copies of $G_{1}^{X_{q}}$ (the
averaged one-site gate) to any site wherever we want, as it is just the
identity on that vector space. Now we apply the isomorphism $V$ to map each
site from an element of $X_{q}$ to an element of the doubled space
${X_{\\!\\!\\!\sqrt{q}}}^{\otimes 2}$ \- converting each site into a pair of
sites, or twinned sites, in the process. From Lemma 19, we see that the
transfer matrix can be rewritten in this new vector space, without changing
any singular values, by replacing $G_{k}^{X_{q}}$ with
$G_{2k}^{{X_{\\!\\!\\!\sqrt{q}}}}$ everywhere it appears.

In the particular case of an incomplete circuit, we obtain a transfer matrix
consisting of $G_{1}^{X_{q}}$ and $G_{2}^{X_{q}}$. We then apply the
isomorphism described above to map $G_{1}^{X_{q}}\rightarrow
G_{2}^{{X_{\\!\\!\\!\sqrt{q}}}}$ and $G_{2}^{X_{q}}\rightarrow
G_{4}^{{X_{\\!\\!\\!\sqrt{q}}}}$.

Figure 5: A two-site gate being split under the
$X_{q}\rightarrow{X_{\\!\\!\\!\sqrt{q}}}^{\otimes 2}$ isomorphism. Each site
on $X_{q}$ becomes a pair of twinned sites (pink dotted lines) on
${X_{\\!\\!\\!\sqrt{q}}}$. Note that the dimensionality of each site does not
necessarily decrease - only the metric between the basis vectors changes. If
we assume that the two-site gate spans two different clusters (blue dotted
circles), then the layer-restricted SSV of a hyperedge connecting all four
split sites is equal to two pairs of edges connecting non-twinned sites.

The former map sends $1$-site gates to $2$-site gates; these correspond to
edges across two twinned sites. The first layer of the original circuit
involved a one- or two-site gate acting on every site, so the split pairs
sites are always joined back into the same cluster by the first layer. The new
$4$-site gates are harder to express in the cluster-merging picture. However,
we know that a mini-circuit of $2$-site gates
$G_{2}^{{X_{\\!\\!\\!\sqrt{q}}}}$, applied in a way that connects all the
sites consistently, will approach $G_{4}^{{X_{\\!\\!\\!\sqrt{q}}}}$ in the
limit of infinite layers. In particular, we can replace each $4$-site gate
$G_{4}^{{X_{\\!\\!\\!\sqrt{q}}}}[a_{1},a_{2},b_{1},b_{2}]$ acting over sites
$a_{1}...b_{2}$ (where $a_{1}$ and $a_{2}$ are twinned, and so are $b_{1}$ and
$b_{2}$) with an arbitrarily large “Jenga tower” of the gates

$\displaystyle\left(G_{2}^{{X_{\\!\\!\\!\sqrt{q}}}}[a_{1},a_{2}]\otimes
G_{2}^{{X_{\\!\\!\\!\sqrt{q}}}}[b_{1},b_{2}]\right)\left(G_{2}^{{X_{\\!\\!\\!\sqrt{q}}}}[a_{1},b_{1}]\otimes
G_{2}^{{X_{\\!\\!\\!\sqrt{q}}}}[a_{2},b_{2}]\right)$

repeated over and over again. In the cluster-merging picture, only the bottom
layer of this tower is capable of joining distinct clusters together. The
other layers either join twinned sites which were part of the same cluster to
begin with, or are copies of the bottom layer. So every layer above the first
has a completely disconnected cluster-merging graph, which corresponds to
$\mathscr{s}=0$. These layers do not contribute to the right-hand side of
Theorem 6. So each $4$-site gate can be replaced with two $2$-site gates
connecting non-twinned members together without increasing the subleading
singular value of the transfer matrix. This process is illustrated in Fig. 5.

We see that we can replace the cluster-merging picture with one where every
site is replaced by twins on ${X_{\\!\\!\\!\sqrt{q}}}$, and every $2$-site
gate is replaced by a pair of $2$-site gates between non-twinned sites.
Moreover, we can freely apply $2$-site gates between any twinned members where
no gate was being originally applied. So all sites in the new picture have
two-site gates acting on them; the layer is complete. Since all twinned sites
belong to the same cluster, all clusters are of even size. These were the two
conditions required to draw an Eulerian cycle on each connected component of
the graph. We can now use Lemma 5 to reduce this graph to a periodic 1D
brickwork composed of gates $G_{2}^{{X_{\\!\\!\\!\sqrt{q}}}}$ acting on the
space ${X_{\\!\\!\\!\sqrt{q}}}^{\otimes 2N}$. Any previous work which has
found a bound for the $\sqrt{q}$ brickwork therefore imposes a bound on the
layer-restricted subleading singular values of arbitrary cluster-merging
graphs.

##  Appendix D Graph-splitting bounds for incomplete layers

In this section we consider strategies for bounding cluster-merging graphs
which originate from incomplete layers, without resorting to 1D brickwork
bounds on non-integer $q$.

###  D.1 Analytical bound in terms of node degree

By removing edges according to Lemma 8, we can reduce any connected cluster-
merging graph into a spanning tree. Let $d$ be the maximum degree of the tree.
To bound this tree’s singular value, we use the following tool for incomplete
graphs:

######  Lemma 20.

The edges of a cluster-merging graph can be split into separate layers without
lowering the subleading singular values.

###### Proof.

This follows from a simple reinterpretation of which gates belong to the same
layer. We know that the gates corresponding to each edge in the cluster-
merging graph commute with each other. Therefore, we are allowed to choose
which gates to apply first. Splitting a layer merely means choosing a subset
of gates to apply first, then choosing another subset to apply in the next new
layer, and so on. This does not lower the subleading singular values because
it does not change the gates at all. ∎

Note that splitting a layer will increase the block width $\ell$, which so our
bound on the subleading singular value of the overall transfer matrix via
Theorem 12 will get looser when a layer is split. Nonetheless, this will be
useful for separating the degree-$d$ tree graph into reducible parts:

######  Theorem 17.

A cluster merging graph of size $N$ with a spanning tree of maximum degree $d$
can be decomposed into at most

$\displaystyle 2\,\min\\!\left(\left\lceil
d/2\right\rceil,6\right)\lceil\log_{2}(N)\rceil$

layers, such that each layer is reducible to the 1D brickwork.

We will prove this statement starting with the similar

######  Lemma 21.

A cluster merging graph of size $N$ with a spanning tree of maximum degree $d$
can be decomposed into at most
$\min\left(\lceil\frac{d}{2}\rceil,6\right)\lceil\log_{2}(N)\rceil$ layers,
such that each layer is made up of isolated strings.

Call $L(N)$ the largest possible number of layers a tree of size $N$ needs to
be decomposed into to satisfy this. We will prove, by induction,
$L(N)\leq\min\left(\lceil\frac{d}{2}\rceil,6\right)\lceil\log_{2}(N)\rceil$.
We have $L(2)=1$ because two connected sites automatically form an isolated
string. It remains to show

######  Lemma 22.

$L(N)\leq
L\left(\lfloor\frac{N}{2}\rfloor\right)+\min\left(\lceil\frac{d}{2}\rceil,6\right)$

Proof. Take an arbitrary root node $C_{1}$ in our tree and construct a path
$C_{1}C_{2}...C_{r}$ starting from that root. At each step $i-1$ in the path,
we choose the child $C_{i}$ of parent $C_{i-1}$ with the most nodes in its
subtree. Call the other child nodes $b_{i}^{(1)},b_{i}^{(2)},...,b_{i}^{(g)}$,
where $g\leq d-2$.

For a given path node $C_{i-1}$, each non-path child
$b_{i}^{(1)},b_{i}^{(2)},...,b_{i}^{(g)}$ has at most
$\lfloor\frac{N}{2}\rfloor$ nodes in its subtree. We can therefore recursively
decompose each subtree in parallel in at most
$L\left(\lfloor\frac{N}{2}\rfloor\right)$ layers. After these layers, each
subtree of $b_{i}^{(j)}$ has been combined into $b_{i}^{(j)}$ to form one
cluster, $B_{i}^{(j)}$.

We then need to combine all $g$ child nodes $B_{i}^{(j)}$ into $C_{i-1}$. To
accomplish this in an efficient way, we use a method for efficient contraction
of high-degree nodes:

Figure 6: The star contraction of Lemma 23. We start with a star with $g$
external edges, meaning its site count (the numerical label of the node) is at
least $g$. In the first pair of layers (a), half of the edges are considered,
then the star node is split into a string of nodes, each with 2 external
edges. In the first layer, each node contracts with its 2 external edges in a
3-site string (Note that the site count on each node is just the minimum
number of sites required to have the correct degree on the node. Extra sites
can be placed in whatever node we want). In the 2nd layer, the resulting
string is contracted back into a single node, leaving a star with half the
edges remaining. The process is then repeated for the other half of the edges.

######  Lemma 23.

We can combine a node with $g$ of its external neighbors using at most 4
layers of isolated strings.

###### Proof.

To accomplish this, we combine our layer splitting process with a cluster
splitting process. The original node has a degree of $g$, so it must contain
at least $g$ sites. We first split the layer, with $\lfloor\frac{g}{2}\rfloor$
of the external neighbors on the bottom layer. This gives us a node with $g$
sites and $\lfloor\frac{g}{2}\rfloor$ edges. We then use Lemma 7 to split this
node into a string of nodes such that each node connects to $2$ of the
external neighbors (as shown by the first step in Fig. 6). Each node therefore
has $2$ external neighbors and at most $2$ new internal edges connecting it to
the other nodes in the string, so can be made with $4$ sites. The exceptions
are the end nodes which need one less site, and if $\lfloor\frac{g}{2}\rfloor$
is odd, one node will have one less neighbor and site. In total, at most
$4\lceil\frac{1}{2}\lfloor\frac{g}{2}\rfloor\rceil-2\leq g$ sites are
required, so there are enough unoccupied sites in the original node to add the
necessary new edges for this splitting.

Once we have split the original node in this way, we spend two layers to
combine all the neighbors and nodes together. In the first layer, each node in
the string combines with its two external neighbors, as together they form a
string of length 3 (Fig. 6, second step). With all the neighbors absorbed, the
string can be recombined into the original node in the second layer (Fig. 6,
third step).

We then spend two more layers to contract the remaining
$g-\lfloor\frac{g}{2}\rfloor$ neighbors. This is either
$\lfloor\frac{g}{2}\rfloor$ or $\lfloor\frac{g}{2}\rfloor+1$ depending on the
parity of $g$. Even if it’s the latter, we will have enough sites to contract
all the neighbors, due to the $\geq\lfloor\frac{g}{2}\rfloor$ extra sites the
root node gained by absorbing its previous neighbors. Therefore all neighbors
can be contracted in 4 layers. ∎

Note that Lemma 23 is inefficient if the number of leaves is 6 or less. This
is because we can also contract $g$ leaves in $\lceil\frac{g}{2}\rceil$
layers, by selecting one or two leaves in each layer and combining with
$C_{i-1}$ into a string of length $2$ or $3$. So the number of layers we have
to spend is
$\min(\lceil\frac{g}{2}\rceil,4)\leq\min(\lceil\frac{d}{2}\rceil-1,4)$
overall.

By performing all of these operations in parallel for each path node, we have
spent at most
$L\left(\lfloor\frac{N}{2}\rfloor\right)+\min(\lceil\frac{d}{2}\rceil-1,5)$
layers to combine each path node’s non-path children into the path node. After
these layers, the cluster-merging picture of the next layer only consists of
the path nodes, which can be combined together with a single, extra, layer.
This completes the proof of Lemma 22. ∎

We have seen that we can decompose the size-$N$ cluster into $L(N)$ layers
such that the cluster merging graph of each layer consists of isolated
strings. Each string can now be split into an open 1D brickwork, as long as
each internal node is of even size (endpoint nodes can be either odd or even),
using Lemma 5. We will call such strings brickwork-compatible. For strings
containing nodes which aren’t even and aren’t on the ends, we can use:

######  Lemma 24.

Any layer of isolated strings can be split into two layers of brickwork-
compatible strings.

###### Proof.

We wish to split a string into two layers such that both layers have cluster-
merging graphs consisting entirely of brickwork-compatible strings. Let $k$ be
the number of odd-sized nodes in the string and number only the odd nodes
$1...k$.

First suppose $k$ is even. Remove the left-hand edge, if any, of odd nodes
$1,3...k-1$ and the right-hand edge of odd nodes $2,4...k$. Now we have split
the string into at least $\frac{k}{2}$ and at most $\frac{k}{2}+2$ substrings,
each of which either has odd nodes only at both endpoints, or has no odd nodes
at all. Since the odd nodes were paired up, contracting the first layer gives
only even nodes for the second layer. So both layers are brickwork-compatible.

Now suppose $k$ is odd. Remove the left-hand edge, if any, of odd nodes
$1,3...k-1$ and the right-hand edge of odd nodes $2,4...k-1$. Every substring
has $2$ odd endpoints except the first, which may have $0$, and the last,
which has exactly $1$. After contracting, the second layer has all even nodes
except for one. But this one odd node is the right endpoint of the second-
layer string, so the second layer is still brickwork-compatible. ∎

Lemma 24 shows that we can make a set of layers of isolated strings brickwork-
compatible with a splitting scheme that at most doubles the number of layers.
Combining this with Lemma 21 completes the proof of Theorem 17.

###  D.2 Log log bound on arbitrary graphs

######  Theorem 18.

A cluster merging graph of size $N$ can be decomposed into at most

$\displaystyle 8\lceil\log_{2}\lfloor\log_{2}(N+1)\rfloor\rceil+2$

layers, such that each layer is reducible to the 1D brickwork.

Given Lemma 24, it is sufficient to prove we can decompose the graph into

$\displaystyle 4\lceil\log_{2}\lfloor\log_{2}(N+1)\rfloor\rceil+1$

layers of isolated strings.

We begin with a tree of at most $N$ sites (Fig. 7a, left). The first layer of
edges we apply will contract substrings of the tree such that the resulting
second-layer tree (Fig. 7a, right) has depth $O(\log N)$. Choose any root
node, which also specifies a direction in the tree from its root down to the
leaves. Then label each node by its subtree weight \- the number of nodes in
the subtree starting from that node. The root node has subtree weight $N$,
leaves have subtree weight $1$, and so on. We add to the first layer the
maximally weighted path starting from the root node, i.e. a path from root to
leaf that always selects the child node with the highest subtree weight. For
every node which neighbors this path (excluding nodes which are part of the
path), we take its subtree, add the maximally weighted path of that subtree to
the first layer, and repeat the process recursively. After the end of this
process, each node is part of exactly one maximally weighted path, so the
first layer consists of disconnected strings. We can also label each maximally
weighted path by a subtree weight, which in this case is the subtree weight of
the node at the start of the path.

After contracting all the paths added to the first layer this way, we are left
with a tree where each node corresponds to one of the maximally weighted
paths. We make the following claim:

a)b) Figure 7: Algorithm for reducing a general tree in $O(\log\log N)$
layers. (a): The first layer of the algorithm, where we contract the maximally
weighted paths. Each path chooses the child node with the highest subtree
weights (blue labels above each node), and starts from non-path children of
nodes in higher paths. (b): Contraction of a balanced tree into a point in
$O(\log\log N)$ steps. At each step, the nodes at depths $2k$ and $2k+1$ are
merged together through the star contraction algorithm (each star is indicated
by a blue dotted circle).

######  Lemma 25.

The height of the new tree is at most $\lfloor\log_{2}(N+1)\rfloor\rceil-1$.

###### Proof.

Suppose we start from a node of the new tree and jump down to one of its
children. This corresponds to jumping from one maximally weighted path on the
original tree to one of the paths below it.

Going back to the original tree, consider a maximally weighted path of a
particular single-root subtree consisting of $n$ nodes. The subtree weight of
the root is, by definition, $n$, and so is the subtree weight of the path
itself. Then any node which is one edge away from the maximally weighted path
(i.e. it is not part of the maximally weighted path, but its parent is) has a
subtree weight bounded above by $\lfloor\frac{n-1}{2}\rfloor$. We can prove
this by contradiction - it cannot be the root node, and the sum of the subtree
weights of it and all its sibling nodes must be $\leq n-1$. So if it had a
subtree weight greater than $\frac{n-1}{2}$, it would’ve had a larger subtree
than all of its siblings, and therefore would be part of the maximally
weighted path after all.

Every time we move from a maximally weighted path to a lower one, our subtree
weight roughly halves; specifically, it goes from $n$ to at most
$\lfloor\frac{n-1}{2}\rfloor$. If we repeat this process, we run out of nodes
after $\lfloor\log_{2}(n+1)\rfloor-1$ steps. Hence, the height of the whole
second-layer tree must be bounded by $\lfloor\log_{2}(N+1)\rfloor\rceil-1$. ∎

Now we reduce the second-layer tree with the following theorem:

######  Lemma 26.

A tree of height $h$ can be decomposed into $4\lceil\log_{2}(h+1)\rceil$
layers of isolated strings

###### Proof.

We decomposed the tree recursively. At each step, we take all the nodes which
are at an even depth (including the root node at depth 0). We can then use
Lemma 23 on each even-depth node to absorb all their children in parallel, in
at most $4$ layers (Fig. 7b, left). This way, after $4$ layers, we have
removed all the nodes which were at an odd depth. Hence, we are left with a
tree of height $\lceil\frac{h+1}{2}\rceil-1$ (Fig. 7b, right). We repeat this
process until we are left with a tree of height $0$, i.e. just the root node.
This takes $\lceil\log_{2}(h+1)\rceil$ steps, or $4\lceil\log_{2}(h+1)\rceil$
layers, in total. ∎

Hence, we can spend $1$ layer to reduce an arbitrary tree to a tree of height
$\lfloor\log_{2}(N+1)\rfloor-1$, then spend
$4\lceil\lfloor\log_{2}(N+1)\rfloor\rceil$ layers to reduce the new tree to a
single node, which proves Theorem 18.

###  D.3 Numerical evidence for stronger bound

Here we present weak numerical evidence for Conjecture 1. We have computed
subleading singular values to within numerical precision for $t=2$, $N\leq
32$, and five architectures: The linear graph, the comb graph, the binary
tree, the star graph, and the starlike tree with three branches. Results are
shown in Figure 8.

In all cases checked, the trees are bounded by the line graph of the same
size. Notice that this is tighter than the analytical bound of the previous
section. Furthermore, the singular value scales roughy with the degrees of the
nodes. The smallest singular values belong to the star, which has a node of
degree $\frac{N}{2}$. The line, which has nodes of degree at most $2$, gives
the largest singular values. The second-largest is the 3-star, for which only
one node is of degree $3$. This matches our intuition that the subleading
singular value should be smaller for more tightly connected graphs.

We can also interpret this intuition physically. The interactions between
nodes are essentially ferromagnetic; there is an energy penalty for differing
permutations with an edge between them. With longer paths (e.g. the line) it
is possible for a state to slowly rotate from one permutation on the left-hand
endpoint to another permutation at the right-hand endpoint. The slower the
rotation, the smaller the energy of the state, which is why longer strings
give larger $\mathscr{s}$. In any other graph, the rotation must occur in
fewer than $\frac{N}{2}$ steps; e.g. the $3$-branch starlike tree has only
$\sim\frac{N}{3}$ edges along a path between endpoints.

Figure 8: Subleading singular values vs. number of sites, shown for five types
of cluster-merging graphs and four values of $q$.

##  Appendix E Tighter bounds for brickworks of arbitrary dimension

For specific, well-connected architectures, we can use the cluster-merging
picture to obtain a tighter bound than that of Theorem 1. One example is the
generalized brickwork architectures on any dimension. We make the following
claim:

######  Lemma 27.

For $t=2$, the effective connection depth $\ell$ on a generalized
$d$-dimensional brickwork architecture on $L^{d}$ sites is at most
$2+o_{L}(1)$. That is, the subleading singular value

$s\leq 1-(1-s_{\text{1D}})^{2}+o_{L}(1)$

In other words, we have taken the $2d$ layers of a $d$-dimensional brickwork’s
periodic block, and have effectively removed all but two of them from
consideration in Theorem 6.

Each of the $2d$ layers in a brickwork’s periodic block chooses one of the $d$
directions (horizontal, vertical, etc.) and one of two parities (odd or even).
The cluster merging picture of these layers comes in three stages. In the
first stage, each layer has a different direction from all the layers below
it. These layers combine finite (i.e. $O(1)$) size clusters into other finite
size clusters. Each cluster after $m$ such layers is an $m$ dimensional
hypercube over $2^{m}$ sites. Depending on the order of the layers, this first
stage can have any number of layers from $1$ to $d$. The second stage begins
once a layer has the same direction as a previous layer below it. In this
stage, the hypercube clusters get strung together along this direction, $L/2$
at a time, forming loops that can be reduced to periodic 1D brickworks. This
stage consists of only one layer.

After this stage, each cluster is of size $\Omega(L)$. Subsequent layers will
connect these clusters either into pairs (if their same-direction counterpart
wasn’t applied yet) or $L/2$-length loops (if it was applied). Either way,
each cluster will have $\Omega(L)$ connections with each neighbor in the
graph. This effectively creates a 1D brickwork with internal dimension
$\tilde{q}=q^{\Omega(L)}$. Since the 1D brickwork singular value is
$\frac{2\tilde{q}}{\tilde{q}^{2}+1}=O(\tilde{q}^{-1})$, all of these layers
will have layer-restricted singular values which decay exponentially in $L$,
hence will contribute a vanishing amount $o_{L}(1)$ to Equation 33.

We have a second stage with one layer that reduces to the periodic 1D
brickwork, and a third stage with vanishing contribution. Therefore, it
remains to show that the combined subleading singular value of the first stage
layers is bounded by the 1D brickwork. In other words, we want to bound the
subleading singular value of an arbitrary hypercube by the 1D brickwork.

The subleading singular value of the $2$D hypercube (i.e. a square of four
sites) is $s_{2}=\frac{2q^{2}}{(q^{2}+1)^{2}}$. We can use the cluster merging
picture to bound hypercubes of higher dimension. At layer $m$, our clusters
are size $2^{m-1}$, and we are joining them together in pairs, with $2^{m-1}$
connections per pair. Since we only have two clusters in each connected
section of our graph, finding the layer-restricted singular value
$\mathscr{s}_{m}$ just amounts to an optimization over $4$ basis states. We
have

$\displaystyle\mathscr{s}_{m}$
$\displaystyle=\frac{1}{(1-q^{-2^{m}})^{2}}\sqrt{2(1+q^{-2^{m}})\left[\frac{2}{q^{2}+1}\right]^{2^{m-1}}-8q^{-2^{m}}}$
$\displaystyle\leq\sqrt{2}\left(\frac{16}{15}\right)\left(\frac{2}{q^{2}}\right)^{2^{m-2}}$
$\displaystyle\leq\sqrt{2}\left(\frac{16}{15}\right)\left(\frac{2}{q^{2}}\right)^{2(m-2)}$
(112)

where we bound the superexponential decay in $m$ by an exponential for all
$m\geq 3$. Then any $d\geq 3$-dimensional hypercube $s_{d}$ has singular
values bounded by

$\displaystyle s_{d}^{2}$ $\displaystyle\leq
1-(1-s_{2}^{2})\prod_{m=3}^{d}(1-\mathscr{s}_{m}^{2})$ $\displaystyle\leq
1-(1-s_{2}^{2})\exp\left[-\sum_{m=3}^{d}\mathscr{s}_{m}^{2}\right]$
$\displaystyle\leq
1-(1-s_{2}^{2})\exp\left[-2\left(\frac{16}{15}\right)^{2}\sum_{m=3}^{d}\left(\frac{2}{q^{2}}\right)^{4(m-2)}\right]$
$\displaystyle\leq
1-\left(1-\frac{4q^{4}}{(q^{4}+1)^{2}}\right)\exp\left[-2\left(\frac{16}{15}\right)^{2}\frac{16}{q^{8}-16}\right]$
(113)

This decays more rapidly in $q$ than the 1D brickwork, and at $q=2$ we get the
bound $s_{d}(2)\leq 0.478<s_{\text{1D}}(2)$. Therefore, the hypercube singular
value is below the 1D brickwork singular value for all $q\geq 2$.

A more thorough optimization over the size $M$ of the first stage will
probably get an overall singular value bound that is much closer to
$s_{\text{1D}}$. This is because the size, and connectivity, of the clusters
in the second stage is $q^{2^{M}}$, so it would probably produce a singular
value that is close to $O(q^{-2^{M}})$. In other words, we aren’t allowed to
make the first stage that deep, without reducing the layer-restricted singular
value of the second stage.