# A random matrix model for random approximate $t$-designs

Piotr Dulian1 and Adam Sawicki 1

(1 Center for Theoretical Physics, Polish Academy of Sciences,
Al. Lotników 32/46, 02-668 Warszawa, Poland, )

###### Abstract

For a Haar random set $\mathcal{S}\subset U(d)$ of quantum gates we consider
the uniform measure $\nu_{\mathcal{S}}$ whose support is given by
$\mathcal{S}$. The measure $\nu_{\mathcal{S}}$ can be regarded as a
$\delta(\nu_{\mathcal{S}},t)$-approximate $t$-design, $t\in\mathbb{Z}_{+}$. We
propose a random matrix model that aims to describe the probability
distribution of $\delta(\nu_{\mathcal{S}},t)$ for any $t$. Our model is given
by a block diagonal matrix whose blocks are independent, given by Gaussian or
Ginibre ensembles, and their number, size and type is determined by $t$. We
prove that, the operator norm of this matrix, $\delta({t})$, is the random
variable to which $\sqrt{|\mathcal{S}|}\delta(\nu_{\mathcal{S}},t)$ converges
in distribution when the number of elements in $\mathcal{S}$ grows to
infinity. Moreover, we characterize our model giving explicit bounds on the
tail probabilities $\mathbb{P}(\delta(t)>2+\epsilon)$, for any $\epsilon>0$.
We also show that our model satisfies the so-called spectral gap conjecture,
i.e. we prove that with the probability $1$ there is $t\in\mathbb{Z}_{+}$ such
that $\sup_{k\in\mathbb{Z}_{+}}\delta(k)=\delta(t)$. Numerical simulations
give convincing evidence that the proposed model is actually almost exact for
any cardinality of $\mathcal{S}$. The heuristic explanation of this
phenomenon, that we provide, leads us to conjecture that the tail
probabilities
$\mathbb{P}(\sqrt{\mathcal{S}}\delta(\nu_{\mathcal{S}},t)>2+\epsilon)$ are
bounded from above by the tail probabilities
$\mathbb{P}(\delta(t)>2+\epsilon)$ of our random matrix model. In particular
our conjecture implies that a Haar random set $\mathcal{S}\subset U(d)$
satisfies the spectral gap conjecture with the probability $1$.

##  1 Introduction and Main Results

Approximate $t$-design are ensembles of unitaries that (approximately) recover
Haar averages of polynomials in entries of unitaries up to the order $t$.
Their relation to the notion of epsilon nets was recently given in [1].
Although there are methods of constructing exact $t$\- designs [2], their
implementation on near term quantum devices is fraught with inevitable noise
and errors that effectively change them into approximate $t$-designs.
Approximate $t$-designs find numerous applications throughout quantum
information, including randomized benchmarking [3], efficient estimation of
properties of quantum states [4], decoupling [5], information transmission
[6], quantum state discrimination [7], criteria for universality of quantum
gates [8] and complexity growth [9, 10, 11, 12]. Recently, there was a lot of
interest in efficient implementations of pseudo-random unitaries. First, it
was shown in [13, 14] that Haar random sets of gates from $U(d)$ form rather
good $t$-designs for $t=O(d^{\frac{1}{6}}/\log(d))$. Moreover, in [15] it was
shown that random circuits built form Haar-random 2-qubit gates acting
(according to the specified layout) on $N$-qubit systems of the depth
polynomial in $N$ form approximate $t$-designs. These results were later
improved in [16] and [17, 18, 19], where even faster convergence in $n$ was
proved. Moreover, the authors of [20] showed that random circuits constructed
from Clifford gates and a small number of non-Clifford gates can be used to
efficiently generate approximate $t$-designs (see also [21, 22] where the
authors show that in practice one needs an extensive number of non-Clifford
resources to reproduce features of $t$-designs).

In this paper we propose a random matrix model that describes approximate
$t$-designs constructed from Haar random sets of gates. In order to explain
our main results we need to first introduce the main object of the paper. Let
$\\{\mathcal{S},\nu_{\mathcal{S}}\\}$ be an ensemble of quantum gates, where
$\mathcal{S}$ is a finite subset of $U(d)$ and $\nu_{\mathcal{S}}$ is the
uniform measure with the support given by $\mathcal{S}$. In order to simplify
notation we will denote the cardinality of the set $\mathcal{S}$ by
$|\mathcal{S}|$ or just by $\mathcal{S}$. We define the _moment operator_
associated with any measure $\nu$ on $U(d)$ by:

$\displaystyle
T_{\nu,t}\coloneqq\int_{U(d)}d\nu(U)U^{t,t},\,\,\mathrm{where}\,U^{t,t}=U^{\otimes
t}\otimes\bar{U}^{\otimes t}.$ (1)

An ensemble for which

$\displaystyle\delta(\nu_{\mathcal{S}},t):=\left\|T_{\nu_{\mathcal{S}},t}-T_{\mu,t}\right\|=\delta<1,$
(2)

is called $\delta$-approximate $t$-design, where $\|\cdot\|$ is the operator
norm and $\mu$ is the Haar measure on $U(d)$ with normalization $\mu(U(d))=1$.
One can also consider

$\displaystyle\delta(\nu_{\mathcal{S}}):=\mathrm{sup}_{t}\delta(\nu_{\mathcal{S}},t)\in[0,1],$
(3)

which, by the Peter-Weyl theorem, is equal to the operator norm of the moment
operator

$\displaystyle(T_{\nu_{\mathcal{S}}}f)(U)=\int
d\nu_{\mathcal{S}}(V)f(V^{-1}U),$ (4)

acting on functions $f\in L^{2}(U(d))$ that have vanishing mean value,
$\int_{U(d)}d\mu(U)f(U)=0$. A long standing conjecture, known as the spectral
gap conjecture, states that for any $\mathcal{S}$ that is universal $1$ is not
an accumulation point of the spectrum of $T_{\nu_{\mathcal{S}}}$. In other
words one has $1-\delta({\nu_{\mathcal{S}}})>0$. So far this was proven
rigorously when the matrices from $\mathcal{S}$ have algebraic entries [23].

In this paper we address an important question of how good $t$-designs are
random sets of gates. In particular we consider two natural gate-sets
$\mathcal{S}$:

  * •

$\mathcal{S}=\\{U_{1},\ldots,U_{n}\\}$, where $U_{k}$’s are independent and
Haar random unitaries from $U(d)$. Such $\mathcal{S}$ will be called Haar
random gate-set

  * •

$\mathcal{S}=\\{U_{1},\ldots,U_{n}\\}\cup\\{U_{1}^{-1},\ldots,U_{n}^{-1}\\}$,
where $U_{k}$’s are independent and Haar random unitaries from $U(d)$. Such
$\mathcal{S}$ will be called symmetric Haar random gate-set.

Clearly, when $\mathcal{S}$ is a (symmetric) Haar random gate-set
$\delta(\nu_{\mathcal{S}},t)$ is a random variable. Our goal is to describe
probability distribution of this random varible and in particular to find
concrete explicit bounds on the tail probability
$\mathbb{P}(\delta(\nu_{\mathcal{S}},t)>\alpha)$, for $\alpha>0$. Some
residual results of this sort can be found in [13]. The bounds obtained there,
however, depend on undetermined and potentially large constants and what is
more important they can be applied only when $t=O(d^{\frac{1}{6}}/\log(d))$.
Moreover, bounds on the tail probability
$\mathbb{P}(\delta(\nu_{\mathcal{S}},t)>\alpha)$, for $\alpha>0$ have been
recently rigorously derived in [24] using matrix concentrations inequalities
[25]. In this paper we present a new approach to the problem which identifies
moment operators as elements of a well known Random Matrix Ensembles. Our
results show much faster decay of the tail probabilities of
$\delta(\nu_{\mathcal{S}},t)$ than any previous results.

First, in Section 2, using representation theory of the unitary group we
provide more useful, for our purposes, formula for
$\delta(\nu_{\mathcal{S}},t)$. This relies on the fact that
$T_{\nu_{\mathcal{S}},t}$ can be brought to a block diagonal form, where
blocks are labeled by sequences of $d$ non-increasing integers
$\lambda\in\Lambda_{t}$ that correspond to irreducible representations
$\pi_{\lambda}:U(d)\rightarrow GL(d_{\lambda})$ appearing in the decomposition
$U^{t,t}\simeq\text{1}^{\oplus
m_{0}}\oplus\bigoplus_{\lambda\in\Lambda_{t}}\left(\pi_{\lambda}\right)^{\oplus
m_{\lambda}}$. More precisely in order to determine
$\delta(\nu_{\mathcal{S}},t)$ we consider a block diagonal operator

$\sum_{U\in\mathcal{S}}\nu_{\mathcal{S}}(U)\begin{bmatrix}\pi_{\lambda_{1}}(U)&\textbf{0}&\cdots&\textbf{0}\\\
\textbf{0}&\pi_{\lambda_{2}}(U)&\cdots&\textbf{0}\\\
\vdots&\vdots&\ddots&\vdots\\\
\textbf{0}&\textbf{0}&\cdots&\pi_{\lambda_{k}}(U)\\\
\end{bmatrix}=\begin{bmatrix}T_{\nu_{\mathcal{S}},\lambda_{1}}&\textbf{0}&\cdots&\textbf{0}\\\
\textbf{0}&T_{\nu_{\mathcal{S}},\lambda_{2}}&\cdots&\textbf{0}\\\
\vdots&\vdots&\ddots&\vdots\\\
\textbf{0}&\textbf{0}&\cdots&T_{\nu_{\mathcal{S}},\lambda_{k}}\\\
\end{bmatrix},$

where $\lambda\in\Lambda_{t}^{\mathrm{ess}}$ and $\Lambda_{t}$,
$\Lambda_{t}^{\mathrm{ess}}$, are defined in Section 2. Denoting
$\delta(\nu_{\mathcal{S}},\lambda):=\|T_{\nu_{\mathcal{S}},\lambda}\|$ we can
write

$\displaystyle\delta(\nu_{\mathcal{S}},t)=\mathrm{sup}_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\delta(\nu_{\mathcal{S}},\lambda),\,\,\,\delta(\nu_{\mathcal{S}}):=\mathrm{sup}_{t}\delta(\nu_{\mathcal{S}},t).$
(5)

We note that $T_{\nu_{\mathcal{S}},\lambda}$ is either (1) a real (symmetric)
random matrix, when $\pi_{\lambda}$ is a real representation and $\mathcal{S}$
is a (symmetric) Haar random gate-set, or (2) A complex (hermitian) random
matrix, when $\pi_{\lambda}$ is a complex representation and $\mathcal{S}$ is
a (symmetric) Haar random gate-set. Using multidimensional Central Limit
Theorem and the orthogonality relations for irreducible representations of the
unitary group that we describe in Section 4.1 we show in Sections 4.2 and 4.3
our first main result:

######  Theorem 1.

When $|\mathcal{S}|\rightarrow\infty$:

  1. 1.

$\sqrt{|\mathcal{S}|}T_{\nu_{\mathcal{S}},\lambda}$ converges in distribution
to a random matrix $T_{\lambda}$ from: (1) the standard Real (Complex) Ginibre
Ensemble when $\mathcal{S}$ is Haar random gate-set and $\pi_{\lambda}$ is a
real (complex) representation, (2) the standard Gaussian Orthogonal (Unitary)
Ensemble when $\mathcal{S}$ is symmetric Haar random gate-set and
$\pi_{\lambda}$ is a real (complex) representation.

  2. 2.

Operator
$\bigoplus_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}T_{\nu_{\mathcal{S}},\lambda}$
converges in distribution to a block diagonal matrix

$\displaystyle
T_{t}=\bigoplus_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}T_{\lambda}.$ (6)

with blocks $T_{\lambda}$ belonging to the ensembles listed above. Moreover
$T_{\lambda}$’s with distinct $\lambda$’s are independent.

Theorem 1 gives a nice Random Matrix model which describes properties of
approximate $t$-designs in the regime of large $\mathcal{S}$. Moreover, we can
characterize rigorously many important properties of this model. In particular
we focus on random variables:

$\displaystyle\delta(\lambda):=\|T_{\lambda}\|=\lim_{|\mathcal{S}|\rightarrow\infty}\sqrt{|\mathcal{S}|}\delta(\nu_{\mathcal{S}},\lambda),\,\,\delta(t):=\|T_{t}\|=\lim_{|\mathcal{S}|\rightarrow\infty}\sqrt{|\mathcal{S}|}\delta(\nu_{\mathcal{S}},t),$
(7)
$\displaystyle\delta:=\lim_{t\rightarrow\infty}\|T_{t}\|=\lim_{|\mathcal{S}|\rightarrow\infty}\sqrt{|\mathcal{S}|}\delta(\nu_{\mathcal{S}}).$
(8)

Making use of concentration inequalities for Gaussian random variables and
following the reasoning which allows to bound the norm of matrices from
Ginibre and Gaussian ensembles given in [26, 27] and described in Section 4.1
we derive the following tail bounds that constitute our next main result

######  Theorem 2.

In the (symmetric) Haar random setting we have the following tail bounds for
$\delta(t)$:

$\displaystyle\mathbb{P}\left(\delta(t)>2+\epsilon\right)\leq\sum_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}F_{\ast}(d_{\lambda},\epsilon)$
(9)

where $\epsilon>0$ and functions $F_{\ast}$ are defined by:
$F_{O}(d_{\lambda},\epsilon)=\frac{1}{2}e^{-\frac{d_{\lambda}\epsilon^{2}}{4}}$,
$F_{U}(d_{\lambda},\epsilon)=F_{R}(d_{\lambda},\epsilon):=\frac{1}{2}e^{-\frac{d_{\lambda}\epsilon^{2}}{2}}$,
$F_{C}(d_{\lambda},\epsilon):=\frac{1}{2}e^{-d_{\lambda}\epsilon^{2}}$.
Moreover, $\ast=R$ ($\ast=O$) when $\lambda$ corresponds to a real
representation and $\mathcal{S}$ is (symmetric) Haar random gate-set and
$\ast=C$ ($\ast=U$) when $\lambda$ corresponds to a complex representation and
$\mathcal{S}$ is (symmetric) Haar random gate-set.

Moreover, using Theorem 2 and the Borel-Cantelli Lemmas that we review in
Section 4.1 we prove in Section 5 that for our Random Matrix model the
spectral gap conjecture is fulfilled with the probability $1$.

######  Theorem 3.

In both Haar random and symmetric Haar random settings with the probability
$1$ there exists finite $t\in\mathbb{Z}_{+}$ such that $\delta=\delta(t)$.

In the same Section we also prove concrete bounds for the tail probability
$\mathbb{P}\left(\delta>2+\epsilon\right)$.

######  Theorem 4.

The tail probability of $\delta(\nu_{\mathcal{S}})$ is bounded by:

$\displaystyle\mathbb{P}\left(\delta>2+\epsilon\right)\leq\frac{e^{-\epsilon^{2}/(2c^{2})}}{2(e^{\epsilon^{2}/c^{2}}-1)},\;\mathrm{if}\;d=2\;\mathrm{and}\;\epsilon>0,$
$\displaystyle\mathbb{P}\left(\delta>2+\epsilon\right)\leq
e^{-\frac{d(d+1)}{4c^{2}}\epsilon^{2}}\left(e^{2\pi\sqrt{\frac{d+2}{3}}}\frac{60+100\pi\sqrt{3d+6}}{d+2}-b\right)+$
$\displaystyle+\frac{60}{d^{2}}\left(2+\frac{\sqrt{2\pi}c}{\epsilon}\right)e^{-\frac{3}{4c^{2}}d(d-1)\epsilon^{2}+2\pi\sqrt{\frac{d}{3}}},\;\mathrm{if}\;d\geq
2\;\mathrm{and}\;\epsilon>c\left(\frac{4\pi^{2}}{3d(d-1)^{2}}\right)^{1/4},$

where

$b=10\left[8\pi^{2}\mathrm{Ei}\left(2\sqrt{\frac{2}{3}}\pi\right)-e^{2\sqrt{\frac{2}{3}}\pi}(3+2\sqrt{6}\pi)\right]\approx
3855.93,$

and $c=1$ in the Haar random setting and $c=\sqrt{2}$ in the symmetric Haar
random setting.

As a direct consequence of Theorem 1 for any $t\in\mathbb{Z}_{+}$ and given
precision $\eta>0$ there is $N_{0}=N(d,\eta,t)$ such that for a (symmetric)
Haar random gate-set $\mathcal{S}$ with $|\mathcal{S}|>N_{0}$ we have
$\mathbb{P}\left(\sqrt{\mathcal{S}}\delta(\nu_{\mathcal{S}},t)>2+\epsilon\right)\leq\eta+\mathbb{P}\left(\delta(t)>2+\epsilon\right)$.
In Section 6 we compare $\delta(\lambda)$ and $\delta(t)$ with the numerical
simulations of $\sqrt{\mathcal{S}}\delta({\nu_{\mathcal{S}},\lambda})$ and
$\sqrt{\mathcal{S}}\delta({\nu_{\mathcal{S}},t})$ for $d=2$, $1\leq t\leq 500$
and for $d=4$, $1\leq t\leq 6$. We show that they match nicely for any
cardinality of $\mathcal{S}$. In Section 6 we provide a heuristic explanation
of this phenomena that uses spectral properties of $T_{\nu_{\mathcal{S}},t}$
and $T_{\nu_{\mathcal{S}},\lambda}$ described in Section 3. This heuristic
arguments and numerical results lead to the following conjecture:

######  Conjecture 1.

