# Random quantum circuits are approximate unitary $t$-designs
in depth $O\left(nt^{5+o(1)}\right)$

Jonas Haferkamp  Dahlem Center for Complex Quantum Systems, Freie Universität
Berlin, Germany

###### Abstract

The applications of random quantum circuits range from quantum computing and
quantum many-body systems to the physics of black holes. Many of these
applications are related to the generation of quantum pseudorandomness: Random
quantum circuits are known to approximate unitary $t$-designs. Unitary
$t$-designs are probability distributions that mimic Haar randomness up to
$t$th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that
random quantum circuits in a brickwork architecture of depth $O(nt^{10.5})$
are approximate unitary $t$-design. In this work, we revisit this argument,
which lower bounds the spectral gap of moment operators for local random
quantum circuits by $\Omega(n^{-1}t^{-9.5})$. We improve this lower bound to
$\Omega(n^{-1}t^{-4-o(1)})$. A direct consequence of this scaling is that
random quantum circuits generate approximate unitary $t$-designs in depth
$O(nt^{5+o(1)})$. Our techniques involve Gao’s quantum union bound and the
unreasonable effectiveness of the Clifford group. As an auxiliary result, we
prove a near optimal convergence to the Haar measure for random Clifford
unitaries interleaved with Haar random single qubit unitaries in Wasserstein
distance.

Random unitaries and states are a ubiquitous concept in quantum information
theory and quantum many-body physics. This includes practial applications such
as randomized benchmarking EAZ (05); MGE (12); KLR+ (08) and mixing in black
holes HP (07). However, the applicability of uniformly (Haar) random unitaries
and states is limited by the fact that they require exponential resources as
counting arguments show Kni (95). It is therefore desirable to consider less
complex probability distributions over the unitary group that are sufficiently
random for practical purposes. This leads naturally to the notion of unitary
$t$-designs Dan (05); DCEL (09); GAE (07); AE (07). These are probability
distributions which mimic the Haar measure up to $t$th moments.

Naturally, there is an ongoing effort to find efficient constructions of
unitary $t$-designs CLLW (15); HL (09). In a seminal result, Brandão, Harrow
and Horodecki proved that local random quantum circuits are approximate
unitary $t$-designs after the application of $O(n^{2}t^{10.5})$ random gates
for all $t\leq O(2^{0.4n})$ BHH16a . This result has several consequences and
many results HM (18); OBK+ (17); NHKW (17); MGDM (18) on the design property
of random processes over the unitary group directly depend on the bound from
Ref. BHH16a .

Recently, unitary $t$-designs played a key role in lower bounding the quantum
circuit complexity BCHJ+ (21); BHH16b . Here, Ref. BCHJ+ (21) shows that
strong notions of quantum circuit complexity of a unitary $t$-design can be
lower bounded by $\Omega(nt)$ with high probability. Combined with the design
depth from Ref. BHH16a , this roughly implies that the complexity of most
quantum circuit of depth $T$ can be lower bounded by $\Omega(T^{1/10.5})$.
This line of research is inspired by the Brown-Susskind conjecture BS (18) in
the context of the AdS/CFT correspondence Sus (18). The conjecture states that
the quantum circuit complexity grows at a linear rate for an exponentially
long time. Indeed, Ref. BCHJ+ (21) implies such a linear lower bound in the
limit of large local dimension HJ (19) (it was later shown that a scaling of
$\sim 6t^{2}$ for the local dimension is sufficient HHJ (21)). More recently,
a variant of the Brown-Susskind conjecture for random quantum circuits was
proven for the special case of the exact circuit complexity HFK+ (21).
However, for error-robust (and therefore more operational) notions of quantum
circuit complexity and for random quantum circuits over qubits, the best lower
bound for exponentially long times is $\Omega(T^{1/10.5})$.

Here, we want to improve the scaling of the design depth in $t$. Indeed, the
scaling in $n$ is already optimal (up to logarithmic factors). It was
conjectured in Ref. BHH16a  that the true scaling of the design depth might be
linear in $t$, which would directly imply an error-robust version of the
Brown-Susskind conjecture BCHJ+ (21).

