# Matrix concentration inequalities and efficiency of random universal sets of
quantum gates

Piotr Dulian 1 and Adam Sawicki1

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

###### Abstract

For a random set $\mathcal{S}$ of quantum gates we provide bounds on the
probability that $\mathcal{S}$ forms a $\delta$-approximate $t$-design. In
particular we show how many random gates are needed to have a
$\delta$-approximate $t$-design with high probability. We also analyze how
$\delta$ concentrates around its expected value $\mathbb{E}\delta$ for random
$\mathcal{S}$. Our results are valid for both symmetric and non-symmetric sets
of gates.

##  1 Introduction and summary of main results

Practical realisations of quantum computers are constricted by noise and
decoherence that affect large-scale quantum systems. Although quantum error
correction codes can overcome those effects they require usage of thousands of
physical qubits to implement a single logical noiseless fault-tolerant qubit
[1]. This is clearly out of reach for contemporary quantum computers with the
number of physical qubits of the order of hundreds [2]. Hence, in the near
future we are forced to work with noisy intermediate-scale quantum devices
(NISQ) [2, 3, 4]. Moreover, currently the best error rates per gate are the
order of $0,1\%$ [5, 6] which implies we cannot build circuits much longer
than thousand [2]. The length of a circuit is also limited by the coherence
time and the time of execution of a single gate. It is noteworthy that it is
hard to make gates that are both fast and have low error rates [5]. Clearly,
there is a great need for quantum computation using as few gates as possible.
One way of achieving this is by using universal sets of gates (gate-sets) of
high efficiency, i.e. such that can approximate any unitary with circuits of
minimal length. This idea is also connected to complexity of unitaries (see
[7] for more details).

The efficiency of a universal set $\mathcal{S}$ (see [8, 9, 10] for criteria
that allow deciding universality) is typically measured by the length of a
circuit needed to approximate any quantum transformation with a given
precision $\epsilon$. The Solovay-Kitaev theorem states that all universal
sets are roughly the same efficient. More precisely, the length of a circuit
that $\epsilon$-approximates any $U\in SU(d)$ is bounded by
$A(\mathcal{S})\log^{c}(1/\epsilon)$ [11], where $c\geq 1$. To estimate the
value of $A(\mathcal{S})$ one can use the concept of $\delta$-approximate
$t$-designs [12, 13]. To this end 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 on $\mathcal{S}$. Such an
ensemble is called $\delta(\nu_{\mathcal{S}},t)$-approximate $t$-design if and
only if

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

where $\|\cdot\|$ is the operator norm and for any measure $\nu$ (in
particular for the Haar measure $\mu$) we define a _moment operator_

$\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}.$

It is known that the constant $A(\mathcal{S})$ from the Solovay-Kitaev theorem
is inversely proportional to $1-\delta(\nu_{\mathcal{S}})$, where
$\delta(\nu_{\mathcal{S}}):=\mathrm{sup}_{t}\delta(\nu_{\mathcal{S}},t)$,
whenever $\delta(\nu_{\mathcal{S}})<1$ [12]. Determining the value of
$\delta(\nu_{\mathcal{S}})$ requires computation of the norm of an infinite
number of operators $T_{\nu_{\mathcal{S}},t}$ which is analytically and
numerically intractable. It is known, however, that
$\delta(\nu_{\mathcal{S}})<1$ under the additional assumption that gates have
algebraic entries [14, 15]. In this case also the constant $c$ in the Solovay-
Kitaev theorem is equal to $1$. Recent results [16, 17, 18, 19, 20] based on
some number theoretic constructions give examples of universal sets with $c=1$
and the smallest possible value of $\delta(\nu_{\mathcal{S}})$. The approach
presented in these contributions has been unified in [20] where the author
pointed out the connection of these new results to the seminal work concerning
distributions of points on the sphere $S^{2}$ [21].

In contrast to the above mentioned contributions, in this work, we do not
focus on concrete gate-sets but instead we aim to answer the natural question
of how likely it is that a set of gates has high efficiency. In order to
achieve this goal we need to characterize efficiency of random universal gate-
sets. For such sets calculation of $\delta(\nu_{\mathcal{S}})$ is of course
intractable. Therefore we follow the approach of [13, 22] and consider
$\delta(\nu_{\mathcal{S}},t)$ for some fixed $t$ (which is determined by a
precision $\epsilon$). The results of [13, 22] ensure that for a given
precision $\epsilon$ the constant $A(\mathcal{S})$ in the Solovay-Kitaev
theorem is inversely proportional to
$1-\delta(\nu_{\mathcal{S}},t(\epsilon))$, where
$t(\epsilon)=O(\epsilon^{-1})$, and the constant $c=1$. Therefore, in order to
characterize efficiency of random universal sets of gates we need to
characterize a probability distribution of $\delta(\nu_{\mathcal{S}},t)$. In
this paper we consider two types of gate-sets:

  1. 1.

$\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

  2. 2.

$\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.

In order to simplify the notation we will often denote the cardinality of
$\mathcal{S}$ by $\mathcal{S}$ (instead of $|\mathcal{S}|$). Our main results
are given in a form of bounds on the probability
$\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)$. In order to
obtain them we first show that $T_{\nu_{\mathcal{S}},t}$ decomposes as a
direct sum over irreducible representations of the unitary group $U(d)$ that
can be labeled by elements subset $\lambda\in\Lambda_{t}\subset\mathbb{Z}^{d}$
(see formula (21)). The blocks appearing in this decomposition, that we denote
by $T_{\nu_{\mathcal{S}},\lambda}$, have dimensions $d_{\lambda}$ given by the
Weyl dimension formula (18). Using the union bound

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)\leq\sum_{\lambda\in\tilde{\Lambda}_{t}}\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)\geq\delta\right),$
(1)

where $\tilde{\Lambda}_{t}=\Lambda_{t}\setminus\\{0\\}$, we reduce the problem
to finding bounds on
$\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)\geq\delta\right)$. We
achieve this combining recently derived matrix concentration inequalities [23]
with the recent result concerning calculation of higher Frobenius-Schur
indicators for semisimple Lie algebras [24], that we further improve. Our main
results are Theorems 1, 2 that give concrete calculable bounds on
$\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)$.

######  Theorem 1.

Let $\mathcal{S}$ be a Haar random gate-set. Then for any $\delta<1$

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)\leq\frac{2e^{-\delta\mathcal{S}\,\mathrm{arctanh}(\delta)}}{(1-\delta^{2})^{\frac{\mathcal{S}}{2}}}\sum_{\lambda\in\tilde{\Lambda}_{t}}d_{\lambda},$
(2)

where, $\Lambda_{t}$ is given by (21),
$\tilde{\Lambda}_{t}=\Lambda_{t}\setminus 0$ and $d_{\lambda}$ is given by
(18).

######  Theorem 2.

Let $\mathcal{S}$ be a symmetric Haar random gate-set. Then for any $\delta<1$

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)\leq\sum_{\lambda\in\tilde{\Lambda}_{t}}d_{\lambda}e^{-\frac{\mathcal{S}\delta^{2}}{\sqrt{1-\delta^{2}}}}\left[F\left(\frac{\mathcal{S}\delta}{\sqrt{1-\delta^{2}}},\lambda,\mathcal{S}\right)+F\left(-\frac{\mathcal{S}\delta}{\sqrt{1-\delta^{2}}},\lambda,\mathcal{S}\right)\right],$
(3)

where $\Lambda_{t}$ is given by (21),
$\tilde{\Lambda}_{t}=\Lambda_{t}\setminus 0$, $d_{\lambda}$ is given by (18)
and $F(\cdot,\cdot,\cdot)$ is given by (29).

These theorems are then used to obtain bounds on the size of a Haar random
gate-set needed to form, with a probability $P$, a $\delta$-approximate
$t$-designs, for various $t$’s and $\delta$’s. We show that this size is of
the order $O(\delta^{-2}(t\log(d)-\log(1-P)))$. Moreover, we compare the
number of independent Haar random $n$-qubit gates, $\mathcal{S}_{n}$, needed
to form $0.01$-approximate $2$-design with the size of the $n$-qubit Clifford
group, $\mathcal{C}_{n}$, that is known to be an exact $2$-design. The ratio
of $\mathcal{C}_{n}/\mathcal{S}_{n}$ turns out to grow exponentially with the
number of qubits.

Finally we analyze concentration properties of $\delta(\nu_{\mathcal{S}},t)$
around its mean value $\mathbb{E}\delta(\nu_{\mathcal{S}},t)$. Our main result
is

######  Theorem 3.

Let $\mathcal{S}$ be a Haar random gate-set. Then

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\mathbb{E}\delta(\nu_{\mathcal{S}},t)+\alpha\right)\leq\exp\left({\frac{-d\mathcal{S}\alpha^{2}}{32t^{2}}}\right).$
(4)

The methods behind its proof [25] can be extended to Haar random gate-sets
with particular structure or architecture. Following this observation we
analyze efficiency of random $d$-mode circuits build from $2$-mode
beamsplitters. More precisely we consider the Hilbert space
$\mathcal{H}=\mathcal{H}_{1}\oplus\ldots\oplus\mathcal{H}_{d}$, where
$\mathcal{H}_{k}\simeq\mathbb{C}$, $d>2$ and we call spaces $\mathcal{H}_{k}$
modes. For a matrix $B\in SU(2)$, which we call a $2$-mode beamsplitter, we
define matrices $B^{ij}$, $i\neq j$, to be the matrices that act on a
$2$-dimensional subspace
$\mathcal{H}_{i}\oplus\mathcal{H}_{j}\subset\mathcal{H}$ as $B$ and on the
other components of $\mathcal{H}$ as the identity. This way a matrix $B\in
SU(2)$ gives $d(d-1)$ matrices in $SU(d)$. Applying this procedure to a Haar
random gate-set set $S\subset SU(2)$ we obtain random gate-set $S^{d}$ (see
[26, 27]) and it is natural to ask about its efficiency. Our main conclusion
here is that a Haar random gate-set $\mathcal{S}\subset SU(2)$ gives the gate-
set $S^{d}\subset SU(d)$ for which $\delta(\nu_{\mathcal{S}^{d}},t)$ has the
same concentration rate around the mean as a Haar random gate-set
$\mathcal{S}^{\prime}\subset SU(d)$ of size:
$\mathcal{S}^{\prime}=\frac{2\mathcal{S}}{d}$, i.e.

######  Theorem 4.

Let $\mathcal{S}\subset SU(2)$ be a Haar radom gate-set and
$\mathcal{S}^{d}\subset SU(d)$ the corresponding $d$-mode gate-set. Then

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}^{d}},t)\geq\mathbb{E}\delta(\nu_{\mathcal{S}^{d}},t)+\alpha\right)\leq\exp\left({\frac{-\mathcal{S}\alpha^{2}}{16t^{2}}}\right).$
(5)

The paper is organized as follows. In Section 2 we present a short review of
matrix concentration inequalities that will play a central role in our
setting. Next, in Section 3 we provide necessary information concerning
irreducible representations of unitary groups. Then in Section 4 we introduce
notion of moment operators. The main results of these paper are then showed in
Section 5, while Section 6 contains analysis of the results and applications.

##  2 Short review of relevant matrix concentration inequalities

In this section we review known upper bounds on the probability that
$\mathbb{P}(F(X)\geq\delta)$, for classes of random matrices $X$ and real
valued functions $F$ that are relevant in our setting. An interested reader is
referred to [23, 25] for more details. The first class of inequalities
concerns a situation when $X=\sum X_{k}$, where
$X_{k}\in\mathrm{Mat}(d,\mathbb{C})$ are independent, random, Hermitian
matrices and the function $F$ is the operator norm of $X$, $F(X)=\|X\|$. Thus
we are looking for an upper bound for
$\mathbb{P}\left(\|X\|\geq\delta\right)$. The line of reasoning is as follows.
Let $\lambda_{\mathrm{max}}(X)$ and $\lambda_{\mathrm{min}}(X)$ denote the
largest and the smallest eigenvalues of $X$ respectively. In the first step
one uses the exponential Markov inequality, i.e.

$\displaystyle\mathbb{P}\left(Y\geq t\right)=\mathbb{P}\left(e^{\theta Y}\geq
e^{\theta t}\right)\leq e^{-\theta t}\mathbb{E}e^{\theta Y},$

for any $\theta>0$. Taking $Y=\lambda_{\mathrm{max}}(X)$ and using the fact
that $e^{\theta\lambda_{\mathrm{max}}(X)}\leq\mathrm{tr}e^{\theta X}$ we get

$\displaystyle\mathbb{P}\left(\lambda_{\mathrm{max}}(X)\geq\delta\right)\leq\mathrm{inf}_{\theta>0}e^{-\theta\delta}\mathbb{E}\mathrm{tr}e^{\theta
X}.$ (6)

Next we note that
$\mathbb{P}\left(\lambda_{\mathrm{min}}(X)\leq\delta\right)=\mathbb{P}\left(-\lambda_{\mathrm{min}}(X)\geq-\delta\right)=\mathbb{P}\left(\lambda_{\mathrm{max}}(-X)\geq-\delta\right)$.
Thus

$\displaystyle\mathbb{P}\left(\lambda_{\mathrm{min}}(X)\leq\delta\right)\leq\mathrm{inf}_{\theta>0}e^{\theta\delta}\mathbb{E}\mathrm{tr}e^{-\theta
X}.$ (7)

Next, using the Lieb theorem [28] (one can alternatively use the Golden-
Thomson inequality [29, 30] but the resulting bound is in general weaker [23]
) we obtain

$\displaystyle\mathbb{E}\mathrm{tr}e^{\theta\sum_{k}X_{k}}\leq\mathrm{tr}\exp\left(\sum_{k}\log\mathbb{E}e^{\theta
X_{k}}\right),$ (8)

for any $\theta\in\mathbb{R}$. Combining (6) and (7) with (8) we get