Let $\epsilon>0$. For any (symmetric) Haar random $\mathcal{S}\subset U(d)$
with at least $3$ elements ($2$ elements and their inverses) we have:

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)>\frac{2+\epsilon}{\sqrt{|\mathcal{S}|}}\right)\leq
F_{\ast}(d_{\lambda},\epsilon),$ (10)

where $\ast\in\\{O,U,R,C\\}$ and the correspondence between $\ast$, $\lambda$
and the type of a gate-set is as in Theorem 2. Moreover, for any fixed
cardinality of $\mathcal{S}$ there is $\lambda_{0}$ such that for any
$\lambda$ with $d_{\lambda}>d_{\lambda_{0}}$ we have

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)>\frac{2+\epsilon}{\sqrt{|\mathcal{S}|}}\right)\leq\mathbb{P}\left(\delta(\lambda)>2+\epsilon\right).$
(11)

As a direct consequence of this conjecture we can rewrite Theorem 2 and
Theorem 4 replacing $\delta(t)$ by
$\sqrt{|\mathcal{S}|}\delta(\nu_{\mathcal{S}},t)$. Moreover, assuming
Conjecture 1 holds we prove in Section 5 that for a (symmetric) Haar random
gate-set $\mathcal{S}$ with the probability $1$ there exists finite
$t\in\mathbb{Z}_{+}$ such that
$\delta(\nu_{\mathcal{S}})=\delta(\nu_{\mathcal{S}},t)$.

Throughout the paper we denote our results by Theorems and Lemmas, and by
Facts we denote results taken from the literature.

##  2 Moment operators

Let $\\{\mathcal{S},\nu_{\mathcal{S}}\\}$ be an ensemble of quantum gates,
where $\mathcal{S}$ is a finite subset of $U(d)$ and $\nu_{\mathcal{S}}$ is
any measure on $\mathcal{S}$. We define the _moment operator_ associated with
a measure $\nu$ by:

$\displaystyle
T_{\nu,t}\coloneqq\int_{G_{d}}d\nu(U)U^{t,t},\,\,\mathrm{where}\,U^{t,t}=U^{\otimes
t}\otimes\bar{U}^{\otimes t}.$ (12)

In the following we will be interested in

$\displaystyle\delta(\nu_{\mathcal{S}},t):=\left\|T_{\nu_{\mathcal{S}},t}-T_{\mu,t}\right\|,$
(13)

where $\|\cdot\|$ is the operator norm and $\mu$ is the Haar measure on $U(d)$
with the normalization $\mu(U(d))=1$. In the remaining part of the paper we
will often use the following notation

$\displaystyle\underset{U\sim\nu}{\mathbb{E}}f(U):=\int_{U(d)}d\nu(U)f(U).$
(14)

Let us first note that the map $U\mapsto U^{t,t}$ is a representation of the
unitary group $U(d)$. This representation is reducible and decomposes into
irreducible representations of $U(d)$. Those are usually labeled by sequences
of $d$ non-increasing integers called highest weights. To simplify our
description we introduce the following notation. For
$\lambda=\left(\lambda_{1},...,\lambda_{d}\right)\in\mathbb{Z}^{d}$, that
satisfies $\lambda_{k}\geq\lambda_{k+1}$ for any $k\in\\{1,\ldots,d-1\\}$, we
denote

  * •

by $\pi_{\lambda}$ the corresponding irreducible representation and by
$d_{\lambda}:=\mathrm{dim}\pi_{\lambda}$ its dimension given by:

$\displaystyle d_{\lambda}=\prod_{1\leq i<j\leq
d}\frac{\lambda_{i}-\lambda_{j}+j-i}{j-i},$ (15)

  * •

by $l(\lambda):=d$ the length of $\lambda$,

  * •

by $\Sigma(\lambda):=\sum_{i=1}^{d}\lambda_{i}$ the sum of the entries of
$\lambda$,

  * •

by $\|\lambda\|_{1}\coloneqq\sum_{k=1}^{d}|\lambda_{k}|$ the sum of the
absolute values of the entries of $\lambda$,

  * •

by $\lambda_{+}$ the subsequence of positive integers in $\lambda$.

It is worth mentioning here that the irreducible representation
$\pi_{\lambda}$ of the unitary group $U(d)$ gives rise to an irreducible
representation of the special unitary group $SU(d)$ by the restriction
$\pi_{\lambda}|_{SU(d)}$. In the literature irreducible representations of
$SU(d)$ are typically labeled by sequences of integers called highest weights
and denoted by $\lambda^{s}$ or by Young diagrams denoted by $\lambda^{Y}$.
The relations between the highest weight $\lambda$ of $\pi_{\lambda}$ and the
highest weight $\lambda^{s}$ and the Young diagram $\lambda^{Y}$ of
$\pi_{\lambda}|_{SU(d)}$ are given by:

$\displaystyle\lambda^{Y}$
$\displaystyle=(\lambda_{1}-\lambda_{d},\lambda_{2}-\lambda_{d},...,\lambda_{d-1}-\lambda_{d},0),$
(16) $\displaystyle\lambda^{s}$
$\displaystyle=(\lambda_{1}-\lambda_{2},\lambda_{2}-\lambda_{3},...,\lambda_{d-1}-\lambda_{d},0).$
(17)

As the last integer in the above formulas is always zero typically it is
omitted. For the further discussion and details see Lemma 5 in our recent work
[24].

######  Fact 1.

([28]) Irreducible representations that appear in the decomposition of
$U\mapsto U^{\otimes t}\otimes\bar{U}^{\otimes t}$ are $\pi_{\lambda}$ with
$l(\lambda)=d$, $\Sigma(\lambda)=0$ and $\Sigma(\lambda_{+})\leq t$. That is
we have

$\displaystyle U^{\otimes t}\otimes\bar{U}^{\otimes t}\simeq\text{1}^{\oplus
m_{0}}\oplus\bigoplus_{\lambda\in\Lambda_{t}}\pi_{\lambda}(U)^{\oplus
m_{\lambda}}\simeq\left(U\otimes\bar{U}\right)^{\otimes t},$ (18)

where

$\displaystyle\Lambda_{t}=\left\\{\lambda=(\lambda_{1},\ldots,\lambda_{d})|\,\lambda\in\mathbb{Z}^{d},\lambda\neq
0,\,\forall_{k}\,\lambda_{k}\geq\lambda_{k+1},\,\Sigma(\lambda)=0,\,\Sigma(\lambda_{+})\leq
t\right\\},$ (19)

and 1 stands for the trivial representation and $m_{0}$ is its multiplicity
and $m_{\lambda}$ is the multiplicity of $\pi_{\lambda}$.

The representations occurring in decomposition (18) are in fact irreducible
representation of the projective unitary group, $PU(d)=U(d)/\sim$, where
$U\sim V$ iff $U=e^{i\phi}V$. One can show that every irreducible
representation of $PU(d)$ arises this way for some, possibly large, $t$ [29].
For $t=1$ decomposition (18) is particularly simple and reads
$U\otimes\bar{U}\simeq\mathrm{Ad}_{U}\oplus\text{1}$, where $\mathrm{Ad}_{U}$
is the adjoint representation of $U(d)$ and
$PU(d)\simeq\mathrm{Ad}_{U(d)}$111By $\mathrm{Ad}_{U}$ we mean the matrix
$\mathrm{Ad}_{U}:\mathfrak{su}(d)\rightarrow\mathfrak{su}(d)$,
$\mathrm{Ad}_{U}(X)=UXU^{-1}.$.

We further note that $U\mapsto U^{\otimes t}\otimes\bar{U}^{\otimes t}$ is a
real representation and as such can be decomposed into the direct sum of real
irreducible representations. When acting on a complex vector space, an
irreducible real representation $\pi(U)$ can be either

  1. 1.

irreducible on both complex and real vector spaces

  2. 2.

irreducible when acting on a real vector space but when acting on a complex
vector space a direct sum
$\pi(U)=\pi_{\lambda}(U)\oplus\overline{\pi_{\lambda}(U)}$, where
$\pi_{\lambda}$ is a complex irreducible representation of $U(d)$ and
$\overline{\pi_{\lambda}}$ is the conjugate representation of $\pi_{\lambda}$.

It is also known that $\overline{\pi_{\lambda}(U)}=\pi_{\lambda^{\ast}}(U)$,
where
$\lambda^{\ast}=-(\lambda_{d},\lambda_{d-1},\ldots,\lambda_{2},\lambda_{1})$.
Summing up irreducible representations showing up in the decomposition (18)
are either real or complex representations (there are no quaternion
representations). Furthermore for $\lambda\in\Lambda_{t}$, the representation
$\pi_{\lambda}$ is real iff $\lambda_{i}=-\lambda_{d-i+1}$, for any
$i\in\\{1,2,\ldots,d\\}$ and is complex otherwise (see also Proposition 26.24
[30] for analogous conditions when $\lambda$ is arbitrary). In the following
we will denote by $\Lambda_{t}^{r}$ a subset of $\lambda$’s in $\Lambda_{t}$
that correspond to real representations and by $\Lambda_{t}^{c}$ a subset of
$\lambda$’s in $\Lambda_{t}$ that correspond to complex representations. For
any irreducible representation $\pi_{\lambda}$, $\lambda\in\Lambda_{t}$ we
define

$\displaystyle
T_{\nu_{\mathcal{S}},\lambda}\coloneqq\underset{U\sim\nu_{\mathcal{S}}}{\mathbb{E}}\pi_{\lambda}(U),\,\,\,\delta(\nu_{\mathcal{S}},\lambda)\coloneqq\|T_{\nu_{\mathcal{S}},\lambda}\|.$
(20)

One easily see that

$\displaystyle\delta(\nu_{\mathcal{S}},\lambda)=\left\|\underset{U\sim\nu_{\mathcal{S}}}{\mathbb{E}}\pi_{\lambda}(U)\right\|\leq\underset{U\sim\nu_{\mathcal{S}}}{\mathbb{E}}\|\pi_{\lambda}(U)\|=1$
(21)

Thus $\delta_{\nu_{\mathcal{S}},\lambda}\in[0,1]$. It follows directly from
Fact 1 that

$\displaystyle T_{\nu_{\mathcal{S}},t}\simeq\text{1}^{\oplus
m_{0}}\oplus\bigoplus_{\lambda\in\Lambda_{t}}\left(T_{\nu_{\mathcal{S}},\lambda}\right)^{\oplus
m_{\lambda}}.$ (22)

Using the fact that $\underset{U\sim\mu}{\mathbb{E}}\pi_{\lambda}(U)=0$ for
any nontrivial irreducible representation $\pi_{\lambda}$ we see that
$T_{\mu,t}=\text{1}^{\oplus m_{0}}$. Thus we have:

$\displaystyle\delta(\nu_{\mathcal{S}},t)=\left\|T_{\nu_{\mathcal{S}},t}-T_{\mu,t}\right\|=\left\|\bigoplus_{\lambda\in\Lambda_{t}}\left(T_{\nu_{\mathcal{S}},\lambda}\right)^{\oplus
m_{\lambda}}\right\|=\mathrm{sup}_{\lambda\in\Lambda_{t}}\|T_{\nu_{\mathcal{S}},\lambda}\|=\mathrm{sup}_{\lambda\in\Lambda_{t}}\delta(\nu_{\mathcal{S}},\lambda).$
(23)

Thus $\delta(\nu_{\mathcal{S}},t)\in[0,1]$. An ensemble for which
$\delta(\nu_{\mathcal{S}},t)=\delta<1$ is called $\delta$-approximate
$t$-design. One can also define

$\displaystyle\delta(\nu_{\mathcal{S}}):=\mathrm{sup}_{t}\delta(\nu_{\mathcal{S}},t)\in[0,1],$
(24)

which, by the Peter-Weyl theorem, is equal to the operator norm of the moment
operator $T_{\nu_{\mathcal{S}}}$ acting on functions $f\in L^{2}(PU(d))$ that
have vanishing mean value, $\int d\mu(U)f(U)=0$ (see [31] for detailed
derivation):

$\displaystyle(T_{\nu_{\mathcal{S}}}f)(U)=\int
d\nu_{\mathcal{S}}(V)f(V^{-1}U).$ (25)

Finally we note that since
$T_{\nu_{\mathcal{S}},\lambda^{\ast}}=\overline{T}_{\nu_{\mathcal{S}},\lambda}$
we have
$\|T_{\nu_{\mathcal{S}},\lambda}\|=\|T_{\nu_{\mathcal{S}},\lambda^{\ast}}\|$.
In order to remove this redundancy we define $\tilde{\Lambda}_{t}^{c}$ to be a
subset of $\Lambda_{t}^{c}$ that for any pair
$\lambda,\lambda^{\ast}\in\Lambda_{t}^{c}$ contains either $\lambda$ or
$\lambda^{\ast}$, but not both. Then

$\displaystyle\Lambda_{t}^{\mathrm{ess}}:=\Lambda_{t}^{r}\cup\tilde{\Lambda}_{t}^{c},$
(26)
$\displaystyle\Lambda^{\mathrm{ess}}:=\bigcup_{t}\Lambda_{t}^{\mathrm{ess}}.$
(27)

In particular

$\displaystyle\delta(\nu_{\mathcal{S}},t)=\mathrm{sup}_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\delta(\nu_{\mathcal{S}},\lambda),$
(28)
$\displaystyle\delta(\nu_{\mathcal{S}})=\sup_{t}\delta(\nu_{\mathcal{S}},t).$
(29)

We will also need some properties of partitions. Recall that a partition of a
positive integer $k$ is a way of writing $k$ as a sum of positive integers. We
will denote by $p_{n}(k)$ the number of partitions of $k$ with exactly $n$
nonzero integers and by $\tilde{p}_{n}(k)$ the number of partitions of $k$
with at most $n$ nonzero integers. Finally by $p(k)$ we will denote the number
of all partitions of the integer $k$. We have the following two Facts:

######  Fact 2.

([24]) Assume $\lambda\in\tilde{\Lambda}_{t}$. Then $\|\lambda\|_{1}=2k$,
where the integer $k$ satisfies $1\leq k\leq t$. Moreover, the number of
distinct irreducible representations $\pi_{\lambda}$ with $\|\lambda\|_{1}=2k$
is given by