In this work, we dissect the bound obtained on the spectral gap of random
quantum circuits in Ref. BHH16a . We improve the lower bound on this spectral
gap from $\Omega(n^{-1}t^{-9.5})$ to $\Omega(n^{-1}t^{4+o(1)})$. Moreover,
this design depth holds for all $t\leq O(2^{n/(2+o(1))}$.

The lion’s share of the improvement is a new unconditional bound on the
spectral gap. We achieve this bound by considering an auxiliary random walk
that interleaves global uniformly random Clifford unitaries with Haar random
unitaries on a single qubit. This walk was introduced in Ref. HMMH+ (20) to
analyze the number on non-Clifford untiaries required to generate unitary
$t$-designs for small values of $t$ satisfying $O(t^{2})\leq n$. We show that
the path coupling technique on the unitary group Oli (09) provides a near
optimal convergence to the Haar measure for this auxiliary random walk. As the
Clifford group is a finite group with upper bounded circuit complexity, the
comparison technique from Ref. DSC (93) provides extremely fast mixing bounds,
which allows us to approximate the uniform measure on the Clifford group with
a local random walk. We then translate these bounds to a spectral gap for
local random quantum circuits by invoking Gao’s quantum union bound Gao (15);
AAV (16).

##  I Preliminaries

A central object of this paper is the moment superoperator defined with
respect to a probability distribution $\nu$ on the unitary group $U(d)$,
defined as

$\Phi_{\nu}^{(t)}(A):=\int U^{\otimes t}A(U^{\dagger})^{\otimes
t}\,\mathrm{d}\nu(U)\,.$ (1)

We denote the Haar-measure on the unitary group by $\mu_{H}$.

We make use of the following isomorphism called vectorization:
$\mathrm{vec}:\mathbb{C}^{D\times D}\to\mathbb{C}^{D^{2}}$ with
$\mathrm{vec}(|i\rangle\langle j|)=|i\rangle\otimes|j\rangle$. This
isomorphism extends to superoperators, mapping them to matrices:
$\mathrm{vec}(T)\mathrm{vec}(M):=\mathrm{vec}(T(M))$ for all
$M\in\mathbb{C}^{D\times D}$ for a superoperator $T$.

We introduce the following notation for the second highest eigenvalue of the
moment operator:

$g(\nu,t):=\big{\|}M(\nu,t)-M(\mu_{H},t)\big{\|}_{\infty}\,,$ (2)

where the $t$-th moment operator of a probability distribution is defined as

$M(\nu,t):=\mathrm{vec}\big{(}\Phi_{\nu}^{(t)}\big{)}=\int U^{\otimes
t}\otimes\overline{U}{}^{\otimes t}\,\mathrm{d}\nu(U)$ (3)

and $\|\bullet\|_{\infty}$ denotes the Schatten $\infty$-norm. The spectral
gap of the moment operator is $1-g(\nu,t)$. Notice that we defined the
spectral gap to be the difference between the first $t!$ eigenvalues and the
$(t!+1)$st eigenvalue of the moment operator. That means that for non-
universal probability distributions the gap can be $0$. A probability
distribution $\nu$ is called a $(\lambda,t)$-tensor product expander if the
spectral gap of the moment operator satisfies $1-g(\nu,t)\geq\lambda$.

Moreover, we denote the Schatten $1$-norm by $||\bullet||_{p}$ and the
Schatten $2$-norm/Frobenious norm by $||\bullet||_{F}$. The stabilized induced
(Schatten) $1$-norm – called diamond norm – of superoperators will be denoted
by $||\bullet||_{\diamond}$ AKN (98); Wat (18). Roughly, the distance between
channels in diamond norm quantifies the “one-shot” distinguishability using
entangled input states.

The second highest eigenvalue $g(\nu,t)$ can be amplified. Specifically, the
$k$-fold convolution of $\nu$ has the property that

$g(\nu^{*k},t)\leq g(\nu,t)^{k}\,.$ (4)

Upper bounds on the second highest eigenvalue can be used to imply an
approximate version of unitary designs BHH16a . We define approximate designs
in two (inequivalent) ways, with a relative error and with an exponentially
small additive error. The relation to the spectral gap turns out to be the
same.

######  Definition 1 (Approximate unitary designs).

a

  1. 1.

A probability distribution $\nu$ on $U(d)$ is an $\varepsilon$-approximate
unitary $t$-design if the moment superoperator obeys

$\big{\|}\Phi_{\nu}^{(t)}-\Phi_{\mu_{H}}^{(t)}\big{\|}_{\diamond}\leq\frac{\varepsilon}{d^{t}}\,.$
(5)

  2. 2.

A probability distribution $\nu$ on $U(d)$ is a relative
$\varepsilon$-approximate $t$-design if

$(1-\varepsilon)\Phi_{\nu}^{(t)}\preccurlyeq\Phi_{\mu_{H}}^{(t)}\preccurlyeq(1+\varepsilon)\Phi_{\nu}^{(t)}\,,$
(6)

where here $A\preccurlyeq B$ if and only if $B-A$ is a completely positive
map.

By applying (BHH16a, , Lemma 4), as well as the fact that
$\|\Phi^{(t)}_{\nu}-\Phi^{(t)}_{\mu_{H}}\|_{\diamond}\leq d^{t}g(\nu,t)$ Low
(10), we can state:

######  Lemma 1.

Let $\nu$ be a probability distribution on $U(d)$ such that
$g(\nu,t)\leq\varepsilon/d^{2t}$. Then $\nu$ is an $\varepsilon$-approximate
unitary $t$-design and obeys both Eq. (5) and Eq. (6).

In this paper we consider the following architectures of random quantum
circuits comprised of 2-local unitary gates on a system of $n$ qubits.

######  Definition 2 (Random quantum circuits).

a

  1. 1.

_Local ( $1D$) random quantum circuits:_ Let $\nu_{n}$ denote the probability
distribution on $U((\mathbb{C}^{2})^{\otimes n})$ defined by first choosing a
random pair of adjacent qudits and then applying a Haar random unitary
$U_{i,i+1}$ from $U(4)$. We assume periodic boundary conditions.

  2. 2.

_Brickwork random quantum circuits:_ Apply first a unitary $U_{1,2}\otimes
U_{3,4}\otimes...$ and then a unitary $U_{2,3}\otimes U_{4,5}\otimes...$,
where all $U_{i,i+1}$ are drawn Haar-randomly. For simplicity we assume in
this case an even number of qudits. We denote this distribution by $\nu^{\rm
bw}_{n}$.

A standard tool for converting results on the gap on local random quantum
circuits into brickwork circuits is the detectability lemma AALV (09); AAV
(16). We will also make use of a strong converse called the quantum union
bound Gao (15); AAV (16). We present both together:

######  Lemma 2 (Detectability lemma and union bound).

Let $H=\sum_{i}Q_{i}$, where $Q_{i}$ are projectors in an arbitrary order.
Assume that each $Q_{i}$commutes with all but $g$ of the projectors. Then, for
a state $|\psi^{\perp}\rangle$ orthogonal to the ground space of $H$,

$\sqrt{1-4\Delta(H)}\leq\left|\left|\prod_{i}(\mathbbl{1}-Q_{i})|\psi^{\perp}\rangle\right|\right|_{2}\leq\sqrt{\frac{1}{\Delta(H)/g^{2}+1}}.$
(7)

Finally, we introduce the Clifford group, which it plays a crucial role in the
proof of Theorem 1: The $n$-qubit Clifford group $\mathrm{Cl}(n)$ is the
unitary normalizer of the Pauli group $\mathcal{P}_{n}$:

$\mathrm{Cl}(n):=\left\\{U\in
U(2^{n},\mathbb{Q}[i])\;\big{|}\;U\mathcal{P}_{n}U^{\dagger}\subset\mathcal{P}_{n}\right\\}.$
(8)

Our interest stems from the fact that this group forms a unitary $2$-design
Web (16); Zhu (17), while every element has a polynomially upper bounded
circuit complexity AG (04); BM (21).

##  II Revisiting the spectral gap of random quantum circuits

Here we review the key steps in the proof technique in Ref. BHH16a . We
introduce the notation $P_{H}:=M(\mu_{H},t)$ and $P_{H,m}$ to specify that we
are talking about the Haar moment operator on $m$ qubits. Ref. BHH16a
introduced the frustration-free Hamiltonian

$H_{n,t}:=\sum_{i=1}^{n}(\mathbbl{1}-\mathbbl{1}_{i-1}\otimes
P_{H,2}\otimes\mathbbl{1}_{n-i-1}).$ (9)

With this definition it holds that (BHH16a, , Lem. 16):

$g(\nu_{n},t)=1-\frac{\Delta(H_{n,t})}{n},$ (10)

where $\Delta(H_{n,t})$ denote the spectral gap of $H_{n,t}$.

Using Nachtergaele’s martingale method for spin systems, Ref. BHH16a  proves
that for all $n$ and $t$ such that $n\geq\lceil 2.5\log_{2}(4t)\rceil$ the
following bound holds:

$\Delta(H_{n,t})\geq\frac{\Delta(H_{\lceil 2.5\log_{2}(4t)\rceil,t})}{4\lceil
2.5\log_{2}(4t)\rceil}.$ (11)

Remarkably, this reduction not only establishes a constant spectral gap for
every fixed value of $t$, but also turns every bound that only depends
exponentially on the system size into one that depends polynomially on $t$.

The reduction (11) to smaller system sizes is then combined with an spectral
gap that holds for all values of $t$. We call such a gap unconditional:

$\Delta(H_{n,t})\geq\frac{1}{n(5e)^{n}}.$ (12)

This bound is obtained from a convergence result: By applying the path
coupling technique on the unitary group Oli (09), the authors of Ref. BHH16a
show that random quantum circuits converge to the Haar measure in the
Wasserstein distance. This convergence result is strong enough to imply the
bound (12) on the spectral gap.

How does the exponent of $t$ for the design depth in Ref. BHH16a  decompose
exactly? Ignoring logarithmic factors, the exponent is approximately

$10.41\leavevmode\nobreak\ \leavevmode\nobreak\ \approx\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\underbrace{1}_{1.}\quad+\quad\left(\underbrace{2}_{2.}\quad+\quad\underbrace{0.5}_{3.}\right)\quad\times\quad\left(\underbrace{\log_{2}{5}}_{4.}\quad+\quad\underbrace{\log_{2}(e)}_{5.}\right).$
(13)

  1. 1.

This contribution comes from the conversion of a spectral gap to the stronger
notions of approximate designs in Definition 1. This contribution is therefore
a necessary consequence of using spectral gaps to bound the design depth.

  2. 2.

Ref. BHH16a  establishes approximate orthogonality of permutations of $t$
tensor factors of $\mathbb{C}^{D}$ in the regime $D\geq t^{2}$. In the
application of Nachtergaele’s martingale method Nac (96), this fact is
repeatedly used and the second contribution can be directly linked to the
square in the condition $t^{2}\leq D$. More precisely, the following
inequality holds

$\left|\left|M(\mu_{H},t)-2^{-tn}\sum_{\pi\in
S_{t}}\mathrm{vec}(r(\pi))\mathrm{vec}(r(\pi))^{\dagger}\right|\right|_{\infty}\leq\frac{t^{2}}{D},$
(14)

where $r$ denotes the representation of the symmetric group that permutes the
$t$ tensor factors. The second operator in Eq. (14) is called the frame
operator of the permutations. It has the same eigenvalues as the Gram matrix
of the permutations and is also the moment operator of random matrices with
i.i.d. Gaussian entries by Wick’s theorem. The approximate orthogonality of
the permutations is therefore equivalent to the moments of the Haar measure
being approximately equal to those of Gaussian matrices with i.i.d. entries.
Each monomial of degree $t$ only contains information about some $t\times t$
submatrix. Indeed, small submatrices $t\sim o(\sqrt{D})$ of Haar random
unitaries are conjectured to be close to an i.i.d. Gaussian ensemble in total
variation distance AA (11); Jia (06). However, as the entries of Haar random
matrices are correlated, large submatrices cannot be close to an i.i.d
Gaussian ensemble. Consequently, we cannot expect to make the RHS of Eq. (14)
scale better than $t/D$.

  3. 3.

This contribution is a consequence of Nachteragale’s bound. More precisely,
the final bound of Ref. (BHH16a, , Lem. 18) is

$\Delta(H_{n,t})\geq\frac{\Delta(H_{l,t})}{4l},$ (15)

for any $l$ that satisfies the inequality

$\frac{6t^{2}}{2^{l}}\leq\frac{1}{2}l^{-\frac{1}{2}}.$ (16)

The choice $l=2.5\lceil\log_{2}(4t)\rceil$ can be seen to always satisfy (16).
This bound gives a comparably simple expressions at the expense of a slightly
worse than optimal exponent in $t$. However, as the objective of this work is
to pedantically optimize the exponent of $t$, we use modern bounds on
Lambert’s W function to obtain such a tight bound in $l$. We present the
resulting bound below in Observation 1,

  4. 4.

The last two contributions are a consequence of the unconditional spectral gap
in Eq. (12). In general, contribution 4. comes from an exponential decay
$(q^{2}+1)^{-n}$ (for qubits $q=2$) of the unconditional bound on the gap.
This part of the bound (12) can be proven for random “staircase circuits” of
the form $U_{1,2}U_{2,3}\ldots U_{n-1,n}$, with Haar random $2$-local
unitaries $U_{i,i+1}$. The same bound holds for permutations of the unitaries
$U_{i,i+1}$. In this work, we observe that the application of the path
coupling method in Ref. BHH16a  uses the full Haar randomness of the first
gate $U_{1,2}$ only. For all other gates, we merely need the second moments of
the Haar measure and we would hence obtain the same bound if the gates
$U_{2,3},\ldots,U_{n-1}$ are drawn uniformly from the Clifford group. The key
idea in our improved bound is to go one step further and directly apply the
full $n$-qubit Clifford group and only worry about locality once this
convergence result is translated into spectral gaps.

  5. 5.

Permutations of these staircase random walks appear with non-zero probability
after $n$ steps of local random quantum circuits. More precisely, these are
realized with a probability of $n!/n^{n}$. This explains the appearance of
Euler’s constant $e$ as Stirling’s approximation of the factorial is
$n!\sim(n/e)^{n}$. By applying Gao’s union bound directly to the moment
operators of Clifford brickwork circuits approximating the uniform
distribution on the Cliffords, we can circumvent this counting step entirely.

We observe that the bound (11) can be slightly improved. A detailed argument
for the following can be found in Appendix A.

######  Observation 1 (Improved gap reduction).

For all $n\geq\lceil 2\log_{2}(4t)+1.5\sqrt{\log_{2}(4t)}\rceil$ the following
bound holds:

$\Delta(H_{n,t})\geq\frac{\Delta\left(H_{\lceil
2\log_{2}(4t)+1.5\sqrt{\log_{2}(4t)}\rceil,t}\right)}{4\left\lceil
2\log_{2}(4t)+1.5\sqrt{\log_{2}(4t)}\right\rceil}.$ (17)

##  III Results

###  III.1 Tensor product expanders and unitary designs

Our first result is a bound on the spectral gap of the moment operator of
local random quantum circuits that is independent of the moment $t$:

######  Theorem 1 (Unconditional gap).

We have the following bound for all $t\geq 1$:

$g(\nu_{n},t)\leq 1-120000^{-1}n^{-5}2^{-2n}$ (18)

This can be combined with the slightly improved reduction in Observation 1 to
yield the following bounds on the tensor product expander properties of local
random quantum circuits:

######  Theorem 2 (Tensor product expanders).

We have the following bounds for $n\geq\lceil
2\log_{2}(4t)+1.5\sqrt{\log_{2}(4t)}\rceil$:

  * •

$g(\nu_{n},t)\leq
1-\left(Cn\ln^{5}(t)t^{4+3\frac{1}{\sqrt{\log_{2}(t)}}}\right)^{-1}$

  * •

$g(\nu^{\mathrm{bw}}_{n},t)\leq
1-\left(3C\ln^{5}(t))t^{4+3\frac{1}{\sqrt{\log_{2}(t)}}}\right)^{-1}$,