$\displaystyle\mathbb{P}\left(\lambda_{\mathrm{max}}(X)\geq\delta\right)\leq\inf_{\theta>0}e^{-\theta\delta}\mathrm{tr}\exp\left(\sum_{k}\log\mathbb{E}e^{\theta
X_{k}}\right),$ (9)
$\displaystyle\mathbb{P}\left(\lambda_{\mathrm{min}}(X)\leq\delta\right)\leq\inf_{\theta>0}e^{\theta\delta}\mathrm{tr}\exp\left(\sum_{k}\log\mathbb{E}e^{-\theta
X_{k}}\right).$ (10)

Finally,

$\displaystyle\mathbb{P}\left(\|X\|\geq\delta\right)=\mathbb{P}\left(\mathrm{max}\\{\lambda_{\mathrm{max}}(X),-\lambda_{\mathrm{min}}(X)\\}\geq\delta\right)\leq\mathbb{P}\left(\lambda_{\mathrm{max}}(X)\geq\delta\right)+\mathbb{P}\left(\lambda_{\mathrm{min}}(X)\leq-\delta\right).$

######  Fact 1 (Master bound).

Let $X=\sum X_{k}$, where $X_{k}\in\mathrm{Mat}(d,\mathbb{C})$ are
independent, random, Hermitian matrices. Then

$\displaystyle\mathbb{P}\left(\|X\|\geq\delta\right)\leq\inf_{\theta>0}e^{-\theta\delta}\mathrm{tr}\exp\left(\sum_{k}\log\mathbb{E}e^{\theta
X_{k}}\right)+\inf_{\theta>0}e^{-\theta\delta}\mathrm{tr}\exp\left(\sum_{k}\log\mathbb{E}e^{-\theta
X_{k}}\right).$

A master bound can be also derived for the sum of non-Hermitian random
matrices. To this end, following [23], we consider the Hermitian dilation map

$\displaystyle\mathcal{H}:\mathrm{Mat}(d,\mathbb{C})\rightarrow\mathbb{H}(2d),$

where $\mathbb{H}(2d)$ is the space of $2d\times 2d$ Hermitian matrices given
by

$\displaystyle\mathcal{H}(X)=\begin{pmatrix}0&X\\\ X^{\ast}&0\end{pmatrix}.$

This map is clearly a real linear map. One can also show (cf. [23]) that
$\|X\|=\|\mathcal{H}(X)\|=\lambda_{\mathrm{max}}\left(\mathcal{H}(X)\right)$.
Making use of (9) we get:

######  Fact 2.

Let $X=\sum X_{k}$, where $X_{k}\in\mathrm{Mat}(d,\mathbb{C})$ are independent
random matrices. Then

$\displaystyle\mathbb{P}\left(\|X\|\geq\delta\right)\leq\inf_{\theta>0}e^{-\theta\delta}\mathrm{tr}\exp\left(\sum_{k}\log\mathbb{E}e^{\theta\mathcal{H}(X_{k})}\right).$

The upper bounds in Facts 1 and 2 can be further simplified by finding a
majorization of $\log\mathbb{E}e^{\theta X_{k}}$ in terms of moments
$\mathbb{E}X_{k}^{n}$ that allow analytic optimization over $\theta$ (see
chapter 6 of [23] for more details). Usage of moments up to order two leads to
the matrix Bernstein inequality.

######  Fact 3 (Matrix Bernstein inequality).

Let $X=\sum X_{k}$, where $X_{k}\in\mathrm{Mat}(d,\mathbb{C})$ are
independent, random matrices such that:

$\forall_{k}\quad\mathbb{E}X_{k}=0\quad\mathrm{and}\quad\|X_{k}\|\leq L.$

Let $v$ be the matrix variance statistic of the sum:

$\displaystyle v$
$\displaystyle=\max\left\\{\|\mathbb{E}(XX^{*})\|,\,\|\mathbb{E}(X^{*}X)\|\right\\},$
$\displaystyle=\max\left\\{\|\sum_{k}\mathbb{E}(X_{k}X_{k}^{*})\|,\,\|\sum_{k}\mathbb{E}(X_{k}^{*}X_{k})\|\right\\}.$

Then for all $\delta\geq 0$

$\mathbb{P}\left(\|X\|\geq\delta\right)\leq
2d\exp\left(\frac{-\delta^{2}/2}{v+L\delta/3}\right).$

###  2.1 Bounds for Haar random matrices

The second type of inequalities we will consider in this paper relay on the
fact that the randomness comes from the Haar measure. The interested reader is
refereed to chapter 5 of [25] for detailed discussion. Here we only give the
main result and mention that its proof is based on the fact that, by Bakery-
Émery curvature criterion, the (special)unitary group equipped with the Haar
measure satisfies the so-called logarithmic Sobolev inequality which, via the
Herbst argument, leads to concentration of measure for Lipschitz functions.

######  Fact 4.

Let $G^{\times\mathcal{S}}$, where $G$ is $SU(d)$ or $U(d)$, be equipped with
the metric given by the $L_{2}$-sum of Hilbert-Schmidt (Frobenius) metrics on
the group $G$, i.e. the distance between $(U_{1},\ldots,U_{\mathcal{S}})\in
G^{\times\mathcal{S}}$ and $(V_{1},\ldots,V_{\mathcal{S}})\in
G^{\times\mathcal{S}}$ is

$\displaystyle\left(\sum_{k=1}^{\mathcal{S}}\|U_{k}-V_{k}\|^{2}_{F}\right)^{\frac{1}{2}}.$

Suppose that

$F:G^{\times\mathcal{S}}\ni(U_{1},...,U_{\mathcal{S}})\rightarrow
F(U_{1},...,U_{\mathcal{S}})\in\mathbb{R},$

is $L$-Lipschitz, i.e.

$\displaystyle|F(U_{1},...,U_{\mathcal{S}})-F(V_{1},...,V_{\mathcal{S}})|\leq
L\left(\sum_{k=1}^{\mathcal{S}}\|U_{k}-V_{k}\|^{2}_{F}\right)^{\frac{1}{2}},$

and that $U_{1},...,U_{\mathcal{S}}$ are independent and chosen according to
the Haar measure on $G$. Then for any $\alpha>0$

$\mathbb{P}\left(F(U_{1},...,U_{\mathcal{S}})\geq\mathbb{E}F(U_{1},...,U_{\mathcal{S}})+\alpha\right)\leq\exp\left(-\frac{d\alpha^{2}}{4CL^{2}}\right).$

where $C$ is equal to $2$ for $SU(d)$ and $6$ for $U(d)$.

##  3 Irreducible representations of $U(d)$ and $SU(d)$

In this section we recall some basic facts about Lie groups, Lie algebras and
their representations in the context of groups $G=U(d)$ and $G=SU(d)$. In
Table 1 we summarize information about those groups, where we used
$M_{d}^{0}({\mathbb{C}}):=\left\\{X\in
M_{d}({\mathbb{C}})\,|\,\mathrm{Tr}(X)=0\right\\}$. We will denote by
$\mathfrak{g}$ the Lie algebra of $G$. The Lie algebra $\mathfrak{su}(d)$ has
no non-trivial ideals and thus is semisimple. On the other hand the algebra
$\mathfrak{u}(d)$ has an abelian ideal consisting of matrices proportional to
the identity and is not semisimple. We note, however, that
$[\mathfrak{u}(d),\mathfrak{u}(d)]=\mathfrak{su}(d)$. We will call a Lie group
semisimple if its Lie algebra is semisimple. Other relevant for us algebras
are Lie algebra complexification
$\mathfrak{g}_{\mathbb{C}}:=\mathfrak{g}+i\mathfrak{g}$, the Lie algebra of
the maximal torus $T$ in $G$ \- $\mathfrak{t}$ and the Cartan subalgebra (CSA)
- $\mathfrak{h}:=\mathfrak{t}+i\mathfrak{t}$.

$G$ | $U(d)$ | $SU(d)$
---|---|---
$\mathfrak{g}$ | $\mathfrak{u}(d):=\left\\{X\in M_{d}({\mathbb{C}})\,|\,X^{\dagger}=-X\right\\}$ | $\mathfrak{su}(d):=\mathfrak{u}(d)\cap M_{d}^{0}({\mathbb{C}})$
semi-simple | no | yes
$\mathfrak{g}_{\mathbb{C}}$ | $\mathfrak{u}(d)_{\mathbb{C}}\cong\mathfrak{gl}(d,{\mathbb{C}}):=M_{d}({\mathbb{C}})$ | $\mathfrak{su}(d)_{\mathbb{C}}\cong\mathfrak{sl}(d,{\mathbb{C}}):=M_{d}^{0}({\mathbb{C}})$
$\mathfrak{t}$ | $\mathfrak{t}:=\left\\{X\in\mathfrak{u}(d)\,|\,X\,\mathrm{diagonal}\right\\}$ | $\mathfrak{t}_{0}:=\mathfrak{t}\cap M_{d}^{0}({\mathbb{C}})$
$\mathfrak{h}$ | $\mathfrak{h}:=\left\\{X\in\mathfrak{gl}(d,{\mathbb{C}})\,|\,X\,\mathrm{diagonal}\right\\}$ | $\mathfrak{h}_{0}:=\mathfrak{h}\cap M_{d}^{0}({\mathbb{C}})$
Table 1: The comparison of groups $U(d)$ and $SU(d)$ in view of the Lie group
theory. We used $M_{d}^{0}({\mathbb{C}})$ to denote $\left\\{X\in
M_{d}({\mathbb{C}})\,|\,\mathrm{Tr}(X)=0\right\\}$.

The functional $\alpha\in\mathfrak{h}^{*}$ is called a root of $\mathfrak{g}$
if and only if there exists $X_{\alpha}\in\mathfrak{g}_{\mathbb{C}}$ such
that:

$\forall_{H\in\mathfrak{h}}\;\left[H,X_{\alpha}\right]=\alpha\left(H\right)X_{\alpha}.$
(11)

We denote the set of all roots by $\Phi$ and call it the root system. For a
given root $\alpha$ the subspace of all $X_{\alpha}$ satisfying (11) is called
a root subspace of $\alpha$ and denoted by $\mathfrak{g}_{\alpha}$. The
algebra $\mathfrak{g}_{\mathbb{C}}$ decomposes

$\mathfrak{g}_{\mathbb{C}}=\mathfrak{h}\oplus\bigoplus_{\alpha\in\Phi}\mathfrak{g}_{\alpha}.$

If we define $L_{i},\alpha_{i,j}\in\mathfrak{h}^{*}$ as

$\displaystyle L_{i}\left(\begin{pmatrix}a_{1}&0&0\\\ 0&\ddots&0\\\
0&0&a_{d}\end{pmatrix}\right):=a_{i},$ (12)
$\displaystyle\alpha_{i,j}:=L_{i}-L_{j},$ (13)

then the root system for $U(d)$ and $SU(d)$ is

$\Phi=\left\\{\alpha_{i,j}\,|\,1\leq i,j\leq d\right\\}.$

Among roots we distinguish positive roots

$\Phi^{+}:=\left\\{\alpha_{i,j}\,|\,1\leq i<j\leq d\right\\},$

and positive simple roots

$\Delta:=\left\\{\alpha_{i,i+1}\,|\,1\leq i\leq d-1\right\\}.$

For $\alpha,\beta\in\mathfrak{h}^{*}$ we say that $\alpha$ is higher (lower)
than $\beta$ iff $\alpha-\beta$ is a linear combination of positive simple
roots with non-negative (non-positive) coefficients and we denote it by
$\alpha>\beta$ ( $\alpha<\beta$).
We introduce the inner product on $\mathfrak{h}^{*}$ defined by

$\braket{L_{i}}{L_{j}}:=\delta_{i,j}.$

The inner product gives us an isomorphism $\mathfrak{h}^{*}\ni
L\mapsto\bra{\bar{L}}\in\mathfrak{h}$ hence further in the text we will
identify $\mathfrak{h}^{*}$ with $\mathfrak{h}$. For any $\alpha\in\Phi$ the
root system is preserved under the reflection about the hyper-plane
perpendicular to $\alpha$:

$s_{\alpha}:\mathfrak{h}\ni H\mapsto
H-\frac{2\braket{H}{\alpha}}{\braket{\alpha}{\alpha}}\alpha.$

The group $\mathcal{W}:=<s_{\alpha}\,|\,\alpha\in\Phi>$ is called the Weyl
group of $\Phi$. In our case $\mathcal{W}$ is isomorphic to the group of
permutations $S_{d}$ and action of $\sigma\in\mathcal{W}$ on $\mathfrak{h}$ is
given by:

$\sigma\cdot L_{i}:=L_{\sigma^{-1}(i)}.$

An element $H\in\mathfrak{h}$ is called:

  * •

integral iff
$\forall_{\alpha\in\Phi}\;\frac{2\braket{H}{\alpha}}{\braket{\alpha}{\alpha}}\in\mathbb{Z}$,

  * •

analytically integral iff for all $X\in\mathfrak{h}$ such that $e^{2\pi
iX}=\text{1}$ there holds $\braket{X}{H}\in\mathbb{Z}$,

  * •

dominant iff $\forall_{\alpha\in\Delta}\;\braket{\alpha}{H}\geq 0$.

For every finite dimensional representation $\pi:G\rightarrow GL(V)$ of $G$
there exists representation $\rho:\mathfrak{g}\rightarrow\mathfrak{gl}(V)$
such that for any $X\in\mathfrak{g}$ there holds

$\pi\left(e^{X}\right)=e^{\rho(X)}.$

Let us define the complexification of $\rho$ to be
$\rho_{\mathbb{C}}:\mathfrak{g}_{\mathbb{C}}\ni
X+iY\mapsto\rho(x)+i\rho(Y)\in\mathfrak{gl}(V,{\mathbb{C}})$. Then the
following are equivalent:

  * •

$\pi$ is irreducible,

  * •

$\rho$ is irreducible,

  * •

$\rho_{\mathbb{C}}$ is irreducible.

Further in the text we will slightly abuse notation and we will use $\rho$
also for $\rho_{\mathbb{C}}$. A weight of $\rho$ is an integral element $\mu$
such that there exists a non-zero vector $v_{\mu}\in\rho$ satisfying:

$\forall_{H\in\mathfrak{h}}\;\rho(H)v_{\mu}=\braket{\mu}{H}v_{\mu}.$ (14)

Subspace of all $v_{\mu}$ satisfying (14) is called the weight space of $\mu$
and we denote it by $\rho^{\mu}$ or $\pi^{\mu}$. The multiplicity $m^{\mu}$
(or $m(\mu)$) of $\mu$ is the dimension of its weight space. Every irreducible
representation is a direct sum of its weight spaces. The notions of weight
space and root space are closely connected. Indeed for $v_{\mu}\in\rho^{\mu}$,
$X_{\alpha}\in\mathfrak{g}_{\alpha}$ and $H\in\mathfrak{h}$ we have:

$\displaystyle\rho\left(H\right)\rho\left(X_{\alpha}\right)v_{\mu}=\left(\rho(\left[H,X_{\alpha}\right])+\rho\left(X_{\alpha}\right)\rho\left(H\right)\right)v_{\mu}=$
$\displaystyle=\left(\braket{\alpha}{H}+\braket{\mu}{H}\right)\rho\left(X_{\alpha}\right)v_{\mu}=\braket{\mu+\alpha}{H}\rho\left(X_{\alpha}\right)v_{\mu},$

thus $\rho\left(X_{\alpha}\right)v_{\mu}$ is either $0$ or in
$\rho^{\mu+\alpha}$. The highest weight $\lambda$ is a weight in $\rho$ that
is higher than all other weights in $\rho$. Now, we can state the theorem of
the highest weight.

######  Fact 5 (Theorem of the highest weight).

For semi-simple complex Lie algebra $\mathfrak{g}_{\mathbb{C}}$ and its
finite-dimensional representation $\rho$ we have:

  1. 1.

$\rho$ has unique highest weight $\lambda$,

  2. 2.

$\lambda$ is dominant,

  3. 3.

if $\tilde{\rho}$ is another representation of $\mathfrak{g}_{\mathbb{C}}$
with highest weight $\lambda$ then $\tilde{\rho}$ is isomorphic to $\rho$,

  4. 4.

if $\lambda$ is dominant and integral then there exists finite-dimensional
irreducible representation of $\mathfrak{g}_{\mathbb{C}}$ with highest weight
$\lambda$.

######  Fact 6.

If $G$ is compact and connected the analogous theorem holds with the only
difference that the highest weight $\lambda$ has to be analytically integral.

In case of $U(d)$ we will identify highest weights $\lambda$ with sequences
$(\lambda_{1},...,\lambda_{d})$ where $\lambda_{i}:=\braket{\lambda}{L_{i}}$
and in case of $SU(d)$ we will identify highest weights $\lambda^{s}$ with
sequences $(\lambda^{s}_{1},...,\lambda^{s}_{d-1})$ where
$\lambda^{s}_{i}:=\braket{\lambda^{s}}{\alpha_{i,i+1}}$. From the second point
of Fact 5 we have that for $i<j$ there holds $\lambda_{i}\geq\lambda_{j}$ and
from analytical integrality $\lambda_{i}\in\mathbb{Z}$. Moreover, from the
fourth point of Fact 5 every sequence from $\mathbb{Z}^{d}$ satisfying those
conditions uniquely defines the highest weight $\lambda$ and the associated
representation. Analogously for $SU(d)$ the condition is
$\lambda^{s}_{i}\in\mathbb{Z}_{+}$ and any element of $\mathbb{Z}^{d-1}_{+}$
defines the highest weight. In both cases we use $\pi_{\lambda}$ and
$\rho_{\lambda}$ to denote the irreducible finite-dimensional representations
with highest weight $\lambda$.

Since $SU(d)$ is a subgroup of $U(d)$ any representation $\pi_{\lambda}$ of
$U(d)$ can be restricted to a representation
$\pi^{\prime}_{\lambda^{s}}:=\pi_{\lambda}|_{SU(d)}$ of $SU(d)$. The question
arises what is the relation between $\lambda$ and $\lambda^{s}$. On the other
hand, irreducible representations of $SU(d)$ are often labeled by the Young
diagrams instead of highest weights. In the following lemma we explore the
relations between highest weights of $U(d)$, highest weights of $SU(d)$ and
Young diagrams.

######  Lemma 5.

Let $\lambda$ be a highest weight of representation $\pi_{\lambda}$ of $U(d)$.
Then the corresponding representation of $SU(d)$ has a Young diagram given by
$(\lambda_{1}-\lambda_{d},\ldots,\lambda_{d-1}-\lambda_{d})$ and the standard
highest weight of this representation is given by
$(\lambda_{1}-\lambda_{2},\ldots,\lambda_{d-2}-\lambda_{d-1},\lambda_{d-1}-\lambda_{d})$.

###### Proof.

By the definition of $\lambda$ we have that for the highest weight vector
$v_{\lambda}\in\rho_{\lambda}^{\lambda}$ and any $H\in\mathfrak{h}$ it holds:

$\rho_{\lambda}(H)v=\braket{\lambda}{H}v_{\lambda}.$

Then for the representation
$\rho^{\prime}_{\lambda}:=\rho_{\lambda}|_{\mathfrak{sl}(d,{\mathbb{C}})}$ and
its any subspace $V$ we have:

$\displaystyle\forall_{X\in\mathfrak{su}(d)}\,\rho_{\lambda}^{\prime}(X)V\subset
V\Rightarrow\forall_{X\in\mathfrak{su}(d),\;\phi\in\mathbb{R}}\,(\rho_{\lambda}^{\prime}(X)+i\phi\text{1})V\subset
V\Rightarrow$
$\displaystyle\Rightarrow\forall_{X\in\mathfrak{su}(d),\;\phi\in\mathbb{R}}\,\rho_{\lambda}(X+i\phi\text{1})V\subset
V\Rightarrow\forall_{X\in\mathfrak{u}(d)}\,\rho_{\lambda}(X)V\subset V.$

Hence irreducibility of $\rho_{\lambda}$ implies the irreducibility of
$\rho^{\prime}_{\lambda}$.
Note that $L_{1}-L_{d},...,L_{d-1}-L_{d}$ is a basis of $\mathfrak{h}_{0}$ and
for $i\in\\{1,...,d-1\\}$:

$\rho^{\prime}_{\lambda}(L_{i}-L_{d})v_{\lambda}=\rho_{\lambda}(L_{i}-L_{d})v_{\lambda}=\braket{\lambda}{L_{i}-L_{d}}v_{\lambda}=(\lambda_{i}-\lambda_{d})v_{\lambda}.$

Since $v_{\lambda}$ is the highest weight vector the sequence
$\lambda^{Y}:=(\lambda_{1}-\lambda_{d},...,\lambda_{d-1}-\lambda_{d})$
uniquely determines the $\mathfrak{sl}(d,{\mathbb{C}})$ representation and the
associated $SU(d)$ representation. Moreover, from the relations
$\lambda_{1}\geq...\geq\lambda_{d}$ we have that $\lambda^{Y}$ is a sequence
of non-negative, descending integers and as such can be interpreted as a Young
diagram. If we choose $L_{1}-L_{2},...,L_{d-1}-L_{d}$ as a basis of
$\mathfrak{h}_{0}$, we analogously obtain the sequence
$\lambda^{s}:=(\lambda_{1}-\lambda_{2},...,\lambda_{d-1}-\lambda_{d})$ that is
a highest weight of $SU(d)$ representation. ∎

To simplify the description of highest weights we introduce the following
notation. For any $\lambda=(\lambda_{1},\ldots,\lambda_{d})$ in
$\mathbb{Z}^{d}$ we will denote its length by $l(\lambda)=d$. By $\lambda_{+}$
we will denote the subsequence of $\lambda$ of positive integers. Moreover

$\displaystyle\Sigma(\lambda)\coloneqq\sum_{k=1}^{d}\lambda_{k},$ (15)
$\displaystyle\|\lambda\|_{1}\coloneqq\sum_{k=1}^{d}|\lambda_{k}|,$ (16)
$\displaystyle d_{\lambda}\coloneqq\mathrm{dim}\pi_{\lambda}$ (17)

The value of $d_{\lambda}$ is determined by the Weyl dimension formula

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

######  Fact 7.

[31] Suppose that $\pi_{\lambda}$ is an irreducible representation of semi-
simple Lie group $G$ then $\mu\in\mathfrak{h}$ is a weight of $\pi_{\lambda}$
if and only if the following two conditions are satisfied:

  1. 1.

$\mu$ is contained in the convex hull of the orbit of $\lambda$ under the Weyl
group,

  2. 2.

$\lambda-\mu$ is a linear combination of positive simple roots with integer
coefficients.

######  Corollary 6.

Since $SU(d)$ is semi-simple and $SU(d)$ and $U(d)$ have the same roots and
root spaces the above fact also applies to $U(d)$.

We use Fact 7 to prove the following lemma.

######  Lemma 7.

For any weight $\mu$ of the representation $\pi_{\lambda}$ we have
$\|\mu\|_{1}\leq\|\lambda\|_{1}$ and $\Sigma(\mu)=\Sigma(\lambda)$.

###### Proof.

The first condition of Fact 7 reads

$\exists\;\\{t_{\sigma}\in[0,1]\;|\;\sigma\in S_{d}\\}\;\textrm{such
that}\;\sum_{\sigma\in S_{d}}t_{\sigma}=1\;\textrm{and}\;\mu=\sum_{\sigma\in
S_{d}}t_{\sigma}\sigma\cdot\lambda,$

hence

$\|\mu\|_{1}=\sum_{i=1}^{d}|\sum_{\sigma\in
S_{d}}t_{\sigma}\lambda_{\sigma(i)}|\leq\sum_{i=1}^{d}\sum_{\sigma\in
S_{d}}t_{\sigma}|\lambda_{\sigma(i)}|=\sum_{\sigma\in
S_{d}}t_{\sigma}\|\lambda\|_{1}=\|\lambda\|_{1},$

which proves the first part of the lemma. The second condition from Fact 7
implies

$\lambda-\mu=\sum_{i=1}^{d-1}c_{i}(\underbrace{0,...,0}_{i-1},1,-1,\underbrace{0,...,0}_{d-i-1}).$

By acting $\Sigma$ on both sides we obtain

$\Sigma(\mu-\lambda)=0\quad\Rightarrow\quad\Sigma(\mu)=\Sigma(\lambda).$

∎

######  Fact 8 (Kostant formula).

Let $p:\mathfrak{h}_{0}\rightarrow\mathbb{N}$ be such that $p(\mu)$ is equal
to the number of ways $\mu$ can be expressed as a linear combinations of
positive simple roots with non-negative integer coefficients,
$m_{\lambda^{s}}(\mu)$ a multiplicity of $\mu$ in $\pi_{\lambda^{s}}$ and
$\rho$ the half-sum of positive roots111Note that the corresponding Lie
algebra representation is denoted by $\rho_{\lambda^{s}}$ then

$m_{\lambda^{s}}(\mu)=\sum_{\sigma\in
S_{d}}\mathrm{sgn}(\sigma)\,p(\sigma\cdot(\lambda^{s}+\rho)-(\mu+\rho))$ (19)

##  4 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
the uniform measure on $\mathcal{S}$. Such an ensemble is called
$\delta(\nu_{\mathcal{S}},t)$-approximate $t$-design if and only if

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

where $\|\cdot\|$ is the operator norm and for any measure $\nu$ (in
particular for the Haar measure $\mu$) we define a _moment operator_

$\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}.$

One can easily show that $0\leq\delta(\nu_{\mathcal{S}},t)\leq 1$ [13]. When
$\delta(\nu_{\mathcal{S}},t)=0$ we say that $\mathcal{S}$ is an exact
$t$-design and when $\delta(\nu_{\mathcal{S}},t)=1$ we say that $\mathcal{S}$
is not a $t$-design. A map $U\mapsto U^{t,t}$ is a representation of the
unitary group $U(d)$. This representation is reducible and decomposes into
some irreducible representations $U(d)$.

######  Fact 9.

([32]) 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\bigoplus_{\lambda\in\Lambda_{t}}\pi_{\lambda}(U)^{\oplus
m^{\lambda}}\simeq\left(U\otimes\bar{U}\right)^{\otimes t},$ (20)

where

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

and $m_{\lambda}$ is the multiplicity of $\pi_{\lambda}$.

The representations occurring in decomposition (20) 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$ [33].
For $t=1$ decomposition (20) is particularly simple and reads
$U\otimes\bar{U}\simeq\mathrm{Ad}_{U}\oplus\text{1}$, where 1 stands for the
trivial representation and $\mathrm{Ad}_{U}$ is the adjoint representation of
$U(d)$ and $PU(d)\simeq\mathrm{Ad}_{U(d)}$222By $\mathrm{Ad}_{U}$ we mean the
matrix $\mathrm{Ad}_{U}:\mathfrak{su}(d)\rightarrow\mathfrak{su}(d)$,
$\mathrm{Ad}_{U}(X)=UXU^{-1}.$.

For any irreducible representation $\pi_{\lambda}$, $\lambda\in\Lambda_{t}$ we
define

$\displaystyle
T_{\nu_{\mathcal{S}},\lambda}=\int_{U(d)}d\nu_{\mathcal{S}}(U)\pi_{\lambda}(U).$

Next we define
$\delta(\nu_{\mathcal{S}},\lambda)\coloneqq\|T_{\nu_{\mathcal{S}},\lambda}\|$.
It follows directly from the definitions and discussion above that

$\displaystyle
T_{\nu_{\mathcal{S}},t}\simeq\bigoplus_{\lambda\in\Lambda_{t}}\left(T_{\nu_{\mathcal{S}},\lambda}\right)^{\oplus
m_{\lambda}},\,\delta(\nu_{S},t)=\mathrm{sup}_{\lambda\in\tilde{\Lambda}_{t}}\delta(\nu_{\mathcal{S}},\lambda),$
(22)