$\displaystyle\alpha_{2k}=\left\\{\begin{array}[]{ll}p(k)^{2}&d\geq 2k,\\\
\sum_{n=1}^{k}p_{n}(k)\tilde{p}_{d-n}(k)&k+1\leq d<2k,\\\
\sum_{n=1}^{d-1}p_{n}(k)\tilde{p}_{d-n}(k)&2\leq d\leq k.\end{array}\right.$
(33)

Moreover, for any $d$ we have $\alpha_{2k}\leq p(k)^{2}$.

######  Fact 3.

([32]) Let $k$ and $n$ be positive integers. Then

$\displaystyle\frac{0.0036}{k}e^{\pi\sqrt{\frac{2k}{3}}}\leq
p(k)\leq\frac{5.44}{k}e^{\pi\sqrt{\frac{2k}{3}}},$ (34) $\displaystyle
p_{n}(k)\leq\frac{1}{n!(n-1)!}\left(k+\frac{n(n-3)}{4}\right)^{n-1},\,4\leq
n\leq k.$

######  Lemma 5.

Let $\lambda\in\Lambda_{t}$ be such that $\|\lambda\|_{1}=2k$ and
$l(\lambda)=d\geq 2$. Then $d_{\lambda}\geq 2k$. Moreover,

$\displaystyle d_{\lambda}\geq\left\\{\begin{array}[]{ll}\binom{d+1}{2}&2k\leq
d,\\\ \binom{d}{2}+(d-1)2k&2k\geq d.\\\ \end{array}\right.$

###### Proof.

Let

$\displaystyle\eta(n):=(\underbrace{1,...,1}_{n},\underbrace{0,\ldots,0}_{d-n})\quad\mathrm{for}\quad
n=1,...,d-1,$

be the so-called fundamental weights of $SL(d,\mathbb{C})$ [30]. For any
$\lambda=(\lambda_{1},\ldots,\lambda_{d})$ that belongs to $\Lambda_{t}$ we
define
$\lambda^{Y}:=(\lambda_{1}-\lambda_{d},\ldots,\lambda_{d-1}-\lambda_{d},0)$.
We note that $\lambda^{Y}$ can be viewed as the Young diagram corresponding to
the irreducible representation of $SU(d)$, and hence $SL(d,\mathbb{C})$, that
arises as the restriction $\pi_{\lambda}|_{SU(d)}$. One can easily see that
$\lambda^{Y}$ can be written as

$\displaystyle\lambda^{Y}=\sum_{n=1}^{d-1}\lambda^{s}_{n}\eta(n),\quad\,\lambda^{s}_{n}:=\lambda_{n}-\lambda_{n+1}.$
(35)

Let us also define

$\displaystyle
h(\lambda):=\sum_{n=1}^{d-1}\lambda^{s}_{n}=\lambda_{1}-\lambda_{d}.$ (36)

Lemmas 2.1 and 2.2 from [33] combined with the fact that
$d_{\lambda}=d_{\lambda^{Y}}$ ensure that

$d_{\lambda}\geq\min_{1\leq n\leq
d-1}d_{h(\lambda)\cdot\eta(n)}=d_{h(\lambda)\cdot\eta(m)},$ (37)

where $1\leq m\leq d-1$ is such that:

$\min_{1\leq n\leq d-1}d_{\eta(n)}=d_{\eta(m)}.$ (38)

Therefore in order to use (37) we need to find out which $d_{\eta(n)}$ is the
smallest one. For this purpose we use the dimension formula (15) and get

$\displaystyle d_{\eta(n)}=\prod_{1\leq i<j\leq
d}\frac{j-i+\eta(n)_{i}-\eta(n)_{j}}{j-i}=\prod_{1\leq i\leq n}\prod_{n<j\leq
d}\frac{j-i+1}{j-i}=$ $\displaystyle=\prod_{1\leq i\leq
n}\frac{(d+1-i)!(n-i)!}{(n+1-i)!(d-i)!}=\prod_{1\leq i\leq
n}\frac{d+1-i}{n+1-i}=\frac{d!}{(d-n)!n!}=\binom{d}{n},$

which is more or equal to $d$ for $1\leq n\leq d-1$. Therefore:

$\min_{1\leq n\leq d-1}d_{\eta(n)}\geq d=d_{\eta(1)}=d_{\eta(d-1)},$

and $m$ from (37) and (38) is equal to $1$ (or $d-1$). If
$\|\lambda\|_{1}=2k\leq d$ then clearly:

$h(\lambda)=\lambda_{1}-\lambda_{d}\geq 1-(-1)=2\geq\frac{4k}{d},$ (39)

and if $2k>d$ then:

$\zeta(n)=(\underbrace{\frac{k}{n},...,\frac{k}{n}}_{n},\underbrace{-\frac{k}{d-n},...,-\frac{k}{d-n}}_{d-n})\quad\mathrm{for}\quad
n=1,...,d-1,$

is an element of $\mathbb{R}^{d}$ with the smallest possible $h(\zeta(n))$
that satisfies $l(\zeta(n)_{+})=n$, $\zeta(n)_{i}\geq\zeta(n)_{i+1}$,
$\Sigma(\zeta(n))=0$ and $\|\zeta(n)\|_{1}=2k$. Thus

$h(\lambda)\geq\min_{1\leq n\leq d-1}h(\zeta(n))=\min_{1\leq n\leq
d-1}\frac{kd}{n(d-n)}=\frac{kd}{\lfloor\frac{d}{2}\rfloor\lceil\frac{d}{2}\rceil}\geq\frac{4k}{d}.$
(40)

Now we can prove our thesis for $2k\leq d$. Using (37) and (39) we get that:

$\displaystyle d_{\lambda}\geq d_{h(\lambda)\cdot\eta(1)}\geq
d_{2\cdot\eta(1)}=\prod_{1\leq i<j\leq
d}\frac{j-i+2(\eta(n)_{i}-\eta(n)_{j})}{j-i}=$ $\displaystyle=\prod_{1<j\leq
d}\frac{j-1+2}{j-1}=\frac{(d+1)!}{2!(d-2)!}=\binom{d+1}{2},$

which is bigger than $d$ when $d\geq 2$. Hence:

$d_{\lambda}\geq d\geq 2k.$

In case $2k>d$ we use (40) to obtain:

$\displaystyle d_{h(\lambda)\cdot\eta(1)}=\prod_{1<j\leq
d}\frac{j-1+h(\lambda)}{j-1}\geq\prod_{1<j\leq
d}\frac{j-1+\frac{4k}{d}}{j-1}=\frac{\prod_{1<j\leq
d}[d(j-1)+4k]}{(d-1)!d^{d-1}}=:f(k)$ (41)

Function $f$ defined in (41) can be naturally extended to $\mathbb{R}$. Under
this extension $f$ is a polynomial of rank $d-1$ with positive coefficients.
From (37) we have $d_{\lambda}\geq f(k)$ so we want to prove that $f(k)\geq
2k$ for any $k\geq\frac{d}{2}$. We first note that at $k=\frac{d}{2}$ this
inequality is satisfied:

$f\left(\frac{d}{2}\right)=\binom{d}{2}\geq d.$

Next we compute the derivative of $f$:

$\displaystyle
f^{\prime}(k)=4\sum_{i=2}^{d}\frac{\prod_{\begin{subarray}{c}1<j\leq d\\\
j\neq
i\end{subarray}}[d(j-1)+4k]}{(d-1)!d^{d-1}}=4f(k)\sum_{i=2}^{d}\frac{1}{d(i-1)+4k}\geq
4f(k)\frac{d-1}{d(d-1)+4k}.$

Using (41) we get:

$\displaystyle f^{\prime}(k)\geq\frac{4\prod_{1<j\leq
d-1}[d(j-1)+4k]}{(d-2)!d^{d-1}}\geq\frac{4\prod_{1<j\leq
d-1}[d(j-1)+2d]}{(d-2)!d^{d-1}}=\frac{4}{d}\binom{d}{2}=2(d-1)>1,$

where in the second inequality we used our assumption that $2k>d$. In summary,
we have that $f\left(\frac{d}{2}\right)>d$ and that for any $k>\frac{d}{2}$ it
holds $f^{\prime}(k)>1$. It follows that for $k\geq\frac{d}{2}$:

$f(k)\geq
f\left(\frac{d}{2}\right)+f^{\prime}\left(\frac{d}{2}\right)k\geq\binom{d}{2}+(d-1)2k>2k.$

∎

##  3 Spectral measures and moment operators

We say that the measure $\nu_{\mathcal{S}}$ is symmetric, if for every $U$ in
$\mathcal{S}$ the inverse $U^{-1}$ is also in $\mathcal{S}$. For symmetric
measures moment operators $T_{\nu_{\mathcal{S}}}$, $T_{\nu_{\mathcal{S}},t}$
and $T_{\nu_{\mathcal{S}},\lambda}$ defined by (25), (12) and (20) are bounded
self-adjoint operators and therefore their spectra are well defined. In this
section we are interested in asymptotic properties of these spectra when the
size of moment operators grows to infinity.

Recall that for a self-adjoint $n\times n$ matrix $H_{n}$ the spectral measure
of any interval $[a,b]\subset\mathbb{R}$ is defined by:

$\sigma_{H_{n}}([a,b]):=\frac{1}{n}(\\#\;of\;H_{n}\;\mathrm{eigenvalues}\;\mathrm{in}\;[a,b]),$

For $\lambda_{1}(H_{n})\leq...\leq\lambda_{n}(H_{n})$ eigenvalues of $H_{n}$
the $m$-th moment of $\sigma_{H_{n}}$ is:

$\sigma_{H_{n}}^{(m)}=\int
x^{m}d\sigma_{H_{n}}(x)=\frac{1}{n}\sum_{i=1}^{n}\lambda_{i}(H_{n})^{m}=\frac{1}{n}\mathrm{Tr}(H_{n}^{m})=\mathrm{tr}(H_{n}^{m}).$

Recall that a compactly supported measure is determined by its moments. Thus
if for a sequence $\\{H_{n}\\}_{n=1}^{\infty}$ of commonly bounded self-
adjoint matrices there is measure $\sigma_{H}$ for which

$\displaystyle\sigma_{H}^{(m)}=\lim_{n\rightarrow\infty}\sigma_{H_{n}}^{(m)},$
(42)

then this measure is unique and

$\displaystyle\int f(x)d\sigma_{H_{n}}(x)\xrightarrow{n\rightarrow\infty}\int
f(x)d\sigma_{H}(x),$

where $f$ is any continuous function, that is $\sigma_{H_{n}}$ converges
weakly to $\sigma_{H}$. In case when $H_{n}$ is a random matrix we define the
averaged spectral measure:

$\bar{\sigma}_{H_{n}}([a,b]):=\mathbb{E}[\sigma_{H_{n}}([a,b])]$

One easily checks that $m$-th moment of $\bar{\sigma}_{H_{n}}$ is given by

$\displaystyle\bar{\sigma}_{H_{n}}^{(m)}=\int
x^{m}d\bar{\sigma}_{H_{n}}(x)=\mathbb{E}\mathrm{tr}(H_{n}^{m})=\mathbb{E}\sigma_{H_{n}}^{(m)}.$
(43)

Thus if for a sequence $\\{H_{n}\\}_{n=1}^{\infty}$ of commonly bounded random
selfadjoint matrices there is measure $\bar{\sigma}_{H}$ for which

$\displaystyle\bar{\sigma}_{H}^{(m)}=\lim_{n\rightarrow\infty}\bar{\sigma}_{H_{n}}^{(m)},$
(44)

then this measure is unique and

$\displaystyle\int
f(x)d\bar{\sigma}_{H_{n}}(x)\xrightarrow{n\rightarrow\infty}\int
f(x)d\bar{\sigma}_{H}(x),$

where $f$ is any continuous function, that is $\bar{\sigma}_{H_{n}}$ converges
weakly to $\bar{\sigma}_{H}$.

Let us consider sequence $\\{T_{\nu_{\mathcal{S}},t}\\}_{t=1}^{\infty}$, where
$\mathcal{S}\subset U(d)$ is a finite symmetric set. In order to simplify
notation let us denote by $\sigma_{\mathcal{S},t}$ the spectral measure of
$T_{\nu_{\mathcal{S}},t}$. Let $\mathcal{S}_{k}=\\{U_{1}U_{2}\ldots
U_{k}|U_{i}\in\mathcal{S}\\}$ and $\nu_{\mathcal{S}}^{\ast k}$ be the $k$-fold
convolution of $\nu_{\mathcal{S}}$. Of course the support of
$\nu_{\mathcal{S}}^{\ast k}$ is given by $\mathcal{S}_{k}$. We have

$\displaystyle\sigma_{\mathcal{S},t}^{(m)}=\frac{\mathrm{Tr}\left(T^{m}_{\nu_{\mathcal{S}},t}\right)}{d^{2t}}=\frac{1}{d^{2t}}\mathrm{Tr}\left(\int_{U(d)}d\nu_{\mathcal{S}}^{\ast
m}(U)U^{t,t}\right)=\sum_{U_{1},\ldots,U_{m}\in\mathcal{S}}\nu_{\mathcal{S}}^{\ast
m}(U_{1}\ldots U_{m})\mathrm{tr}\left(\left(U_{1}\ldots
U_{m}\right)^{t,t}\right).$ (45)

Note next that for any $U\in U(d)$ that has eigenvalues
$\lambda_{j}(U)=e^{i\phi_{j}}$ we have

$\displaystyle\mathrm{tr}{U^{t,t}}=|\mathrm{tr}(U)|^{2t}=\left|\frac{e^{\phi_{1}}+\ldots+e^{i\phi_{d}}}{d}\right|^{2t}\xrightarrow{t\rightarrow\infty}\left\\{\begin{array}[]{ll}1&\text{if
$U\propto I$ },\\\ 0&\text{otherwise}.\end{array}\right.$ (48)

Assuming the group generated by $\mathcal{S}$ is free we get

$\displaystyle\mathrm{tr}{(U_{1}\ldots
U_{m})^{t,t}}\xrightarrow{t\rightarrow\infty}\left\\{\begin{array}[]{ll}1&\text{if
$U_{1}\ldots U_{m}=I$ },\\\ 0&\text{otherwise}.\end{array}\right.$ (51)

Thus in case when $\nu_{\mathcal{S}}$ is the uniform measure on $\mathcal{S}$
we have

$\displaystyle\lim_{t\rightarrow\infty}\sigma_{\mathcal{S},t}^{(m)}=\frac{1}{|\mathcal{S}|^{m}}\sum_{\begin{subarray}{c}U_{1},...,U_{m}\in\mathcal{S}\\\
U_{1}...U_{m}=\mathbb{I}\end{subarray}}1.$ (52)

The above summation can be interpreted as the number of walks of length $m$
that begin and end in some vertex $v$ on $|S|$-regular tree. This problem was
solved in [34] and

$\displaystyle\lim_{t\rightarrow\infty}\sigma_{\mathcal{S},t}^{(m)}=\left\\{\begin{array}[]{ll}\frac{1}{|\mathcal{S}|^{m}}\sum_{j=1}^{m/2}{m-j\choose
m/2}\frac{j}{m-j}|\mathcal{S}|^{j}(|\mathcal{S}-1|)^{m/2-j}&\text{if
$m$-even},\\\ 0&\text{otherwise}.\end{array}\right.$ (55)

The author of [34] also showed that there is a measure $\sigma_{\mathcal{S}}$
such that
$\sigma_{\mathcal{S}}^{(m)}=\lim_{t\rightarrow\infty}\sigma_{\mathcal{S},t}^{(m)}$.
This measure is know as the Kesten-McKay measure [35, 36] and is given by:

$\displaystyle
d\sigma_{\mathcal{S}}(x)=\frac{|\mathcal{S}|\sqrt{\delta_{\mathrm{opt}}^{2}(\mathcal{S})-x^{2}}}{2\pi(1-x^{2})}\mathbf{1}_{[-\delta_{\mathrm{opt}}(\mathcal{S}),\delta_{\mathrm{opt}}(\mathcal{S})]}dx,$
(56)

where
$\delta_{\mathrm{opt}}(\mathcal{S}):=\frac{2\sqrt{|\mathcal{S}|-1}}{|\mathcal{S}|}$.
We also note that the $m$-th moment of the spectral measure of
$T_{\nu_{\mathcal{S}}}^{2}$, i.e.
$\lim_{t\rightarrow\infty}\frac{\mathrm{Tr}\left(T^{2m}_{\nu_{\mathcal{S}},t}\right)}{d^{2t}}$
is given by

$\displaystyle\frac{1}{|\mathcal{S}|^{2m}}\sum_{j=1}^{m}{2m-j\choose
m}\frac{j}{2m-j}|\mathcal{S}|^{j}(|\mathcal{S}-1|)^{m-j}.$ (57)

Using the symmetry of measure (56) making the change of variables $y=x^{2}$ in
(56) one can easily see that when $t\rightarrow\infty$ the spectral measure of
$T_{\nu_{\mathcal{S}},t}^{2}$ is given by

$\displaystyle\frac{|\mathcal{S}|\sqrt{\delta_{\mathrm{opt}}^{2}(\mathcal{S})y-y^{2}}}{2\pi(1-y)y}\mathbf{1}_{[0,\delta_{\mathrm{opt}}^{2}(\mathcal{S})]}dy.$
(58)

One can verify that the $m$-th moment of (58), i.e.

$\displaystyle\int_{0}^{\delta^{2}_{\mathrm{opt}}(\mathcal{S})}y^{m-1}\frac{|\mathcal{S}|\sqrt{\delta_{\mathrm{opt}}^{2}(\mathcal{S})y-y^{2}}}{2\pi(1-y)}dy,$
(59)

is indeed given by (57) for every $m\in\mathbb{Z}_{+}$. We are now ready to
treat the case when $\mathcal{S}$ is not symmetric. To this end assume
$\mathcal{S}=\\{U_{1},\ldots,U_{n}\\}$ is such that
$\mathcal{S}\cup\mathcal{S}^{-1}$ generates a free group. Repeating similar
arguments as for $T_{\nu_{\mathcal{S}},t}$, one sees that the $m$-th moment of
the spectral measure of
$T_{\nu_{\mathcal{S}},t}T_{\nu_{\mathcal{S}},t}^{\ast}$ can be calculated as
the number of closed paths of the length $2m$, starting and ending at the same
vertex of the infinite $|\mathcal{S}|$-regular tree. Thus it is given by the
formula (57), where $|S|=n$. Therefore the spectral measure of
$T_{\nu_{\mathcal{S}},t}T_{\nu_{\mathcal{S}},t}^{\ast}$, when
$t\rightarrow\infty$ is given by (58). Hence the distribution of singular
values of $T_{\nu_{\mathcal{S}}}$, or in other words the spectral measure of
$\left(T_{\nu_{\mathcal{S}}}T_{\nu_{\mathcal{S}}}^{\ast}\right)^{\frac{1}{2}}$
is given by:

$\displaystyle\frac{|\mathcal{S}|\sqrt{\delta_{\mathrm{opt}}^{2}(\mathcal{S})-x^{2}}}{\pi(1-x^{2})}\mathbf{1}_{[0,\delta_{\mathrm{opt}}(\mathcal{S})]}dx.$
(60)

Obviously formula (60) gives also the distribution of the singular values of
$T_{\nu_{\mathcal{S}}}$ when $\mathcal{S}$ is symmetric. As a conclusion we
get

######  Fact 4.

Let $\mathcal{S}\subset U(d)$ be a finite set and assume that the group
generated by $\mathcal{S}\cup\mathcal{S}^{-1}$ is free. Then
$\delta(\nu_{\mathcal{S}})\in[\delta_{\mathrm{opt}}(\mathcal{S}),1]$.

Finally we note that similar reasoning can be mutatis mutandis repeated for
$T_{\nu_{\mathcal{S}},\lambda}$. Let us denote by
$\sigma_{\mathcal{S},\lambda}$ the spectral measure of
$T_{\nu_{\mathcal{S}},\lambda}$. For example when $d=2$ we have

$\displaystyle\sigma_{\mathcal{S},\lambda}^{(m)}=\frac{1}{d_{\lambda}}\mathrm{Tr}\left(\int_{U(d)}d\nu_{\mathcal{S}}^{\ast
m}(U)\pi_{\lambda}(U)\right)=\frac{1}{d_{\lambda}}\sum_{U_{1},\ldots,U_{m}\in\mathcal{S}}\nu_{\mathcal{S}}^{\ast
m}(U_{1}\ldots U_{m})\chi_{\lambda}(U_{1}\ldots U_{m}),$ (61)

where $\chi_{\lambda}(U)=\mathrm{Tr}(\pi_{\lambda}(U))$ is the character of
the representation $\pi_{\lambda}$. In case of $d=2$ we have $\lambda=(k,-k)$,
$d_{\lambda}=2k+1$ and

$\displaystyle\chi_{\lambda}(U)=\frac{\sin(2k+1)\theta}{\sin\theta},$ (62)

where $\theta$ is such that the spectrum of $U$ is
$\\{e^{i\theta},e^{-i\theta}\\}$. It is clear that when $k\rightarrow\infty$

$\displaystyle\lim_{k\rightarrow\infty}\frac{1}{2k+1}\chi_{\lambda}(U)\xrightarrow{k\rightarrow\infty}\left\\{\begin{array}[]{ll}1&\text{if
$U\propto I$ },\\\ 0&\text{otherwise}.\end{array}\right.$ (65)

Therefore, continuing like for $\sigma_{\mathcal{S},t}$, we obtain that in the
limit $k\rightarrow\infty$ the distribution of the singular values of
$T_{\nu_{\mathcal{S}},\lambda}$ converges weakly to the measure given by (60).
Similar, although much more technical reasoning can be also repeated when
$d>2$.

##  4 Asymptotic behaviour of $\delta(\nu_{\mathcal{S}},t)$ for large
$\mathcal{S}$

In Section 3 we showed that for a universal (symmetric) set $\mathcal{S}$ such
that ($\mathcal{S}$) $\mathcal{S}\cup\mathcal{S}^{-1}$ generates a free group,
when $t\rightarrow\infty$ the singular values of $T_{\nu_{\mathcal{S}},t}$ are
distributed in the interval $[0,\delta_{\mathrm{opt}}(\mathcal{S})]$ with the
density given by (60). We first note that when
$|\mathcal{S}|\rightarrow\infty$ then
$\delta_{\mathrm{opt}}(\mathcal{S})\rightarrow 0$. Thus in order to capture
asymptotic properties of $\delta(\nu_{\mathcal{S}},t)$ we normalize it by the
factor $\sqrt{\mathcal{S}}$, that is in the following we will consider
operator $\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},t}$. The distribution of
singular values of this normalized operator can be easily obtained from (60)
by the change of variables $y=\sqrt{S}x$ and is given by the density:

$\displaystyle\frac{1}{\pi(1-\frac{y^{2}}{\mathcal{S}})}\sqrt{\frac{4\left(\mathcal{S}-1\right)}{\mathcal{S}}-y^{2}}\mathbf{1}_{[0,2\sqrt{\frac{\mathcal{S}-1}{\mathcal{S}}}]}.$
(66)

When $S\rightarrow\infty$ one easily shows that (66) converges to the quarter-
circle distribution with the density function

$\displaystyle\sigma_{QC}(y)=\frac{1}{\pi}\sqrt{4-y^{2}}\mathbf{1}_{[0,2]}.$
(67)

Unfortunately, this limiting behaviour of the spectrum of
$T_{\nu_{\mathcal{S}},t}$ (or $T_{\nu_{\mathcal{S}},\lambda}$) does not fully
determine distribution of the norm. For example, it is known that for all
properly normalized random matrix $\beta$-ensembles the limiting spectral
measure is given by (67) but the distributions of the largest/smallest
eigenvalues or of the norm depend on $\beta$. In the next sections we
determine ensembles that correspond to the distribution of the norm of
$\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}$ for (symmetric) Haar random
gate-sets. In particular we show that they depend on the type of
representation $\lambda$ and on the symmetry of $\mathcal{S}$.

###  4.1 Tools

In this section we explain tools that will be used in the subsequent sections
to study the distribution of $\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}$
when $\mathcal{S}\rightarrow\infty$.

##### Orthogonality relations

Let $\pi_{\lambda}$ and $\pi_{\eta}$ be two irreducible representation of
$U(d)$. It is easy to check that for any linear map
$\Psi:V_{\lambda}\rightarrow V_{\eta}$ the map

$\displaystyle\Psi_{0}=\underset{U\sim\mu}{\mathbb{E}}\left(\pi_{\eta}(U^{-1})\Psi\pi_{\lambda}(U)\right),$
(68)

satisfies $\pi_{\eta}(V^{-1})\Psi_{0}\pi_{\lambda}(V)=\Psi_{0}$, for any $V\in
U(d)$. Thus by Schur’s lemma $\Psi_{0}=0$ if $\eta\neq\lambda$ and
$\Psi_{0}=\frac{\mathrm{Tr}\Psi}{d_{\lambda}}\text{1}_{d_{\lambda}}=\mathrm{tr}\Psi\text{1}_{d_{\lambda}}$
if $\lambda=\eta$. Choosing
$[\Psi]_{j^{\prime}k^{\prime}}=\delta_{jj^{\prime}}\delta_{kk^{\prime}}$ for
some fixed $j$ and $k$ we get222For a matrix $A$ we denote by $[A]_{ij}$ its
entry $(i,j)$.

$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[\pi_{\eta}(U^{-1})\right]_{ij}\left[\pi_{\lambda}(U)\right]_{kl}\right)=\frac{\delta_{\eta,\lambda}\delta_{il}\delta_{jk}}{d_{\lambda}}.$
(69)

We also know that there is a basis in $V_{\lambda}$ such that:

  1. 1.

$\pi_{\lambda}(U^{-1})=\pi_{\lambda}(U)^{T}$, when
$\lambda\in\Lambda_{t}^{r}$,

  2. 2.

$\pi_{\lambda}(U^{-1})=\pi_{\lambda}(U)^{\dagger}$, when
$\lambda\in\Lambda_{t}^{c}$.

Therefore

$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[\pi_{\lambda}(U)\right]_{ji}\left[\pi_{\lambda}(U)\right]_{kl}\right)=\frac{\delta_{jk}\delta_{il}}{d_{\lambda}}\,\,\mathrm{if}\,\lambda\in\Lambda_{t}^{r},$
(70)

and

$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\overline{\left[\pi_{\lambda}(U)\right]}_{ji}\left[\pi_{\lambda}(U)\right]_{kl}\right)=\frac{\delta_{jk}\delta_{il}}{d_{\lambda}}\,\,\mathrm{if}\,\lambda\in\Lambda_{t}^{c}.$
(71)