where the constant can be taken to be $C=10^{13}$.

###### Proof.

The bound on $g(\nu_{n},t)$ follows from plugging the unconditional bound

$\Delta(H_{m,t})\geq 120000^{-1}m^{-4}2^{-2m}$ (19)

from Theorem 1 into the reduction (17) in Observation 1. The bound on
$g(\nu_{n}^{\mathrm{bw}})$ can be obtained from this by applying the
detectability lemma (Lemma 2):

$g(\nu^{\mathrm{bw}}_{n})\leq\sqrt{\frac{1}{\Delta(H_{n,t})/4+1}}\leq
1-\left(3C\ln^{5}(t))t^{4+3\frac{1}{\sqrt{\log_{2}(t)}}}\right)^{-1},$ (20)

which is the second part of Theorem 2. ∎

By Lemma 1, this immediately implies the following corollary, which is the
main application of Theorem 2:

######  Corollary 1 (Unitary designs).

For $n\geq\lceil 2\log_{2}(4t)+1.5\sqrt{\log_{2}(4t)}\rceil$, the following
bounds hold

  * •

Local random quantum circuits are $\varepsilon$-approximate unitary
$t$-designs after

$k\geq
Cn\ln^{5}(t)t^{4+3\frac{1}{\sqrt{\log_{2}(t)}}}(2nt+\log_{2}(1/\varepsilon))$
(21)

steps.

  * •

Brickwork quantum circuits are $\varepsilon$-approximate unitary $t$-designs
after

$k\geq
C\ln^{5}(t)t^{4+3\frac{1}{\sqrt{\log_{2}(t)}}}(2nt+\log_{2}(1/\varepsilon))$
(22)

steps.

In comparison to the exponent in Eq. (13), the new exponent decomposes as
follows.

$5+3\frac{1}{\sqrt{\log_{2}(t)}}\leavevmode\nobreak\ \leavevmode\nobreak\
=\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\underbrace{1}_{1.}\quad+\quad\left(\underbrace{2}_{2.}\quad+\quad\underbrace{1.5\frac{1}{\sqrt{\log_{2}(t)}}}_{3.}\right)\quad\times\quad\underbrace{2}_{4.},$
(23)