where $\tilde{\Lambda}_{t}=\Lambda_{t}\setminus\\{0\\}$. One can also define
$\delta(\nu_{\mathcal{S}}):=\mathrm{sup}_{t}\delta(\nu_{\mathcal{S}},t)$. It
is known that $\delta_{opt}(\mathcal{S})\leq\delta(\nu_{\mathcal{S}})\leq 1$,
where $\delta_{opt}=\frac{2\sqrt{\mathcal{S}-1}}{\mathcal{S}}$ [20].

######  Lemma 8.

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}=\sum_{1\leq n\leq d-1}p_{n}(k)\tilde{p}_{d-n}(k),$
(23)

where $p_{n}(k)$ is the number of partitions of $k$ with exactly $n$ integers
and $\tilde{p}_{n}(k)$ is the number of partitions of $k$ with at most $n$
integers. When $d\geq 2t$ formula (23) simplifies to

$\displaystyle\alpha_{2k}=p(k)^{2},$ (24)

where $p(k)$ is number of all partitions of $k$.

###### Proof.

First, we will prove $\|\lambda\|_{1}=2k$. We define $\lambda_{-}$ to be the
subsequence of $\lambda$ of negative integers. Then from the condition
$\Sigma(\lambda)=0$ we have:

$\Sigma(\lambda_{-})=(\Sigma(\lambda_{-})+\Sigma(\lambda_{+}))-\Sigma(\lambda_{+})=\Sigma(\lambda)-\Sigma(\lambda_{+})=-\Sigma(\lambda_{+}).$

Next, from the Eq. 16:

$\|\lambda\|_{1}=\sum_{k=1}^{d}|\lambda_{k}|=\Sigma(\lambda_{+})-\Sigma(\lambda_{-})=2\Sigma(\lambda_{+})\leq
2t.$

Thus $\|\lambda\|_{1}=2k$ for $k=\Sigma(\lambda_{+})$. Now let us put
$n=l(\lambda_{+})$ then the $\lambda_{+}$ is a decreasing sequence of $n$
positive integers that sum up to $\Sigma(\lambda_{+})=k$ so it is a partition
of $k$ with exactly $n$ integers and
$(-(\lambda_{-})_{l(\lambda_{-})},...,-(\lambda_{-})_{1})$ is a decreasing
sequence of $l(\lambda_{-})\leq d-n$ positive integers that sum up to
$-\Sigma(\lambda_{-})=k$ so it is a partition of $k$ with at most $n$
integers.
On the other hand, any partition of $k$ with exactly $n$ integers - $\eta$
with any partition of $k$ with at most $n$ integers - $\zeta$ can be combined
into a sequence:

$\tilde{\lambda}=(\eta_{1},...,\eta_{n},\underbrace{0,...,0}_{d-n-l(\zeta)},-\zeta_{l(\zeta)},...,\zeta_{1}),$

that is clearly an element of $\tilde{\Lambda}_{t}$ and
$\|\tilde{\lambda}\|_{1}=2k$. Hence there is a one to one correspondence
between sequences like $\lambda$ and pairs of partitions like $(\eta,\zeta)$.
Thus to proof the formula (23) the only thing left to do is to note that the
equations $\Sigma(\lambda)=0$ and $\lambda\neq 0$ imply inequalities $n\geq 1$
and $n\leq d-l(\lambda_{-})\leq d-1$.
The formula (24) results easily from the fact that for $n>k$ we have
$p_{n}(k)=0$ and $\tilde{p}_{n}(k)=p(k)$ for $n\geq k$. ∎

######  Lemma 9.

Let $U,V\in U(d)$. Assume $\lambda\in\tilde{\Lambda}_{t}$. Then

$\displaystyle\|\pi_{\lambda}(U)-\pi_{\lambda}(V)\|\leq\frac{\pi}{2}\|\lambda\|_{1}\|U-V\|.$

###### Proof.

As the operator norm is unitarly invariant it is enough to show that for a
diagonal unitary matrix
$U=\mathrm{diag}\left(e^{i\phi_{1}},\ldots,e^{i\phi_{d}}\right)\in U(d)$,
$\phi_{k}\in(-\pi,\pi]$ we have:

$\displaystyle\|\pi_{\lambda}(U)-\pi_{\lambda}(\text{1})\|\leq\frac{\pi}{2}\|\lambda\|_{1}\|U-\text{1}\|.$

One easily sees that

$\displaystyle\|U-\text{1}\|=2\sup_{1\leq k\leq
d}\left|\sin\left(\frac{\phi_{k}}{2}\right)\right|,$
$\displaystyle\frac{2}{\pi}\sup_{1\leq k\leq
d}|\phi_{k}|\leq\|U-\text{1}\|\leq\sup_{1\leq k\leq d}|\phi_{k}|.$

The eigenvalues of $\pi_{\lambda}(U)$ are given by

$\displaystyle
e^{i\psi_{k}},\,\,\psi_{k}=\sum_{i=1}^{d}\lambda_{i,k}\phi_{i},$

where $\lambda_{k}=(\lambda_{1,k},\ldots,\lambda_{d,k})$ satisfies
$\|\lambda_{k}\|_{1}\leq\|\lambda\|_{1}$ (see Lemma 7). Thus

$\displaystyle\|\pi_{\lambda}(U)-\text{1}\|=2\sup_{1\leq k\leq
d_{\lambda}}\left|\sin\left(\frac{\psi_{k}}{2}\right)\right|\leq\sup_{1\leq
k\leq d_{\lambda}}|\psi_{k}|\leq\|\lambda\|_{1}\sup_{1\leq k\leq
d}|\phi_{k}|\leq\frac{\pi}{2}\|\lambda\|_{1}\|U-\text{1}\|.$

∎

##  5 Main results

In this section we will consider two types of gate-sets:

  1. 1.

$\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.

  2. 2.

$\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.

In order to simplify the notation we will often denote the cardinality of
$\mathcal{S}$ by $\mathcal{S}$ (instead of $|\mathcal{S}|$). The moment
operators associated with the above two types of random sets of gates are
random matrices. When $\mathcal{S}$ is symmetric they are actually random
Hermitian matrices. Using inequalities listed in Section 2 we derive upper
bounds on $\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)\geq\delta\right)$
and $\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)$. Before we
proceed with concrete inequalities we note that

######  Lemma 10.

Assume that $\mathcal{S}\subset U(d)$ is a random set of quantum gates and
that for every $\lambda\in\tilde{\Lambda}_{t}$ we have
$\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)\geq\delta\right)\leq
F(\delta,\lambda,\mathcal{S})$. Then

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)\leq\sum_{\lambda\in\tilde{\Lambda}_{t}}F(\delta,\lambda,\mathcal{S}).$

###### Proof.

By (22) and using the union bound for probabilities we have

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)=\mathbb{P}\left(\mathrm{sup}_{\lambda\in\tilde{\Lambda}_{t}}\delta(\nu_{\mathcal{S}},\lambda)\geq\delta\right)\leq\sum_{\lambda\in\tilde{\Lambda}_{t}}\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)\geq\delta\right)\leq\sum_{\lambda\in\tilde{\Lambda}_{t}}F(\delta,\lambda,\mathcal{S}).$

∎

Therefore, to find a bound on
$\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\delta\right)$ it is enough to
find bounds on
$\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)\geq\delta\right)$,
$\lambda\in\tilde{\Lambda}_{t}$, which we do in next sections.

###  5.1 Bernstein type bounds

In this section we derive bounds on
$\mathbb{P}\left(\|T_{\nu_{\mathcal{S}},\lambda}\|\geq\delta\right)$ using
Bernstein inequality (see Section 2). It is worth to mention that
computationally this is the simplest derivation presented in this paper as it
requires only the knowledge of the second moments.

######  Theorem 11.

Let $\mathcal{S}$ be a Haar random gate-set. Then

$\displaystyle\mathbb{P}\left(\|T_{\nu_{\mathcal{S}},\lambda}\|\geq\delta\right)\leq\begin{cases}B_{1}(\delta,\lambda,\mathcal{S}),&\,\mathrm{when}\,\mathcal{S}-\textrm{symmetric
Haar random gate-set}\\\
B_{2}(\delta,\lambda,\mathcal{S}),&\,\mathrm{when}\,\mathcal{S}-\textrm{Haar
random gate-set}\end{cases}$

where

$\displaystyle
B_{1}(\delta,\lambda,\mathcal{S})=2d_{\lambda}\exp\left({\frac{-3\mathcal{S}\delta^{2}}{6\left(1+\delta_{\lambda}(2)\right)+4\delta}}\right),$
$\displaystyle
B_{2}(\delta,\lambda,\mathcal{S})=2d_{\lambda}\exp\left({\frac{-3\mathcal{S}\delta^{2}}{6+2\delta}}\right),$
$\displaystyle\delta_{\lambda}(2)=\begin{cases}\frac{1}{d_{\lambda}}&\mathrm{if}\,\pi_{\lambda}\,\mathrm{real}\\\
0&\mathrm{if}\,\pi_{\lambda}\,\mathrm{complex}\\\
-\frac{1}{d_{\lambda}}&\mathrm{if}\,\pi_{\lambda}\,\mathrm{quaternionic}\\\
\end{cases}.$

###### Proof.

In this proof we will use Fact 3 where we take $X=\sum_{k}X_{k}$ to be equal
$T_{\nu_{\mathcal{S}},\lambda}=\frac{1}{\mathcal{S}}\sum_{U\in\mathcal{S}}\pi_{\lambda}(U)$.
Let us start with the Haar random case. In this case all elements of
$\mathcal{S}$ are independent. Thus we will put
$X_{k}=\frac{1}{\mathcal{S}}\pi_{\lambda}(U_{k})$ for $k=1,...,\mathcal{S}$.
Then, since $\pi_{\lambda}$ is unitary we have

$\displaystyle\|X_{k}\|=\frac{1}{\mathcal{S}}\|\pi_{\lambda}(U_{k})\|=\frac{1}{\mathcal{S}},$
$\displaystyle
X_{k}X_{k}^{*}=X_{k}^{*}X_{k}=\frac{1}{\mathcal{S}^{2}}\text{1}_{\delta_{\lambda}}.$

Hence $L=\frac{1}{\mathcal{S}}$ and
$\nu=\|\sum_{k=1}^{\mathcal{S}}\mathbb{E}(X_{k}X_{k}^{*})\|=\frac{1}{\mathcal{S}}$
satisfy conditions from Fact 3 and the result follows.

When $\mathcal{S}$ is symmetric we put
$X_{k}=\frac{1}{\mathcal{S}}\left(\pi_{\lambda}\left(U\right)+\pi_{\lambda}\left(U^{-1}\right)\right)$
then using triangle inequality we get

$\|X_{k}\|=\frac{1}{\mathcal{S}}\|\pi_{\lambda}(U)+\pi_{\lambda}(U^{-1})\|\leq\frac{2}{\mathcal{S}}\|\pi_{\lambda}(U)\|=\frac{2}{\mathcal{S}},$

and from hermiticity of $X_{k}$

$X_{k}X_{k}^{*}=X_{k}^{*}X_{k}=\frac{1}{\mathcal{S}^{2}}\left(\pi_{\lambda}\left(U^{2}\right)+2\text{1}_{d_{\lambda}}+\pi_{\lambda}\left(U^{-2}\right)\right).$

Note that from the Schur’s lemma and the translation invariance of the Haar
measure the matrix

$\mathbb{E}\left(\pi_{\lambda}\left(U^{\pm
2}\right)\right)=\int\pi_{\lambda}\left(U^{\pm 2}\right)d\mu(U),$

is proportional to unity and the proportionality constant is a Frobenius-Schur
indicator of $\pi_{\lambda}$ divided by $d_{\lambda}$. We will call this
constant $\delta_{\lambda}(2)$. The reason for such designation together with
more formal proof of this fact will be presented further in the text in Lemma
13. For now, let us recall that the Frobenius-Schur indicator is equal to $1$,
$0$ or $-1$ for $\pi_{\lambda}$ real, complex or quaternionic respectively.
Thus

$\delta_{\lambda}(2)=\begin{cases}\frac{1}{d_{\lambda}}&\mathrm{if}\,\pi_{\lambda}\,\mathrm{real}\\\
0&\mathrm{if}\,\pi_{\lambda}\,\mathrm{complex}\\\
-\frac{1}{d_{\lambda}}&\mathrm{if}\,\pi_{\lambda}\,\mathrm{quaternionic}\\\
\end{cases}.$

Hence for $L=\frac{2}{\mathcal{S}}$ and

$\nu=\|\sum_{k=1}^{\frac{\mathcal{S}}{2}}\mathbb{E}(X_{k}X_{k}^{*})\|=\frac{\delta_{\lambda}(2)+1}{\mathcal{S}},$

the result follows from Fact 3.

∎

###  5.2 Master bounds

In this section we derive bounds on
$\mathbb{P}\left(\|T_{\nu_{\mathcal{S}},\lambda}\|\geq\delta\right)$ using the
formula for the master bound (see Section 2). This derivation requires
knowledge of all moments and is much more accurate than the Bernstein bound
given in the previous section.

####  5.2.1 Haar random gate-sets

For Haar random gate-sets the derivation of the bound for
$\mathbb{P}\left(\|T_{\nu_{\mathcal{S}},\lambda}\|\geq\delta\right)$ turns out
to be relatively simple.

######  Theorem 12.

Let $\mathcal{S}$ be a Haar random gate-set. Then for any $\delta<1$

$\displaystyle\mathbb{P}\left(\|T_{\nu_{\mathcal{S}},\lambda}\|\geq\delta\right)\leq
F(\delta,\lambda,\mathcal{S}),$

where

$\displaystyle
F(\delta,\lambda,\mathcal{S})=\frac{2d_{\lambda}}{\left(1+\delta\right)^{\frac{\mathcal{S}}{2}\left(1+\delta\right)}\left(1-\delta\right)^{\frac{\mathcal{S}}{2}\left(1-\delta\right)}}=\frac{2d_{\lambda}}{(1-\delta^{2})^{\frac{S}{2}}}e^{-\delta\mathcal{S}\,\mathrm{arctanh}(\delta)}.$