In addition to (71) we have one more relation for complex representations. If
$\lambda\in\Lambda_{t}^{c}$ then $\pi_{\lambda^{\ast}}$ is not equivalent to
$\pi_{\lambda}$. On the other hand, in a basis in which $\pi_{\lambda}(U)$ is
unitary we have $\pi_{\lambda^{\ast}}(U)=\overline{\pi_{\lambda}(U)}$. Thus

$\displaystyle
0=\underset{U\sim\mu}{\mathbb{E}}\left(\left[\pi_{\lambda^{\ast}}(U^{-1})\right]_{ij}\left[\pi_{\lambda}(U)\right]_{kl}\right)=\underset{U\sim\mu}{\mathbb{E}}\left(\left[\overline{\pi_{\lambda}(U^{-1})}\right]_{ij}\left[\pi_{\lambda}(U)\right]_{kl}\right)=$
(72)
$\displaystyle=\underset{U\sim\mu}{\mathbb{E}}\left(\left[\pi_{\lambda}(U)\right]_{ji}\left[\pi_{\lambda}(U)\right]_{kl}\right),\,\,\mathrm{for}\,\mathrm{all}\,i,j,k,l,\,\mathrm{if}\,\lambda\in\Lambda_{t}^{c}.$

Relations (70), (71) and (72) will play a central role in the next sections.

##### Central Limit Theorem

Let us next note that for a (symmetric) Haar random gate-set $\mathcal{S}$ the
entries of $T_{\nu_{\mathcal{S}},\lambda}$ are given by sums of $n$
independent random variables. Therefore we recall the following variant of the
Central Limit Theorem [37]:

######  Fact 5.

Let $\overline{X}=(X_{1},X_{2},\ldots,X_{d})$ be a random vector in
$\mathbb{R}^{d}$ with finite second moments and $\mathbb{E}(X_{i})=0$, for
every $i$. Let $\mathrm{Cov}(\overline{X})$ be the covariance matrix of
$\overline{X}$, i.e. a matrix whose $ij^{\mathrm{th}}$ entry is

$\displaystyle\Sigma_{ij}:=\left[\mathrm{Cov}(X)\right]_{ij}=\mathbb{E}\left(X_{i}X_{j}\right).$
(73)

Let

$\displaystyle\overline{M}_{n}=\frac{\overline{X}_{1}+\overline{X}_{2}+\ldots+\overline{X}_{n}}{\sqrt{n}},$
(74)

be the sum of $n$ IID (Independent Identically Distributed) copies of
$\overline{X}$. Then $\overline{M}_{n}$ converges in distribution to the
random vector $\overline{M}$ which is distributed according to the
multivariate normal distribution $N(0,\Sigma)$ with the density

$\displaystyle
f(\overline{M})=\frac{1}{\left((2\pi)^{d}\det{\Sigma}\right)^{1/2}}e^{-\frac{1}{2}\overline{M}^{T}\Sigma^{-1}\overline{M}}.$
(75)

##### Vectorization

In order to change matrices into real vectors we will use the so-called
vectorization technique.

  * •

For any real symmetric $n\times n$ matrix $A$

$\displaystyle\mathrm{vec}_{O}(A)=\left(A_{11},\ldots,A_{1n},A_{22},\ldots
A_{2n},\ldots,A_{nn}\right)^{T}$ (76)

  * •

For any complex hermitian $n\times n$ matrix $A$

$\displaystyle\mathrm{vec}_{U}(A)=\left(\mathrm{Re}A_{11},\mathrm{Im}A_{11},\ldots,\mathrm{Re}A_{1n},\mathrm{Im}A_{1n},\ldots,\mathrm{Re}A_{nn},\mathrm{Im}A_{nn}\right)^{T}$
(77)

  * •

For any real $n\times n$ matrix $A$

$\displaystyle\mathrm{vec}_{R}(A)=\left(A_{11},\ldots,A_{1n},A_{21},\ldots
A_{2n},\ldots,A_{n1},\ldots,A_{nn}\right)^{T}$ (78)

  * •

For any complex $n\times n$ matrix $A$

$\displaystyle\mathrm{vec}_{C}(A)=\left(\mathrm{Re}A_{11},\mathrm{Im}A_{11},\ldots,\mathrm{Re}A_{1n},\mathrm{Im}A_{1n},\ldots,\mathrm{Re}A_{n1},\mathrm{Im}A_{n1},\ldots,\mathrm{Re}A_{nn},\mathrm{Im}A_{nn}\right)^{T}$
(79)

##### Gaussian and Ginibre ensembles

Next we recall some basic definitions of random matrix ensembles. Let
$H_{N}=(H_{i,j})_{i,j=1}^{N}$ be $N\times N$ matrix. We distinguish four
ensembles:

  * •

Gaussian Orthogonal Ensemble (GOEN) real symmetric matrices:

    * –

$H_{k,l}=\frac{1}{\sqrt{N}}N(0,(1+\delta_{k,l}))$ for $k\leq l$,

    * –

entries $H_{k,l}$ are independent for $k\leq l$,

    * –

probability measure:
$d\mathbb{P}(H_{N})\sim\exp{(-\frac{N}{4}\mathrm{Tr}(H_{N}^{2}))}\prod_{i\leq
j}dH_{i,j}$,

  * •

Gaussian Unitary Ensemble (GUEN) hermitian matrices:

    * –

$H_{k,l}=\frac{1}{\sqrt{N}}\left(X_{k,l}+iY_{k,l}\right)$ for $k\neq l$, where
$X_{k,l}$ and $Y_{kl}$ are independent $N(0,\frac{1}{2})$ and $H_{k,k}$ is
$N(0,1)$,

    * –

entries $H_{k,l}$ are independent for $k\leq l$,

    * –

probability measure:
$d\mathbb{P}(H_{N})\sim\exp{(-\frac{N}{2}\mathrm{Tr}(H_{N}^{2}))}\prod_{i\leq
j}dX_{i,j}dY_{i,j}$,

  * •

Real Ginibre ensemble RGN:

    * –

$H_{k,l}=\frac{1}{\sqrt{N}}N(0,1)$

    * –

entries $H_{k,l}$ are independent

    * –

probability measure:
$d\mathbb{P}(H_{N})\sim\exp{(-\frac{N}{2}\mathrm{Tr}(H_{N}^{t}H_{N}))}\prod_{1\leq
i,j\leq d_{\lambda}}dH_{i,j}$,

  * •

Complex Ginibre ensemble (CGN)

    * –

entries: $H_{k,l}=\frac{1}{\sqrt{N}}\left(X_{k,l}+iY_{k,l}\right)$, where
$X_{k,l}$ and $Y_{kl}$ are independent $N(0,\frac{1}{2})$

    * –

entries $H_{k,l}$ are independent

    * –

probability measure:
$d\mathbb{P}(H_{N})\sim\exp{(-N\mathrm{Tr}(H_{N}^{\dagger}H_{N}))}\prod_{1\leq
i,j\leq d_{\lambda}}dX_{i,j}dY_{i,j}$,

##### Bounds on the norm

Using vectorization one has the following correspondence:

  * •

$H_{N}$ form GOEN – $\mathrm{vec}_{O}(H_{N})$ is a real Gaussian vector in
$\mathbb{R}^{N_{O}}$, where $N_{O}=N(N+1)/2$, distributed according to
$N(0,\Sigma_{O})$, where $\Sigma_{O}$ is diagonal $N_{O}\times N_{O}$ matrix
whose diagonal elements are either $\frac{1}{N}$ or $\frac{2}{N}$.

  * •

$H_{N}$ form GUEN – $\mathrm{vec}_{U}(H_{N})$ is a real Real Gaussian vector
in $\mathbb{R}^{N_{U}}$, where $N_{U}=N^{2}$, distributed according to
$N(0,\Sigma_{U})$, where $\Sigma_{U}$ is diagonal $N_{U}\times N_{U}$ matrix
whose diagonal elements are either $\frac{1}{2N}$ or $\frac{1}{N}$.

  * •

$H_{N}$ form RGN – $\mathrm{vec}_{R}(H_{N})$ is a real Gaussian vector in
$\mathbb{R}^{N_{R}}$, where $N_{R}=N^{2}$, distributed according to
$N(0,\Sigma_{R})$, where $\Sigma_{R}$ is $N_{R}\times N_{R}$ matrix given by
$\Sigma_{R}=\frac{1}{N}\text{1}_{N_{R}}$.

  * •

$H_{N}$ form CGN – $\mathrm{vec}_{C}(H_{N})$ is a Real Gaussian vector in
$\mathbb{R}^{N_{C}}$, where $N_{C}=2N^{2}$, distributed according to
$N(0,\Sigma_{C})$, where $\Sigma_{C}$ is $N_{C}\times N_{C}$ matrix given by
$\Sigma_{C}=\frac{1}{2N}\text{1}_{N_{C}}$.

In this paragraph we present short derivation of the bounds on the probability
$\mathbb{P}\left(\|H_{N}\|>2+\epsilon\right)$ originally presented in [26,
27]. Recall that the standard real Gaussian vector $X_{N}$ in $\mathbb{R}^{N}$
is distributed according $N(0,\text{1}_{N})$. Let $\mathbb{P}_{N}$ be the
probability measure of $N(0,\text{1}_{N})$. We say that
$f:\mathbb{R}^{N}\rightarrow\mathbb{R}$ is $L$-Lipschitz iff:

$\displaystyle|f(X)-f(Y)|\leq
L\|X-Y\|_{2}\,\mathrm{for}\,\mathrm{all}\,X,Y\in\mathbb{R}^{N},$ (80)

where $\|X\|_{2}^{2}=\sum_{i=1}^{N}X_{i}^{2}$. We have the following two
useful facts [26, 27]:

######  Fact 6.

Let $f:\mathbb{R}^{N}\rightarrow\mathbb{R}$ be $L$-Lipschitz and $X$ be the
standard real Gaussian vector in $\mathbb{R}^{N}$, i.e. $X\simeq
N(0,\text{1}_{N})$. Then for $\epsilon>0$

$\displaystyle\mathbb{P}_{N}\left(f(X_{N})>M_{f(X_{N})}+\epsilon\right)\leq\frac{1}{2}e^{-\frac{\epsilon^{2}}{2L^{2}}},$
(81)

where $M_{f(X_{N})}$ is the median of the random variable $f(X_{N})$.

######  Fact 7.

Let $f:\mathbb{R}^{N}\rightarrow\mathbb{R}$ be a convex function and $X_{N}$
be the standard real Gaussian vector in $\mathbb{R}^{N}$. Then
$M_{f(X_{N})}\leq\mathbb{E}\left(f(X_{N})\right)$

Combining the above two Facts we get

######  Corollary 6.

Let $f:\mathbb{R}^{N}\rightarrow\mathbb{R}$ be convex and $L$-Lipschitz and
$X_{N}$ be the standard real Gaussian vector in $\mathbb{R}^{N}$. Then

$\displaystyle\mathbb{P}_{N}\left(f(X_{N})>\mathbb{E}\left(f(X_{N})\right)+\epsilon\right)\leq\frac{1}{2}e^{-\frac{\epsilon^{2}}{2L^{2}}}$
(82)

Our goal is to bound
$\mathbb{P}\left(\|H_{N}\|>\mathbb{E}\left(\|H_{N}\|\right)+\epsilon\right)$,
where $H_{N}$ is from one of the ensembles listed in the previous paragraph.
For this propose we consider the function
$f_{\ast}:\mathbb{R}^{N_{\ast}}\rightarrow\mathrm{Mat}_{N}$ given by

$\displaystyle
f_{\ast}(X_{N_{\ast}}):=\|\mathrm{vec_{\ast}}^{-1}(\Sigma_{\ast}^{\frac{1}{2}}X_{N_{\ast}})\|,$
(83)