where we again ignored the log-factors in (21). Here, contribution $1.$ and
$2.$ appear for the same reason as $1.$ and $2.$ in Eq. (13). Contribution 3.
is a direct consequence of Observation 1 and 4. follows from the improved
bound on the unconditional gap in Theorem 1.

######  Remark 1.

By applying an argument from Ref. BHH16a , the same scaling can be implied for
random quantum circuits drawn from a discrete invertible gate set with
algebraic entries, using a powerful result by Bourgain and Gamburd BG (12).
This bound comes with an implicit constant depending on the gate set.
Moreover, at the expense of additional polylogarithmic factors in $t$, the
assumption of algebraic entries can be dropped Var (13). Similarly, it was
shown recently that the assumption of invertibility can be dropped at the
expense of an additional factor of $n$ OSH (21).

###  III.2 Quantum circuit complexity

We apply our result to the growth of circuit complexity BCHJ+ (21); BHH16b .
Let $\mathcal{G}$ denote a universal gate set of $2$-local gates. Moreover,
denote by $M_{\mathcal{G},R}$ the set of all unitaries that can be realized by
concatenation of at most $R$ gates in $\mathcal{G}$.

######  Definition 3 (Quantum circuit complexity).

For $\delta\in(0,1]$ a

  * •

state $|\psi\rangle$ has $\delta$-state complexity

$\mathcal{C}_{\delta}(|\psi\rangle):=\min\\{R,\exists V\in
M_{\mathcal{G},R}\leavevmode\nobreak\ \text{with}\leavevmode\nobreak\
\frac{1}{2}||V|0^{n}\rangle\langle
0^{n}|V^{\dagger}-|\psi\rangle\langle\psi|||_{1}\leq\delta\\}.$ (24)

  * •

unitary $U$ has $\delta$-unitary complexity

$C_{\delta}(U):=\min\\{R,\exists V\in M_{\mathcal{G},R}\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\
|||\mathsf{V}-\mathsf{U}||_{\diamond}\leq\delta\\},$ (25)

where $\mathsf{U}$ is the channel defined by $\mathsf{U}(\rho)=U\rho
U^{\dagger}$ and $\mathsf{V}$ likewise.

We can use the following bound:

######  Theorem 3 (Informal, Ref. BHH16a ).

Let $\nu$ be a relative approximate unitary $t$-design for some $t\leq
O(2^{n/2})$. Then, a unitary $U$ drawn from $\nu$ satisfies
$\mathcal{C}_{\delta}(U)\geq\Omega(nt)$ and
$\mathcal{C}_{\delta}(U|\psi\rangle)\geq\Omega(nt)$ with high probability.

Combining this theorem with Corollary 1 yields the following lower bounds on
the circuit complexity:

######  Corollary 2 (Growth of quantum circuit complexity).

Let $U$ be drawn from a random quantum circuit in brickwork architecture of
depth $T$. Moreover, let $\delta\in(0,1)$ be constant in the system size.
Then, with overwhelming probability, we have for the

  * •

$\delta$-state complexity

$\mathcal{C}_{\delta}(U)\geq\Omega\left(T^{1/(5+o(1))}\right)$

  * •

$\delta$-unitary complexity

$\mathcal{C}_{\delta}(U|0^{n}\rangle)\geq\Omega\left(T^{1/(5+o(1))}\right)$

until $T\geq\Omega(2^{n/(2+o(1))})$.

For the error-robust notions of quantum circuit complexity defined above
Corollary 2 provides the strongest existing bounds for random quantum circuits
over qubits of superpolynomial depth so far.

######  Remark 2.

Ref. BCHJ+ (21) in fact provides a much stronger result. Even an operational
notion of complexity that quantifies the resources necessary to distinguish a
unitary from the maximally depolarizing channel (the “most useless” channel)
is lower bounded by $\Omega(T^{1/(5+o(1))})$.

######  Remark 3.

In this paper we focus on random quantum circuits over qubits. This is because
there are very concrete bounds available for the maximal circuit complexity of
the multiqubit Clifford group AG (04); BM (21). However, the same proof
strategy works for every local dimension that is prime because in these
dimensions the Clifford group forms a unitary $2$-design. Therefore, all
results in this section can be proven for every prime power dimension with
constants depending on the maximal circuit complexity of the multiqudit
Clifford group.

##  IV Proof of Theorem 2 and Theorem 1

Denote by $\mu_{H,1}$ the Haar measure on the subgroup
$U(2)\otimes\mathbbm{1}_{n-1}$ and $\mu_{\mathrm{Cl}}$ the uniform measure on
the Clifford group. We apply the path coupling technique BD (97) for the
unitary group developed in Ref. Oli (09) to the following auxiliary random
walk that is defined by

$\sigma^{*k}:=(\mu_{\mathrm{Cl}}*\mu_{H,1}*\mu_{\mathrm{Cl}})^{*k}.$ (26)

This walk was defined in HMMH+ (20) and shown to generate unitary $t$-designs
in depth $k=O(t^{4})$ for “small” $t$. More precisely, the result holds for
the regime $t^{2}\leq O(n)$ and for a weaker definition of approximate unitary
design.

Figure 1: Four steps of the random walk $\sigma$ on $n=6$ qubits.

The first lemma is an unconditional spectral gap on the random walk $\sigma$:

######  Lemma 3.

We have for all $t\geq 1$ and $n\geq 1$ that

$g(\sigma,t)\leq 1-\frac{3}{2}\frac{1}{2^{2n}-1}$ (27)

The path coupling technique provides a bound on the convergence to the Haar
measure in the Wasserstein distance, which is based on the notion of a random
coupling: A random variable $(X,Y)$ is called a coupling for the distributions
$\nu_{1}$ and $\nu_{2}$ if the marginal distributions for random variables $X$
and $Y$ are $\nu_{1}$ and $\nu_{2}$, respectively. This allows us to define
the Wasserstein distance:

$W_{\mathfrak{g},p}(\nu_{1},\nu_{2}):=\inf\\{(\mathbb{E}\leavevmode\nobreak\
\mathfrak{g}(X,Y)^{p})^{1/p},\quad(X,Y)\leavevmode\nobreak\ \text{is a random
coupling}\\}.$ (28)

In Ref. BHH16a  a convergence result is proven for for the distance
$W_{\mathrm{Rie},2}$. Here, $\mathfrak{g}_{\mathrm{Rie}}$ is the metric
induced by the unique Riemannian metric that is invariant under left and right
translations. For our purposes, however, it is sufficient to prove a
convergence in the weaker distance $W_{\mathrm{Fro},2}$. We remark that the
stronger convergence result can be obtained from our analyzis as in Ref.
BHH16a .

It was proven in Ref. Oli (09) that infinitesimal contractions can be boosted
to a global contraction of a random walk. More precisely, Theorem 2 in Ref.
Oli (09) contains the following lemma as a special case:

######  Lemma 4.

Suppose that

$\limsup_{X\to
Y}\left\\{\frac{W_{\mathrm{Fro},2}(\nu*\delta_{X},\nu*\delta_{Y})}{||X-Y||_{F}}:||X-Y||_{F}\leq\varepsilon\right\\}\leq\eta,$
(29)

for some probability distribution $\nu$ over $SU(d)$. Then, for all
probability measures $\mu_{1}$ and $\mu_{2}$,

$W_{\mathrm{Fro},2}(\nu*\mu_{1},\nu*\mu_{2})\leq\eta
W_{\mathrm{Fro},2}(\mu_{1},\mu_{2}).$ (30)