###### Proof.

To compute the master bound for non-Hermitian matrix (Fact 2) we need to
compute
$\mathbb{E}\exp\left(\frac{\theta}{\mathcal{S}}\mathcal{H}(\pi_{\lambda}(U))\right)$.
First, let us note that for any unitary matrix $U\in U(d_{\lambda})$:

$\mathcal{H}(U)^{2}=\begin{pmatrix}0&U\\\
U^{*}&0\end{pmatrix}^{2}=\begin{pmatrix}UU^{*}&0\\\
0&U^{*}U\end{pmatrix}=\text{1}_{2d_{\lambda}}.$

Since $\pi_{\lambda}$ is unitary we have

$\mathbb{E}\exp\left(\frac{\theta}{\mathcal{S}}\mathcal{H}(\pi_{\lambda}(U))\right)=\cosh{\left(\frac{\theta}{\mathcal{S}}\right)}\text{1}_{2d_{\lambda}}+\sinh{\left(\frac{\theta}{\mathcal{S}}\right)}\mathbb{E}\mathcal{H}(\pi_{\lambda}(U)).$

From Lemma 13 and the orthogonality of characters:

$\mathbb{E}\mathcal{H}(\pi_{\lambda}(U))=\mathcal{H}(\mathbb{E}\pi_{\lambda}(U))=0.$

Hence the right hand side of the master bound is:

$\inf_{\theta>0}e^{-\theta\delta}\mathrm{tr}\exp\left(\mathcal{S}\log\mathbb{E}e^{\frac{\theta}{\mathcal{S}}\mathcal{H}(X_{k})}\right)=\inf_{\theta>0}2d_{\lambda}\;e^{-\theta\delta}\cosh^{\mathcal{S}}\left(\frac{\theta}{\mathcal{S}}\right).$

By calculating derivative we easily get that the infimum is obtained for
$\theta=\mathcal{S}\,\mathrm{arctanh}(\delta)$ and the bound is:

$F(\delta,\lambda,\mathcal{S})=\frac{2d_{\lambda}}{\left(1+\delta\right)^{\frac{\mathcal{S}}{2}\left(1+\delta\right)}\left(1-\delta\right)^{\frac{\mathcal{S}}{2}\left(1-\delta\right)}}=\frac{2d_{\lambda}}{(1-\delta^{2})^{\frac{S}{2}}}e^{-\delta\mathcal{S}\,\mathrm{arctanh}(\delta)}.$

∎

####  5.2.2 Symmetric Haar random gate-sets

In the following we develop new bounds which are based on the fact that we can
calculate explicitly the expected values that appear in the master bound (see
Section 2). In order to perform this calculation we need a formula for
$\int_{U(d)}\pi_{\lambda}(U^{n})d\mu(U)$ for any $n$, $d$ and $\lambda$. First
in Lemma 13 we show that
$\int_{U(d)}\pi_{\lambda}(U^{n})d\mu(U)=\delta_{\lambda}(n)\text{1}_{d_{\lambda}}$.
Having this, we use [24] to give in Fact 10 an explicit formula for
$\delta_{\lambda}(n)$. Next, in Lemma 14 we prove that formula given in Fact
10 simplifies greatly when $n\geq d+1$ and $\delta_{\lambda}(n)$ is determined
by the multiplicity of the $0$-weight space, which, as we show in Lemma 15 is
always nonzero for $\lambda\in\tilde{\Lambda}_{t}$. Finally, we combine all
these intermediate results to formulate Theorem 17 which, using Fact 11, we
next optimize to obtain the main result of this section, that is, Theorem 18.

######  Lemma 13.

For any irreducible representation $\pi_{\lambda}$ of a compact Lie group $G$
we have

$\displaystyle\int_{G}\pi_{\lambda}(U^{n})d\mu(U)=\delta_{\lambda}(n)\text{1}_{d_{\lambda}},$
$\displaystyle\delta_{\lambda}(n)=\frac{1}{d_{\lambda}}\int_{G}\chi_{\lambda}(U^{n})d\mu(U).$

###### Proof.

For any $g\in G$ we have

$\displaystyle\pi_{\lambda}(g)\int_{G}\pi_{\lambda}(U^{n})d\mu(U)=\int_{G}\pi_{\lambda}(gU^{n})d\mu(U)=\int_{G}\pi_{\lambda}(gVgV\ldots
gVg)d\mu(V),$

where in the last equality we performed a change of variables $U=Vg$ and used
the invariance of the Haar measure. Similarly

$\displaystyle\left(\int_{G}\pi_{\lambda}(U^{n})d\mu(U)\right)\pi_{\lambda}(g)=\int_{G}\pi_{\lambda}(U^{n}g)d\mu(U)=\int_{G}\pi_{\lambda}(gVgV\ldots
gVg)d\mu(V),$

where in the last equality we performed a change of variables $U=Vg$ and used
the invariance of the Haar measure. Thus for any $g\in G$, the matrix
$\pi^{\lambda}(g)$ commutes with the integral in (13). By Schur lemma this
integral must be proportional to identity. The proportionality constant,
$\delta_{\lambda}(n)$, can be establish by taking trace of both sides of
equation (13).

∎

To calculate $\delta_{\lambda}(n)$ we will use the following result from [24].

######  Fact 10.

Let $G$ be a finite dimensional semisimple Lie group. Let $\pi_{\lambda^{s}}$
be an irreducible representation of $G$ with highest weight $\lambda^{s}$,
$\mathcal{W}$ the Weyl group of $\mathfrak{g}$ and $\rho$ the half sum of
positive roots. Then for $n\neq 0$

$\delta_{\lambda^{s}}(n)=\frac{1}{d_{\lambda^{s}}}\sum_{\sigma\in\mathcal{W}}\mathrm{sgn}(\sigma)\;m_{\lambda^{s}}\left(\frac{\rho-\sigma\cdot\rho}{n}\right).$

Immediate conclusion from Fact 10 is that there is $n_{0}$ such that for
$n\geq n_{0}$ elements $\frac{\rho-\sigma\cdot\rho}{n}$ are integral elements
if and only if $\sigma\cdot\rho=\rho$. In the next lemma we calculate $n_{0}$
for the group $SU(d)$.

######  Lemma 14.

For the group $SU(d)$ the constant $n_{0}$ is equal to $d+1$ and for $n\geq
n_{0}$ the formula (10) simplifies to:

$\delta_{\lambda^{s}}(n)=\frac{m_{\lambda^{s}}(0)}{d_{\lambda^{s}}}.$ (25)

###### Proof.

First, let us calculate $\rho$:

$\rho=\frac{1}{2}\sum_{\alpha\in\Phi^{+}}\alpha=\frac{1}{2}\sum_{1\leq i<j\leq
d}\alpha_{i,j}=\frac{1}{2}\sum_{1\leq i<j\leq
d}L_{i}-L_{j}=\sum_{i=1}^{d}\left(\frac{d-1}{2}-i+1\right)L_{i}.$

Thus for $i\neq j$ we have $\rho_{i}\neq\rho_{j}$ and the only $\sigma\in
S_{d}$ such that $\sigma\cdot\rho=\rho$ is the identity, which proves the
simplified formula (25). In order to find minimal $n_{0}$ note first that

$(\rho-\sigma\cdot\rho)_{i}=\rho_{i}-\rho_{\sigma(i)}=\sigma(i)-i,$

and that for $\frac{\rho-\sigma\cdot\rho}{n}$ to be an integral element it is
required that for all $1\leq i\leq d-1$

$\braket{\rho-\sigma\cdot\rho}{\alpha_{i,i+1}}=(\rho-\sigma\cdot\rho)_{i}-(\rho-\sigma\cdot\rho)_{i+1}=\sigma(i)-\sigma(i+1)+1,$

is divisible by $n$ or equivalently

$\forall_{1\leq i\leq
d-1}\exists_{C_{i}\in\mathbb{Z}}\quad\sigma(i+1)-\sigma(i)=C_{i}n+1.$ (26)

If $n=d$ then $\sigma(i)=i-1\;\mathrm{mod}\;d$ satisfies this condition thus
$n_{0}>d$. On the other hand, for $n>d$ the condition
$|\sigma(i+1)-\sigma(i)|\leq d-1$ implies that the constant $C_{i}$ in (26)
has to be zero for all $i$. Let us choose $j$ such that $j\neq d$ and
$\sigma(j)=d$ then

$1=C_{j}n+1=\sigma(j+1)-\sigma(j)=\sigma(j+1)-d\quad\Rightarrow\quad\sigma(j+1)=d+1,$

what is an obvious contradiction and $\sigma^{-1}(d)$ has to be $d$ but this
implies $\sigma(d-1)=\sigma(d)-1=d-1$ and analogously for all $1\leq i\leq d$
we have $\sigma(i)=i$. Therefore for $n>d$ the only $\sigma$ satisfying (26)
is the trivial one. ∎

In the next lemma we show when the representation $\pi_{\lambda^{s}}$ has the
weight $0$.

######  Lemma 15.

Suppose $\pi_{\lambda^{s}}$ is a representation of $SU(d)$ with the highest
weight $\lambda^{s}$. Then the following are equivalent:

  1. 1.

$\pi_{\lambda^{s}}$ has weight $0$,

  2. 2.

$\frac{1}{d}\sum_{j=1}^{d-1}j\lambda^{s}_{j}$ is an integer,

  3. 3.

there exists an irreducible finite-dimensional representation of $U(d)$ with
highest weight $\lambda$ \- $\pi_{\lambda}$ such that $\Sigma(\lambda)=0$ and
$\pi_{\lambda}|_{SU(d)}=\pi_{\lambda^{s}}$.

###### Proof.

We will start with 1) $\Rightarrow$ 2).
From Fact 7 there exist $c_{1},...,c_{d-1}\in\mathbb{Z}$ such that

$\lambda^{s}=\lambda^{s}-0=\sum_{i=1}^{d-1}c_{i}\alpha_{i,i+1},$

thus

$\lambda^{s}_{j}=\braket{\lambda^{s}}{\alpha_{j,j+1}}=\braket{\sum_{i=1}^{d-1}c_{i}\alpha_{i,i+1}}{\alpha_{j,j+1}}=\sum_{i=1}^{d-1}c_{i}\braket{\alpha_{i,i+1}}{\alpha_{j,j+1}}=-c_{j-1}+2c_{j}-c_{j+1},$

where we assume $c_{0}=0=c_{d}$. It follows

$\displaystyle\frac{1}{d}\sum_{j=1}^{d-1}j\lambda^{s}_{j}=\frac{1}{d}\sum_{j=1}^{d-1}j(-c_{j-1}+2c_{j}-c_{j+1})=$
$\displaystyle=\frac{1}{d}\left\\{\sum_{j=1}^{d-2}\left[-(j-1)+2j-(j+1)\right]c_{j}+\left[-(d-2)+2(d-1)\right]c_{d-1}\right\\}=$
$\displaystyle=\frac{d}{d}c_{d-1}=c_{d-1}\in\mathbb{Z}.$

2) $\Rightarrow$ 3)
For any $m\in\mathbb{Z}$

$\lambda=(m+\sum_{i=1}^{d-1}\lambda^{s}_{i},\;m+\sum_{i=2}^{d-1}\lambda^{s}_{i},\;...\;,\;m+\lambda^{s}_{d-1},\;m),$

satisfies $\lambda_{i}\in\mathbb{Z}$ and
$i<j\,\Rightarrow\,\lambda_{i}\geq\lambda_{j}$. Therefore there exists an
irreducible finite-dimensional representation of $U(d)$ with highest weight
$\lambda$ \- $\pi_{\lambda}$. From Lemma 5 clearly
$\pi_{\lambda}|_{SU(d)}=\pi_{\lambda^{s}}$ and for
$m=-\frac{1}{d}\sum_{j=1}^{d-1}j\lambda^{s}_{j}$ we have $\Sigma(\lambda)=0$.

3) $\Rightarrow$ 1)
Let us choose $\forall_{\sigma\in S_{d}}\;t_{\sigma}=\frac{1}{d!}$ then
$\sum_{\sigma\in S_{d}}t_{\sigma}=1$ and

$\displaystyle\sum_{\sigma\in
S_{d}}t_{\sigma}\sigma\cdot\lambda=\frac{1}{d!}(\sum_{\sigma\in
S_{d}}\lambda_{\sigma(1)},\;...\;,\;\sum_{\sigma\in
S_{d}}\lambda_{\sigma(d-1)})=\frac{1}{d}(\Sigma(\lambda),\;...\;,\;\Sigma(\lambda))=0.$

What is more for $c_{1}=\lambda_{1}$ and $\forall_{2\leq i\leq
d-1}\;c_{i}=\lambda_{i-1}+\lambda_{i}$ we have

$\sum_{i=1}^{d-1}c_{i}\alpha_{i,i+1}=\lambda=\lambda-0.$

Hence by Fact 7 weight $0$ is in $\pi_{\lambda}$ what implies that weight $0$
is in $\pi_{\lambda^{s}}$.

∎

As an example we next explicitly calculate the value of $\delta_{\lambda}(n)$
for $G=SU(2)$.

######  Lemma 16.

The constant in Lemma 13 for $SU(2)$ and non-trivial $\pi^{\lambda}$ is given
by

$\displaystyle\delta_{\lambda}(n)=\begin{cases}1&\text{if $n=0$,}\\\
0&\text{if $n=\pm 1$,}\\\ \frac{1}{d_{\lambda}}&\text{if
$n\in\mathbb{Z}\smallsetminus\\{-1,0,1\\}$ and $\lambda$-even, }\\\
-\frac{1}{d_{\lambda}}&\text{if $n=\pm 2$ and $\lambda$-odd}\\\ 0&\text{if
$n\in\mathbb{Z}\smallsetminus\\{-2,0,2\\}$ and $\lambda$-odd}\end{cases}$

###### Proof.