where $\ast\in\\{O,U,R,C\\}$. It is easy to see that (83) is equal to
$\|H_{N}\|$, where $H_{N}$ form GOEN, GUEN, RGN or CGN. Moreover we easily see
that

$\displaystyle\left|\|\mathrm{vec}_{\ast}^{-1}(\Sigma_{\ast}^{\frac{1}{2}}X_{N_{\ast}})\|-\|\mathrm{vec}_{\ast}^{-1}(\Sigma_{\ast}^{\frac{1}{2}}Y_{N_{\ast}})\|\right|\leq\|\mathrm{vec}_{\ast}^{-1}(\Sigma_{\ast}^{\frac{1}{2}}(X_{N_{\ast}}-Y_{N_{\ast}}))\|\leq$
(84)
$\displaystyle\leq\|\mathrm{vec}_{\ast}^{-1}(\Sigma_{\ast}^{\frac{1}{2}}(X_{N_{\ast}}-Y_{N_{\ast}}))\|_{\mathrm{HS}}\leq
L_{\ast}\|X_{N_{\ast}}-Y_{N_{\ast}}\|_{2},$ (85)

where $L_{O}=\sqrt{\frac{2}{N}}$, $L_{U}=L_{R}=\frac{1}{\sqrt{N}}$,
$L_{C}=\frac{1}{\sqrt{2N}}$ and
$\|X\|_{\mathrm{HS}}^{2}=\sum_{i,j=1}^{N}|X_{ij}|^{2}$. One can also easily
verify that $f_{\ast}$ is a convex function. Thus making use of Corollary 6 we
get

$\displaystyle\mathbb{P}\left(\|H_{N}\|>\mathbb{E}\left(\|H_{N}\|\right)+\epsilon\right)=\mathbb{P}_{N}\left(f_{\ast}(X_{N_{\ast}})>\mathbb{E}\left(f_{\ast}(X_{N_{\ast}})\right)+\epsilon\right)\leq\frac{1}{2}e^{-\frac{\epsilon^{2}}{2L_{\ast}^{2}}}$
(86)

For $H_{N}$ in GOEN, GUEN, RGN or CGN we know that
$\mathbb{E}\left(\|H_{N}\|\right)\leq 2$ for every $N\geq 2$, hence:

######  Fact 8.

([26, 27]) We have the following tail bounds:

  * •

$\mathbb{P}\left(\|H_{N}\|>2+\epsilon\right)\leq\frac{1}{2}e^{-\frac{N\epsilon^{2}}{4}}=:F_{O}(N,\epsilon)$,
when $H_{N}$ in GOEN,

  * •

$\mathbb{P}\left(\|H_{N}\|>2+\epsilon\right)\leq\frac{1}{2}e^{-\frac{N\epsilon^{2}}{2}}=:F_{U}(N,\epsilon)$,
when $H_{N}$ in GUEN,

  * •

$\mathbb{P}\left(\|H_{N}\|>2+\epsilon\right)\leq\frac{1}{2}e^{-\frac{N\epsilon^{2}}{2}}=:F_{R}(N,\epsilon)$,
when $H_{N}$ in RGN,

  * •

$\mathbb{P}\left(\|H_{N}\|>2+\epsilon\right)\leq\frac{1}{2}e^{-N\epsilon^{2}}=:F_{C}(N,\epsilon)$,
when $H_{N}$ in CGN.

##### Finitely and infinitely often

We will also need the notion of events that occur infinitely and finitely
often. Let $(\Omega,\mathcal{F},\mathbb{P})$ be the probability space, i.e.
$\Omega$ is a space of elementary events aka a sample space, $\mathcal{F}$ is
the sigma algebra of events and $\mathbb{P}:\mathcal{F}\rightarrow[0,1]$ is a
probability measure. Let $\\{A_{n}\\}_{n=1}^{\infty}$ be a sequence of events.
We say that

  * •

Events in the sequence $\\{A_{n}\\}_{n=1}^{\infty}$ occur infinitely often iff
$A_{n}$ occurs for infinite number of indices $n\in\mathbb{Z}_{+}$. We denote
this by $\\{A_{n}\,\,i.o.\\}$. More precisely

$\\{A_{n}\,\,i.o.\\}:=\\{\omega\in\Omega:\omega\in
A_{n}\,\mathrm{for\,infinite\,number\,of\,indices}\,n\\}.$

  * •

Events in the sequence $\\{A_{n}\\}_{n=1}^{\infty}$ occur finitely often iff
$A_{n}$ occurs for at most finite number of indices $n\in\mathbb{Z}_{+}$. We
denote this by $\\{A_{n}\,\,f.o.\\}$. More precisely

$\\{A_{n}\,\,f.o.\\}:=\\{\omega\in\Omega:\omega\in
A_{n}\,\mathrm{for\,at\,most\,finite\,number\,of\,indices}\,n\\}.$

Moreover, using formulas from [37]

$\displaystyle\\{A_{n}\,\,i.o.\\}=\bigcap_{m=1}^{\infty}\bigcup_{n\geq
m}A_{n},\,\,\,\,\\{A_{n}\,\,f.o.\\}=\bigcup_{m=1}^{\infty}\bigcap_{n\geq
m}A_{n}^{c},$ (87)

it can be verified that both $\\{A_{n}\,\,i.o.\\}$ and $\\{A_{n}\,\,f.o.\\}$
are elements of $\mathcal{F}$ and
$\\{A_{n}\,\,i.o.\\}^{c}=\\{A_{n}\,\,f.o.\\}$. We also have:

######  Fact 9.

(Borel-Cantelli lemmas) Let $\\{A_{n}\\}_{n=1}^{\infty}$ be a sequence of
events. Then:

  1. 1.

If $\sum_{n}\mathbb{P}(A_{n})<\infty$ then
$\mathbb{P}(\\{A_{n}\,\,f.o.\\})=1$.

  2. 2.

If $\sum_{n}\mathbb{P}(A_{n})=\infty$ and events $\\{A_{n}\\}_{n=1}^{\infty}$
are independent then $\mathbb{P}(\\{A_{n}\,\,f.o.\\})=0$.

###  4.2 Haar random gate-sets

In this section we consider a Haar random gate-set
$\mathcal{S}=\\{U_{1},\ldots,U_{n}\\}$, where $U_{k}$’s are independent and
Haar random unitaries from $U(d)$. Using tools from Section 4.1 we look for
the limiting properties of $\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}$
when $\mathcal{S}\rightarrow\infty$. In particular we show that
$\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}$ converges in distribution to
a random matrix from either the real Ginibre ensemble if
$\lambda\in\Lambda_{t}^{r}$ or to a random matrix from the complex Ginibre
ensemble if $\lambda\in\Lambda_{t}^{c}$.

####  4.2.1 Real representations

For a Haar random $U$ and $\lambda\in\Lambda_{t}^{r}$ the vectorization
$\mathrm{vec}_{R}\left(\pi_{\lambda}(U)\right)$ is a random vector in
$\mathbb{R}^{d_{\lambda}^{2}}$ with
$\underset{U\sim\mu}{\mathbb{E}}\left([\pi_{\lambda}(U)]_{ij}\right)=0$. Using
(70) we can calculate the covariance matrix of
$\mathrm{vec}_{R}\left(\pi_{\lambda}(U)\right)$:

$\displaystyle\Sigma_{(ij),(kl)}=\left[\mathrm{Cov}\left(\mathrm{vec}_{R}\left(\pi_{\lambda}(U)\right)\right)\right]_{(ij),(kl)}=\underset{U\sim\mu}{\mathbb{E}}\left([\pi_{\lambda}(U)]_{ij}[\pi_{\lambda}(U)]_{kl}\right)=\frac{\delta_{ik}\delta_{jl}}{d_{\lambda}}.$
(88)

Hence the covariance matrix is $d_{\lambda}^{2}\times d_{\lambda}^{2}$ matrix
given by $\Sigma=\frac{1}{d_{\lambda}}\text{1}_{d_{\lambda}^{2}}$. For a Haar
random gate-set $\mathcal{S}$, using the Central Limit Theorem (see Fact 5)
the random operator

$\displaystyle\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}=\frac{1}{\sqrt{\mathcal{S}}}\sum_{U\in\mathcal{S}}\pi_{\lambda}(U),$
(89)

when $\mathcal{S}\rightarrow\infty$, converges in distribution to a random
operator $T_{\lambda}$ whose entries are distributed according to
$N(0,\frac{1}{d_{\lambda}}\text{1}_{d_{\lambda}^{2}})$. Thus using (75) the
limiting density is given by the density of the real Ginibre ensemble
RG${{}_{d{{}_{\lambda}}}}$, i.e. is proportional to

$\displaystyle
e^{-\frac{d_{\lambda}}{2}\mathrm{Tr}(T_{\lambda}^{T}T_{\lambda})}\prod_{1\leq
i,j\leq d_{\lambda}}d[T_{\lambda}]_{ij}.$ (90)

####  4.2.2 Complex representations

For a Haar random $U$ and $\lambda\in\Lambda_{t}^{c}$ we first decompose
$\pi_{\lambda}(U)$ into a sum of two matrices $x(U)$ and $y(U)$ corresponding
to the real and imaginary parts, i.e. $\pi_{\lambda}(U)=x(U)+iy(U)$.
Obviously,
$\underset{U\sim\mu}{\mathbb{E}}\left([x(U)]_{ij}\right)=0=\underset{U\sim\mu}{\mathbb{E}}\left([y(U)]_{ij}\right)$.
One easily sees that $\mathrm{vec}_{C}\left(\pi_{\lambda}(U)\right)$ is a
random vector in $\mathbb{R}^{2d_{\lambda}^{2}}$. From (71) and (72) we have:

$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[x(U)\right]_{ji}\left[x(U)\right]_{kl}+\left[y(U)\right]_{ji}\left[y(U)\right]_{kl}\right)=\frac{\delta_{jk}\delta_{il}}{d_{\lambda}},$
(91)
$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[x(U)\right]_{ji}\left[y(U)\right]_{kl}-\left[y(U)\right]_{ji}\left[x(U)\right]_{kl}\right)=0,$
(92)
$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[x(U)\right]_{ji}\left[x(U)\right]_{kl}-\left[y(U)\right]_{ji}\left[y(U)\right]_{kl}\right)=0,$
(93)
$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[x(U)\right]_{ji}\left[y(U)\right]_{kl}+\left[y(U)\right]_{ji}\left[x(U)\right]_{kl}\right)=0.$
(94)

Using the above four relations we can calculate the following expectations:

$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[x(U)\right]_{ji}\left[x(U)\right]_{kl}\right)=\frac{\delta_{jk}\delta_{il}}{2d_{\lambda}},$
(95)
$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[y(U)\right]_{ji}\left[y(U)\right]_{kl}\right)=\frac{\delta_{jk}\delta_{il}}{2d_{\lambda}},$
$\displaystyle\underset{U\sim\mu}{\mathbb{E}}\left(\left[x(U)\right]_{ji}\left[y(U)\right]_{kl}\right)=0.$

The covariance matrix of $\mathrm{vec}_{C}\left(\pi_{\lambda}(U)\right)$ is
determined by the above expected values and is $2d_{\lambda}^{2}\times
2d_{\lambda}^{2}$ matrix given by
$\Sigma=\frac{1}{2d_{\lambda}}\text{1}_{2d_{\lambda}^{2}}$. Using the Central
Limit Theorem (see Fact 5) the random operator

$\displaystyle\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}=\frac{1}{\sqrt{\mathcal{S}}}\sum_{U\in\mathcal{S}}\pi_{\lambda}(U),$
(96)

when $\mathcal{S}\rightarrow\infty$, converges in distribution to a random
operator $T_{\lambda}=X_{\lambda}+iY_{\lambda}$ whose real and imaginary parts
of entries are distributed according to
$N(0,\frac{1}{2d_{\lambda}}\text{1}_{2d_{\lambda}^{2}})$. Thus using (75) the
limiting density is given by the density of the complex Ginibre ensemble
CG${{}_{d{{}_{\lambda}}}}$, i.e. is proportional to

$\displaystyle
e^{-d_{\lambda}\mathrm{Tr}(T_{\lambda}^{\dagger}T_{\lambda})}\prod_{1\leq
i,j\leq d_{\lambda}}d[X_{\lambda}]_{ij}\prod_{1\leq i,j\leq
d_{\lambda}}d[Y_{\lambda}]_{i,j}.$ (97)

###  4.3 Symmetric Haar random gate-sets

In this section we consider a symmetric Haar random gate-set
$\mathcal{S}=\\{U_{1},\ldots,U_{n}\\}\cup\\{U_{1}^{-1},\ldots,U_{n}^{-1}\\}$,
where $U_{k}$’s are independent and Haar random unitaries from $U(d)$. Using
tools from Section 4.1 we look for the limiting distribution of
$\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}$ when
$\mathcal{S}\rightarrow\infty$. In particular we show that
$\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}$ converges in distribution to
a random matrix from the Gaussian orthogonal ensemble if
$\lambda\in\Lambda_{t}^{r}$ or to a random matrix from the Gaussian unitary
ensemble if $\lambda\in\Lambda_{t}^{c}$.

####  4.3.1 Real representations

For a Haar random $U$ and $\lambda\in\Lambda_{t}^{r}$ the matrix
$\pi_{\lambda}(U)+\pi_{\lambda}(U^{-1})$ is a symmetric matrix. Therefore,
using (76) the vectorization
$\mathrm{vec}_{O}\left(\pi_{\lambda}(U)+\pi_{\lambda}(U^{-1})\right)$ is a
random vector in $\mathbb{R}^{d_{\lambda}(d_{\lambda}+1)/2}$ with
$\underset{U\sim\mu}{\mathbb{E}}\left([\pi_{\lambda}(U)+\pi_{\lambda}(U^{-1})]_{ij}\right)=0$.
Using (70) we can calculate the covariance matrix of
$\frac{1}{\sqrt{2}}\mathrm{vec}_{O}\left(\pi_{\lambda}(U)+\pi_{\lambda}(U^{-1})\right)$:

$\displaystyle\Sigma_{(ij),(kl)}=\frac{1}{2}\left[\mathrm{Cov}\left(\mathrm{vec}_{O}\left(\pi_{\lambda}(U)+\pi_{\lambda}(U^{-1})\right)\right)\right]_{(ij),(kl)}=$
(98)
$\displaystyle=\frac{1}{2}\underset{U\sim\mu}{\mathbb{E}}\left(\left([\pi_{\lambda}(U)]_{ij}+[\pi_{\lambda}(U)]_{ji}\right)\left([\pi_{\lambda}(U)]_{kl}+[\pi_{\lambda}(U)]_{lk}\right)\right)=$
(99)
$\displaystyle=\frac{\delta_{ik}\delta_{jl}+\delta_{il}\delta_{jk}}{d_{\lambda}}.$
(100)

Taking into account that $i\leq j$ and $k\leq l$ we see that the covariance
matrix is a diagonal matrix. For a Haar random symmetric gate-set
$\mathcal{S}=\\{U_{1},\ldots,U_{n}\\}\cup\\{U_{1}^{-1},\ldots,U_{n}^{-1}\\}$,
using the Central Limit Theorem (see fact 5) the random operator

$\displaystyle\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}=\frac{\sqrt{2}}{\sqrt{\mathcal{S}}}\sum_{i=1}^{n}\frac{\left(\pi_{\lambda}(U_{i})+\pi_{\lambda}(U_{i}^{-1})\right)}{\sqrt{2}},$
(101)

when $\mathcal{S}\rightarrow\infty$, converges in distribution to a random
operator $T_{\lambda}$ whose entries are distributed according to
$N(0,\Sigma)$. Thus using (75) the limiting density is given by the density of
the Gaussian orthogonal ensemble GOE${{}_{d{{}_{\lambda}}}}$, i.e. is
proportional to

$\displaystyle
e^{-\frac{d_{\lambda}}{4}\mathrm{Tr}(T_{\lambda}^{2})}\prod_{1\leq i\leq j\leq
d_{\lambda}}d[T_{\lambda}]_{ij}.$ (102)

####  4.3.2 Complex representations

For a Haar random $U$ and $\lambda\in\Lambda_{t}^{c}$ let us first decompose
$\pi_{\lambda}(U)$ ($\pi_{\lambda}(U^{-1})$) into a sum of two matrices $x(U)$
($x(U^{-1})$) and $y(U)$ ($y(U^{-1})$) corresponding to the real and imaginary
parts, i.e. $\pi_{\lambda}(U)=x(U)+iy(U)$,
$\pi_{\lambda}(U^{-1})=x(U^{-1})+iy(U^{-1})$. The expected values of $x(U)$,
$x(U^{-1})$, $y(U)$, $y(U^{-1})$ are all zeros. We also have

$\displaystyle[x(U^{-1})]_{ij}=[x(U)]_{ji},$ (103)
$\displaystyle[y(U^{-1})]_{ij}=-[y(U)]_{ji}.$

The covariance matrix of

$\displaystyle\mathrm{vec}_{U}\left(\frac{\pi_{\lambda}(U)+\pi_{\lambda}(U^{-1})}{\sqrt{2}}\right),$
(104)

is determined by