Using Lemma 4, we prove the following convergence result:

######  Lemma 5.

For every $k\geq 1$, we have the bound:

$W_{\mathfrak{g}_{\mathrm{Fro}},2}\big{(}\sigma^{*k},\mu_{H}\big{)}\leq\left(1-\frac{3}{2^{2n}-1}\right)^{k/2}\pi
2^{n/2}.$ (31)

###### Proof.

A single step of the random walk $\sigma$ applied to a fixed unitary $X\in
U(2^{n})$ by left multiplication yields:

$X\to\left\\{C^{\prime}(U\otimes\mathbbm{1}_{n-1})CX\right\\},$ (32)

for $U\in U(2)$ and $C,C^{\prime}\in\mathrm{Cl}(n)$. The unitary $Y$ undergoes
the same transformation. We can now introduce a family of random couplings for
$(\sigma*\delta_{X},\sigma*\delta_{Y})$:

$X^{\prime}=C^{\prime}(UV\otimes\mathbbm{1}_{n-1})CX\qquad\qquad
Y^{\prime}=C^{\prime}(U\otimes\mathbbm{1}_{n-1})CX$ (33)

defined for a unitary $V\in U(2)$ that is independent of $U$ but can depend on
$X,Y$ and $C$.

We need to bound:

$\displaystyle\mathbb{E}||X^{\prime}-Y^{\prime}||_{\mathrm{F}}^{2}=\mathbb{E}||C^{\prime}(UV\otimes\mathbbm{1}_{n-1})CX-C^{\prime}(U\otimes\mathbbm{1}_{n-1})CY||_{\mathrm{F}}^{2}.$
(34)

We can choose $V$ to be minimal for all $C,X$ and $Y$. Then, we find

$\displaystyle\begin{split}\mathbb{E}\left(\min_{V}||C^{\prime}(UV\otimes\mathbbm{1}_{n-1})CX-C^{\prime}(U\otimes\mathbbm{1}_{n-1})CY||_{\mathrm{F}}^{2}\right)&=2\left(\mathrm{Tr}[\mathbbm{1}_{n}]-\max_{V}\mathrm{Tr}[V\otimes\mathbbm{1}_{n-1}CXY^{\dagger}C^{\dagger}]\right)\\\
&=2\left(\mathrm{Tr}[\mathbbm{1}_{n}]-\mathbb{E}||\mathrm{Tr}_{[2,n]}(CXY^{\dagger}C^{\dagger})||_{1}\right),\end{split}$
(35)

where we used the variational characterization of the Schatten $1$-norm. We
can choose $X$ and $Y$ to be infinitesimally close together and write

$R:=XY^{\dagger}=\exp(\mathrm{i}\varepsilon
H)=\mathbbm{1}_{n}+\mathrm{i}\varepsilon
H-\frac{\varepsilon^{2}}{2}H^{2}+O(\varepsilon^{3}),$ (36)

with $||H||_{\mathrm{F}}\leq 1$. By Taylor expanding the $1$-norm, this
implies (as in Ref. BHH16a ):

$\mathbb{E}\left(\min_{V}||C^{\prime}(UV\otimes\mathbbm{1}_{n-1})CX-C^{\prime}(U\otimes\mathbbm{1}_{n-1})CY||_{\mathrm{F}}^{2}\right)\\\
=\varepsilon^{2}\left(\mathrm{Tr}(H^{2})-\frac{1}{2^{n-1}}\mathbb{E}\left[\mathrm{Tr}\left(\mathrm{Tr}_{[2,n]}\left[CHC^{\dagger}\right]\right)^{2}\right]\right)+O(\varepsilon^{3}).$
(37)

The “replica trick”

$\mathrm{Tr}[A^{2}]=\mathrm{Tr}[A^{\otimes 2}\mathbb{F}]$ (38)

for every matrix $A$ can be applied to show

$\displaystyle\begin{split}\mathbb{E}\left[\mathrm{Tr}\left(\mathrm{Tr}_{[2,n]}\left[CHC^{\dagger}\right]\right)^{2}\right]&=\mathrm{Tr}\left[(CHC^{\dagger})^{\otimes
2}\leavevmode\nobreak\ \mathbb{F}_{1}\otimes\mathbbm{1}_{[2,n]}\right]\\\
&=\mathrm{Tr}\left[H^{\otimes 2}\leavevmode\nobreak\ (C^{\dagger})^{\otimes
2}(\mathbb{F}_{1}\otimes\mathbbm{1}_{[2,n]})C^{\otimes 2}\right].\end{split}$
(39)

We now use that the Clifford group is an exact unitary $2$-design: the
expectation value in the above equation is the same as that for Haar-random
unitaries $C$. We employ standard formulas (ADHW, 09, Lem. IV.3) for the twirl
over the Haar measure:

$\displaystyle\begin{split}\mathbb{E}_{C\sim\mu_{\mathrm{Cl}}}\leavevmode\nobreak\
&\mathrm{Tr}[H^{\otimes 2}\leavevmode\nobreak\ (C^{\dagger})^{\otimes
2}(\mathbb{F}_{1}\otimes\mathbbm{1}_{[2,n]})C^{\otimes 2}]\\\
&=\mathrm{Tr}\left[H^{\otimes
2}\left(\frac{2+2^{n-1}}{2^{n}+1}\frac{1}{2}(\mathbbl{1}+\mathbb{F})-\frac{2-2^{n-1}}{2^{n}-1}\frac{1}{2}(\mathbbl{1}-\mathbb{F})\right)\right]\\\
&=\frac{1}{2}\left(\frac{2+2^{n-1}}{2^{n}+1}+\frac{2-2^{n-1}}{2^{n}-1}\right)\mathrm{Tr}\left[H^{\otimes
2}\mathbb{F}\right]+\frac{1}{2}\left(\frac{2+2^{n-1}}{2^{n}+1}-\frac{2-2^{n-1}}{2^{n}-1}\right)\mathrm{Tr}\left[H^{\otimes
2}\mathbbl{1}\right]\\\
&=\left(\frac{2-2^{-1}}{2^{n}-2^{-n}}\right)\mathrm{Tr}[H^{2}]+\left(\frac{2^{2n-1}-2}{2^{2n}-1}\right)\mathrm{Tr}[H]^{2}\\\
&\geq\left(\frac{2-2^{-1}}{2^{n}-2^{-n}}\right)\mathrm{Tr}[H^{2}].\end{split}$
(40)

Consequently, we obtain

$\mathbb{E}\left(\min_{V}||C^{\prime}(UV\otimes\mathbbm{1}_{n-1})CX-C^{\prime}(U\otimes\mathbbm{1}_{n-1})CY||_{\mathrm{F}}^{2}\right)\leq\left(1-\frac{3}{2^{2n}-1}\right)\varepsilon^{2}\mathrm{Tr}(H^{2})+O(\varepsilon^{3}).$
(41)

From

$\displaystyle\begin{split}||X-Y||^{2}_{F}=\varepsilon^{2}\mathrm{Tr}(H^{2})+O(\varepsilon^{3}),\end{split}$
(42)

we find

$\mathbb{E}||X^{\prime}-Y^{\prime}||^{2}_{F}\leq\left(1-\frac{3}{2^{2n}-1}\right)||X-Y||^{2}_{F}+O(\varepsilon^{3}).$
(43)

Notice, that for $X\neq Y$, we can always choose $\varepsilon$, such that
$\mathrm{Tr}(H^{2})=||H||_{F}^{2}=1$. Therefore, we find that