The result for $n=0$ and $n=1$ follows from definition of $\delta_{\lambda}$
and irreducibility of $\pi_{\lambda}$. For remaining $n$’s we will use Fact
10. First, let us notify that for $SU(2)$:

$\Delta=\\{\alpha_{12}\\},\qquad\alpha_{12}=2,\qquad\rho=1,\qquad[1\;2]\cdot\mu=-\mu,$

then from Kostant formula 8:

$m_{\lambda^{s}}(\mu)=\sum_{\sigma\in
S_{2}}\mathrm{sgn}(\sigma)\,p(\sigma\cdot(\lambda^{s}+\rho)-(\mu+\rho))=p(\lambda^{s}-\mu)-p(-\lambda^{s}-\mu-2).$
(27)

Recall that $p(m)$ is the number of ways $m$ can be expressed as a linear
combinations of positive simple roots with non-negative integer coefficients
so in our case

$p(m)=\begin{cases}1&\text{if $m$-even and non-negative,}\\\ 0&\text{if
$m$-odd or negative.}\end{cases}$

This combined with the fact that $-\lambda^{s}-\mu-2>0$ implies
$\|\mu\|_{1}>\|\lambda\|_{1}$ and Lemma 7 simplifies (27) to

$m_{\lambda^{s}}(\mu)=p(\lambda^{s}-\mu)=\begin{cases}1&\text{if
$(\lambda^{s}-\mu)$-even and non-negative,}\\\ 0&\text{if
$(\lambda^{s}-\mu)$-odd or negative.}\end{cases}$

Now, we are ready to use formula (10) which for $SU(2)$ has a form

$\delta_{\lambda^{s}}(n)=\frac{1}{d_{\lambda^{s}}}\left(m_{\lambda^{s}}(0)-m_{\lambda^{s}}\left(\frac{2}{n}\right)\right).$

Hence

$\delta_{\lambda^{s}}(\pm
2)=\frac{1}{d_{\lambda^{s}}}\left(m_{\lambda^{s}}(0)-m_{\lambda^{s}}(\pm
1)\right)=\begin{cases}\frac{1}{d_{\lambda^{s}}}&\text{if
$\lambda^{s}$-even,}\\\ -\frac{1}{d_{\lambda^{s}}}&\text{if
$\lambda^{s}$-odd.}\end{cases},$

and for $|n|\geq 3$

$\delta_{\lambda^{s}}(n)=\frac{1}{d_{\lambda^{s}}}m_{\lambda^{s}}(0)=\begin{cases}\frac{1}{d_{\lambda^{s}}}&\text{if
$\lambda^{s}$-even,}\\\ 0&\text{if $\lambda^{s}$-odd.}\end{cases}$

∎

######  Theorem 17.

Let $\mathcal{S}$ be a symmetric Haar random gate-set from $SU(d)$. Then

$\displaystyle\mathbb{P}\left(\|T_{\nu_{\mathcal{S}},\lambda^{s}}\|\geq\delta\right)\leq
d_{\lambda^{s}}\left[\mathrm{inf}_{\theta>0}\;e^{-\theta\delta}F(\theta,\lambda^{s},\mathcal{S})+\mathrm{inf}_{\theta>0}\;e^{-\theta\delta}F(-\theta,\lambda^{s},\mathcal{S})\right],$
(28)

where

$\displaystyle F(\theta,\lambda^{s},\mathcal{S})$
$\displaystyle=\left[\frac{m_{\lambda^{s}}^{0}}{d_{\lambda^{s}}}e^{\frac{2\theta}{\mathcal{S}}}+\sum_{k=-d}^{d}\gamma_{\lambda^{s}}(k)I_{|k|}\left(\frac{2\theta}{\mathcal{S}}\right)\right]^{\frac{\mathcal{S}}{2}},$
(29) $\displaystyle\gamma_{\lambda^{s}}(k)$
$\displaystyle=\begin{cases}1-\frac{m^{0}_{\lambda^{s}}}{d_{\lambda^{s}}}&\text{if
$k=0$},\\\ \frac{1}{d_{\lambda^{s}}}\sum_{\begin{subarray}{c}\sigma\in
S_{d}\\\ \sigma\neq
id\end{subarray}}\mathrm{sgn}(\sigma)m_{\lambda^{s}}\left(\frac{\rho-\sigma\cdot\rho}{k}\right)&\text{if
$k\neq 0$},\end{cases}$

and $I_{n}(x)$ is $n$-th modified Bessel function of the first kind.

###### Proof.

Clearly, the bound from Fact 1 is of the form

$\mathrm{inf}_{\theta>0}\;e^{-\theta\delta}\tilde{F}(\theta,\lambda^{s},\mathcal{S})+\mathrm{inf}_{\theta>0}\;e^{-\theta\delta}\tilde{F}(-\theta,\lambda^{s},\mathcal{S}),$

where

$\displaystyle\tilde{F}(\theta,\lambda^{s},\mathcal{S})$
$\displaystyle=\mathrm{tr}\exp\left(\sum_{k=1}^{\mathcal{S}/2}\log\mathbb{E}e^{\frac{\theta}{\mathcal{S}}X_{U_{k},\lambda^{s}}}\right),$
$\displaystyle X_{U,\lambda^{s}}$
$\displaystyle=\pi_{\lambda^{s}}(U)+\pi_{\lambda^{s}}(U^{-1}).$

Thus our main objective is to compute the
$\mathbb{E}e^{\frac{\theta}{\mathcal{S}}X_{U,\lambda^{s}}}$. Using the
binomial formula one easily gets:

$\displaystyle\operatorname{\mathbb{E}}X_{U,\lambda^{s}}^{n}=\sum_{k=0}^{n}{n\choose
k}\operatorname{\mathbb{E}}\pi_{\lambda^{s}}(U^{n-2k})=\text{1}_{\lambda^{s}}\left[\sum_{k=0}^{n}{n\choose
k}\delta_{\lambda^{s}}(n-2k)\right].$ (30)

From Lemma 14 we know that for $|n-2k|>d$ the value of $\delta_{\lambda^{s}}$
is $\frac{m_{\lambda^{s}}^{0}}{d_{\lambda^{s}}}$. Thus Eq. (30) becomes

$\displaystyle\operatorname{\mathbb{E}}X_{U,\lambda^{s}}^{n}=\text{1}_{\lambda^{s}}\left[\sum_{k=0}^{n}{n\choose
k}\frac{m_{\lambda^{s}}^{0}}{d_{\lambda^{s}}}+\sum_{k=\lceil\frac{n-d}{2}\rceil}^{\lfloor\frac{n+d}{2}\rfloor}{n\choose
k}\left(\delta_{\lambda^{s}}(n-2k)-\frac{m_{\lambda^{s}}^{0}}{d_{\lambda^{s}}}\right)\right]=$
$\displaystyle=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{n}}{d_{\lambda^{s}}}+\sum_{k=\lceil\frac{n-d}{2}\rceil}^{\lfloor\frac{n+d}{2}\rfloor}{n\choose
k}\gamma_{\lambda^{s}}(n-2k)\right],$

where we assume ${n\choose k}=0$ for $n<k$ or $k<0$. We will consider
separately cases for different parities of $d$ and $n$:

$\bullet\quad d=2p$ and $n=2l$:

$\displaystyle\operatorname{\mathbb{E}}X_{U,\lambda^{s}}^{2l}=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l}}{d_{\lambda^{s}}}+\sum_{k=l-p}^{l+p}{2l\choose
k}\gamma_{\lambda^{s}}(2l-2k)\right]=$
$\displaystyle=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l}}{d_{\lambda^{s}}}+\sum_{k=-p}^{p}{2l\choose
l+k}\gamma_{\lambda^{s}}(2k)\right],$

$\bullet\quad d=2p$ and $n=2l+1$:

$\displaystyle\operatorname{\mathbb{E}}X_{U,\lambda^{s}}^{2l+1}=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l+1}}{d_{\lambda^{s}}}+\sum_{k=l+1-p}^{l+p}{2l+1\choose
k}\gamma_{\lambda^{s}}(2l+1-2k)\right]=$
$\displaystyle=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l+1}}{d_{\lambda^{s}}}+\sum_{k=-p+1}^{p}{2l+1\choose
l+k}\gamma_{\lambda^{s}}(2k-1)\right].$

Then we have:

$\displaystyle\operatorname{\mathbb{E}}e^{\frac{\theta}{\mathcal{S}}X_{U,\lambda^{s}}}=\text{1}\left[\frac{m^{0}_{\lambda^{s}}}{d_{\lambda^{s}}}e^{\frac{2\theta}{\mathcal{S}}}+\sum_{k=-p}^{p}\gamma_{\lambda^{s}}(2k)I_{|2k|}\left(\frac{2\theta}{\mathcal{S}}\right)+\sum_{k=-p+1}^{p}\gamma_{\lambda^{s}}(2k-1)I_{|2k-1|}\left(\frac{2\theta}{\mathcal{S}}\right)\right]=$
$\displaystyle=\text{1}\left[\frac{m^{0}_{\lambda^{s}}}{d_{\lambda^{s}}}e^{\frac{2\theta}{\mathcal{S}}}+\sum_{k=-d}^{d}\gamma_{\lambda^{s}}(k)I_{|k|}\left(\frac{2\theta}{\mathcal{S}}\right)\right].$
(31)

$\bullet\quad d=2p+1$ and $n=2l$:

$\displaystyle\operatorname{\mathbb{E}}X_{U,\lambda^{s}}^{2l}=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l}}{d_{\lambda^{s}}}+\sum_{k=l-p}^{l+p}{2l\choose
k}\gamma_{\lambda^{s}}(2l-2k)\right]=$
$\displaystyle=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l}}{d_{\lambda^{s}}}+\sum_{k=-p}^{p}{2l\choose
l+k}\gamma_{\lambda^{s}}(2k)\right],$

$\bullet\quad d=2p+1$ and $n=2l+1$:

$\displaystyle\operatorname{\mathbb{E}}X_{U,\lambda^{s}}^{2l+1}=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l+1}}{d_{\lambda^{s}}}+\sum_{k=l-p}^{l+p+1}{2l+1\choose
k}\gamma_{\lambda^{s}}(2l+1-2k)\right]=$
$\displaystyle=\text{1}_{\lambda^{s}}\left[\frac{m_{\lambda^{s}}^{0}\,2^{2l+1}}{d_{\lambda^{s}}}+\sum_{k=-p}^{p+1}{2l+1\choose
l+k}\gamma_{\lambda^{s}}(2k-1)\right].$

Then we have:

$\displaystyle\operatorname{\mathbb{E}}e^{\frac{\theta}{\mathcal{S}}X_{U,\lambda^{s}}}=\text{1}\left[\frac{m^{0}_{\lambda^{s}}}{d_{\lambda^{s}}}e^{\frac{2\theta}{\mathcal{S}}}+\sum_{k=-p}^{p}\gamma_{\lambda^{s}}(2k)I_{|2k|}\left(\frac{2\theta}{\mathcal{S}}\right)+\sum_{k=-p}^{p+1}\gamma_{\lambda^{s}}(2k-1)I_{|2k-1|}\left(\frac{2\theta}{\mathcal{S}}\right)\right]=$
$\displaystyle=\text{1}\left[\frac{m^{0}_{\lambda^{s}}}{d_{\lambda^{s}}}e^{\frac{2\theta}{\mathcal{S}}}+\sum_{k=-d}^{d}\gamma_{\lambda^{s}}(k)I_{|k|}\left(\frac{2\theta}{\mathcal{S}}\right)\right].$
(32)

Combining Eq. 31 and Eq. 32 with Fact 1 we get the desired result.

∎

Note that from Kostant formula (8) the multiplicities $m^{\mu}_{\lambda^{s}}$
are polynomials in coefficients of $\lambda^{s}$ with degree up to
$\frac{(d-2)(d-1)}{2}$ while from Weyl dimension formula (18) the dimension
$d_{\lambda^{s}}$ is a polynomial of degree $\frac{(d-1)d}{2}$. Thus for
$\lambda^{s}$ with large coefficients the expression in bracket in Eq. (28) is
approximately equal to
$\gamma_{\lambda^{s}}(0)I_{0}(\frac{2\theta}{\mathcal{S}})$. In order to
proceed we need the following property of the modified Bessel functions.

######  Fact 11.

[34] For any $n\geq 0$ we have the following upper and lower bounds on the
ratio of the modified Bessel functions

$\displaystyle\frac{x}{n-\frac{1}{2}+\sqrt{\left(n+\frac{1}{2}\right)^{2}+x^{2}}}<\frac{I_{n}(x)}{I_{n-1}(x)}<\frac{x}{n-1+\sqrt{\left(n+1\right)^{2}+x^{2}}}.$

Combining Fact 11 with Theorem 17 we arrive at

######  Theorem 18.

Let $\mathcal{S}$ be a symmetric Haar random gate-set from $SU(d)$. Then

$\displaystyle\mathbb{P}\left(\|T_{\nu_{\mathcal{S}},\lambda}\|\geq\delta\right)\leq
d_{\lambda^{s}}e^{-\frac{\mathcal{S}\delta^{2}}{\sqrt{1-\delta^{2}}}}\left[F\left(\frac{\mathcal{S}\delta}{\sqrt{1-\delta^{2}}},\lambda,\mathcal{S}\right)+F\left(-\frac{\mathcal{S}\delta}{\sqrt{1-\delta^{2}}},\lambda,\mathcal{S}\right)\right],$

where $F(\cdot,\cdot,\cdot)$ is given by (29).

###### Proof.

In order to find the best bound we need to determine $\theta$ that realizes

$\displaystyle\mathrm{inf}_{\theta>0}\;e^{-\theta\delta}\left[\frac{m_{\lambda^{s}}^{0}}{d_{\lambda^{s}}}e^{\frac{2\theta}{\mathcal{S}}}+\sum_{k=-d}^{d}\gamma_{\lambda^{s}}(k)I_{|k|}\left(\frac{2\theta}{\mathcal{S}}\right)\right]^{\frac{\mathcal{S}}{2}}.$