$\displaystyle\frac{1}{2}\underset{U\sim\mu}{\mathbb{E}}\left((\left[x(U)\right]_{ij}+\left[x(U)\right]_{ji})\left(\left[x(U)\right]_{kl}+\left[x(U)\right]_{lk}\right)\right)=\frac{\delta_{ik}\delta_{jl}+\delta_{il}\delta_{jk}}{2d_{\lambda}},$
(105)
$\displaystyle\frac{1}{2}\underset{U\sim\mu}{\mathbb{E}}\left((\left[y(U)\right]_{ij}-\left[y(U)\right]_{ji})\left(\left[y(U)\right]_{kl}-\left[y(U)\right]_{lk}\right)\right)=\frac{\delta_{ik}\delta_{jl}-\delta_{il}\delta_{jk}}{2d_{\lambda}},$
$\displaystyle\frac{1}{2}\underset{U\sim\mu}{\mathbb{E}}\left((\left[x(U)\right]_{ij}+\left[x(U)\right]_{ji})\left(\left[y(U)\right]_{kl}-\left[y(U)\right]_{lk}\right)\right)=0,$

where we used relations (95). Taking into account that $i\leq j$ and $k\leq l$
we see that the covariance matrix is a diagonal matrix. For a Haar random
symmetric gate-set
$\mathcal{S}=\\{U_{1},\ldots,U_{n}\\}\cup\\{U_{1}^{-1},\ldots,U_{n}^{-1}\\}$,
using the Central Limit Theorem (see Fact 5) the random operator

$\displaystyle\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}=\frac{\sqrt{2}}{\sqrt{\mathcal{S}}}\sum_{i=1}^{n}\frac{\left(\pi_{\lambda}(U_{i})+\pi_{\lambda}(U_{i}^{-1})\right)}{\sqrt{2}},$
(106)

when $\mathcal{S}\rightarrow\infty$, converges in distribution to a random
operator $T_{\lambda}=X_{\lambda}+iY_{\lambda}$ whose real and imaginary parts
of entries are distributed according to $N(0,\Sigma)$. Thus using (75) the
limiting density is given by the density of the Gaussian unitary ensemble
GUE${{}_{d{{}_{\lambda}}}}$, i.e. is proportional to

$\displaystyle
e^{-\frac{d_{\lambda}}{2}\mathrm{Tr}(T_{\lambda}^{2})}\prod_{1\leq i\leq j\leq
d_{\lambda}}d[X_{\lambda}]_{ij}\prod_{1\leq i\leq j\leq
d_{\lambda}}d[Y_{\lambda}]_{i,j}.$ (107)

##  5 The random matrix model and its properties

As we have seen in the previous sections a matrix
$\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},\lambda}$ converges, when
$\mathcal{S}\rightarrow\infty$, in distribution to a random matrix
$T_{\lambda}$ from: (1) real Ginibre ensemble when $\mathcal{S}$ is Haar
random and $\lambda\in\Lambda^{r}_{t}$, (2) Gaussian orthogonal ensemble when
$\mathcal{S}$ is symmetric Haar random and $\lambda\in\Lambda^{r}_{t}$, (3)
complex Ginibre ensemble when $\mathcal{S}$ is Haar random and
$\lambda\in\Lambda^{c}_{t}$, (4) Gaussian unitary ensemble when $\mathcal{S}$
is symmetric Haar random and $\lambda\in\Lambda^{c}_{t}$. Therefore when
$\mathcal{S}\rightarrow\infty$ the matrix $T_{\nu_{\mathcal{S}},t}$ given by
(22) converges in distribution to a block diagonal matrix
$\text{1}^{m_{0}}\oplus\bigoplus_{\lambda\in\Lambda_{t}}\left(T_{\lambda}\right)^{\oplus
m_{\lambda}}$, with blocks $T_{\lambda}$ belonging to the ensembles listed
above. By similar arguments as in Section 2, the norm
$\|\text{1}^{m_{0}}\oplus\bigoplus_{\lambda\in\Lambda_{t}}\left(T_{\lambda}\right)^{\oplus
m_{\lambda}}-\text{1}^{m_{0}}\|$ is the same as the the norm of
$T_{t}=\bigoplus_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}T_{\lambda}$. It is
also easy to see that for any $\lambda\neq\eta$, where
$\lambda,\eta\in\Lambda_{t}^{\mathrm{ess}}$ blocks $T_{\lambda}$ and
$T_{\eta}$ are independent. This follows directly from the Central Limit
Theorem (Fact 5) and the orthogonality relations given in Section 4.1. We next
introduce

$\displaystyle\delta(\lambda):=\|T_{\lambda}\|,\,\,\delta(t)=\sup_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\delta(\lambda),\,\,\delta=\sup_{t}\delta(t).$
(108)

Summing up we proved that:

######  Theorem 7.

When $|\mathcal{S}|\rightarrow\infty$:

  1. 1.

$\sqrt{|\mathcal{S}|}T_{\nu_{\mathcal{S}},\lambda}$ converges in distribution
to a random matrix $T_{\lambda}$ from: (1) the real (complex) Ginibre ensemble
RG${}_{d_{\lambda}}$ (CG${}_{d_{\lambda}}$) when $\mathcal{S}$ is Haar random
gate-set and $\pi_{\lambda}$ is a real (complex) representation, (2) the
Gaussian orthogonal (unitary) ensemble GOE${}_{d_{\lambda}}$
(GUE${}_{d_{\lambda}}$), when $\mathcal{S}$ is symmetric Haar random gate-set
and $\pi_{\lambda}$ is a real (complex) representation.

  2. 2.

Operator
$\bigoplus_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}T_{\nu_{\mathcal{S}},\lambda}$
converges in distribution to a block diagonal matrix

$\displaystyle
T_{t}=\bigoplus_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}T_{\lambda},$ (109)

with blocks $T_{\lambda}$ belonging to the ensembles listed above. Moreover
$T_{\lambda}$’s with distinct $\lambda$’s are independent.

Next we charactarize properties of our random matrix model, i.e. the
probability distributions of : $\delta(\lambda)$, $\delta(t)$ and $\delta$.
The tail bounds for the norm of any block $T_{\lambda}$ are given in Fact 8,
where $N$ should be replaced by $d_{\lambda}$. Moreover, since blocks are
independent we can formulate the following theorem.

######  Theorem 8.

In the symmetric Haar random setting we have the following tail bounds for
$\delta(t)$:

$\displaystyle\mathbb{P}\left(\delta(t)>2+\epsilon\right)\leq\sum_{\lambda\in\Lambda_{t}^{\mathrm{r}}}F_{O}(d_{\lambda},\epsilon)+\frac{1}{2}\sum_{\lambda\in\Lambda_{t}^{c}}F_{U}(d_{\lambda},\epsilon)$
(110) $\displaystyle\mathbb{P}\left(\delta(t)>2+\epsilon\right)\leq
1-\exp\left(-\sum_{\lambda\in\Lambda_{t}^{\mathrm{r}}}F_{O}(d_{\lambda},\epsilon)-\frac{1}{2}\sum_{\lambda\in\Lambda_{t}^{\mathrm{c}}}F_{U}(d_{\lambda},\epsilon)\right),$
(111)

where functions $F_{\ast}$ are defined in Fact 8. The bounds for Haar random
setting are the same albeit we have to exchange $O\leftrightarrow R$ and
$U\leftrightarrow C$.

###### Proof.

The first bound is the union bound, i.e using (109) we have

$\displaystyle\mathbb{P}\left(\|T_{t}\|>2+\epsilon\right)=\mathbb{P}\left(\bigcup_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\left(\|T_{\lambda}\|>2+\epsilon\right)\right)=\sum_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\mathbb{P}\left(\|T_{\lambda}\|>2+\epsilon\right),$
(112)

which combined with Fact 8 gives (110). For the second bound let
$p_{\lambda}=\mathbb{P}\left(\|T_{\lambda}\|>2+\epsilon\right)$. Then

$\displaystyle\mathbb{P}\left(\|T_{t}\|>2+\epsilon\right)=\mathbb{P}\left(\bigcup_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\left(\|T_{\lambda}\|>2+\epsilon\right)\right)=1-\mathbb{P}\left(\bigcap_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\left(\|T_{\lambda}\|\leq
2+\epsilon\right)\right)=$ (113)
$\displaystyle=1-\prod_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\mathbb{P}\left(\|T_{\lambda}\|\leq
2+\epsilon\right)=1-\prod_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}\left(1-p_{\lambda}\right)\leq
1-\exp\left(-\sum_{\lambda\in\Lambda_{t}^{\mathrm{ess}}}p_{\lambda}\right)\leq$
$\displaystyle\leq
1-\exp\left(-\sum_{\lambda\in\Lambda_{t}^{\mathrm{r}}}F_{O}(d_{\lambda},\epsilon)-\frac{1}{2}\sum_{\lambda\in\Lambda_{t}^{\mathrm{c}}}F_{U}(d_{\lambda},\epsilon)\right),$

where in the third equality we used the independence of $T_{\lambda}$’s. We
also note that both bounds coincide when the RHS of (110) is close to zero. ∎

######  Example 1.

Before we proceed further we consider an example of a qubit approximate
$t$-design in the symmetric Haar random setting, i.e. when $d=2$. In this case
$\Lambda_{t}=\Lambda_{t}^{r}=\\{(k,-k):k\in\\{1,...,t\\}\\}$ and the dimension
$d_{\lambda}=d_{(k,-k)}=2k+1$. Thus

$\displaystyle\mathbb{P}\left(\|T_{t}\|>2+\epsilon\right)\leq\sum_{\lambda\in\Lambda_{t}^{\mathrm{r}}}F_{O}(d_{\lambda},\epsilon)=\frac{1}{2}\sum_{k=1}^{t}e^{-\frac{(2k+1)\epsilon^{2}}{4}}=\frac{e^{-\epsilon^{2}/4}(1-e^{-t\epsilon^{2}/2})}{2(e^{\epsilon^{2}/2}-1)}.$
(114)

Thus by Theorem 8 we get the following bounds:

$\displaystyle\mathbb{P}\left(\delta(t)>2+\epsilon\right)\leq\frac{e^{-\epsilon^{2}/4}(1-e^{-t\epsilon^{2}/2})}{2(e^{\epsilon^{2}/2}-1)},$
(115)
$\displaystyle\mathbb{P}\left(\delta>2+\epsilon\right)\leq\frac{e^{-\epsilon^{2}/4}}{2(e^{\epsilon^{2}/2}-1)}.$
(116)

For a fixed $\epsilon>0$ let us consider a series of events:

$\displaystyle A_{k}=\\{\delta\left(\left(k,-k\right)\right)>2+\epsilon\\}.$
(117)

We note that the sum

$\displaystyle\sum_{k=1}^{\infty}\mathbb{P}(A_{k})<\frac{e^{-\epsilon^{2}/4}}{2(e^{\epsilon^{2}/2}-1)}<\infty.$
(118)

Therefore using the Borel-Cantelli lemmas (see Fact 9) we can deduce that for
any given $\epsilon>0$ we have

$\displaystyle\mathbb{P}\left(\\{A_{k}\,\,f.o.\\}\right)=1.$ (119)

In other words, for any $\epsilon>0$ with the probability $1$ there is
$\lambda\in\Lambda_{t}$ such that for all
$\lambda^{\prime}\in\Lambda_{t^{\prime}}$, where $t^{\prime}>t$ we have
$\delta(\lambda^{\prime})\leq 2+\epsilon$. Thus in order to determine the
value of $\delta$ it is enough to determine $\delta(\nu_{\mathcal{S}},t)$ for
some finite $t$. Next, we prove similar result for any $d\geq 2$.

######  Theorem 9.

For both Haar random and symmetric Haar random settings in any dimension
$d\geq 2$ with the probability $1$ there exists finite $t\in\mathbb{Z}_{+}$
such that $\delta=\delta(t)$.

###### Proof.

Let $\Lambda^{\mathrm{ess}}:=\bigcup_{t}\Lambda_{t}^{\mathrm{ess}}$. We equip
$\Lambda^{\mathrm{ess}}$ with the order $\prec$ such that form any
$\lambda\in\Lambda_{t}^{\mathrm{ess}}$ and
$\lambda^{\prime}\in\Lambda_{t^{\prime}}^{\mathrm{ess}}$ we have
$\lambda\prec\lambda^{\prime}$ when $t<t^{\prime}$ and when $t=t^{\prime}$ the
order is the lexicographic order. For a fixed $\epsilon>0$ let us consider a
sequence of events $\\{A_{\lambda}\\}_{\lambda\in\Lambda^{\mathrm{ess}}}$,
where

$\displaystyle A_{\lambda}=\\{\delta(\lambda)>2+\epsilon\\}.$ (120)

Following the discussion presented for $d=2$ we need to show that

$\displaystyle\mathbb{P}\left(\\{A_{\lambda}\,\,f.o.\\}\right)=1.$ (121)

Using the Borel-Cantelli lemmas (see Fact 9) and Theorem 8, in the symmetric
Haar random setting, it is enough to show that

$\displaystyle\sum_{\lambda\in\Lambda^{\mathrm{ess}}}\mathbb{P}(A_{\lambda})\leq\lim_{t\rightarrow\infty}\left(\sum_{\lambda\in\Lambda_{t}^{\mathrm{r}}}F_{O}(d_{\lambda},\epsilon)+\frac{1}{2}\sum_{\lambda\in\Lambda_{t}^{c}}F_{U}(d_{\lambda},\epsilon)\right)<\infty.$
(122)

For the Haar random setting we have to exchange $O\leftrightarrow R$ and
$U\leftrightarrow C$. First we note that the number of distinct irreducible
representations $\pi_{\lambda}$ with $\|\lambda\|_{1}=2k$ is given by the
$\alpha_{2k}$ from Fact 2. By Fact 3 for a fixed $n$ the function $p_{n}(k)$
grows like $O(k^{n-1})$. Therefore $\alpha_{2k}$ is bounded by $c_{d}k^{d-2}$,
where $c_{d}$ is a positive constant that can depend on $d$. Next, using Fact
5 we can bound $d_{\lambda}\geq 2k$. Thus (122) is bounded from above by

$\displaystyle\sum_{\lambda\in\Lambda^{\mathrm{ess}}}\mathbb{P}(A_{\lambda})\leq\sum_{k=1}^{\infty}c_{d}k^{d-2}e^{-\frac{1}{2}dk\epsilon^{2}},$
(123)

We note that for $d>2$

$\displaystyle\int_{0}^{\infty}dk\left(c_{d}k^{d-2}e^{-\frac{1}{2}k\epsilon^{2}}\right)=\frac{2^{d-1}c_{d}(d-2)!}{\epsilon^{2(d-1)}}.$
(124)

Hence (123) is is evidently finite for any $d$. ∎

######  Theorem 10.

In the (symmetric) Haar random setting in any dimension $d>2$ and for any
$\epsilon>c\left(\frac{4\pi^{2}}{3d(d-1)^{2}}\right)^{1/4}$ we have

$\displaystyle\mathbb{P}\left(\delta>2+\epsilon\right)\leq
e^{-\frac{d(d+1)}{4c^{2}}\epsilon^{2}}\left(e^{2\pi\sqrt{\frac{d+2}{3}}}\frac{60+100\pi\sqrt{3d+6}}{d+2}-b\right)+$
$\displaystyle+\frac{60}{d^{2}}\left(2+\frac{\sqrt{2\pi}c}{\epsilon}\right)e^{-\frac{3d(d-1)}{4c^{2}}\epsilon^{2}+2\pi\sqrt{\frac{d}{3}}},$

where

$b=10\left[8\pi^{2}\mathrm{Ei}\left(2\sqrt{\frac{2}{3}}\pi\right)-e^{2\sqrt{\frac{2}{3}}\pi}(3+2\sqrt{6}\pi)\right]\approx
3855.93,$

and $c=1$ in the Haar random setting and $c=\sqrt{2}$ in the symmetric Haar
random setting.

###### Proof.

We will prove our thesis for the Haar random setting. The proof for the
symmetric Haar random case is analogous. Recall that

$\displaystyle\mathbb{P}\left(\delta>2+\epsilon\right)\leq\sum_{\lambda\in\Lambda^{\mathrm{ess}}}\mathbb{P}(\delta(\lambda)>2+\epsilon).$
(125)

Let $\alpha_{2k}$ be as in the Fact 2. Using Fact 3 we can write

$\displaystyle\alpha_{2k}\leq\frac{30}{k^{2}}e^{2\pi\sqrt{\frac{2k}{3}}}.$
(126)

Using the bound given in Lemma 5 we can bound (125) from above by

$\displaystyle 30\left[\sum_{k=1}^{\lfloor
d/2\rfloor}\frac{\exp\left(-\frac{d(d+1)}{4}\epsilon^{2}+a\sqrt{k}\right)}{k^{2}}+\sum_{k=\lceil
d/2\rceil}^{\infty}\frac{\exp\left(-(d-1)\left(k+\frac{d}{4}\right)\epsilon^{2}+a\sqrt{k}\right)}{k^{2}}\right],$
(127)

where $a=2\pi\sqrt{\frac{2}{3}}$. First, let us consider the first summation.
We note that the function $f(x)=\exp(a\sqrt{x})/x^{2}$ is growing for all $x$
greater than $\frac{16}{a^{2}}<1$. Thus:

$\displaystyle 30e^{-\frac{d(d+1)}{4}\epsilon^{2}}\sum_{k=1}^{\lfloor
d/2\rfloor}\frac{e^{a\sqrt{k}}}{k^{2}}\leq
30e^{-\frac{d(d+1)}{4}\epsilon^{2}}\int_{1}^{(d+2)/2}\frac{e^{a\sqrt{x}}}{x^{2}}dx.$
(128)

The integral above is equal to

$\frac{1}{3}\left[e^{a}(3+2\sqrt{6}\pi)-e^{2\sqrt{\frac{d+2}{3}}\pi}\frac{6+4\sqrt{3d+6}\pi}{d+2}-8\pi^{2}\mathrm{Ei}\left(a\right)+8\pi^{2}\mathrm{Ei}\left(2\sqrt{\frac{d+2}{3}}\pi\right)\right],$