$\displaystyle\begin{split}\frac{W_{\mathrm{Fro},2}(\sigma*\delta_{X},\sigma*\delta_{Y})}{||X-Y||_{F}}&\leq\frac{(\mathbb{E}||X^{\prime}-Y^{\prime}||_{F}^{2})^{\frac{1}{2}}}{||X-Y||_{F}}\\\
&\leq\frac{\sqrt{\left(1-\frac{3}{2^{2n}-1}\right)||X-Y||^{2}_{F}+O(\varepsilon^{3}})}{||X-Y||_{F}}\\\
&\leq\sqrt{\left(1-\frac{3}{2^{2n}-1}\right)}+\sqrt{\frac{O(\varepsilon^{3})}{\varepsilon^{2}+O(\varepsilon^{3})}}\\\
&\leq\sqrt{\left(1-\frac{3}{2^{2n}-1}\right)}+O(\sqrt{\varepsilon}),\end{split}$
(44)

with $\varepsilon\to 0$ as $X\to Y$. Invoking Lemma 4 $k$ times with
$\eta:=\sqrt{(1-\frac{3}{2^{2n}-1})}$ implies

$\displaystyle\begin{split}W_{\mathrm{Fro},2}(\sigma^{*k},\mu_{H})&=W_{\mathrm{Fro},2}(\sigma^{*k}*\delta_{\mathbbm{1}},\sigma*\mu_{H})\\\
&\leq\eta^{k}W_{\mathrm{Fro},2}(\delta_{\mathbbm{1}},\mu_{H})\\\
&\leq\eta^{k}(\mathbb{E}_{U}||\mathbbm{1}-U||_{F}^{2})^{\frac{1}{2}}\\\
&=\sqrt{2}2^{n/2}\eta^{k},\end{split}$ (45)

which is the satement of Lemma 5. ∎

We can now prove Lemma 3:

###### Proof of Lemma 3.

We use the following formula BHH16a , which holds for any probability
distribution $\nu$:

$g(\nu,t)\leq 2tW_{\mathrm{Fro},1}(\nu,\mu_{H})$ (46)

Combining this with Lemma 5 yields:

$\displaystyle\begin{split}g(\sigma^{*k},t)&\leq
2tW_{\mathrm{Fro},1}(\nu,\mu_{H})\\\ &\leq
2tW_{\mathrm{Fro},2}\big{(}\sigma^{*k},\mu_{H}\big{)}\\\
&\leq\left(1-\frac{3}{2^{2n}-1}\right)^{k/2}2\sqrt{2}t2^{n/2},\end{split}$
(47)

where the second inequality follows immediately from Jensen’s inequality.
$\sigma$ is a symmetric measure, that is, it is invariant under taking
inverses. Consequently, the moment operators are hermitian, which implies

$g(\sigma^{*k},t)=g(\sigma,t)^{k}.$ (48)

Notice that the inequality $g(\sigma^{*k},t)\leq g(\sigma,t)^{k}$ holds for
all measure but not equality. We plug (48) into (47), take the $k$-th square
root and the limit $k\to\infty$. This yields

$g(\sigma,t)\leq\left(1-\frac{3}{2^{2n}-1}\right)^{1/2}\leq
1-\frac{1}{2}\frac{3}{2^{2n}-1}.$ (49)

∎

Before we can prove Theorem 1, we need another auxiliary bound. More
precisely, we show that a local random walk over Clifford generators quickly
approximates the uniform measure on the Clifford group: Apply first a unitary
$U_{1,2}\otimes U_{3,4}\otimes...$ and then a unitary $U_{2,3}\otimes
U_{4,5}\otimes...$, where all $U_{i,i+1}$ are drawn uniformly from the
Clifford group on $2$ qubits. We denote this distribution by $\nu^{\rm
Cl,bw}_{n}$

The Clifford group is a finite group with polynomially bounded circuit
complexity AG (04); BM (21) and we can use this fact to apply the comparison
technique DSC (93). This gives the following bound:

######  Lemma 6.

The following bound holds for all $t\geq 1$:

$\left|\left|M\left(\nu^{\rm
Cl,bw}_{n},t\right)-M(\mu_{\mathrm{Cl}},t)\right|\right|_{\infty}\leq
1-\frac{1}{2000n^{3}}.$ (50)

###### Proof.

Consider the averaging operator on the group algebra
$T_{\nu}:L^{2}(\mathrm{Cl}_{n})\to L^{2}(\mathrm{Cl}_{n})$ defined by

$(T_{\nu}f)(g):=\int f(h^{-1}g)\mathrm{d}\nu(h).$ (51)

By DSC (93), we have

$\lambda_{2}(T_{\sigma})\leq 1-\frac{\eta}{d^{2}},$ (52)

where $\eta$ is the probability of the least probable generator and $d$ is the
minimal number of generators necessary to generate any group element. Here,
$d=9n$ by BM (21) and $\eta=1/|\mathrm{Cl}_{2}|n=1/24n$. By the Peter-Weyl
theorem, the entire spectrum of the moment operators is contained in the
spectrum of the averaging operator and thus we obtain Eq. (50). ∎

We remark that the comparison technique was previously applied to the Clifford
group in Ref. DLT (02).

We can now put everything together.

###### Proof of Theorem 1.

For simplicity, we use the following notation:

$P_{\mathrm{Cl},n}=M(\mu_{\mathrm{Cl}_{n}},t).$ (53)

We use

$\left|\left|M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k}-P_{\mathrm{Cl},n}\right|\right|_{\infty}\leq\left|\left|M\left(\nu^{\rm
Cl,bw}_{n},t\right)-P_{\mathrm{Cl},n}\right|\right|^{k}_{\infty}\leq\left(1-\frac{1}{2000n^{3}}\right)^{k}.$
(54)

In particular, we have the approximation

$\left|\left|M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}-P_{\mathrm{Cl},n}\right|\right|_{\infty}\leq\frac{1}{2}\frac{1}{2^{2n}-1}$
(55)

for a number of layers $k_{n}$ that we can choose as

$k_{n}=6000n^{4}.$ (56)

Therefore, by applying the triangle inequality twice, we obtain

$\displaystyle\begin{split}||M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}M(\mu_{H,1}&,t)M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}-P_{H}||_{\infty}\\\
&\leq||P_{\mathrm{Cl},n}M(\mu_{H,1},t)P_{\mathrm{Cl},n}-P_{H}||_{\infty}+\frac{1}{2^{2n}-1}\\\
&=||M(\sigma,t)-P_{H}||_{\infty}+\frac{1}{2^{2n}-1}\\\ &\leq
1-\frac{1}{2}\frac{3}{2^{2n}-1}+\frac{1}{2^{2n}-1}\\\ &\leq
1-\frac{1}{2(2^{2n}-1)},\end{split}$ (57)

where we used Lemma 3 in the third inequality.

$M\left(\nu^{\rm Cl,bw}_{n},t\right)^{k_{n}}M(\mu_{H,1},t)M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}$ is a product of $(2nk_{n}+1)$ orthogonal
projectors. In the following we denote these projectors as
$\mathbbl{1}-Q_{1},\ldots,\mathbbl{1}-Q_{2nk_{n}+1}$. E.g. we set

$Q_{1}:=\mathbbl{1}-P_{\mathrm{Cl},2}\otimes\mathbbl{1}_{n-2}$ (58)

and $Q_{nk_{n}+1}:=\mathbbl{1}-P_{H,1}$. The order of these labelings will not
matter in the following. As in Lemma 2, we define a Hamiltonian
$\tilde{H}:=\sum_{i=1}^{2nk_{n}+1}Q_{i}$. We can now relate the bound (57) to
the gap of the Hamiltonian $\tilde{H}$ via the quantum union bound or reversed
detectability lemma (Lemma 2):