As finding minimum of the above functions is analytically intractable, in both
cases we look for $\theta$ that minimizes
$e^{-\theta\delta}I_{0}\left(\frac{2\theta}{\mathcal{S}}\right)^{\frac{\mathcal{S}}{2}}$.
Taking the derivative with respect to $\theta$ we get

$\displaystyle\delta=\frac{I_{1}\left(x\right)}{I_{0}\left(x\right)},$

where $x=\frac{2\theta}{\mathcal{S}}$. Using the upper bound for the ration of
modified Bessel functions from Fact 11 we get

$\displaystyle\delta=\frac{x}{\sqrt{4+x^{2}}}\,\implies\,x=\frac{2\delta}{\sqrt{1-\delta^{2}}}.$

The result follows. ∎

###  5.3 Concentration of $\delta(\nu_{\mathcal{S}},t)$ and
$\delta(\nu_{\mathcal{S}},\lambda)$ around their expected values

In this section we explore concentration properties of
$\delta(\nu_{\mathcal{S}},t)$ and $\delta(\nu_{\mathcal{S}},\lambda)$ using
Fact 4.

######  Theorem 19.

Let $\mathcal{S}\subset SU(d)$ be a Haar random gate-set. Then

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},t)\geq\mathbb{E}\delta(\nu_{\mathcal{S}},t)+\alpha\right)\leq\exp\left({\frac{-d\mathcal{S}\alpha^{2}}{32t^{2}}}\right).$

###### Proof.

Let $\mathcal{S}\subset SU(d)$ be any set of cardinality $n>1$. For the
convenience we denote by $\mathcal{S}_{1}=\\{U_{1},\ldots,U_{n}\\}$, and
$\mathcal{S}_{2}=\\{V_{1},\ldots,V_{n}\\}$ two exemplary sets $\mathcal{S}$.
Let

$\displaystyle
F(U_{1},\ldots,U_{n})=\|T_{\nu_{\mathcal{S}_{1}},t}-T_{\mu,t}\|.$

We need to show that there is a constant $L$ such that for any
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ we have

$\displaystyle|F(U_{1},\ldots,U_{n})-F(V_{1},\ldots,V_{n})|\leq
L\left(\sum_{i=1}^{n}\|U_{i}-V_{i}\|^{2}_{F}\right)^{\frac{1}{2}}.$

In order to determine the value of $L$ we go through the following chain of
inequalities

$\displaystyle\left|\|T_{\nu_{\mathcal{S}_{1}},t}-T_{\mu,t}\|-\|T_{\nu_{\mathcal{S}_{2}},t}-T_{\mu,t}\|\right|\leq\|T_{\nu_{\mathcal{S}_{1}},t}-T_{\nu_{\mathcal{S}_{2}},t}\|\leq\frac{1}{n}\sum_{i=1}^{n}\|U_{i}^{t,t}-V_{i}^{t,t}\|\leq$
$\displaystyle\leq\frac{2t}{n}\sum_{i=1}^{n}\|U_{i}-V_{i}\|\leq\frac{2t}{n}\sum_{i=1}^{n}\|U_{i}-V_{i}\|_{F}\leq\frac{2t}{\sqrt{n}}\left(\sum_{i=1}^{n}\|U_{i}-V_{i}\|^{2}_{F}\right)^{\frac{1}{2}}.$

Thus the Lipschitz constant is $L=\frac{2t}{\sqrt{\mathcal{S}}}$. Knowing the
value of $L$ we use Fact 4 and obtain the result. ∎

######  Theorem 20.

Let $\mathcal{S}\subset SU(d)$ be a Haar random gate-set. Then

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}},\lambda)\geq\mathbb{E}\delta(\nu_{\mathcal{S}},\lambda)+\alpha\right)\leq\exp\left({\frac{-d\mathcal{S}\alpha^{2}}{2\pi^{2}\|\lambda\|_{1}^{2}}}\right).$

###### Proof.

Let $\mathcal{S}\subset SU(d)$ be any set of cardinality $n>1$. For the
convenience we denote by $\mathcal{S}_{1}=\\{U_{1},\ldots,U_{n}\\}$, and
$\mathcal{S}_{2}=\\{V_{1},\ldots,V_{n}\\}$ two exemplary sets $\mathcal{S}$.
Let

$\displaystyle F(U_{1},\ldots,U_{n})=\|T_{\nu_{\mathcal{S}_{1}},\lambda}\|.$

We need to show that there is a constant $L$ such that for any
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ we have

$\displaystyle|F(U_{1},\ldots,U_{n})-F(V_{1},\ldots,V_{n})|\leq
L\left(\sum_{i=1}^{n}\|U_{i}-V_{i}\|^{2}_{F}\right)^{\frac{1}{2}}.$

In order to determine the value of $L$ we go through the following chain of
inequalities

$\displaystyle\left|\|T_{\nu_{\mathcal{S}_{1}},\lambda}\|-\|T_{\nu_{\mathcal{S}_{2}},\lambda}\|\right|\leq\frac{1}{n}\sum_{i=1}^{n}\|\pi_{\lambda}({U_{i}})-\pi_{\lambda}({V_{i}})\|\leq$
$\displaystyle\leq\frac{\pi\|\lambda\|_{1}}{2n}\sum_{i=1}^{n}\|U_{i}-V_{i}\|\leq\frac{\pi\|\lambda\|_{1}}{2\sqrt{n}}\left(\sum_{i=1}^{n}\|U_{i}-V_{i}\|^{2}_{F}\right)^{\frac{1}{2}},$

where in the second inequality we used Lemma 9. Thus the Lipschitz constant is
$L=\frac{\pi\|\lambda\|_{1}}{2\sqrt{\mathcal{S}}}$. Knowing the value of $L$
we use Fact 4 and obtain the result. ∎

####  5.3.1 $d$-mode beamsplitters built from random $2$-mode beamsplitters

In this section we consider the Hilbert space
$\mathcal{H}=\mathcal{H}_{1}\oplus\ldots\oplus\mathcal{H}_{d}$, where
$\mathcal{H}_{k}\simeq\mathbb{C}$, $d>2$. We will call spaces
$\mathcal{H}_{k}$ modes. For a matrix $B\in SU(2)$, which we call a $2$-mode
beamsplitter, we define matrices $B^{ij}$, $i\neq j$, to be the matrices that
act on a $2$-dimensional subspace
$\mathcal{H}_{i}\oplus\mathcal{H}_{j}\subset\mathcal{H}$ as $B$ and on the
other components of $\mathcal{H}$ as the identity. This way a matrix $B\in
SU(2)$ gives $d(d-1)$ matrices in $SU(d)$. Applying this procedure to a Haar
random gate-set set $S\subset SU(2)$ we obtain random gate-set $S^{d}$ (see
[26, 27]). We are interested in efficiency of $\mathcal{S}^{d}$.

######  Theorem 21.

Let $\mathcal{S}\subset SU(2)$ be a Haar random gate-set and
$\mathcal{S}^{d}\subset SU(d)$ the corresponding $d$-mode gate-set. Then

$\displaystyle\mathbb{P}\left(\delta(\nu_{\mathcal{S}^{d}},t)\geq\mathbb{E}\delta(\nu_{\mathcal{S}^{d}},t)+\alpha\right)\leq\exp\left({\frac{-\mathcal{S}\alpha^{2}}{16t^{2}}}\right).$

###### Proof.

Let $\mathcal{S}_{1},\mathcal{S}_{2}\subset SU(2)$ be two gate-sets of the
same size $n$, i.e. $\mathcal{S}_{1}=\\{U_{1},\ldots,U_{n}\\}$, and
$\mathcal{S}_{2}=\\{V_{1},\ldots,V_{n}\\}$. We denote by
$\mathcal{S}_{1}^{d}$, and $\mathcal{S}_{2}^{d}$ the corresponding $d$-mode
gate-sets

$\displaystyle\mathcal{S}_{1}^{d}=\\{U_{k}^{i,j}|k\in\\{1,\ldots,n\\},\,i,j\in\\{1,\ldots,d\\}\,,i\,\neq
j\\},$
$\displaystyle\mathcal{S}_{2}^{d}=\\{V_{k}^{i,j}|k\in\\{1,\ldots,n\\},\,i,j\in\\{1,\ldots,d\\}\,,\,i\neq
j\\}.$

Similarly as in the proofs of Theorems 19 and 20 we calculate,

$\displaystyle\left|\|T_{\nu_{\mathcal{S}_{1}^{d}},t}-T_{\mu,t}\|-\|T_{\nu_{\mathcal{S}_{2}^{d}},t}-T_{\mu,t}\|\right|\leq\|T_{\nu_{\mathcal{S}_{1}^{d}},t}-T_{\nu_{\mathcal{S}_{2}^{d}},t}\|\leq$
$\displaystyle\leq\frac{1}{d(d-1)}\sum_{1\leq i\neq j\leq
d}\frac{1}{n}\sum_{k=1}^{n}\|(U_{k}^{i,j})^{t,t}-(V_{k}^{i,j})^{t,t}\|\leq\frac{1}{d(d-1)}\sum_{1\leq
i\neq j\leq d}\frac{2t}{n}\sum_{k=1}^{n}\|U_{k}-V_{k}\|_{F}\leq$
$\displaystyle\frac{1}{d(d-1)}\sum_{1\leq i\neq j\leq
d}\frac{2t}{\sqrt{n}}\left(\sum_{k=1}^{n}\|U_{k}-V_{k}\|^{2}_{F}\right)^{\frac{1}{2}}=\frac{2t}{\sqrt{n}}\left(\sum_{k=1}^{n}\|U_{k}-V_{k}\|^{2}_{F}\right)^{\frac{1}{2}}.$

Thus the Lipschitz constant is $L=\frac{2t}{\sqrt{\mathcal{S}}}$. Knowing the
value of $L$ we use Fact 4 and obtain the result. ∎

As a conclusion we see that a Haar random gate-set $\mathcal{S}\subset SU(2)$
gives the gate-set $S^{d}\subset SU(d)$ for which
$\delta(\nu_{\mathcal{S}^{d}},t)$ has the same concentration rate around the
mean as a Haar random gate-set $\mathcal{S}^{\prime}\subset SU(d)$ of size:

$\displaystyle\mathcal{S}^{\prime}=\frac{2\mathcal{S}}{d}.$

We note, however, that using this approach one cannot say anything about the
relationship between $\mathbb{E}\delta(\nu_{\mathcal{S}^{d}},t)$ and
$\mathbb{E}\delta(\nu_{\mathcal{S}^{\prime}},t)$.

##  6 Comparison of bounds

In this section we use numerical results to compare derived bounds for various
values of $t$ (Fig. 1), $d$ (Fig. 2) and $\mathcal{S}$ (Fig. 3). Throughout
this section we will use the following convention:

  * •

Bounds using Theorem 11 will be called Bernstein bounds and symmetric
Bernstein bounds. They will be plotted with a dashed yellow line and a solid
yellow line respectively.

  * •

Bounds using Theorem 12 will be called master bounds and they will be plotted
with a dashed blue line.

  * •

Bounds using Theorem 17 will be called symmetric master bounds and they will
be plotted with a solid blue line.

  * •

Bounds using Theorem 18 will be called simplified symmetric master bound and
they will be plotted with solid orange line with crosses.

Figure 1: Upper bounds on $\mathbb{P}(\|T_{\nu_{\mathcal{S}},t}\|\geq\delta)$
for $d=2$, $\mathcal{S}=50$ or in symmetric case $\mathcal{S}=2\times 50$ and
different $t$: top - $5$, middle - $50$, bottom - $500$. Master - dashed blue,
symmetric master - solid blue, simplified symmetric master - solid orange with
x-markers, Bernstein - dashed yellow and symmetric Bernstein - solid yellow.
Figure 2: Upper bounds on $\mathbb{P}(\|T_{\nu_{\mathcal{S}},t}\|\geq\delta)$
for $t=5$, $\mathcal{S}=50$ or in symmetric case $\mathcal{S}=2\times 50$ and
different $d$: top - $2$, middle - $4$, bottom - $8$. Master - dashed blue,
symmetric master - solid blue, simplified symmetric master - solid orange with
x-markers, Bernstein - dashed yellow and symmetric Bernstein - solid yellow.
Figure 3: Upper bounds on $\mathbb{P}(\|T_{\nu_{\mathcal{S}},t}\|\geq\delta)$
for $d=2$, $t=2$ and different $\mathcal{S}$: top - $5$, middle - $50$, bottom
- $500$ or in symmetric case $\mathcal{S}$: top - $2\times 5$, middle -
$2\times 50$, bottom - $2\times 500$. Master - dashed blue, symmetric master -
solid blue, simplified symmetric master - solid orange with x-markers,
Bernstein - dashed yellow and symmetric Bernstein - solid yellow. Black
vertical lines indicate the value of $\delta_{opt}(\mathcal{S})$.

First conclusion from Figures 1, 2 and 3 is that the master bound is the
tightest both in Haar random and in symmetric Haar random case. Its lead over
the Bernstein bound gets more pronounced with bigger $t$ and $d$ and small
$\mathcal{S}$. Next note that simplified symmetric master bound is almost
identical with symmetric master bound what implies that our guess in
derivation of Theorem 18 was very close to optimal, even for small $t$. This
can be explained by the fact that the functions under the infimum from (28)
have the derivatives very close to zero in a quite wide interval near the
minimum (see Fig. 4). Thus the range of close to optimal guesses for infimum
is quite wide as well.

Figure 4: Functions under the infimum from Eq. (28) for $\mathcal{S}=30$ and
$\delta=0.5$.

We also analyze what is (according to our bounds) the gain of adding inverses
to Haar random gate-sets i.e. by making them symmetric. Figures 1, 2 and 3
indicate that bounds for set with inverses are tighter but the difference
decreases with growing $\mathcal{S}$.

Next we check what are minimal sizes of $\mathcal{S}$ required to obtain
$\delta$-approximate $t$-design, with probability at least $P$ according to
the master bound. For Haar random gate-sets the formula can be easily obtained
from Theorem 1 and reads:

$\displaystyle\mathcal{S}\geq\frac{2\left(\log\left(2\sum_{\lambda\in\tilde{\Lambda}_{t}}d_{\lambda}\right)-\log\left(1-P\right)\right)}{\log\left(\left(1+\delta\right)^{1+\delta}\left(1-\delta\right)^{1-\delta}\right)}.$
(33)

For symmetric Haar random gate-sets, however, it is much more difficult to
obtain analogous formula using Theorem 2. Nevertheless the numerical
calculations of Table 2 suggest that the required number of gates is around
half of (33) plus inverses.

For $d=2^{n}$ and $t=2$, $P=0.99$, $\delta=0.01$, it is interesting to compare
the number of gates given by (33) with the number of elements of the $n$-qubit
Clifford group, $\mathcal{C}_{n}$, which is know to be an exact $2$-design.
Using Lemma 8 one easily checks that for $t=2$ and $d\geq 4$ the set
$\tilde{\Lambda}_{2}$ has exactly $p(2)^{2}+p(1)^{2}=5$ distinct $\lambda$’s.
They are given by

$\displaystyle\lambda_{1}=(1,0,\ldots,0,-1),\,\|\lambda_{1}\|_{1}=2,\,d_{\lambda_{1}}=d^{2}-1,$
$\displaystyle\lambda_{2}=(2,0,\ldots,0,-2),\,\|\lambda_{2}\|_{1}=4,\,d_{\lambda_{2}}=\frac{d^{2}(d-1)(d+3)}{4},$
$\displaystyle\lambda_{3}=(2,0,\ldots,0,-1,-1),\,\|\lambda_{3}\|_{1}=4,\,d_{\lambda_{3}}=\frac{(d^{2}-1)(d^{2}-4)}{4},$
$\displaystyle\lambda_{4}=(1,1,0,\ldots,0,-1,-1),\,\|\lambda_{4}\|_{1}=4,\,d_{\lambda_{4}}=\frac{d^{2}(d-3)(d+1)}{4},$
$\displaystyle\lambda_{5}=(1,1,0,\ldots,0,-2),\,\|\lambda_{5}\|_{1}=4,\,d_{\lambda_{5}}=\frac{(d^{2}-1)(d^{2}-4)}{4}.$

Thus $\sum_{\lambda\in\tilde{\Lambda}_{2}}d_{\lambda}=d^{4}-3d^{2}+1$. Using
these results we find that Haar random gate-set $\mathcal{S}_{n}\subset
SU(2^{n})$, $n\geq 2$, with

$\displaystyle\mathcal{S}_{n}\geq\left\lceil 2\cdot
10^{4}\left(\log\left(2^{4n+1}-3\cdot
2^{2n+1}+2\right)+4.61\right)\right\rceil.$

forms $0.01$-approximate $2$-design with the probability $P=0.99$. On the
other hand the cardinality of $\mathcal{C}_{n}$ is given by [11]

$\displaystyle|\mathcal{C}_{n}|=2^{n^{2}+2n}\prod_{j=1}^{n}\left(4^{j}-1\right).$

Figure 5 shows $\frac{|\mathcal{C}_{n}|}{\mathcal{S}_{n}}$ for up to $50$
qubits. The ratio $\frac{|\mathcal{C}_{n}|}{\mathcal{S}_{n}}$ grows at least
exponentially with $n$.

Figure 5: Ratio $\frac{|\mathcal{C}_{n}|}{\mathcal{S}_{n}}$ for up to $50$
qubits

In fact, one can easily see, that
$\sum_{\lambda\in\tilde{\Lambda}_{t}}d_{\lambda}\leq d^{2t}$. Thus (33) grows
in a logarithmic way with $d$ and linearly with $t$ and Haar random gate-set
$\mathcal{S}$ with

$\displaystyle\mathcal{S}\geq\frac{2\left(2t\log\left(d\right)+\log(2)-\log\left(1-P\right)\right)}{\log\left(\left(1+\delta\right)^{1+\delta}\left(1-\delta\right)^{1-\delta}\right)},$

forms $\delta$-approximate $t$-design with the probability $P$. Moreover, for
a small $\delta$ we can further reduce this formula using
$\log\left(\left(1+\delta\right)^{1+\delta}\left(1-\delta\right)^{1-\delta}\right)\simeq\delta^{2}$.
Thus we get that $S$ scales like $O(\delta^{-2}(t\log(d)-\log(1-P)))$.

We also note that if $\nu_{\mathcal{S}}$ is a $\delta$-approximate $t$-design
with probability bounded by $1-\epsilon$. Then $\nu_{\mathcal{S}}^{\ast l}$,
whose support are all circuits of depth $l$ built from gates form
$\mathcal{S}$, is $\delta^{l}$-approximate $t$-design with probability bounded
by $1-\epsilon$. Thus one can construct first $1/2$-approximate $t$-design and
then by building all possible circuits of length $l$ change it to
$1/2^{l}$-approximate $t$-design. Table 2) present numerical calculations for
various $t$ and $d$.

t | $2$ | $3$ | $4$ | $5$ | $20$ | $500$ | $5000$
---|---|---|---|---|---|---|---
$d=2$ | Master | $\mathcal{S}$ | $57$ | $62$ | $65$ | $68$ | $88$ | $136$ | $171$
$\mathcal{S}$-symmetric | $2\times 36$ | $2\times 37$ | $2\times 39$ | $2\times 40$ | $2\times 46$ | $2\times 67$ | $2\times 84$
Bernstein | $\mathcal{S}$ | $69$ | $75$ | $80$ | $83$ | $107$ | $166$ | $209$
$\mathcal{S}$-symmetric | $2\times 47$ | $2\times 50$ | $2\times 52$ | $2\times 53$ | $2\times 64$ | $2\times 95$ | $2\times 120$
$d=4$ | Master | $\mathcal{S}$ | $82$ | $96$ | $108$ | $118$ | $195$ |  |
$\mathcal{S}$-symmetric | $2\times 41$ | $2\times 47$ | $2\times 53$ | $2\times 58$ | $2\times 95$ |  |
Bernstein | $\mathcal{S}$ | $100$ | $117$ | $132$ | $144$ | $238$ |  |
$\mathcal{S}$-symmetric | $2\times 58$ | $2\times 67$ | $2\times 76$ | $2\times 82$ | $2\times 136$ |  |
$d=8$ | Master | $\mathcal{S}$ | $104$ | $129$ | $154$ | $175$ |  |  |
$\mathcal{S}$-symmetric | $2\times 51$ | $2\times 63$ | $2\times 75$ | $2\times 85$ |  |  |
Bernstein | $\mathcal{S}$ | $127$ | $158$ | $187$ | $213$ |  |  |
$\mathcal{S}$-symmetric | $2\times 73$ | $2\times 90$ | $2\times 107$ | $2\times 122$ |  |  |
$d=16$ | Master | $\mathcal{S}$ | $126$ | $162$ | $197$ | $229$ |  |  |
Bernstein | $\mathcal{S}$ | $153$ | $197$ | $240$ | $280$ |  |  |
$\mathcal{S}$-symmetric | $2\times 88$ | $2\times 113$ | $2\times 137$ | $2\times 160$ |  |  |
$d=32$ | Master | $\mathcal{S}$ | $147$ | $194$ | $239$ | $282$ |  |  |
Bernstein | $\mathcal{S}$ | $179$ | $236$ | $292$ | $345$ |  |  |
$\mathcal{S}$-symmetric | $2\times 103$ | $2\times 135$ | $2\times 167$ | $2\times 197$ |  |  |
$d=64$ | Master | $\mathcal{S}$ | $168$ | $226$ | $282$ | $336$ |  |  |
Bernstein | $\mathcal{S}$ | $205$ | $275$ | $344$ | $410$ |  |  |
$\mathcal{S}$-symmetric | $2\times 117$ | $2\times 158$ | $2\times 197$ | $2\times 234$ |  |  |
Table 2: Minimal sizes of Haar random gate-sets $\mathcal{S}$ required to
obtain $\frac{1}{2}$-approximate $t$-design with probability at least $0.99$.

## 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] A.. Fowler, M. Mariantoni, J.. Martinis and A.. Cleland  “Surface codes: Towards practical large-scale quantum computation”  In _Phys. Rev. A_ 86, 2012, pp. 032324  DOI: 10.1103/PhysRevA.86.032324
  * [2] J. Preskill  “Quantum Computing in the NISQ era and beyond”  In _Quantum_ 2, 2018, pp. 79  DOI: 10.22331/q-2018-08-06-79
  * [3] S. Boixo et al.  “Characterizing Quantum Supremacy in Near-Term Devices”  In _Nature Physics_ 14, 2018, pp. 595–600  DOI: 10.1038/s41567-018-0124-x
  * [4] A.. Harrow and A. Montanaro  “Quantum Computational Supremacy”  In _Nature_ 549, 2017, pp. 203–209  DOI: 10.1038/nature23458
  * [5] C.. Ballance et al.  “High-fidelity quantum logic gates using trapped-ion hyperfine qubits”  In _Phys. Rev. Lett._ 117, 2016, pp. 060504  DOI: ¯10.1103/PhysRevLett.117.060504
  * [6] R. Barends et al.  “Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing”  In _Nature 508_ , 2014, pp. 500–503  DOI: 10.1038/nature13171
  * [7] L. Susskind  “Three Lectures on Complexity and Black Holes”  In _arXiv:1810.11563_ , 2018  URL: https://arxiv.org/abs/1810.11563
  * [8] A. Sawicki and K. Karnas  “Criteria for universality of quantum gates”  In _Physical Review A_ 95 American Physical Society (APS), 2017, pp. 062303  DOI: 10.1103/physreva.95.062303
  * [9] A. Sawicki and K. Karnas  “Universality of Single-Qudit Gates”  In _Annales Henri Poincaré_ 18, 2017, pp. 3515–3552
  * [10] A. Sawicki, L. Mattioli and Z. Zimborás  “How to check universality of quantum gates?”  In _arXiv:2111.03862_ , 2021
  * [11] M.. Nielsen and I.. Chuang  “Quantum Computation and Quantum Information: 10th Anniversary Edition”  Cambridge University Press, 2010  DOI: 10.1017/CBO9780511976667
  * [12] A.. Harrow, B. Recht and Isaac L. Chuang  “Efficient Discrete Approximations of Quantum Gates”  In _J. Math. Phys._ 43, 2002, pp. 4445  DOI: 10.1063/1.1495899
  * [13] M. Oszmaniec, A. Sawicki and M. Horodecki  “Epsilon-Nets, Unitary Designs, and Random Quantum Circuits”  In _IEEE Transactions on Information Theory_ 68, 2022, pp. 989–1015
  * [14] 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
  * [15] J Bourgain and Alex Gamburd  “On the spectral gap for finitely-generated subgroups of SU(2).”  In _Invent. math._ 171, 2008, pp. 83–121  DOI: 10.1007/s00222-007-0072-z
  * [16] A. Bocharov, Y. Gurevich and K.. Svore  “Efficient decomposition of single-qubit gates into V basis circuits”  In _Phys. Rev. A_ 88 American Physical Society (APS), 2013, pp. 012313  DOI: 10.1103/physreva.88.012313
  * [17] V. Kliuchnikov, A. Bocharov, M. Roetteler and J. Yard  “A Framework for Approximating Qubit Unitaries”  In _arXiv:1510.03888_ , 2015  URL: https://arxiv.org/abs/1510.03888
  * [18] V. Kliuchnikov, D. Maslov and M. Mosca  “Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates”  In _Quantum Information and Computation_ 13 (7-8), 2013, pp. 607–630
  * [19] P. Selinger  “Efficient Clifford+T approximation of single-qubit operators”  In _Quantum Information and Computation_ 15, 2015, pp. 159–180
  * [20] P. Sarnak  “Letter to Scott Aaronson and Andy Pollington on the Solovay-Kitaev theorem”, 2015
  * [21] 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
  * [22] P.. Varjú  “Random walks in compact groups”  In _Doc. Math._ 18, 2013, pp. 1137–1175
  * [23] J.. Tropp  “An Introduction to Matrix Concentration Inequalities”, Foundations and Trends in Machine Learning  Now Publishers Inc, 2015  URL: https://arxiv.org/abs/1501.01571
  * [24] M. Abu-Hamed and S. Gelaki  “Frobenius-Schur indicators for semisimple Lie algebras”  In _Journal of Algebra_ 315(1), 2007, pp. 178–191  DOI: 10.1016/j.jalgebra.2007.06.003
  * [25] E.. Meckes  “The Random Matrix Theory of the Classical Compact Groups”, Cambridge Tracts in Mathematics  Cambridge University Press, 2019  DOI: 10.1017/9781108303453
  * [26] M. Reck, A. Zeilinger, H.. Bernstein and P. Bertani  “Experimental realization of any discrete unitary operator”  In _Phys. Rev. Lett._ 73 American Physical Society, 1994, pp. 58–61  DOI: 10.1103/PhysRevLett.73.58
  * [27] A. Sawicki  “Universality of beamsplitters”  In _Quantum Information and Computation_ 16, 3 and 4, 2016, pp. 291–312
  * [28] E.. Lieb  “Convex trace functions and the Wigner-Yanase-Dyson conjecture”  In _Advances in Mathematics_ 11 (3), 1973, pp. 267–288
  * [29] S. Golden  “Lower Bounds for the Helmholtz Function”  In _Phys. Rev._ 137 (4B), 1965, pp. B1127–B1128
  * [30] C.. Thompson  “Inequality with Applications in Statistical Mechanics”  In _J. Math. Phys._ 6 (11), 1965, pp. 1812–1813
  * [31] B.. Hall  “Lie Groups Lie Algebras and Representations An Elementary Introduction”, Graduate Texts in Mathematics  Springer-Verlag New York, 2004
  * [32] 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
  * [33] 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
  * [34] D. Ruiz-Antolin and J. Segura  “A new type of sharp bounds for ratios of modified Bessel functions”  In _J. Math. Anal. Appl._ 443, 2016, pp. 1232–1246