where

$\mathrm{Ei}\left(x\right)=\int_{-\infty}^{x}\frac{e^{t}}{t}dt,$

is the exponential integral function. We observe that for
$g(x)=p\frac{\exp(x)}{x}-\mathrm{Ei}\left(x\right)$ and some $p>1$ we have
that:

$g^{\prime}(x)=\left[(p-1)x-p\right]\frac{e^{x}}{x^{2}}$

is $0$ at $x=x_{p}=\frac{p}{p-1}$ and positive for $x\geq x_{p}$. Moreover for
$p=\frac{3}{2}$ we have that $g\left(x_{p}\right)>0$ and $x_{p}=3\leq
2\sqrt{\frac{d+2}{3}}\pi$ thus for $x>3$ it holds
$\frac{3\exp(x)}{2x}>\mathrm{Ei}\left(x\right)$ and (128) is bounded by:

$\displaystyle
e^{-\frac{d(d+1)}{4}\epsilon^{2}}\left[e^{2\sqrt{\frac{d+2}{3}}\pi}\frac{60+100\pi\sqrt{3d+6}}{d+2}-b\right],$
$\displaystyle
b=10\left[8\pi^{2}\mathrm{Ei}\left(2\sqrt{\frac{2}{3}}\pi\right)-e^{2\sqrt{\frac{2}{3}}\pi}(3+2\sqrt{6}\pi)\right]\approx
3855.93.$

Next, we will deal with the second summation in (127). In order to change
summation to integration we first note that the function
$h(x)=\exp\left(-(d-1)\left(x+\frac{d}{4}\right)\epsilon^{2}+a\sqrt{x}\right)$
attains maximum at $x=\frac{2\pi^{2}}{3(d-1)^{2}\epsilon^{4}}$. Thus if we
assume
$\epsilon>\epsilon_{d}:=\left(\frac{4\pi^{2}}{3d(d-1)^{2}}\right)^{1/4}$ then
the function $h$ is decreasing for $x\geq\frac{d}{2}$. Therefore when
$\epsilon>\epsilon_{d}$ the function $h(x)/x^{2}$ is also decreasing for
$x>\frac{d}{2}$. Assume that $\epsilon>\epsilon_{d}$. Then the second sum in
(127) is bounded by

$\displaystyle\frac{120}{d^{2}}h\left(\frac{d}{2}\right)+60e^{-\frac{d(d-1)}{4}\epsilon^{2}}\int_{\sqrt{d/2}}^{\infty}\frac{e^{-(d-1)\epsilon^{2}x^{2}+ax}}{x^{3}}dx\leq$
$\displaystyle\leq\frac{120}{d^{2}}h\left(\frac{d}{2}\right)+60\left(\frac{2}{d}\right)^{\frac{3}{2}}e^{-\frac{d(d-1)}{4}\epsilon^{2}}\int_{\sqrt{d/2}}^{\infty}e^{-(d-1)\epsilon^{2}x^{2}+ax}dx=$
$\displaystyle=\frac{120}{d^{2}}h\left(\frac{d}{2}\right)+60\left(\frac{2}{d}\right)^{\frac{3}{2}}e^{-\frac{d(d-1)}{4}\epsilon^{2}}\int_{\sqrt{d/2}}^{\infty}\exp{\left(-(d-1)\epsilon^{2}\left(x-\frac{a}{2(d-1)\epsilon^{2}}\right)^{2}+\frac{a^{2}}{4(d-1)\epsilon^{2}}\right)}dx=$
$\displaystyle=\frac{120}{d^{2}}h\left(\frac{d}{2}\right)+60\left(\frac{2}{d}\right)^{\frac{3}{2}}e^{-\frac{d(d-1)}{4}\epsilon^{2}+\frac{a^{2}}{4(d-1)\epsilon^{2}}}\int_{\sqrt{d/2}}^{\infty}\exp{\left(-\frac{\left(x-\mu\right)^{2}}{2\sigma^{2}}\right)}dx,$
(129)

where $\mu=\frac{a}{2(d-1)\epsilon^{2}}$ and
$\sigma^{2}=\frac{1}{2(d-1)\epsilon^{2}}$. Next, for a Gaussian random
variable $X\sim N(\mu,\sigma^{2})$ we use Fact 6 and obtain

$\displaystyle\mathbb{P}(X\geq\mu+\beta)\leq\frac{1}{2}e^{-\frac{\beta^{2}}{2\sigma^{2}}}.$
(130)

Thus using (130) we get

$\displaystyle\int_{\sqrt{d/2}}^{\infty}\exp{\left(-\frac{\left(x-\mu\right)^{2}}{2\sigma^{2}}\right)}dx=\sqrt{2\pi}\sigma\mathbb{P}\left(X\geq\sqrt{\frac{d}{2}}\right)\leq$
$\displaystyle\leq\frac{\sqrt{\pi}}{2\sqrt{d-1}\epsilon}\exp{\left(-(d-1)\epsilon^{2}\left(\sqrt{\frac{d}{2}}-\frac{a}{2(d-1)\epsilon^{2}}\right)^{2}\right)},$

and (129) is bounded by

$\frac{120}{d^{2}}e^{-\frac{3}{4}d(d-1)\epsilon^{2}+a\sqrt{\frac{d}{2}}}+\frac{30\sqrt{\pi}}{\sqrt{d-1}\epsilon}\left(\frac{2}{d}\right)^{\frac{3}{2}}e^{-\frac{3}{4}d(d-1)\epsilon^{2}+a\sqrt{\frac{d}{2}}}\leq\frac{60}{d^{2}}\left(2+\frac{\sqrt{2\pi}}{\epsilon}\right)e^{-\frac{3}{4}d(d-1)\epsilon^{2}+a\sqrt{\frac{d}{2}}}$

Finally, we have:

$\displaystyle\mathbb{P}\left(\delta>2+\epsilon\right)\leq
e^{-\frac{d(d+1)}{4}\epsilon^{2}}\left(e^{2\pi\sqrt{\frac{d+2}{3}}}\frac{60+100\pi\sqrt{3d+6}}{d+2}-b\right)+$
$\displaystyle+\frac{60}{d^{2}}\left(2+\frac{\sqrt{2\pi}}{\epsilon}\right)e^{-\frac{3}{4}d(d-1)\epsilon^{2}+2\pi\sqrt{\frac{d}{3}}}.$

∎

Combining Theorem 9 with the Conjecture 1 we can say that for any $\epsilon>0$
and any (symmetric) Haar random $\mathcal{S}$ there exists, with the
probability $1$ a weight $\lambda\in\Lambda_{t}$ such that for all
$\lambda^{\prime}\in\Lambda_{t^{\prime}}$, where $t^{\prime}>t$ we have
$\delta(\nu_{\mathcal{S}},\lambda^{\prime})\leq\frac{2+\epsilon}{\sqrt{\mathcal{S}}}$.
Thus in order to determine the value of $\delta(\nu_{\mathcal{S}})$ it is
enough to determine $\delta(\nu_{\mathcal{S}},t)$ for some finite $t$. We
note, however, that the required value $t$ can depend on $\mathcal{S}$ and
using our methods we cannot decide if
$\mathrm{sup}_{\mathcal{S}}t(\mathcal{S})$ is finite.

######  Corollary 11.

Assume Conjeture 1 holds. Let $\mathcal{S}$ be a (symmetric) Haar random gate-
set. Then with the probability $1$ there exists finite $t\in\mathbb{Z}_{+}$
such that $\delta(\nu_{\mathcal{S}})=\delta(\nu_{\mathcal{S}},t)$. Moreover,
for any $d\geq 2$ we have

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}})>\frac{2+\epsilon}{\sqrt{\mathcal{S}}}\right)\leq\frac{e^{-\epsilon^{2}/(2c^{2})}}{2(e^{\epsilon^{2}/c^{2}}-1)},\;\mathrm{if}\;d=2\;\mathrm{and}\;\epsilon>0,$
$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}})>\frac{2+\epsilon}{\sqrt{\mathcal{S}}}\right)\leq
e^{-\frac{d(d+1)}{4c^{2}}\epsilon^{2}}\left(e^{2\pi\sqrt{\frac{d+2}{3}}}\frac{60+100\pi\sqrt{3d+6}}{d+2}-b\right)+$
$\displaystyle+\frac{60}{d^{2}}\left(2+\frac{\sqrt{2\pi}c}{\epsilon}\right)e^{-\frac{3d(d-1)}{4c^{2}}\epsilon^{2}+2\pi\sqrt{\frac{d}{3}}},\;\mathrm{if}\;d\geq
2\;\mathrm{and}\;\epsilon>c\left(\frac{4\pi^{2}}{3d(d-1)^{2}}\right)^{1/4},$

where

$b=10\left[8\pi^{2}\mathrm{Ei}\left(2\sqrt{\frac{2}{3}}\pi\right)-e^{2\sqrt{\frac{2}{3}}\pi}(3+2\sqrt{6}\pi)\right]\approx
3855.93,$

and $c=1$ in the Haar random setting and $c=\sqrt{2}$ in the symmetric Haar
random setting.

Using above inequalities we can make some conclusions about the benefits of
adding inverses to our sets of gates. The inequalities are of the form:

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}})>\frac{2+\epsilon}{\sqrt{\mathcal{S}}}\right)\leq
F\left(\frac{\epsilon}{c}\right),$

where $F$ is an appropriate function. We can make the dependence on
$\mathcal{S}$ more explicit by a substitution
$\epsilon\mapsto\frac{\epsilon}{\sqrt{\mathcal{S}}}$:

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}})>\frac{2}{\sqrt{\mathcal{S}}}+\epsilon\right)\leq
F\left(\frac{\sqrt{S}}{c}\epsilon\right).$

Note that the constant $c$ is such that, in both settings i.e. for a Haar
random set $\mathcal{S}=n$ and for a symmetric Haar random set
$\mathcal{S}=2\times n$, we get the same result:

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}})>\frac{2}{\sqrt{\mathcal{S}}}+\epsilon\right)\leq
F\left(\sqrt{n}\epsilon\right).$

Thus we can conclude that the concentration around
$\frac{2}{\sqrt{\mathcal{S}}}$ is the same in both scenarios. The advantage of
the symmetric set lays in the fact that this concentration is around the value
that is $\sqrt{2}$ times smaller than in the Haar random setting.

##  6 Numerical computations

In order to justify Conjecture 1 we numerically sampled
$\|T_{\nu_{\mathcal{S}},\lambda}\|$ and $\|T_{\nu_{\mathcal{S}},t}\|$ in the
following scenarios:

  * •

$d=2$, all $\lambda$ from $\Lambda_{500}^{\mathrm{ess}}$, $t=500$:

    1. 1.

Haar random sets with sizes from $3$ to $13$,

    2. 2.

symmetric Haar random sets with sizes from $2\times 2$ to $2\times 13$,

  * •

$d=4$, all $\lambda$ from $\Lambda_{6}^{\mathrm{ess}}$, $t=6$:

    1. 1.

Haar random sets with sizes from $3$ to $10$,

    2. 2.

symmetric Haar random sets with sizes from $2\times 2$ to $2\times 10$,

with sample sizes $2500-5000$. In the subsequent section we explain how we
performed those computations and present their results.

###  6.1 Algorithm

A sketch of the algorithm we used to perform our computations is shown in
Listing 1 in a form of a Python code.

⬇

1def t_design_norms(d, t, sample_size, set_size, is_symmetric):

2 weights = t_design_weights(d, t)

3 reps = [URepresentation(w) for w in weights]

4 all_norms = []

5

6 for i in range(sample_size):

7 norms = []

8 gates = [get_random_U(d) for j in range(set_size)]

9

10 for pi in reps:

11 T = sum(pi(U) for U in gates) / set_size

12

13 if is_symmetric:

14 T = (T + T.transpose().conjugate()) / 2

15

16 norms.append(norm(T))

17

18 all_norms.append(norms)

19

20 return weights, all_norms

Listing 1: Caption

The main function t_design_norms computes sample_size many times norms of
$T_{\nu_{\mathcal{S}},\lambda}$ for a random $\mathcal{S}$ and for all
$\lambda\in\Lambda^{\mathrm{ess}}_{t}$. Then it returns two lists. One is a
list of weights - weights used in a computation and the other is a two-
dimensional list of norms with sample_size many rows and
$|\tilde{\Lambda}_{t}|$ many columns - all_norms. Each row in all_norms
represents a different $\mathcal{S}$ and contains norms
$\delta(\nu_{S},\lambda^{1})$, $\delta(\nu_{S},\lambda^{2})$,
$\delta(\nu_{S},\lambda^{3})$, … where the order of $\lambda^{i}$ is the same
as in the list weights.
More precisely, t_design_norms function takes arguments:

  * •

d \- group dimension, an integer bigger than $1$,

  * •

t \- scale of a $t$-design that defines set of weights $\tilde{\Lambda}_{t}$,
an integer bigger than $0$,

  * •

sample_size \- the number of different random $\mathcal{S}$ for which the
computation is performed, an integer bigger than $0$,

  * •

set_size \- the size of $\mathcal{S}$ if is_symmetric is False and a half of
the size of $\mathcal{S}$ otherwise, an integer bigger than $0$,

  * •

is_symmetric \- an answer to a question: Is the set $\mathcal{S}$ symmetric?,
a boolean,

and returns:

weights | = | [ |  $\lambda^{1}$, |  $\lambda^{2}$, |  $\lambda^{3}$, | … | ]
---|---|---|---|---|---|---|---
all_norms | = | [ |
|  |  | [ |  $\delta(\nu_{S_{1}},\lambda^{1})$, |  $\delta(\nu_{S_{1}},\lambda^{2})$, |  $\delta(\nu_{S_{1}},\lambda^{3})$ , | … | ],
|  |  | [ |  $\delta(\nu_{S_{2}},\lambda^{1})$, |  $\delta(\nu_{S_{2}},\lambda^{2})$, |  $\delta(\nu_{S_{2}},\lambda^{3})$ , | … | ],
|  |  |  |  | ⋮ |  |  |
|  |  | [ |  $\delta(\nu_{S_{N}},\lambda^{1})$, |  $\delta(\nu_{S_{N}},\lambda^{2})$, |  $\delta(\nu_{S_{N}},\lambda^{3})$ , | … | ]
|  | ] |  |  |  |  |  |

where $N$ = sample_size. Then when we wanted to compute $\delta(\nu_{S},t)$ we
used formula 23.
To use the code from Listing 1 one needs to implement also:

  * •

t_design_weights \- a function that for a given d and t returns a list of
weights from $\Lambda_{t}^{\mathrm{ess}}$. Its implementation can be easily
derived from the definition of $\Lambda_{t}$ (19) and
$\Lambda_{t}^{\mathrm{ess}}$ (26).

  * •

URepresentation \- a class (or a function) that takes as argument a weight
$\lambda$ and computes $\pi_{\lambda}$. It was implemented using the fact that
$\pi_{\lambda}=\exp\circ\,\rho_{\lambda}\circ\log$ where $\rho_{\lambda}$ is a
$\mathfrak{u}(d)$ algebra representation with the highest weight $\lambda$.
The representation $\rho_{\lambda}$ was implemented using the Gelfand-Tsetlin
construction from [38].

  * •

get_random_U \- a function that for a given d computes a Haar-random matrix
from $U(d)$. The implementation of such a function was described in [39].

  * •

norm \- a function that computes an operator norm. We used the linalg.norm
from the scipy package.

###  6.2 Results

In Figure 1 one can see the relations between probabilities from Conjecture 1:

  1. A

$\mathbb{P}\left(\delta\left(\nu_{\mathcal{S}},\lambda\right)>\frac{2+\epsilon}{\sqrt{\mathcal{S}}}\right)$,

  2. B

$\mathbb{P}\left(\delta\left(\lambda\right)>2+\epsilon\right)$,

  3. C

tail bounds $F_{*}(d_{\lambda},\epsilon)$ from Fact 8.

Our data clearly indicates that the inequalities from our conjecture A $\leq$
B $\leq$ C hold. Moreover, the data from Figures 4 and 6 shows that for
$d_{\lambda}\rightarrow\infty$ we have

$\displaystyle\mathbb{E}\left(\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)\right)\rightarrow
2\sqrt{\frac{\mathcal{S}-1}{\mathcal{S}}},$
$\displaystyle\mathbb{E}\left(\delta\left(\lambda\right)\right)\rightarrow 2.$

Although, both limits are the same for $\mathcal{S}\rightarrow\infty$ the
first one is always strictly smaller then the second one. On the other hand,
standard deviations - "widths" - of those distributions in the same limit go
to $0$. Combining those two facts we get that with growing $d_{\lambda}$
distributions of
$\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)$ and
$\delta\left(\lambda\right)$ concentrate around
$2\sqrt{\frac{\mathcal{S}-1}{\mathcal{S}}}$ and $2$ respectively. This leads
us to the conclusion that our conjecture is true even for representations with
much higher dimensions than those we considered.

The other argument for our conjecture comes from the observation that (see
Figure 5)

$M_{\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)}\leq 2,$

similarly to the random matrix ensembles (Fact 7). Since median is a value at
which tail probability is equal to $\frac{1}{2}$ we obtain that for
$\epsilon=0$ it holds A $\leq\frac{1}{2}$ while from the Theorem 8 we know
that for the same $\epsilon$ we have C$=\frac{1}{2}$. So at least in
$\epsilon=0$ it holds A $\leq$ C and unless C is decreasing with $\epsilon$
much faster than A, which we observe not to be the case, the inequality holds
for all $\epsilon>0$.