$\displaystyle\begin{split}||M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}M(\mu_{H,1}&,t)M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}-P_{H}||_{\infty}\\\
&=\max_{|\psi^{\perp}\rangle}||M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}M(\mu_{H,1},t)M\left(\nu^{\rm
Cl,bw}_{n},t\right)^{k_{n}}|\psi^{\perp}\rangle||_{2}\\\
&=\max_{|\psi^{\perp}\rangle}\left|\left|\prod_{i=1}^{2nk_{n}+1}(\mathbbl{1}-Q_{i})|\psi^{\perp}\rangle\right|\right|_{2}\\\
&\geq\sqrt{1-4\Delta(\tilde{H})}\\\ &\geq 1-4\Delta(\tilde{H}).\end{split}$
(59)

Combining this with (57), yields:

$\frac{1}{8}\frac{1}{2^{2n}-1}\leq\Delta(\tilde{H}).$ (60)

We still need to relate the gap of $\tilde{H}$ to that of $H_{n,t}$. Using the
operator inequalities $P_{\mathrm{Cl}}\geq P_{H}$ and $P_{H,1}\geq P_{H,2}$,
we obtain

$\displaystyle\begin{split}\tilde{H}&=2k_{n}\sum_{i=1}^{n}(\mathbbl{1}-\mathbbl{1}_{i-1}\otimes
P_{\mathrm{Cl},2}\otimes\mathbbl{1}_{n-i-1})+(\mathbbl{1}-P_{H,1}\otimes\mathbbl{1}_{n-1})\\\
&\leq 2k_{n}\sum_{i=1}^{n}(\mathbbl{1}-\mathbbl{1}_{i-1}\otimes
P_{H,2}\otimes\mathbbl{1}_{n-i-1})+(\mathbbl{1}-P_{H,1}\otimes\mathbbl{1}_{n-1})\\\
&\leq(2k_{n}+1)\sum_{i=1}^{n}(\mathbbl{1}-\mathbbl{1}_{i-1}\otimes
P_{H,2}\otimes\mathbbl{1}_{n-i-1})\\\ &=(2k_{n}+1)H_{n,t}.\end{split}$ (61)

Moverover, notice that $\tilde{H}$ and $H_{n,t}$ have the same ground state
space with ground state energy $0$ as the gate set consisting of all $2$-local
Clifford unitaries plus single qubit unitaries are universal NRS (01). Indeed,
it was proven in Ref. HL (09) that the eigenvalue $1$ eigenspace of a moment
operator for a probability distribution with universal support equals the
image of the Haar random moment operator. Consequently, we find

$\Delta(H_{n,t})\geq\frac{1}{8(2k_{n}+1)(2^{2n}-1)}\geq
120000^{-1}n^{-4}2^{-2n}.$ (62)

Together with Eq. (10), this implies Theorem 1. ∎

##  V Outlook: Gaps from representations of the Clifford group?

In this work, we improved the scaling of the design depth for local random
quantum circuits over qubits. The lion’s share of the improvement comes from
the near-optimal convergence of an auxiliary random walk that interleaves
global random Clifford unitaries and single qubit Haar random unitaries.

The key open question, posed in Ref. BHH16a , is to either prove or disprove a
subexponential unconditional gap. An unconditional gap that scales inverse
polynomially in $n$ would imply a robust version of the Brown-Susskind
conjecture for random quantum circuits. For approaches based on techniques
from harmonic analysis, see Ref. HHJ (21). The techniques presented in this
paper open up another potential path towards this goal: It suffices to prove
such a gap for the auxiliary walk defined in Eq. (26).

The commutant of tensor powers of the Clifford group was studied in Ref. GNW
(17); MMG (21) and it was proven in Ref. HMMH+ (20) that the action of a
single qubit Haar average has a strong shrinking effect on a natural basis of
the Clifford commutant labeled by Lagrangian subspaces of
$\mathbb{Z}_{2}^{2t}$. Therefore, Lemma 13 in Ref. HMMH+ (20) can be viewed as
a sanity check for the constant spectral gap conjecture.

To prove the generation of state designs in linear depth, we do not require a
spectral gap of the entire moment operator. Indeed, it would suffice to show a
spectral gap of the moment operator restricted to the endomorphisms of the
symmetric subspace $\mathrm{End}(S^{t}[(\mathbb{C}^{2})^{\otimes n}])$:

$\left|\left|(M(\nu_{n},t)-P_{H})\large|_{\mathrm{vec}\left(\mathrm{End}(S^{t}[(\mathbb{C}^{2})^{\otimes
n}])\right)}\right|\right|_{\infty}\leq 1-\mathrm{poly}^{-1}(n)?$ (63)

To characterize the commutant of powers of the Clifford group on the
endomorphisms of the symmetric subspace, one would need to understand how the
symmetric subspace decomposes into irreducible representations of the Clifford
group.

##  VI Acknowledgements

I am grateful to Nick Hunter-Jones, Richard Kueng and Felipe Montealegre-Mora
for fruitful discussions. This work was funded by the foundational questions
institute (FQXi).