In Figures 2 and 3 we show similar data as in 1 but this time for various $t$.
In those Figures we compare:

  * A

$\mathbb{P}\left(\delta\left(\nu_{\mathcal{S}},t\right)>\frac{2+\epsilon}{\sqrt{\mathcal{S}}}\right)$,

  * B

$\mathbb{P}\left(\delta\left(t\right)>2+\epsilon\right)$,

  * C

bounds 110 and 111 from Theorem 8

for various values of $t$ and $\mathcal{S}$ and again we observe that A $\leq$
B $\leq$ C. We also note that the bound 111 is mach better for small
$\epsilon$ than the bound 110.

###  6.3 Rescaling

In Section 3 we showed that when $t\rightarrow\infty$ the distribution of
singular values of $T_{\nu_{\mathcal{S}},t}$ converges to (60):

$\frac{|\mathcal{S}|\sqrt{\delta_{\mathrm{opt}}^{2}(\mathcal{S})-x^{2}}}{\pi(1-x^{2})},\quad
x\in\left[0,\delta_{\mathrm{opt}}(\mathcal{S})\right].$

where
$\delta_{\mathrm{opt}}(\mathcal{S})=\frac{2\sqrt{\mathcal{S}-1}}{\mathcal{S}}$.
We note that, by standard dimensionality arguments, for (symmetric) Haar
random gate-set $\mathcal{S}$ the group generated by
$\mathcal{S}\cup\mathcal{S}^{-1}$ is free with the probability $1$. Then in
Section 4 we obtained that in the same limit the distribution of singular
values of $\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},t}$ converges to:

$\frac{1}{\pi(1-\frac{y^{2}}{\mathcal{S}})}\sqrt{\frac{4\left(\mathcal{S}-1\right)}{\mathcal{S}}-y^{2}}\,\,,\quad
y\in\left[0,2\sqrt{\frac{\mathcal{S}-1}{\mathcal{S}}}\right],$ (131)

which in a limit $\mathcal{S}\rightarrow\infty$ converges to the quarter-
circle distribution:

$\displaystyle\sigma_{QC}(y)=\frac{1}{\pi}\sqrt{4-y^{2}},\quad y\in[0,2].$

From Figure 4 we know that for $d_{\lambda}\rightarrow\infty$ expected values
$\mathbb{E}\left(\sqrt{\mathcal{S}}\|T_{\nu_{\mathcal{S}},\lambda}\|\right)$
and $\mathbb{E}\left(\|T_{\lambda}\|\right)$ concentrate around the right
endpoints of supports of (131) and $\sigma_{QC}$ respectively. The fact that
those endpoints are different for (131) and $\sigma_{QC}$ is causing the
divergence of the distributions
$\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)$ and
$\delta\left(\lambda\right)$ for large $d_{\lambda}$ what we observed in
Figures 4 and 6 and discussed in previous subsection.
If we want our random matrix model to match $T_{\nu_{\mathcal{S}},\lambda}$
also in a regime of big $d_{\lambda}$ we have to multiply our operator by
$\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}$ instead of
$\sqrt{\mathcal{S}}$. We can easily compute that the distribution of singular
values of
$\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}T_{\nu_{\mathcal{S}},t}$ is:

$\displaystyle\frac{|\mathcal{S}|-1}{|\mathcal{S}|(1-\frac{|\mathcal{S}|-1}{|\mathcal{S}|^{2}}y^{2})}\frac{1}{\pi}\sqrt{4-y^{2}},\quad
y\in[0,2],$ (132)

so we kept the asymptotic behaviour for $\mathcal{S}\rightarrow\infty$ and the
endpoints are now the same. In order to show that
$\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}T_{\nu_{\mathcal{S}},t}$
converges to the same random matrix ensemble model as
$\sqrt{\mathcal{S}}T_{\nu_{\mathcal{S}},t}$ we can either repeat the steps
from Section 4 or note that
$\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}=\frac{\mathcal{S}}{\sqrt{\mathcal{S}-1}}=\Theta(\sqrt{\mathcal{S}})$
so asymptotically those two operators are the same.
Figure 6 shows how $\sqrt{\mathcal{S}}$ and
$\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}$ scalings change with
$d_{\lambda}$. Clearly, the second one is much more similar to the random
matrix ensemble model. On the other hand we can also see that the distribution
of
$\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}\delta\left(\nu_{\mathcal{S}},\lambda\right)$
is shifted relative to the distribution of $\delta\left(\lambda\right)$
towards bigger values. In other words, our data indicates that:

$\mathbb{P}\left(\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)>2+\epsilon\right)\leq\mathbb{P}\left(\delta\left(\lambda\right)>2+\epsilon\right)\leq\mathbb{P}\left(\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}\delta\left(\nu_{\mathcal{S}},\lambda\right)>2+\epsilon\right).$

In summary, the $\frac{2}{\delta_{\mathrm{opt}}(\mathcal{S})}$ scaling has
better asymptotic behaviour for $d_{\lambda}\rightarrow\infty$ but it is less
useful for theoretical purposes where we need an upper bound on a tail
probability.

Figure 1: Comparison of
$\mathbb{P}\left(\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)>2+\epsilon\right)$
\- blue, $\mathbb{P}\left(\delta\left(\lambda\right)>2+\epsilon\right)$ \-
yellow and tail bounds $F_{\ast}(d_{\lambda},\epsilon)$ from Fact 8 \- orange
for Haar random gate-sets of dimension $d=4$, sizes: $\mathcal{S}=2\times 2$
\- left, $\mathcal{S}=2\times 4$ \- middle, $\mathcal{S}=2\times 6$ \- right
and for weights: $\lambda=(1,0,0,-1)$ \- top, $\lambda=(2,0,-1,-1)$ \- middle,
$\lambda=(3,1,-1,-3)$ \- bottom. Figure 2: Comparison of
$\mathbb{P}\left(\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},t\right)>2+\epsilon\right)$
\- blue, $\mathbb{P}\left(\delta\left(t\right)>2+\epsilon\right)$ \- yellow,
bound (110) - solid orange and bound (111) - dashed orange for symmetric Haar
random gate-sets of dimension $d=4$, sizes: $\mathcal{S}=3$ \- left,
$\mathcal{S}=6$ \- middle, $\mathcal{S}=10$ \- right and for values of $t$:
$t=2$ \- top, $t=4$ \- middle, $t=6$ \- bottom. Figure 3: Comparison of
$\mathbb{P}\left(\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},t\right)>2+\epsilon\right)$
\- blue, $\mathbb{P}\left(\delta\left(t\right)>2+\epsilon\right)$ \- yellow,
bound (110) - solid orange and bound (111) - dashed orange for symmetric Haar
random gate-sets of dimension $d=2$, sizes: $\mathcal{S}=2\times 2$ \- left,
$\mathcal{S}=2\times 7$ \- middle, $\mathcal{S}=2\times 13$ \- right and for
values of $t$: $t=5$ \- top, $t=50$ \- middle, $t=500$ \- bottom.

Figure 4: Averages and standard deviations of the distributions of
$\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)$ \- blue and
$\delta\left(\lambda\right)$ \- orange for
$\lambda\in\Lambda^{\mathrm{ess}}_{6}$, $d=4$, Haar random sets with
$\mathcal{S}=9$ \- top and symmetric Haar random sets with
$\mathcal{S}=2\times 9$ \- bottom.

Figure 5: Medians
$M_{\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)}$ for
$\lambda\in\Lambda^{\mathrm{ess}}_{6}$, $d=4$, Haar random sets with
$\mathcal{S}=6$ \- top and symmetric Haar random sets with
$\mathcal{S}=2\times 6$ \- bottom. With dashed lines we designated
$2\sqrt{\frac{\mathcal{S}-1}{\mathcal{S}}}$ and $2$.

Figure 6: Histograms of
$\sqrt{\mathcal{S}}\delta\left(\nu_{\mathcal{S}},\lambda\right)$ \- blue,
$\frac{2}{\delta_{opt}(\mathcal{S})}\delta\left(\nu_{\mathcal{S}},\lambda\right)$
\- orange and $\delta\left(\lambda\right)$ \- yellow for dimension $d=4$, Haar
random gate-set with size $\mathcal{S}=8$ \- top, symmetric Haar random gate-
set with size $\mathcal{S}=2\times 8$ \- bottom and for weights:
$\lambda=(1,1,1,-3)$, $\lambda=(3,0,0,-3)$, $\lambda=(3,3,0,-6)$.

## Acknowledgments

This research was funded by the National Science Centre, Poland under the
grant OPUS: UMO-2020/37/B/ST2/02478 and supported in part by PLGrid
Infrastructure.

## References

  * [1] M. Oszmaniec, A. Sawicki and M. Horodecki  “Epsilon-Nets, Unitary Designs, and Random Quantum Circuits”  In _IEEE Transactions on Information Theory_ 68.2, 2022, pp. 989–1015  DOI: 10.1109/TIT.2021.3128110
  * [2] Y. Nakata et al.  “Quantum Circuits for Exact Unitary $t$-Designs and Applications to Higher-Order Randomized Benchmarking”  In _PRX Quantum_ 2 American Physical Society, 2021, pp. 030339  DOI: 10.1103/PRXQuantum.2.030339
  * [3] J.. Epstein, A.. Cross, E. Magesan and J.. Gambetta  “Investigating the limits of randomized benchmarking protocols”  In _Physical Review A_ 89.6 American Physical Society (APS), 2014  DOI: 10.1103/physreva.89.062321
  * [4] H. Huang, R. Kueng and J. Preskill  “Predicting Many Properties of a Quantum System from Very Few Measurements”  In _Nature Physics_ 16.10 Springer ScienceBusiness Media LLC, 2020, pp. 1050–1057  DOI: 10.1038/s41567-020-0932-7
  * [5] O. Szehr, F. Dupuis, M. Tomamichel and R. Renner  “Decoupling with unitary approximate two-designs”  In _New Journal of Physics_ 15.5, 2013, pp. 053022  DOI: 10.1088/1367-2630/15/5/053022
  * [6] A. Abeyesinghe, I. Devetak, P. Hayden and A. Winter  “The mother of all protocols: restructuring quantum information’s family tree”  In _Proceedings of the Royal Society of London Series A_ 465.2108, 2009, pp. 2537–2563  DOI: 10.1098/rspa.2009.0202
  * [7] J. Radhakrishnan, M. Rötteler and P. Sen  “Random measurement bases, quantum state distinction and applications to the hidden subgroup problem”  In _Algorithmica_ 55, 2009, pp. 490–516
  * [8] A. Sawicki, L. Mattioli and Z. Zimborás  “Universality verification for a set of quantum gates”  In _Phys. Rev. A_ 105 American Physical Society, 2022, pp. 052602  DOI: 10.1103/PhysRevA.105.052602
  * [9] L. Susskind  “Three Lectures on Complexity and Black Holes”  Springer Cham, 2020  arXiv:1810.11563 [hep-th]
  * [10] Daniel A. Roberts and Beni Yoshida  “Chaos and complexity by design”  In _Journal of High Energy Physics_ 2017.4, 2017, pp. 121  DOI: 10.1007/JHEP04(2017)121
  * [11] M. Oszmaniec, M. Horodecki and N. Hunter-Jones  “Saturation and recurrence of quantum complexity in random quantum circuits”  In _arXiv e-prints_ arXiv, 2022  DOI: 10.48550/ARXIV.2205.09734
  * [12] J. Haferkamp et al.  “Linear growth of quantum circuit complexity”  In _Nature Physics_ 18.5, 2022, pp. 528–532  arXiv:2106.05305
  * [13] M.. Hastings and A.. Harrow  “Classical and Quantum Tensor Product Expanders”  In _Quantum Info. Comput._ 9.3 Paramus, NJ: Rinton Press, Incorporated, 2009, pp. 336–360  arXiv:0804.0011
  * [14] A.. Harrow and R.. Low  “Efficient Quantum Tensor Product Expanders and k-Designs”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 548–561  arXiv:0811.2597
  * [15] F…. Brandão, A.. Harrow and M. Horodecki  “Local Random Quantum Circuits are Approximate Polynomial-Designs”  In _Communications in Mathematical Physics_ 346.2, 2016, pp. 397–434  DOI: 10.1007/s00220-016-2706-8
  * [16] A. Harrow and S. Mehraban  “Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates”  In _arXiv e-prints_ , 2018  arXiv:1809.06957 [quant-ph]
  * [17] J. Haferkamp  “Random quantum circuits are approximate unitary $t$-designs in depth $O\left(nt^{5+o(1)}\right)$”  In _Quantum_ 6 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2022, pp. 795  DOI: 10.22331/q-2022-09-08-795
  * [18] J. Haferkamp and N. Hunter-Jones  “Improved spectral gaps for random quantum circuits: Large local dimensions and all-to-all interactions”  In _Phys. Rev. A_ 104 American Physical Society, 2021, pp. 022417  DOI: 10.1103/PhysRevA.104.022417
  * [19] Y. Nakata, C. Hirche, M. Koashi and A. Winter  “Efficient Quantum Pseudorandomness with Nearly Time-Independent Hamiltonian Dynamics”  In _Phys. Rev. X_ 7 American Physical Society, 2017, pp. 021006  DOI: 10.1103/PhysRevX.7.021006
  * [20] J. Haferkamp et al.  “Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates”  In _arXiv e-prints_ , 2020  arXiv:2002.09524 [quant-ph]
  * [21] S… Oliviero, L. Leone and A. Hamma  “Transitions in entanglement complexity in random quantum circuits by measurements”  In _Physics Letters A_ 418, 2021, pp. 127721  DOI: https://doi.org/10.1016/j.physleta.2021.127721
  * [22] L. Leone, S… Oliviero, Y. Zhou and A. Hamma  “Quantum Chaos is Quantum”  In _Quantum_ 5 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 453  DOI: 10.22331/q-2021-05-04-453
  * [23] J. Bourgain and A. Gamburd  “A spectral gap theorem in SU(d)”  In _J. Eur. Math. Soc._ 14.5, 2012, pp. 1455–1511  DOI: 10.4171/JEMS/337
  * [24] P. Dulian and A. Sawicki  “Matrix concentration inequalities and efficiency of random universal sets of quantum gates”  In _arXiv e-prints_ , 2022  arXiv:2202.05371
  * [25] J.. Tropp  “An Introduction to Matrix Concentration Inequalities”, Foundations and Trends in Machine Learning  Now Publishers Inc, 2015  arXiv: https://arxiv.org/abs/1501.01571
  * [26] K.. Davidson and S.. Szarek  “Chapter 8 - Local Operator Theory, Random Matrices and Banach Spaces”  In _Handbook of the Geometry of Banach Spaces_ 1, 2001  DOI: 10.1016/S1874-5849(01)80010-3
  * [27] G. Aubrun and S. Szarek  “Alice and Bob meet Banach: the interface of asymptotic geometric analysis and quantum information theory”, Mathematical surveys and monographs  Providence, RI: American Mathematical Society, 2017  URL: https://cds.cern.ch/record/2296008
  * [28] G. Benkart et al.  “Tensor product representations of general linear groups and their connections with Brauer algebras”  In _J. Algebra_ 166, 1994, pp. 529–567
  * [29] T. Bröcker and T. Dieck  “Representations of Compact Lie Groups”, Graduate Texts in Mathematics  Springer Berlin Heidelberg, 2003  URL: https://books.google.pl/books?id=AfBzWL5bIIQC
  * [30] W. Fulton and J. Harris  “Representation Theory: A First Course”, Graduate Texts in Mathematics  Springer New York, 1991  URL: https://books.google.pl/books?id=TuQZAQAAIAAJ
  * [31] O. Słowik and A. Sawicki  “Calculable lower bounds on the efficiency of universal sets of quantum gates”  In _arXiv e-prints_ arXiv, 2022  DOI: 10.48550/ARXIV.2201.11774
  * [32] A. Oruc  “On number of partitions of an integer into a fixed number of positive integers”  In _Journal of Number Theory_ 159, 2016, pp. 355–369  DOI: https://doi.org/10.1016/j.jnt.2015.06.023
  * [33] D. Goldstein, R. Guralnick and R. Stong  “A lower bound for the dimension of a highest weight module”  In _Representation Theory of the American Mathematical Society 21(20)_ arXiv, 2016  DOI: 10.48550/ARXIV.1603.03076
  * [34] H. Kesten  “Symmetric Random Walks on Groups”  In _Transactions of the American Mathematical Society_ 92.2 American Mathematical Society, 1959, pp. 336–354  URL: http://www.jstor.org/stable/1993160
  * [35] A. Lubotzky, R. Phillips and P. Sarnak  “Hecke operators and distributing points on S2. II”  In _Communications on Pure and Applied Mathematics_ 40 Wiley Subscription Services, Inc., A Wiley Company, 1987, pp. 401–420
  * [36] K. Życzkowski, K.. Penson, I. Nechita and B. Collins  “Generating random density matrices”  In _Journal of Mathematical Physics_ 52.6, 2011, pp. 062201  arXiv:1010.3570
  * [37] W. Feller and V. Feller  “An Introduction to Probability Theory and Its Applications”  Wiley, 1957  URL: https://books.google.pl/books?id=BsSwAAAAIAAJ
  * [38] A.. Barut and R. Rączka  “Theory of group representations and applications”  World Scientific Publishing Co Pte Ltd., 1986
  * [39] F. Mezzadri  “How to generate random matrices from the classical compact groups”  In _Notices of the American Mathematical Society_ 54, 2007, pp. 592–604  arXiv:math-ph/0609050