## References

  * AA [11] S. Aaronson and A. Arkhipov.  The computational complexity of linear optics.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333–342, 2011.
  * AALV [09] D. Aharonov, I. Arad, Z. Landau, and U. Vazirani.  The Detectability Lemma and Quantum Gap Amplification.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 417, 2009.
  * AAV [16] A. Anshu, I. Arad, and T. Vidick.  Simple proof of the detectability lemma and spectral gap amplification.  Phys. Rev. B, 93:205142, 2016.
  * ADHW [09] A. Abeyesinghe, I. Devetak, P. Hayden, and A. Winter.  The mother of all protocols: restructuring quantum information’s family tree.  Proc. R. Soc. A, 465:2537, 2009.
  * AE [07] A. Ambainis and J. Emerson.  Quantum t-designs: t-wise independence in the quantum world.  In Computational Complexity, 2007. CCC ’07. Twenty-Second Annual IEEE Conference on, pages 129–140, June 2007.
  * AG [04] S. Aaronson and D. Gottesman.  Improved simulation of stabilizer circuits.  Physical Review A, 70(5):052328, 2004.
  * AKN [98] D. Aharonov, A. Kitaev, and N. Nisan.  Quantum circuits with mixed states.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 20–30, 1998.
  * BCHJ+ [21] Fernando GSL Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill.  Models of quantum complexity growth.  PRX Quantum, 2(3):030316, 2021.
  * BD [97] R. Bubley and M. Dyer.  Path coupling: A technique for proving rapid mixing in Markov chains.  In Proceedings 38th Annual Symposium on Foundations of Computer Science, page 223, 1997.
  * BG [12] J. Bourgain and A. Gamburd.  A spectral gap theorem in su $(d)$.  Journal of the European Mathematical Society, 14(5):1455–1511, 2012\.
  * [11] F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki.  Local Random Quantum Circuits are Approximate Polynomial-Designs.  Commun. Math. Phys., 346:397, 2016.
  * [12] F. G. S. L. Brandao, A. W. Harrow, and M. Horodecki.  Efficient quantum pseudorandomness.  Physical review letters, 116(17):170502, 2016.
  * BM [21] S. Bravyi and D. Maslov.  Hadamard-free circuits expose the structure of the Clifford group.  IEEE Transactions on Information Theory, 67(7):4546–4563, 2021\.
  * BS [18] A. R. Brown and L. Susskind.  Second law of quantum complexity.  Phys. Rev., D97:086015, 2018.
  * Cha [13] I. Chatzigeorgiou.  Bounds on the Lambert function and their application to the outage analysis of user cooperation.  IEEE Communications Letters, 17(8):1505–1508, 2013.
  * CLLW [15] R. Cleve, D. Leung, L. Liu, and C. Wang.  Near-linear constructions of exact unitary 2-designs.  Quant. Inf. Comp., 16:0721–0756, 2015.
  * Dan [05] C. Dankert.  Efficient simulation of random quantum states and operators, 2005.
  * DCEL [09] C. Dankert, R. Cleve, J. Emerson, and E. Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Phys. Rev., A80:012304, 2009.
  * DLT [02] D. P DiVincenzo, D. W. Leung, and B. M. Terhal.  Quantum data hiding.  IEEE, Trans. Inf Theory, 48:3580–599, 2002.
  * DSC [93] P. Diaconis and L. Saloff-Coste.  Comparison techniques for random walk on finite groups.  The Annals of Probability, pages 2131–2156, 1993.
  * EAZ [05] J. Emerson, R. Alicki, and K. Życzkowski.  Scalable noise estimation with random unitary operators.  J. Opt. B: Quantum Semiclass. Opt., 7(10):S347, 2005.
  * GAE [07] D. Gross, K. Audenaert, and J. Eisert.  Evenly distributed unitaries: On the structure of unitary designs.  J. Math. Phys., 48:052104, 2007.
  * Gao [15] J. Gao.  Quantum union bounds for sequential projective measurements.  Phys. Rev. A, 92:052331, 2015.
  * GNW [17] D. Gross, S. Nezami, and M. Walter.  Schur-Weyl duality for the Clifford group with applications.  2017\.  arXiv:1712.08628.
  * HFK+ [21] J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, and N. Yunger Halpern.  Linear growth of quantum circuit complexity.  arXiv preprint arXiv:2106.05305, 2021.
  * HHJ [21] J. Haferkamp and N. Hunter-Jones.  Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions.  Physical Review A, 104(2):022417, 2021.
  * HJ [19] N. Hunter-Jones.  Unitary designs from statistical mechanics in random quantum circuits.  arXiv preprint arXiv:1905.12053, 2019.
  * HL [09] A. W. Harrow and R. A. Low.  Random quantum circuits are approximate 2-designs.  Communications in Mathematical Physics, 291(1):257–302, 2009.
  * HM [18] A. Harrow and S. Mehraban.  Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates.  arXiv preprint arXiv:1809.06957, 2018.
  * HMMH+ [20] J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, and I. Roth.  Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates.  arXiv preprint arXiv:2002.09524, 2020.
  * HP [07] P. Hayden and J. Preskill.  Black holes as mirrors: Quantum information in random subsystems.  JHEP, 09:120, 2007.
  * Jia [06] T. Jiang.  How many entries of a typical orthogonal matrix can be approximated by independent normals?  The Annals of Probability, 34(4):1497–1529, 2006.
  * KLR+ [08] E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland.  Randomized benchmarking of quantum gates.  Phys. Rev. A, 77:012307, 2008.
  * Kni [95] E. Knill.  Approximation by quantum circuits.  arXiv preprint quant-ph/9508006, 1995.
  * Low [10] R. A. Low.  Pseudo-randomness and Learning in Quantum Computation.  1006.5227, 2010.  PhD Thesis, 2010.
  * MGDM [18] R. Mezher, J. Ghalbouni, J. Dgheim, and D. Markham.  Efficient quantum pseudorandomness with simple graph states.  Physical Review A, 97(2):022333, 2018.
  * MGE [12] E. Magesan, J. M. Gambetta, and J. Emerson.  Characterizing quantum gates via randomized benchmarking.  Phys. Rev. A, 85:042311, 2012.
  * MMG [21] F. Montealegre-Mora and David Gross.  Rank-deficient representations in Howe duality over finite fields arise from quantum codes.  Representation Theory of the American Mathematical Society, 25(8):193–223, 2021.
  * Nac [96] B. Nachtergaele.  The spectral gap for some spin chains with discrete symmetry breaking.  Commun. Math. Phys., 175:565, 1996.
  * NHKW [17] Y. Nakata, C. Hirche, M. Koashi, and A. Winter.  Efficient quantum pseudorandomness with nearly time-independent hamiltonian dynamics.  Physical Review X, 7(2):021006, 2017.
  * NRS [01] G. Nebe, E. M. Rains, and N. J. A Sloane.  The invariants of the Clifford groups.  2001\.
  * OBK+ [17] E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert.  Mixing properties of stochastic quantum Hamiltonians.  Communications in Mathematical Physics, 355(3):905–947, 2017.
  * Oli [09] R. I. Oliveira.  On the convergence to equilibrium of Kac’s random walk on matrices.  Ann. Appl. Probab., 19:1200, 2009.
  * OSH [21] M. Oszmaniec, A. Sawicki, and M. Horodecki.  Epsilon-nets, unitary designs and random quantum circuits.  IEEE Transactions on Information Theory, 2021.
  * Sus [18] L. Susskind.  Black Holes and Complexity Classes.  2018\.
  * Var [13] P. P. Varjú.  Random walks in compact groups.  Doc. Math., 18:1137–1175, 2013.
  * Wat [18] J. Watrous.  The theory of quantum information.  Cambridge university press, 2018.
  * Web [16] Z. Webb.  The Clifford group forms a unitary 3-design.  Quantum Info. Comput., 16:1379, 2016.
  * Zhu [17] H. Zhu.  Multiqubit clifford groups are unitary 3-designs.  Phys. Rev. A, 96:062336, 2017.

##  Appendix A Proof of Observation 1

In this appendix we show how Observation 1 follows from bounds on Lambert’s W
function.

###### Proof.

Eq. (16) is implied by

$l-\frac{1}{2\ln(2)}\ln(l)\geq 2\log_{2}(4t).$ (64)

First, we consider the equation $y-a\ln(y)=b$. This is equivalent to

$e^{-\frac{y}{a}}\left(-\frac{y}{a}\right)=-\frac{e^{-\frac{b}{a}}}{a}.$ (65)

If the right hand side of Eq. (65) is larger than $-1/e$, this can be solved
by

$y=-aW_{-1}\left(-\frac{e^{-b/a}}{a}\right),$ (66)

where $W_{-1}$ denotes one of the branches [15] of Lambert’s W function (also
called log product function). By definition, all branches of Lambert’s W
function solve the equation

$ye^{y}=x$ (67)

for $y$.

We can now use the following bound for $x>0$ proven in Ref. [15]:

$W_{-1}(e^{-x-1})\geq-1-(2x)^{\frac{1}{2}}-x.$ (68)

With $x=b/a+\ln(a)-1$, $b=2\log_{2}(4t)$ and $a=(2\ln(2))^{-1}$, this implies

$\displaystyle\begin{split}y&\leq-a\left(-1-\sqrt{2\left(\frac{b}{a}+\ln(a)-1\right)}-\frac{b}{a}-\ln(a)+1\right)\\\
&\leq 2\log_{2}(4t)+1.5\sqrt{\log_{2}(4t)}.\end{split}$ (69)

The LHS of Eq. (64) is monotone in $l$. Hence, choosing

$l=\left\lceil 2\log_{2}(4t)+1.5\sqrt{\log_{2}(4t)}\right\rceil$ (70)

implies Eq. (64) and thus, by Nachtergaele’s bound, Eq. (17). ∎