# Cavities with Non-Spherical Mirrors for Enhanced Quantum Emitter-Cavity
Photon Interaction

Denis V. Karpov  Optoelectronics Research Centre, University of Southampton,
Southampton SO17 1BJ, United Kingdom  Peter Horak  Optoelectronics Research
Centre, University of Southampton, Southampton SO17 1BJ, United Kingdom
<EMAIL_ADDRESS>
(October 2021)

###### Abstract

We propose a procedure for the significant enhancement of the strong coupling
rate between photons in an optical cavity and a single quantum emitter, such
as an atom, quantum dot or trapped ion. We show that specially designed, non-
spherical mirrors can lead to cavity eigenmodes that exhibit a large field
enhancement at the center of the cavity while inducing significantly less beam
divergence, and therefore smaller round trip losses and higher cooperativity,
than can be achieved by operating a spherical-mirror cavity in the near-
concentric regime. We verify our designs using mode matching theory and
discuss their robustness relative to different kinds of manufacturing
deviations.

##  I Introduction

For various applications of modern quantum optics, both in experimental
academic research and commercial quantum technology, strong coupling of a
quantum emitter with an optical resonator is required, and simultaneously a
long photon lifetime in this resonator is critically important. Some of the
most promising systems to meet these requirements for practical applications
are fiber-optic microcavities [1, 2, 3, 4], ion beam etched dielectric
resonators [5], or micro-assembled structures [6].

Strong coupling of a quantum emitter to an optical cavity for quantum
technology applications can be achieved by tightly localising a single cavity
photon, i.e., by making the cavity very small. However, for most realistic
quantum information processing schemes optical access to the emitter from the
side is required, e.g., for optical cooling [7], state preparation, and final
state readout [8]. Moreover, channels for the delivery of atoms or ions into
the cavity and the integration of trapping structures into the cavity may
impose further constraints on the cavity length. In the case of ion-trap
quantum computing [9], the dielectric mirrors forming the cavity can also
distort the radio-frequency fields required for trapping the ion due to their
electric susceptibility and due to surface charges if they are too close to
the trap electrodes [10, 11].

Overall, there is thus a need for optical cavities used in quantum information
applications to combine a strong coupling rate with low losses, while at the
same time also keeping the mirrors sufficiently apart. The goal of our work
here is to present a new method to achieve these requirements by moving away
from the paradigm of spherical mirrors to engineer optical cavity modes with
better confinement properties than the standard Gaussian modes.

Let us first review the principal parameters to characterize optical
resonators for strong coupling to single particles. The coherent coupling
between a two-level quantum emitter, such as a quantum dot, ion or cold atom,
located at a coordinate r in an cavity with an optical field mode
$E(\textbf{r})$ is characterized by the single-photon strong coupling rate or
coupling strength [12]

$g_{0}(\textbf{r})=\sqrt{\frac{3\lambda^{2}c\Gamma}{4\pi
V_{\psi}}}\psi(\textbf{r}),\
\psi(\textbf{r})=\frac{E(\textbf{r})}{|E(\textbf{r}_{m})|}$ (1)

where $\Gamma$, $\lambda$, $L$ are the spontaneous dipole decay rate of the
emitter $\Gamma=\frac{\omega^{3}\mu^{2}}{3\pi\varepsilon_{0}\hbar c^{3}}$
(where $\omega$ is the transition angular frequency and $\mu$ is the electric
dipole moment), its transition wavelength, and the cavity length,
respectively. $V_{\psi}$ is the mode volume which we define as

$V_{\psi}=\frac{1}{|E(\textbf{r}_{m})|^{2}}\int|E(\textbf{r})|^{2}dV=\int|\psi(\textbf{r})|^{2}dV$
(2)

where $\textbf{r}_{m}$ is the position of the maximum electric field in the
cavity and the integration goes over the entire cavity volume. For a cavity
mode with an emitter located at the maximum field intensity point
$\textbf{r}_{m}$ the strong coupling rate is
$g_{0}(\textbf{r}_{m})=\sqrt{\frac{3\lambda^{2}c\Gamma}{4\pi V_{\psi}}}$.

To achieve strong emitter-cavity coupling, the coherent coupling rate $g_{0}$
between the emitter and the cavity mode must be larger than the strength of
competing incoherent processes, i.e., larger than the dipole decay rate
$\Gamma$ and the cavity loss rate $\kappa$. Therefore, the cooperativity
parameter defined as

$C_{0}=\frac{g_{0}^{2}}{\kappa\Gamma}=\frac{3\lambda^{2}c}{4\pi\kappa
V_{\psi}}$ (3)

must be larger than one.

We see from Eq. (3) that the cooperativity can be increased by decreasing the
mode volume. However, as discussed above, the cavity length $L$ must be
sufficiently large to allow for optical side access and constraints imposed by
atom/ion delivery and trapping. Therefore, if we write the mode volume as
$V_{\psi}=LA_{\psi}$, reducing the mode volume can only be achieved by
reducing the mode cross section $A_{\psi}$ (at the position of the particle).
The common approach for this is to operate the cavity in a near-concentric
regime [13] where, in paraxial approximation, the mode cross section can be
made arbitrarily small. On the other hand, this cavity configuration leads to
excessive mode divergence and therefore to increased cavity losses $\kappa$
because large fractions of the mode fields miss the resonator mirrors, which
eventually reduces the cooperativity again according to Eq. (3). Furthermore,
concentricity leads to cavity instability [13] and thus makes cavity
performance sensitive to smallest alignment errors.

Here we propose another method to increase the field amplitude in the center
of the cavity $\psi(0)$, and thus to enhance cooperativity: by modifying the
shape of the cavity mirrors we generate optimized interference patterns in the
mode field. We explore modulated spherical mirror profiles that give rise to
highly localized cavity modes while at the same time providing cavity loss
rates far below those obtained with near-concentric cavities with comparable
field localization for a wide range of parameters.

This paper is organized as follows. First, in Sec. II, we describe our
theoretical model and compare the enhancement of the strong coupling rate,
mode losses, and cooperativity of target mode superpositions compared to near-
concentric cavities. In Sec. III we discuss how to design non-spherical
mirrors to generate cavity eigenmodes that consist of such mode superpositions
and we verify those designs with a-priory simulations. We also investigate the
stability of our designs against fabrication errors and briefly discuss
potential fabrication methods. Finally we summarize and conclude in Sec. IV.

##  II Cavity Field Enhancement by Mode Superpositions

###  II.1 Mode Matching Theory

We start our investigation by introducing the formalism used later in the
paper to calculate the eigenmodes of an optical cavity with arbitrarily shaped
mirrors, following the approach of Refs. [14, 15].

We write the optical mode fields $\Psi(\textbf{r})$ as a superposition of a
given set of basis modes $\\{\psi_{n}(\textbf{r})\\}$,

$\Psi(\textbf{r})=\sum_{n}T_{n}\psi_{n}(\textbf{r}).$ (4)

We will consider only linearly polarized modes and thus the optical field can
be described by a scalar field $\Psi(\textbf{r})$. For simplicity we also
assume cylindrical symmetry of the cavity and thus restrict our model to
radially symmetric basis modes. For mirror shapes that are modifications of
standard spherical profiles, it is thus convenient to use the well-known
Laguerre-Gaussian (LG) modes of symmetric, spherical-mirror cavities as the
basis modes in our model. The basis mode functions are thus defined as

$\displaystyle\psi_{n}^{\pm}(\rho,\zeta)$ $\displaystyle=$
$\displaystyle\sqrt{\frac{2}{\pi}}L_{n}(2\rho^{2})\times$ (5)
$\displaystyle\exp{\\{-\rho^{2}\pm i(-\zeta\rho^{2}+(2n+1)\tan^{-1}\zeta)}\\}$

where $\rho=r/w(\zeta)$ and $\zeta=z/z_{0}$ are the dimensionless radial and
axial coordinates, $w(\zeta)=w_{0}\sqrt{1+\zeta^{2}}$ is the basis mode
radius, $w_{0}$ is the mode waist of the fundamental mode,
$z_{0}=kw_{0}^{2}/2$ is the Rayleigh length, $k=2\pi/\lambda$ is the wave
number, $L_{n}$ are Laguerre polynomials and $n$ is the mode order. The index
$\pm$ marks the propagation direction.

The change of an optical field undergoing one round trip through the cavity
can be represented by a mode-mixing operator $M$. Then finding the cavity
eigenmodes reduces to solving the eigenproblem [16, 14]

$M\Psi=\gamma\Psi$ (6)

where the eigenvectors are the cavity modes expressed as superpositions of the
basis LG modes and the eigenvalues $\gamma$ define the field amplitude changes
of the corresponding modes acquired per round trip. The fractional loss per
round trip $D$ for the mode $\Psi$ is given by

$D=1-|\gamma|^{2}.$ (7)

The mode-mixing matrix of the cavity is given by

$M=\exp{\\{2ikL}\\}AB,$ (8)

where the exponential represents the longitudinal phase shift acquired over
one cavity round trip, i.e., by propagation through twice the cavity length.
The matrices $A$ and $B$ represent the left and right-side mirrors of the
cavity positioned at coordinates $z=-L/2$ and $+L/2$, respectively, and are
given by the mode overlap integrals taken over the finite extent of the
mirrors,

$\displaystyle A_{n,m}$ $\displaystyle=$
$\displaystyle\int_{0}^{\rho_{a}}\psi_{n}^{+}\psi_{m}^{-*}\exp{\\{-2ik\Delta(\rho)\\}}\,2\pi\rho\,d\rho\Bigr{|}_{\begin{subarray}{c}\zeta=-\zeta_{m}\end{subarray}},$
(9) $\displaystyle B_{n,m}$ $\displaystyle=$
$\displaystyle\int_{0}^{\rho_{a}}\psi_{n}^{-}\psi_{m}^{+*}\exp{\\{+2ik\Delta(\rho)\\}}\,2\pi\rho\,d\rho\Bigr{|}_{\begin{subarray}{c}\zeta=\zeta_{m}\end{subarray}},$
(10)

where $\rho_{a}=R_{a}/w(\zeta_{m})$ with the mirror radius $R_{a}$ and the
axial mirror position $\zeta_{m}=\frac{L}{2z_{0}}$. $\Delta(r)$ describes the
deviation of the mirror profile from a plane surface.

The calculation of the cavity modes consists of the following steps. As we are
interested in cavity mirrors that are close in shape to a spherical profile,
we first define a mirror radius of curvature $R$ and a cavity length $L$. We
then calculate the waist $w_{0}$ of the fundamental mode of this spherical-
mirror cavity and use this to define the fundamental and higher order modes
$\psi_{n}^{\pm}$, Eq. (5). The overlap integrals, Eqs. (9)-(10) are then
calculated numerically in Matlab for the modified mirror shapes discussed
later in Section III. Finally, the full matrix $M$ and its eigenvalues and
eigenvectors are calculated. We normalize the eigenvectors $\Psi$ to have the
same mode volume $V_{\Psi}$ as the LG modes $V_{\psi}$ (note that all LG modes
have the same mode volume),

$V_{\Psi}=V_{\psi}=\frac{\pi}{4}w_{0}^{2}L$ (11)

where the last equality is evaluated from the mode definitions (5). In this
case the coherent coupling rate for $\Psi$ has the same form as Eq. (1), i.e.,

$g(\textbf{r})=\sqrt{\frac{3\lambda^{2}c\Gamma}{4\pi
V_{\psi}}}\Psi(\textbf{r}).$ (12)

The eigenvectors of matrix $M$ contain the mode composition coefficients
$T_{n}$ and thus the field profile of any cavity eigenmode at any point in the
cavity can be found using Eq. (4). The corresponding cavity loss is obtained
from the eigenvalue as per Eq. (7).

###  II.2 Comparison of Mode Superpositions and Concentric Cavities

Figure 1: Schematic representation of 1) a spherical-mirror cavity and 2) a
cavity with modified mirror shape obtained by our formalism. In case 1) the
fundamental mode of the cavity is a fundamental Gaussian mode, in case 2) it
is a superposition of the fundamental and of higher order modes. In both cases
the cavities are assumed to be coupled to optical fibres at the mirror
outputs.

We are interested in comparing two methods to increase the intensity of the
field at the center of the cavity as discussed in the following

1) The “traditional” approach is to operate the cavity in the near concentric
regime and use the fundamental Gaussian mode of the cavity, see top of Fig. 1.
In this case the strong coupling rate scales as $g_{0}\sim 1/w_{0}$ where
$w_{0}$ is the waist at the center. The mode spot size on the mirrors (in the
far field where $L/2$ is much larger than the Rayleigh length) scales with
$1/w_{0}$ [13]. So the spot size on the mirrors increases proportional to
$g_{0}$. Once the spot size reaches the finite radius of the cavity mirrors,
the majority of the light field misses the mirror, leading to clipping losses
that increase exponentially with the spot size and thus with $g_{0}$. Thus,
setting the cavity close to concentric maximizes the cavity field in the
center, but rapidly increases the clipping loss and therefore strongly reduces
the cooperativity.

2) The alternative method we are investigating here is using a superposition
of higher order LG modes, see bottom of Fig. 1. Let us assume that we can
shape the mirrors in such a way that the cavity supports an eigenmode that is
an equal superposition of the first $N$ LG modes (we will discuss in Section
III how this can be achieved). Hence, the eigenmode takes the form

$\Psi(\rho,\zeta)=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}\psi_{n}^{+}(\rho,\zeta)$
(13)

for the right-propagating field, and analogously for the left-propagating
field. Note that the mode is normalized to maintain the mode volume of a
single LG mode. For this mode, the strong coupling rate $g(0)$ at the center,
Eq. (12), scales with $\sqrt{N}$ because for all Laguerre polynomials we have
$L_{n}(0)=1$ in the mode ansatz in Eq. (13). On the other hand, the spot size
of n-th LG mode on the mirror scales as $\sqrt{(2n+1)}$ [18]. Thus, the spot
size of the highest order mode used in the superposition (13) scales as
$\sqrt{N}$ and therefore proportional to $g(0)$. This is the same scaling as
for the concentric approach discussed above, however, in the case considered
here the $N$-th LG mode only carries $1/N$ of the power. It is therefore
expected that for the equal mode superposition (13) the clipping losses due to
the increasing mode spot size on the mirror with increasing strong coupling
rate are smaller than for the near-concentric case.

Figure 2: Clipping loss as a function of coupling rate (local electric field)
enhancement factor. For the near-concentric cavity approach (blue curve) $g$
is enhanced by reducing the mirror radius of curvature towards $L/2$. For the
mode superposition approach (red curve) $g$ is enhanced by increasing the
number of modes in the superposition. Enhancement of $g$ is relative to the
value $g_{0}$ of a reference cavity with $L=500\,\mu$m, $R=255\,\mu$m,
$R_{a}=100~{}\mu$m, $\lambda=0.866~{}\mu$m.

We show a numerical example of the scaling of clipping losses with increased
strong coupling rate in Fig. 2, where the clipping losses are calculated
numerically from evaluating the mode overlap with the mirrors with finite
radius $R_{a}$. Here we start with a reference cavity with cavity length
$L=500\,\mu$m, mirror radius of curvature $R=255\,\mu$m, mirror radius
$R_{a}=100~{}\mu$m, operating at wavelength $\lambda=0.866~{}\mu$m. The strong
coupling rate of this reference cavity at the center is denoted $g_{0}$ and
the clipping losses are below the numerical accuracy in our simulations of
$10^{-9}$ per round trip. For the near-concentric cavity approach, blue curve
in Fig. 2, we then scan the radius of curvature towards $L/2=250\,\mu$m. This
increases the strong coupling rate $g$ at the center but simultaneously
increases the cavity round trip losses. For the mode superposition approach,
red curve in Fig. 2, we increase the number of constituent modes $N$ in Eq.
(13) from 1 to 50. As discussed above, this increases the strong coupling rate
$g$ proportional to $\sqrt{N}$. We can clearly see that the corresponding
increase in losses is significantly below the near-concentric approach - over
a wide range of parameters comparable strong coupling amplification factors
can be achieved with orders of magnitude lower losses.

###  II.3 Coupling Rate Enhancement

In Fig. 2 we considered strong coupling rate enhancement relative to a
specific reference cavity of given mirror radius of curvature. We now
investigate how the enhancement depends on radius of curvature in more detail.

(a)

(b)

Figure 3: (a) Clipping losses as a function of enhancement of strong coupling
rate for different radius of curvature, $L=500~{}\mu m$. (b) Clipping losses
as a function of strong coupling rate of Ca+ ion for different radius of
curvature, $L=500~{}\mu m,\Gamma_{Ca^{+}}=22$ MHz/$2\pi$.

Figure 3(a) shows the enhancement of the strong coupling rate $g/g_{0}$ and
the corresponding increase in clipping losses of the mode superposition
approach for different reference cavities, i.e., cavities with different
mirror radius of curvature. As before, the enhancement in $g/g_{0}$ is
achieved by increasing the number $N$ of modes in the mode superposition. For
near-concentric reference cavities, e.g. for $R=250.1\,\mu$m, only a modest
enhancement in $g$ can be realized before the round trip losses increase
significantly. In this limit, already the fundamental mode has a large spot
size on the mirrors and thus adding more higher order modes to the
superposition will quickly lead to excessive losses. As we move away from the
concentric regime by increasing the mirror radius of curvature, the
fundamental mode spot size on the mirrors decreases and thus more higher order
modes can be added before losses increase substantially.

Note, however, that for increasing radius of curvature $R$ the strong coupling
rate $g_{0}$ of the reference cavity decreases and thus every curve in Figure
3(a) is relative to a different value $g_{0}$. In Figure 3(b) we therefore
plot the data versus $g$ in real units, where we use the parameters for the
$866$-nm transition in Ca+, a species frequently used in ion trap quantum
information experiments [17]. As mentioned above, for a reference cavity very
close to the concentric limit the benefit of using higher-order mode
superpositions is reduced. As the radius of curvature is increased, larger
strong coupling rates become accessible at lower losses. Approaching a more
confocal arrangement we can significantly enhance $g$ and keep losses under
control, which corresponds to the region below the curve for the concentric
cavity (black dashed line) in Figure 3(b). However, we observe that for too
large radii of curvature (300 or 400 $\mu$m in the figure) the achievable
enhancement factor reduces again.

Figure 3(b) shows clearly that there are parameter regions of cavities with
larger strong coupling rate and lower loss that can be achieved with the mode
superposition approach but are not accessible by near-concentric resonators.
Finally, we note, however, that in order to achieve large strong coupling rate
enhancement for cavities with relatively large mirror radius curvature, a very
large number of higher order modes need to be included in the mode
superposition. This may be difficult to realize, as discussed in Section
III.3.

###  II.4 Cooperativity Enhancement

Next we consider the enhancement of the cooperativity using the mode
superposition approach for a more realistic situation which takes into account
intrinsic cavity round trip losses because of light absorption or partial
transmission through the mirrors, which typically are in the range of
$D_{mir}=10^{-5}-10^{-4}$. In this case the total loss rate $\kappa$ relates
to both the loss of the mirrors $D_{mir}$ and the clipping loss per round trip
$D(N)$ which depends on the number of LG modes in representation (13),

$\kappa=\frac{c}{2L}(D(N)+D_{mir}).$ (14)

Using Eqs. (11)-(14), the cooperativity $C$, Eq. (3), then becomes

$C=\frac{6}{\pi^{2}}\left(\frac{\lambda}{w_{0}}\right)^{2}\frac{N}{D(N)+D_{mir}}.$
(15)

We now denote the cooperativity of the fundamental Gaussian mode as $C_{0}$
and assume it has negligible clipping losses, $D(N=1)=0$. The enhancement of
cooperativity by an $N$-mode superposition is finally expressed as

$\frac{C}{C_{0}}=\frac{N}{\frac{D(N)}{D_{mir}}+1}.$ (16)

Figure 4: Cooperativity enhancement as a function of the number of modes $N$
in the superposition (13) for different intrinsic mirror losses $D_{mir}$.
Other parameters are L$=500~{}\mu$m, $R=400~{}\mu$m, $\lambda=0.866~{}\mu$m.

We show this cooperativity enhancement for different values of $D_{mir}$ in
Fig. 4. As long as the clipping losses are smaller than the intrinsic losses,
$D<D_{mir}$, the cooperativity increases linearly with $N$ and is independent
of $D_{mir}$. Thus, a superposition of 100 modes would ideally enhance the
cooperativity by two orders of magnitude. In practice, the region of $N$
between 0 and 10 is the most interesting because it provides a significant
cooperativity enhancement and at the same time does not require too many
modes, which would pose excessive constraints on the fabrication accuracy of
the mirrors.

The cooperativity starts to drop sharply with increasing $N$ when the clipping
losses exceed $D_{mir}$. This happens when the $N$-th order mode spot size on
the mirror [18],

$w_{N}(L/2)=w_{0}\sqrt{2N+1}\sqrt{1+[L/(2z_{0})]^{2}},$ (17)

becomes comparable to the mirror radius $R_{a}$. This allows us to derive an
estimate for a maximum useful number of modes in the superposition,

$N_{\mathrm{cutoff}}\approx 2\left(\frac{\pi w_{0}R_{a}}{\lambda
L}\right)^{2}.$ (18)

This value of $N_{\mathrm{cutoff}}$ thus marks the position of the sharp
cutoff observed in Fig. 4.

##  III Design of Mirror Profiles

In the previous section we showed that certain superpositions of LG modes
exhibit a large field enhancement in the cavity center while maintaining low
cavity loss rates. We will now discuss the shape of the cavity mirrors that
are required to generate such mode superpositions as eigenmodes of an optical
cavity.

###  III.1 Mode Field Phase Fronts

The principle of designing a mirror that will generate a desired
electromagnetic field as an eigenmode of the cavity is as follows. We first
calculate the desired field and analyze its wave fronts in the area of one
mirror; an example is shown in Fig. 5(a). The required mirror shape then needs
to follow a surface of constant phase, as presented by the red curve in the
figure.

For a field composed of a low number of LG modes, $N=3$ in Fig. 5, this mirror
shape still mainly follows a spherical profile. It is thus instructive to plot
the mirror shape as the deviation from the spherical profile, shown in Fig.
5(b). We see that the mirror can effectively be fabricated by manufacturing a
“hole” of a certain shape and a maximum depth of the order of one micron into
the center of a spherical mirror. We will further discuss possible routes to
fabrication and the required manufacturing precision in Sec. III.4 and Sec.
III.3, respectively.

(a)

(b)

Figure 5: Phase of the target field (superposition of $N=3$ LG modes) near one
of the cavity mirrors. The red curve marks a contour of constant phase, which
would be an appropriate mirror profile to generate this field as a cavity
eigenmode. (b) Shape of the required mirror profile as a deviation from a
spherical profile. Parameters are L$=500~{}\mu$m, $R=400~{}\mu$m,
$\lambda=0.866~{}\mu$m.

Note that all calculations in this paper are based on the paraxial
approximation [19], and therefore are only valid for fields with low
divergence angles. Within this approximation a spherical mirror is equivalent
to a parabolic profile. Moreoever, the mode mixing matrices $A$ and $B$, Eqs.
(9)-(10), are calculated in the limit of thin mirrors, i.e., by applying a
phase shift on a plane of constant position $z=L/2$. Numerically, instead of
extracting a contour of constant phase as described above, we calculate the
phase of the target field along $z=L/2$ and use this phase for the terms
$\exp\\{\pm 2ik\Delta(\rho)\\}$ in Eqs. (9)-(10). Within the paraxial and
thin-mirror approximations the two approaches are equivalent.

###  III.2 Verification of Mirror Designs

Having extracted the shape of the mirror from the wave front pattern near
$z=L/2$, as described above, we now use it to verify our mirror design. Using
the formalism presented in Sec. II.1 we calculate the eigenmodes of the cavity
formed by two identical mirrors with the extracted shape and analyze the
clipping losses $D$ of the eigenmodes, Eq. (7), and their coefficients
$|T_{i}|^{2}$ which describe the weight of each LG mode $i$ in each cavity
mode.

(a)

(b)

Figure 6: Eigenmodes of a cavity formed by mirrors designed in Fig. 5 using
mode matching theory. (a) Clipping loss per round trip $D$ for different
eigenmodes sorted by increasing loss. (b) Corresponding coefficients
$|T_{i}|^{2}$. The lowest loss eigenmode has weights 1/3 for the lowest 3 LGs,
confirming the target mode design. Parameters are are L$=500~{}\mu$m,
$R=400~{}\mu$m, $\lambda=0.866~{}\mu$m.

An example for a target mode which contains an equal superposition of $N=3$ LG
modes, Eq. (13), is shown in Fig. 6. Figure (a) shows that the cavity supports
exactly one low-loss eigenmode for the chosen parameters while all other modes
exhibit large round trip losses. Figure (b) shows the corresponding values of
$|T_{i}|^{2}$. The lowest loss mode (eigenmode number 1) is an equal
superposition of the first three LG modes with weight 1/3 each, confirming
that our mirror design in fact makes this target superposition an eigenmode of
the cavity. All other modes contain contributions from high LG modes, which
explains their large loss seen in figure (a). For all parameters we tested
numerically, we always found that the mirror shapes designed by the procedure
described in Section III.1 generate the target cavity eigenmodes.

As discussed above, our calculations are performed within the paraxial
approximation. For the parameters of Fig. 6 we found that the error in the
obtained coefficients $T_{i}$ does not exceed $5\%$ when we use the mirror
profile extracted from the geometrical phase front (as in Fig. 5) instead of
the thin-mirror approximation. This check shows the limitations of the
paraxial approximation together with mode mixing theory.

(a) near concentric, N=3 (b) near confocal, N=3

(c) near concentric, N=5 (d) near confocal, N=5

(e) near concentric, N=7 (f) near confocal, N=7

Figure 7: Loss per round trip for the lowest loss mode for mirror shapes with
systematic fabrication errors. Blue, red and yellow lines correspond to axial,
radial and longitudinal misplacements given by deviations of parameters $a$,
$b$, and $L$, respectively, see Eq. (19). (a), (c), (e) Near-concentric cavity
with parameters $L=500~{}\mu$m, $R=255~{}\mu$m. (b), (d), (f) Near-confocal
cavity with parameters $L=500~{}\mu$m, $R=400~{}\mu$m. Line styles express
different numbers of LG modes in the target eigenmode superposition, solid,
dashed and dash-dotted lines correspond to $N=3,5,7$, respectively.

###  III.3 Fabrication Tolerances

As we discussed in Sec. III.1 the target mirror has a spherical shape
(parabolic within the paraxial approximation) with some deviations as seen,
for example, in Fig. 5(b). In this section we investigate the effect on cavity
eigenmode losses if this target mirror profile is implemented with some
errors, e.g., by fabrication imprecision.

Let us assume that our mirror is described by a profile $P(r)$ as

$P(r)=-\frac{r^{2}}{2R}+a\Delta(br),$ (19)

where the first term is a parabolic mirror with radius of curvature $R$ and
the second term is the deviation from the parabolic profile predicted by our
theory to generate the desired cavity eigenmode. We assume that the mirrors
are fabricated with some systematic error described by two coefficients $a$
and $b$ in Eq. (19) which correspond to axial and radial stretch,
respectively, of the target profile $\Delta(r)$ that is machined into the
parabolic mirror. We also consider longitudinal misalignment of the cavity,
i.e., a cavity length $L$ different from the one used to design the mirrors.

Figure (7) shows the loss of the lowest-loss cavity mode eigenmode when the
coefficients $a$ and $b$ in Eq. (19) differ from their design value of 1 and
when the cavity length $L$ is slightly varied. Results for two values of the
mirror radius of curvature are shown as well as for target mode superpositions
containing $N=3,5,7$ LG modes. Overall, we can conclude that manufacturing
inaccuracies of the order of $0.5\%$ will not increase the cavity mode loss
beyond an intrinsic mirror absorption/transmission loss of $D_{mir}=10^{-5}$.
Note that according to these simulations an error in cavity length $L$ seems
to be the most severe in many cases. However, in practice the cavity length in
quantum optics experiments is always controlled to extremely high precision in
order to maintain the cavity resonance frequency close to the transition
frequency of the quantum particle of the experiment (atom, ion, or quantum
dot) and therefore this requirement should not pose any additional
restrictions on cavity alignment.

In general, we find that superpositions of more LG modes are more difficult to
achieve with good stability, i.e., they are more susceptible to fabrication
errors. However, for the chosen parameters in Fig. 7 it appears interestingly
that the near-confocal cavity with a three-mode superposition is less stable
than the cavity with a five-mode superposition

###  III.4 Comments on Fabrication

Our scheme requires mirrors that are machined with a small deviation from a
spherical (parabolic) profile, as calculated in Section III.1. We envisage
that these profiles are machined into the mirror substrate before the
substrate is coated with a high-reflectivity dielectric stack.

Various methods exist that, in principle, allow the fabrication of such fine
mechanical structures. Laser micro-fabrication has successfully been
demonstrated in silica [20, 21, 22]. Pulses of a CO2 laser can be used for
thermal evaporation of surface material [23, 24] and laser radiation focused
on the cleaved surface can compose a surface landscape with extremely low
roughness. Another method is focused ion beam milling [5] that can be used for
material ablation with nanometer precision. Finally, modern mechanical micro-
machining tools [25, 26, 27] can also provide sufficient precision to meet the
fabrication requirements discussed in Section III.3.

##  IV Conclusions

In this work we developed a novel approach that allows us to achieve a
significant enhancement of the coupling rate and cooperativity between a
quantum emitter and a low-loss optical cavity without increasing mode
instability. We proposed to modify the cavity mirror geometry in such a way
that a specific superposition of LG modes becomes an eigenmode of the cavity
and provides significant local field enhancement. We demonstrated that such
mode superposition can provide lower losses and higher stability at the same
electric field amplitude than can be achieved by a more conventional approach
using near-concentric cavities. We envisage that such cavities could find
widespread use in a variety of research and engineering problems.

We demonstrated an approach to design the required mirror shapes by following
the contours of constant phase of the target mode superposition field and
verified our designs using mode matching theory. Finally we briefly discussed
options for manufacturing such mirrors and we investigated the effect of
systematic errors in fabrication on the performance of the cavity designs.
Overall, our approach appears realistic for state-of-the-art manufacturing
methods.

##  V Acknowledgments

We acknowledge financial support by the UK Quantum Technology Programme under
the EPSRC Hub in Quantum Computing and Simulation (EP/T001062/1).

## References

  * [1] Pellizzari T, Gardiner S, Cirac J and Zoller P 1995 Phys. Rev. Lett. 75 3788–3791
  * [2] Cirac J I, Zoller P, Kimble H J and Mabuchi H 1997 Phys. Rev. Lett. 78 3221–3224
  * [3] Kimble H J 2008 Nature 453 1023–1030
  * [4] Monroe C and Kim J 2013 Science 339 1164–1169
  * [5] Romagnoli, P., Maeda, M., Ward, J.M. et al. Fabrication of optical nanofibre-based cavities using focussed ion-beam milling: a review. Appl. Phys. B 126, 111 (2020).
  * [6] Bitarafan MH, DeCorby RG. On-Chip High-Finesse Fabry-Perot Microcavities for Optical Sensing and Quantum Information. Sensors (Basel). 2017 Jul 31;17(8):1748.
  * [7] Laser cooling and trapping of neutral atoms Nobel Lecture by William D. Phillips, Dec 8, 1997: Phillips, William D. (1998). ”Nobel Lecture: Laser cooling and trapping of neutral atoms”. Reviews of Modern Physics. 70 (3): 721–741. Bibcode:1998RvMP…70..721P. doi:10.1103/RevModPhys.70.721.
  * [8] I. H. Deutsch and P. S. Jessen, ”Quantum state preparation in optical lattices,” in Quantum Electronics and Laser Science Conference, J. Bokor, R. Slusher, P. Bucksbaum, and R. Falcone, eds., Vol. 12 of OSA Technical Digest (Optical Society of America, 1997), paper QTuJ3.
  * [9] D. M. Lucas, C. J. S. Donald, J. P. Home, M. J. McDonnell, A. Ramos, D. N. Stacey, J.-P. Stacey, A. M. Steane, S. C. Webster Philos. Transact. A Math Phys Eng Sci. 361, 1401-8
  * [10] Harlander M, Brownnutt M, Hänsel W, R and Blatt R 2010 New J. Phys. 12 093035
  * [11] Podoliak N, Takahashi H, Keller M and Horak P 2016 Phys. Rev. Appl. 6 044008
  * [12] Jelena Vučković, Stanford University Lectures given at Les Houches 101th summer school on “Quantum Optics and Nanophotonics”, August 2013 (to be published by Oxford University Press)
  * [13] Amnon Yariv, Quantum Electronics, 3rd Edition, ISBN: 978-0-471-60997-1, January 1991, 704 Pages
  * [14] Kleckner D, Irvine W T M, Oemrawsingh S S R and Bouwmeester D 2010 Phys. Rev. A 81 043814
  * [15] Nina Podoliak, Hiroki Takahashi, Matthias Keller and Peter Horak, J. Phys. B. 50, 085503 (2017)
  * [16] Benedikter J, Hümmer T, Mader M, Schlederer B, Reichel J, Hänsch T W and Hunger D 2015 New J. Phys. 17 053051
  * [17] B. Brandstätter, A. McClung, K. Schüppert, B. Casabone, K. Friebe, A. Stute, P. O. Schmidt, C. Deutsch, J. Reichel, R. Blatt, and T. E. Northup , ”Integrated fiber-mirror ion trap for strong ion-cavity coupling”, Review of Scientific Instruments 84, 123104 (2013)
  * [18] Phillips, R.L., and Andrews, L.C. Spot size and divergence for Laguerre Gaussian beams of any order. Appl. Opt. 22, 643-644 (1983)
  * [19] From Maxwell to paraxial wave optics Melvin Lax, William H. Louisell, and William B. McKnight Phys. Rev. A 11, 1365 (1975)
  * [20] Hunger D, Deutsch C, Warburton R and Reichel J, Laser micro-fabrication of concave, low-roughness features in silica, AIP Advances 2, 012119 (2012)
  * [21] Vernooy D W, Furusawa A, Georgiades N P, Ilchenko V S and Kimble H J 1998 Phys. Rev. A 57 R2293
  * [22] Armani D K, Kippenberg T J, Spillane S M and Vahala K J 2003 Nature 421 925
  * [23] Hunger D, Steinmetz T, Colombe Y, Deutsch C, Hänsch T W and Reichel J 2010 New J. Phys. 12 065038
  * [24] Gulati, G.K., Takahashi, H., Podoliak, N. et al. Fiber cavities with integrated mode matching optics. Sci Rep 7, 5556 (2017). https://doi.org/10.1038/s41598-017-05729-8
  * [25] Brinksmeier Ekkard and Preuss Werner, Micro-machining, Phil. Trans. R. Soc. A., 3703973–3992 (2012).
  * [26] Gao, S., Huang, H., Recent advances in micro- and nano-machining technologies., Front. Mech. Eng. 12, 18–32 (2017).
  * [27] Schneider, F., Das, J., Kirsch, B. et al., Sustainability in Ultra Precision and Micro Machining: A Review., Int. J. of Precis. Eng. and Manuf.-Green Tech., 6 601–610 (2019).


# Calculable lower bounds on the efficiency of universal sets of quantum gates

Oskar Słowik∗, Adam Sawicki†

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

###### Abstract

Currently available quantum computers, so called Noisy Intermediate-Scale
Quantum (NISQ) devices, are characterized by relatively low number of qubits
and moderate gate fidelities. In such scenario, the implementation of quantum
error correction is impossible and the performance of those devices is quite
modest. In particular, the depth of circuits implementable with reasonably
high fidelity is limited, and the minimization of circuit depth is required.
Such depths depend on the efficiency of the universal set of gates
$\mathcal{S}$ used in computation, and can be bounded using the Solovay-Kitaev
theorem. However, it is known that much better, asymptotically tight bounds of
the form $\mathcal{O}(\mathrm{log}(\epsilon^{-1}))$, can be obtained for
specific $\mathcal{S}$. Those bounds are controlled by, so called, spectral
gap at a certain scale $r(\epsilon)$, denoted $\mathrm{gap}_{r}(\mathcal{S})$.
In this paper we derive lower bounds on $\mathrm{gap}_{r}(\mathcal{S})$ and,
as a consequence, on the efficiency of universal sets of $d$-dimensional
quantum gates $\mathcal{S}$ satisfying an additional condition. The condition
is naturally met for generic quantum gates, such as e.g. Haar random gates.
Our bounds are explicit in the sense that all parameters can be determined by
numerical calculations on existing computers, at least for small $d$. This is
in contrast with known lower bounds on $\mathrm{gap}_{r}(\mathcal{S})$ which
involve parameters with ambiguous values.

##  1 Introduction and main results

Universal, scalable and fault-tolerant quantum computers are the holy grail of
quantum computing. Such devices require quantum error correction that, due to
quantum threshold theorem, can be implemented if the levels of gate errors are
small enough [1, 2, 3]. However, recent quantum hardware, so called Noisy
Intermediate-Scale Quantum (NISQ) devices, does not offer gate fidelities
required for quantum error correction and their performance is heavily
affected by gate imperfections [4, 5, 6]. Because of error accumulation
effects, the depth of circuits feasible for NISQ devices is very modest. Hence
it is imperative to find ways to minimize such depths. One of the ways to
address this issue is to focus on the efficiency of universal sets [7, 8] of
gates $\mathcal{S}$ used for the computations.

Spectral gap is an useful measure of efficiency of universal sets of quantum
gates $\mathcal{S}\subset\mathrm{SU}(d)$. The value of gap for chosen
$\mathcal{S}$, denoted $\mathrm{gap}(\mathcal{S})$, lies between 0 (no gap)
and some optimal value $\mathrm{gap}_{\mathrm{opt}}<1$, depending only on the
number of gates $|\mathcal{S}|$ [9]. The higher the value of
$\mathrm{gap}(\mathcal{S})$, the better is the upper bound on the minimal
length (circuit depth) $\ell$ of a sequence of gates from $\mathcal{S}$
required to $\epsilon$-approximate any unitary operation from
$\mathrm{SU}(d)$. Recall that the Solovay-Kitaev theorem [10] provides such a
bound for depth $\ell$,

$\ell=\tilde{A}(\mathcal{S})\cdot\mathrm{log}^{3+\delta}(1/\epsilon)),\quad\delta>0\mathcal{.}$
(1)

However, the existence of gap, i.e. $\mathrm{gap}(\mathcal{S})>0$, implies
that

$\ell=A(\mathcal{S})\cdot\mathrm{log}(1/\epsilon))+B(\mathcal{S})$ (2)

is enough, with the constants $A$ and $B$ proportional to
$\mathrm{log}^{-1}(1/(1-\mathrm{gap}(\mathcal{S})))$ [11]. In fact,
$\ell=\mathcal{O}(\mathrm{log}(1/\epsilon)))$ is optimal, which can be seen
from a simple volumetric argument.

One should note that some properties of $\mathcal{S}$ with optimal spectral
gap are known. For instance, if the gates from the universal set $\mathcal{S}$
have algebraic entries then the gap exists [12, 13]. Moreover, it has been
conjectured that any universal $\mathcal{S}$ has the gap and there are
explicit constructions of examples of $\mathcal{S}$ with the optimal spectral
gap for $\mathrm{SU}(2)$ with $|\mathcal{S}|=p-1$ for $p\equiv
1\,\mathrm{mod}\,4$ [14, 15]. Finally, some commonly used one-qubit universal
sets turned out to have the optimal spectral gap [16, 17, 18, 19]. However,
the construction of many-qubit gates with the optimal spectral gap remains an
open problem.

The calculation of $\mathrm{gap}(\mathcal{S})$ is challenging and in practice
one often considers the gap up to the certain scale $r$, denoted
$\mathrm{gap}_{r}(\mathcal{S})$, such that $\mathrm{gap}(\mathcal{S})$ is the
infimum of $\mathrm{gap}_{r}(\mathcal{S})$ over all scales $r$ 111The exact
definition of a scale depends on the approach.. Since it is impossible to
implement gates without any error, in practice $\epsilon$ can be bounded from
below. In such a case, in order to bound
$\ell=\mathcal{O}(\mathrm{log}(1/\epsilon))$ it is sufficient to have the
knowledge of $\mathrm{gap}_{r}(\mathcal{S})$ at some scale $r(\epsilon)$
instead of $\mathrm{gap}(\mathcal{S})$. This is due to the existence of the
Solovay-Kitaev-like theorems involving $\mathrm{gap}_{r}(\mathcal{S})$.
Specifically, it is known that one can bound
$\ell=\mathcal{O}(\mathrm{log}(1/\epsilon))$, for any universal $\mathcal{S}$,
where the proportionality constant is
$\propto\mathrm{gap}_{r}^{-1}(\mathcal{S})$ at some scale $r(\epsilon)$ (see
the first part of Lemma 5 in [20] and the improved version with
$r(\epsilon)\simeq\mathcal{O}(1/\epsilon\cdot\mathrm{log}(1/\epsilon))$ \-
Proposition 2 in [21]). Thus, bounding $\mathrm{gap}_{r}(\mathcal{S})$ is
imperative. From the seminal paper [20] it is known, in more general setting
of semisimple compact connected Lie groups, that there exist group constants
$c,A$ and $r_{0}$ such that

$\mathrm{gap}_{r}(\mathcal{S})\geq
c\cdot\mathrm{gap}_{r_{0}}(\mathcal{S})\cdot\mathrm{log}^{-A}(r)\mathrm{,}$
(3)

for any $r\geq r_{0}$. Thus, the knowledge of gap at the certain scale $r_{0}$
enables to bound the rate at which $\mathrm{gap}_{r}(\mathcal{S})$ vanishes
with growing $r\geq r_{0}$. However it is unclear what is the magnitude of the
minimal scale $r_{0}$ from which the bound (3) holds, even for
$\mathrm{SU}(2)$. Our preliminary analysis of this bound suggests that the
value of $r_{0}$ for $\mathrm{SU}(2)$ resulting from the proof is enormous -
orders of magnitude larger than the scale for which the numerical calculation
of $\mathrm{gap}_{r_{0}}(\mathcal{S})$ is remotely possible.

In this paper we exploit Bourgain’s argument for bounding
$\mathrm{gap}_{r}(\mathcal{S})$ by the diameter of $\mathcal{S}$, which was
communicated in the proof of the second part of Lemma 5 from [20]. By
introducing an additional assumption on $\mathcal{S}$ we obtain calculable
bounds on $\mathrm{gap}_{r}(\mathcal{S})$ for universal sets of quantum gates.
Our additional assumption on $\mathcal{S}$ is satisfied e.g. for generic
quantum gates, such as Haar random gates (with probability 1). The main result
of the paper is the following.

######  Theorem 1.

Let $\mathcal{S}=\\{U_{1},\ldots,U_{k},U_{1}^{-1},\ldots U_{k}^{-1}\\}$ be a
universal symmetric set of $d$-dimensional quantum gates, such that for any
$U_{i},U_{j}\in\mathcal{S}$, $i\neq j$, the set
$\\{U_{i}^{2},U_{j}^{2},U_{i}^{-2},U_{j}^{-2}\\}$ is universal. Then

$\mathrm{gap}_{t}(\mathcal{S})\geq\alpha\cdot
g_{t_{0}}(\mathcal{S})\cdot\mathrm{log}^{-2c}(\beta t)\mathrm{,}$ (4)

where $c=\mathrm{log}(5)/\mathrm{log}(3/2)\approx 4$, $\alpha$ and $\beta$ are
known constants and $g_{t_{0}}(\mathcal{S})$ can be determined by the
numerical calculations of gaps at a known scale $t_{0}$ of certain universal
sets that can be derived from $\mathcal{S}$.

The quantity $g_{t_{0}}(\mathcal{S})$ is defined in equation (137), see also
(138) and (96). Crucially, we provide explicit formulas (136) and (139), (78)
for $\alpha=\alpha(d,\epsilon_{0})$, $\beta=\beta(d)$ and
$t_{0}=t_{0}(d,\epsilon_{0})$, where $\epsilon_{0}$ is the parameter in the
construction leading to different bounds. The value of $t_{0}$ is small enough
to enable numerical calculations of $g_{t_{0}}(\mathcal{S})$, at least for
$d=2,3$ and $4$. Hence, our bounds can be made explicit by numerical
experiments for fixed $\mathcal{S}$. We provide examples of specific values of
$t_{0}$, $\alpha$ and $\beta$, for $d=2,3$ and $4$ in Tables 1 and 2. The
minimal possible values of $t_{0}$ are indicated by bold font and given by

$t_{\mathrm{min}}\coloneqq\lceil
5d^{5/2}/\epsilon_{0,\mathrm{min}}\cdot\tau(\epsilon_{0,\mathrm{min}},d)\rceil\mathrm{,}\quad\epsilon_{0,\mathrm{min}}\coloneqq
1/(d+2)\mathrm{,}$ (5)

where $\tau(\epsilon,d)$ is defined in (78). We present the values of $t_{0}$
up to the ones giving $\alpha$ around 1.

$\epsilon_{0}$ | $t_{0}$ | $\alpha$ | $\beta$
---|---|---|---
0.04 | 4599 | 9.68e-01 | 0.393
0.05 | 3544 | 3.67e-01 | 0.393
0.06 | 2860 | 1.49e-01 | 0.393
0.07 | 2384 | 6.29e-02 | 0.393
0.08 | 2035 | 2.72e-02 | 0.393
0.09 | 1769 | 1.18e-02 | 0.393
0.1 | 1559 | 5.15e-03 | 0.393
0.11 | 1391 | 2.22e-03 | 0.393
0.12 | 1252 | 9.38e-04 | 0.393
0.13 | 1137 | 3.85e-04 | 0.393
0.14 | 1039 | 2.62e-04 | 0.393
0.15 | 955 | 5.68e-05 | 0.393
0.16 | 883 | 1.99e-05 | 0.393
0.17 | 820 | 6.36e-06 | 0.393
$\lessapprox$ 0.25 | 509 |  $\gtrapprox$ 0 | 0.393

,  $\epsilon_{0}$ $t_{0}$ $\alpha$ $\beta$ 0.02 29199 7.25e-01 0.251 0.03
18353 1.73e-01 0.251 0.04 13170 5.07e-02 0.251 0.05 10166 1.65e-02 0.251 0.06
8219 5.69e-03 0.251 0.07 6861 2.01e-03 0.251 0.08 5864 7.10e-04 0.251 0.09
5103 2.47e-04 0.251 0.1 4504 8.31e-05 0.251 0.11 4022 2.65e-05 0.251 0.12 3625
7.81e-06 0.251 0.13 3295 2.07e-06 0.251 0.14 3014 4.75e-07 0.251 0.15 2775
8.82e-08 0.251 $\lessapprox$ 0.20 1958 $\gtrapprox$ 0 0.251

Table 1: Examples of values of $t_{0}$, $\alpha$ and $\beta$ for $d=2$ (left) and $d=3$ (right). The parameter $\epsilon_{0}$ is an element of the construction determining $t_{0}$ (along with $d$). Bold font indicates the choice of smallest possible $t_{0}$. $\epsilon_{0}$ | $t_{0}$ | $\alpha$ | $\beta$
---|---|---|---
0.01 | 134232 | 8.46e-01 | 0.175
0.02 | 61313 | 1.06e-01 | 0.175
0.03 | 38602 | 2.18e-02 | 0.175
0.04 | 27738 | 5.49e-03 | 0.175
0.05 | 21435 | 1.52e-03 | 0.175
0.06 | 17347 | 4.34e-04 | 0.175
0.07 | 14494 | 1.24e-04 | 0.175
0.08 | 12398 | 3.43e-05 | 0.175
0.09 | 10797 | 8.86e-06 | 0.175
0.1 | 9537 | 2.07e-06 | 0.175
0.11 | 8522 | 4.14e-07 | 0.175
0.12 | 7687 | 6.59e-08 | 0.175
0.13 | 6990 | 7.37e-09 | 0.175
0.14 | 6400 | 4.54e-10 | 0.175
$\lessapprox$ 0.1(6) | 5195 |  $\gtrapprox$ 0 | 0.175
Table 2: Examples of values of $t_{0}$, $\alpha$ and $\beta$ for $d=4$. The
parameter $\epsilon_{0}$ is an element of the construction determining $t_{0}$
(along with $d$). Bold font indicates the choice of smallest possible $t_{0}$.

The structure of this paper is as follows. In Section 2 we introduce the
mathematics used in the paper, such as the averaging operators and their
relevant spectral gaps. In Section 3 we provide an alternative proof of the
efficiency bound (2) from [11] with $A$ and $B$ proportional to
$\mathrm{gap}^{-1}(\mathcal{S})$. In Section 4 we present the proof of our
main result, Theorem 1.

##  2 Averaging operators and their spectral gaps

By $G_{d}$ we denote the projective unitary group $\mathrm{PU}(d)$, which is
the quotient of the unitary group $\mathrm{U}(d)$ by its center

$\mathrm{U}(1)=\\{e^{i\theta}|\,\theta\in[0,2\pi)\\}\mathrm{.}$ (6)

Consider the space $L^{2}(G_{d})$ of square integrable complex functions on
$G_{d}$ with respect to $\mu$, equipped with the standard scalar product
$\langle\cdot,\cdot\rangle$ (linear on the second slot). Since $G_{d}$ is
compact we consider only unitary representations. A group $G_{d}$ acts on
$L^{2}(G_{d})$ via (left) regular representation $\mathrm{Reg}$. Given a
function $f\in L^{2}(G_{d})$ and element $g\in G_{d}$

$(\mathrm{Reg}(g)f)(x)=f(g^{-1}x)\mathrm{,}$ (7)

so the regular representation acts on functions by shifts. Regular
representation is not irreducible. In fact, due to Peter-Weyl theorem, it
decomposes into an orthogonal direct sum of all the irreducible unitary
representations (irreps) with multiplicities equal to their dimensions

$L^{2}(G_{d})=\mathop{\widehat{\bigoplus}}\slimits@_{\lambda\in\Lambda}V_{\lambda}^{\oplus
d_{\lambda}}\mathrm{,}$ (8)

where $\Lambda$ is the set of highest weights of $G_{d}$ (enumerating all
irreps up to isomorphism), $V_{\lambda}$ is the representation space of irrep
$\pi_{\lambda}$ with highest weight $\lambda$ and dimension $d_{\lambda}$ and
hat denotes the closure of an infinite direct sum. Moreover for each
$\lambda\in\Lambda$

$\left\\{\sqrt{d_{\lambda}}(\pi_{\lambda})_{ij}|1\leq i,j\leq
d_{\lambda}\right\\}\mathrm{,}$ (9)

is an orthonormal basis of $V_{\lambda}$ where matrix elements
$(\pi_{\lambda})_{ij}$ are functions in $L^{2}(G_{d})$ given by

$(\pi_{\lambda})_{ij}(g)\coloneqq\langle
e_{i},\pi_{\lambda}(g)e_{j}\rangle\mathrm{,}$ (10)

for some fixed orthonormal basis of $V_{\lambda}$, $\\{e_{k}|1\leq k\leq
d_{\lambda}\\}$. Clearly, sum of all such basis form an orthonormal basis of
$L^{2}(G_{d})$

$\left\\{\sqrt{d_{\lambda}}(\pi_{\lambda})_{ij}|\lambda\in\Lambda,1\leq
i,j\leq d_{\lambda}\right\\}\mathrm{.}$ (11)

Hence any function $f\in V_{\lambda}$, as a linear combination of matrix
elements, is given by

$f(g)=\mathrm{Tr}[A\pi_{\lambda}(g)],\quad g\in G_{d}$ (12)

for some complex $d_{\lambda}\times d_{\lambda}$ matrix $A$. The regular
representation restricted to functions in $V_{\lambda}$ is isomorphic to
representation $\pi_{\lambda}$. If $\pi$ is any (possibly reducible)
representation of $G_{d}$, then $\pi$ is isomorphic to the direct sum of
irreps which can be identified with function spaces from Peter-Weyl
decomposition $V_{\lambda_{1}}^{\otimes m_{1}}\oplus\ldots\oplus
V_{\lambda_{k}}^{\otimes m_{k}}$, for some $k\geq 1$ and multiplicities
$m_{i}\geq 1$. If $m_{i}\leq d_{\lambda_{i}}$ for all $1\leq i\leq k$, then
representation $\pi$ will appear as a subrepresentation of $L^{2}(G)$. The
corresponding space of functions consists of all functions obtained via

$f(g)=\mathrm{Tr}[A\pi(g)],\quad g\in G_{d}$ (13)

for all matrices $A$.

We now comment on how one may naturally choose a scale up to which one would
like to consider irreps of $G_{d}$.

The Lie algebra of $G_{d}$ is isomorphic to $\mathfrak{su}(d)$ since

$G_{d}=\mathrm{PU}(d)\cong\mathrm{PSU(d)}=\mathrm{SU(d)}/Z(\mathrm{SU}(d))\mathrm{,}$
(14)

where $Z(\mathrm{SU}(d))\simeq\mathbb{Z}_{d}$, the center of $\mathrm{SU}(d)$,
is discrete.

The adjoint representation $\mathrm{Ad}$ of $\mathrm{U}(d)$ descents into the
quotient group $G_{d}$ forming the adjoint representation $\mathrm{Ad}$ of a
group $G_{d}$ acting on its representation space $\mathfrak{su}(d)$ via

$\mathrm{Ad}_{U}(X)=\hat{U}X\hat{U}^{-1},\quad U\in
G_{d},X\in\mathfrak{su}(d)\mathrm{,}$ (15)

where $\hat{U}\in\mathrm{U}(d)$ is any representative of $U\in G_{d}$.
Importantly $\mathrm{Ad}$ is faithful hence every representation of $G_{d}$ is
realized inside $\mathrm{Ad}^{\otimes n}$ for $n$ large enough. The defining
representation $U$ of $\mathrm{U}(d)$ does not descend into a well-defined
representation $U$ of $G_{d}$ but $U\otimes\overline{U}$ does, where
$\overline{U}$ is the adjoint of $U$. In fact,

$U\otimes\overline{U}\cong\mathrm{Ad}\oplus I\mathrm{,}$ (16)

where by $I$ we denote the one-dimensional trivial representation. Thus each
irrep of $G_{d}$ appears in rep $(U\otimes\overline{U})^{\otimes t}$ for some
$t$. Moreover this rep contains only projective irreps of $\mathrm{U}(d)$
hence reps of $G_{d}$.

Consider $t\geq 2$. Then

$(U\otimes\overline{U})^{\otimes t}\cong(U\otimes\overline{U})^{\otimes
t-1}\otimes(\mathrm{Ad}\oplus I)\cong[(U\otimes\overline{U})^{\otimes
t-1}\otimes\mathrm{Ad}]\oplus(U\otimes\overline{U})^{\otimes t-1}$ (17)

and applying this reasoning inductively we see that all irreps of
$(U\otimes\overline{U})^{\otimes s}$ appear in
$(U\otimes\overline{U})^{\otimes t}$ for $s\leq t$. Thus we see that with $t$
increasing the rep $(U\otimes\overline{U})^{\otimes t}$ contains more and more
irreps of $G_{d}$ and each irrep of $G_{d}$ is contained in this rep for $t$
large enough. In the language of Peter-Weyl theorem the corresponding
functions in $L^{2}(G)$ are

$f(U)=\mathrm{Tr}[A(U\otimes\overline{U})^{\otimes t}],g\in G$ (18)

so they are balanced polynomials in $U$ and $\overline{U}$ of degree $t$. Thus
increasing $t$ corresponds to considering polynomials with higher degrees.
This motivates us to consider the following function spaces in $L^{2}(G_{d})$,

$L^{2}_{t}(G_{d})=\bigoplus_{\lambda\in\Lambda_{t}}V_{\lambda}\mathrm{,}$ (19)

where $\Lambda_{t}$ is the set of unique (i.e. without repetitions and up to
isomorphism) highest weights of irreps of $G_{d}$ appearing in
$(U\otimes\overline{U})^{\otimes t}$. In the case $t=0$, we set

$L^{2}_{0}(G_{d})=I\mathrm{.}$ (20)

Additionally we define the following related symbols. The set
$\tilde{\Lambda}_{t}$ which equals $\Lambda_{t}$ without the weight of the
trivial representation and the set of all unique highest weights

$\Lambda_{\infty}\coloneqq\bigcup_{t=0}^{\infty}\Lambda_{t}\mathrm{.}$ (21)

Fortunately the weights $\Lambda_{t}$ have a nice description in terms of the
sequences of integers.

######  Lemma 2.

The set $\Lambda_{t}$ consists precisely of weights indexed by nonincreasing
length $d$ integer sequences $\lambda$ such that $|\lambda|=0$ and
$|\lambda_{+}|\leq t$, where $|\lambda|$ denotes the sum of entries and
$\lambda_{+}$ is the subsequence of positive entries.

Each sequence $\lambda=(\lambda_{1},\ldots,\lambda_{d})\in\Lambda_{t}$
corresponds to a weight (the linear functional on the Cartan subalgebra
$\mathfrak{h}\subset\mathfrak{su}(d)$)

$\lambda=\lambda_{1}L_{1}+\ldots\lambda_{d}L_{d}\mathrm{,}$ (22)

where $L_{i}$ are the standard basis elements 222The linear functional $L_{i}$
returns the $i$-th diagonal entry of a matrix in $\mathfrak{h}$.. Since
$L_{1}+\ldots+L_{d}=0$ in $\mathfrak{h}^{*}$, adding a constant sequence,
$(c,\ldots,c)$ for some $c\in\mathbb{Z}$, to $\lambda$ does not change the
weight.

######  Example 1.

Consider the system of two qutrits $\mathbb{C}^{3}\otimes\mathbb{C}^{3}$ and
$t=2$. Then, from Lemma 2, we have

$\Lambda_{t}=\\{(2,0,-2),(2,-1,-1),(1,1,-2),(1,0,-1),(0,0,0)\\}$ (23)

which is equivalent to

$\Lambda_{t}=\\{(4,2,0),(3,0,0),(3,3,0),(2,1,0),(0,0,0)\\}\mathrm{,}$ (24)

and for example $\lambda=(2,1,0)$ corresponds to the highest weight
$2L_{1}+L_{2}$ i.e. to the adjoint representation. Similarly we can represent
$\tilde{\Lambda}_{t}$ as

$\tilde{\Lambda}_{t}=\\{(4,2,0),(3,0,0),(3,3,0),(2,1,0)\\}\mathrm{.}$ (25)

We introduce the following norm on the space of weights of $G_{d}$

$||\lambda||_{1}\coloneqq\sum_{i=1}^{d}|\lambda_{i}|\mathrm{.}$ (26)

It is clear that for each $\lambda\in\Lambda_{t}$,

$||\lambda||_{1}\leq 2t\mathrm{.}$ (27)

From now on we represent each irrep $\lambda$ by the sequence with smallest
$||\lambda||_{1}$. In particular, the trivial representation is given by
$\lambda=(0,0,\ldots,0)$.

By choosing the orthonormal basis of function spaces (11) we have the
isomorphisms

$V_{\lambda}\simeq\mathcal{H}_{\lambda}\mathrm{,}$ (28)

where $\mathcal{H}_{\lambda}\coloneqq\mathbb{C}^{d_{\lambda}}$. We define

$\mathcal{H}_{t}\coloneqq\bigoplus_{\lambda\in\Lambda_{t}}\mathcal{H}_{\lambda}\simeq
L^{2}_{t}(G_{d})\mathrm{,}$ (29)

and analogously we define $\mathcal{H}_{\infty}$ 333Here we use the closure of
the direct sum.. By $\mathcal{H}$ we denote the vector space isomorphic to
$L^{2}(G_{d})$. Clearly,

$L^{2}(G_{d})\simeq\mathcal{H}\coloneqq\bigoplus_{\lambda\in\Lambda_{\infty}}\mathcal{H}_{\lambda}^{\oplus
d_{\lambda}}\mathrm{.}$ (30)

For any representation of $G_{d}$ and any finite Borel measure $\nu$ on
$G_{d}$ we define the operator

$\pi(\nu)\coloneqq\int_{G_{d}}\pi(g)d\nu(g)\mathrm{,}$ (31)

acting on the representation space of $\pi$. We use can use (31) to define
various averaging operators. By $\mathcal{S}$ we denote a finite set of
generators of $G_{d}$ and $\nu_{\mathcal{S}}$ is the counting measure of
$\mathcal{S}$ on $G_{d}$.

The $t$-averaging operator wrt to $\mathcal{S}$,
$T_{\nu_{\mathcal{S}},t}:\mathcal{H}_{t}\rightarrow\mathcal{H}_{t}$ is

$T_{\nu_{\mathcal{S}},t}\coloneqq\bigoplus_{\lambda\in\Lambda_{t}}\pi_{\lambda}(\nu_{S})\mathrm{,}$
(32)

and can be represented as a block-diagonal matrix. Analogously we define the
$\infty$-averaging operator wrt to $\mathcal{S}$,
$T_{\nu_{\mathcal{S}},\infty}:\mathcal{H}_{\infty}\rightarrow\mathcal{H}_{\infty}$,

$T_{\nu_{\mathcal{S}},\infty}\coloneqq\bigoplus_{\lambda\in\Lambda_{\infty}}\pi_{\lambda}(\nu_{S})\mathrm{.}$
(33)

Finally, the (global) averaging operator wrt to $\mathcal{S}$,
$T_{\nu_{\mathcal{S}}}:\mathcal{H}\rightarrow\mathcal{H}$ is

$T_{\nu_{\mathcal{S}}}\coloneqq\bigoplus_{\lambda\in\Lambda_{\infty}}\pi_{\lambda}(\nu_{S})^{\oplus
d_{\lambda}}\mathrm{.}$ (34)

In the language of functions, introduced averaging operators correspond to
restrictions of $\mathrm{Reg}(\nu_{\mathcal{S}})$ to corresponding function
subspaces. We denote such isomorphic averaging operators using the same
symbols. For example, the global averaging operator is

$T_{\nu_{\mathcal{S}}}=\mathrm{Reg}(\nu_{\mathcal{S}})\mathrm{,}$ (35)

so the action on $f\in L^{2}(G_{d})$ is

$(T_{\nu_{\mathcal{S}}}f)(h)=\int_{G_{d}}(\mathrm{Reg}(g)f)(h)d\nu_{\mathcal{S}}(g)=\frac{1}{|\mathcal{S}|}\sum_{i=1}^{|\mathcal{S}|}f(g_{i}^{-1}h)\mathrm{.}$
(36)

The justification for the name averaging operator is clear from (36). Indeed,
$T_{\nu_{\mathcal{S}}}$ replaces the function $f$ with the averaged function,
whose value at $h$ is the average of the values of $f$ over all translates of
$h$ by the elements of $\mathcal{S}$.

Similarly, the $t$-averaging operator is

$T_{\nu_{\mathcal{S}},t}={\left.\kern-1.2pt\mathrm{Reg}(\nu_{\mathcal{S}})\vphantom{\big{|}}\right|_{L^{2}_{t}(G_{d})}}\mathrm{,}$
(37)

so it acts just like $T_{\nu_{\mathcal{S}}}$ but on a restricted domain of
functions.

Since $T_{\nu_{\mathcal{S}},t}$ is a sum of $|\mathcal{S}|$ left shift
operators, normalized by $1/|\mathcal{S}|$, and due to left-invariance of Haar
measure, each such operator is unitary on $L^{2}_{t}(G_{d})$, we see that
$||T_{\nu_{\mathcal{S}},t}||_{op}\leq 1$, where by $||\cdot||_{op}$ we denote
the operator norm. On the other hand $T_{\nu_{\mathcal{S}},t}$ acts trivially
on $\mathcal{H}_{\lambda_{0}}$, where $\lambda_{0}=(0,0,\ldots,0)$ so
$||T_{\nu_{\mathcal{S}},t}||_{op}\geq 1$ and hence
$||T_{\nu_{\mathcal{S}},t}||_{op}=1$.

The subspace $\mathcal{H}_{\lambda_{0}}$ corresponds to the subspace of
constant functions $L^{2}_{0}(G_{d})=V_{\lambda_{0}}$, with orthogonal
compliment being the space of functions with Haar-average zero. Let $T_{\mu}$
denote the projector onto $\mathcal{H}_{\lambda_{0}}$. At the level of
function spaces, $T_{\mu}$ is the projector onto $L^{2}_{0}(G_{d})$ which
assigns to each function $f$ the constant function with value being the Haar
average 444From now on the symbol $\mu$ denotes the Haar measure on $G_{d}$.
of $f$ ,

$(T_{\mu}f)(h)=\int_{G_{d}}f(g)d\mu(g)\mathrm{.}$ (38)

In order to assess how quick the words in $\mathcal{S}$ fill the group
$G_{d}$, we compare the averaging operator $T_{\nu_{\mathcal{S}}}$ with
$T_{\mu}$ by checking the operator of their difference. Since
${\left.\kern-1.2ptT_{\nu_{\mathcal{S}}}\vphantom{\big{|}}\right|_{\mathcal{H}_{\lambda_{0}}}}={\left.\kern-1.2ptT_{\mu}\vphantom{\big{|}}\right|_{\mathcal{H}_{\lambda_{0}}}}$,
the norm $||T_{\nu_{\mathcal{S}}}-T_{\mu}||_{op}$ equals the norm of the
operator

$\tilde{T}_{\nu_{\mathcal{S}}}\coloneqq\bigoplus_{\lambda\in\tilde{\Lambda}_{\infty}}\pi_{\lambda}(\nu_{S})^{\oplus
d_{\lambda}}\mathrm{.}$ (39)

Similarly, we define $\tilde{T}_{\nu_{\mathcal{S}},t}$ and
$\tilde{T}_{\nu_{\mathcal{S}},\infty}$. Clearly,

$\sigma(T_{\nu_{\mathcal{S}}})=\sigma(T_{\nu_{\mathcal{S}},\infty})\mathrm{,}$
(40)

so we have

$||T_{\nu_{\mathcal{S}}}-T_{\mu}||_{op}=||\tilde{T}_{\nu_{\mathcal{S}}}||_{op}=||\tilde{T}_{\nu_{\mathcal{S}},\infty}||_{op}\mathrm{.}$
(41)

This motivates us to define the spectral gap of $\mathcal{S}$ as

$\mathrm{gap}(\mathcal{S})\coloneqq
1-||\tilde{T}_{\nu_{\mathcal{S}}}||_{op}\mathrm{.}$ (42)

The spectral gap is an useful numerical value describing the set $\mathcal{S}$
via the properties of the corresponding averaging operator.

Similarly, we define spectral gap of $\mathcal{S}$ at scale $t$ as

$\mathrm{gap_{t}}(\mathcal{S})\coloneqq
1-||\tilde{T}_{\nu_{\mathcal{S}},t}||_{op}\mathrm{.}$ (43)

In general we can define analogous gaps for any finite Borel measure $\nu$ on
$G_{d}$. For example,

$\mathrm{gap_{t}}(\nu)\coloneqq 1-||\tilde{T}_{\nu,t}||_{op}\mathrm{,}$ (44)

where $\tilde{T}_{\nu,t}$ is defined as in (32) with $\nu_{\mathcal{S}}$
substituted by $\nu$. It is clear that

$\mathrm{gap}(\mathcal{S})=\inf_{t}\mathrm{gap_{t}}(\mathcal{S})\mathrm{,}$
(45)

and the gaps (42)-(44) belong to $[0,1]$.

We argue that we can assume that $\mathcal{S}$ is symmetric without the loss
of generality. For a measure $\nu$ on $G_{d}$ we define its conjugate
$\tilde{\nu}$ via the property

$\int_{G_{d}}f(g)d\tilde{\nu}(g)=\int_{G_{d}}f(g^{-1})d\nu(g)$ (46)

for all continuous functions $f$ on $G_{d}$. We say a measure $\nu$ is
symmetric if $\nu=\tilde{\nu}$. For two measures $\nu_{1}$ and $\nu_{2}$ on
$G_{d}$, their convolution $\nu_{1}*\nu_{2}$ is a measure on $G_{d}$ defined
via

$\nu_{1}*\nu_{2}(\Omega)=\int_{G_{d}}\mathbbm{1}_{\Omega}(gh)\nu_{1}(g)\nu_{2}(h)\mathrm{.}$
(47)

Going back to the definition (31) we have

$\pi(\nu_{1}*\nu_{2})=\pi(\nu_{1})\pi(\nu_{2})\mathrm{.}$ (48)

It is easy to see that $\pi(\tilde{\nu})=\pi(\nu)^{*}$. In particular if $\nu$
is symmetric then $\pi(\nu)$ is self-adjoint and hence $\sigma(\pi(\nu))$ is
real. Note also that $\nu*\tilde{\nu}$ is automatically symmetric. We can
write

$\pi(\tilde{\nu}*\nu)=\pi(\tilde{\nu})\cdot\pi(\nu)=\pi(\nu)^{*}\cdot\pi(\nu)\mathrm{,}$
(49)

which means that

$||\pi(\tilde{\nu}*\nu)||_{op}=||\pi(\nu)||_{op}^{2}\mathrm{.}$ (50)

Finally, because $\sqrt{1-x}\leq 1-\frac{x}{2}$ for any $0\leq x\leq 1$,

$\mathrm{gap}_{t}(\tilde{\nu}_{\mathcal{S}}*\nu_{\mathcal{S}})\geq\mathrm{gap}_{t}(\mathcal{S})\geq\frac{1}{2}\mathrm{gap}_{t}(\tilde{\nu}_{\mathcal{S}}*\nu_{\mathcal{S}})\mathrm{.}$
(51)

Since $\mathcal{S}$ is symmetric, $T_{\nu_{\mathcal{S}},t}$ is Hermitian and
so its spectrum $\sigma(T_{\nu_{\mathcal{S}},t})$ is contained in $[-1,1]$.
The same is true for $T_{\nu_{\mathrm{S}},\infty}$ and $T_{\nu_{\mathrm{S}}}$.
Note that since the subspace $\mathcal{H}_{\lambda_{0}}$ is excluded, the
question if $\mathrm{gap}(\mathcal{S})>0$ is non-trivial. The gap exists, i.e.
$\mathrm{gap}(\mathcal{S})>0$, if and only if $1$ belongs to the spectrum
$\sigma(T_{\nu_{\mathcal{S}}})$ i.e. it is the accumulation point of
$\sigma(T_{\nu_{\mathcal{S}}})$. In such a case we say that
$T_{\nu_{\mathcal{S}}}$ has a spectral gap.

Let’s denote by $\mathcal{S_{\ell}}$ a set of words in $G_{d}$ of length
$\ell$ built from elements of $\mathcal{S}$

$\mathcal{S_{\ell}}\coloneqq\\{g_{1}g_{2}\ldots g_{\ell}|\,g_{1},g_{2},\ldots
g_{\ell}\in\mathcal{S}\\}\mathrm{.}$ (52)

The corresponding averaging operator is $T_{\nu_{\mathcal{S}}}^{\ell}$.
Indeed,

$T_{\nu_{\mathcal{S}}}^{\ell}=T_{\nu_{\mathcal{S}}^{*(\ell)}}\mathrm{,}$ (53)

and since $\nu_{\mathcal{S}}^{*(\ell)}$ is the law for $\mathcal{S}_{\ell}$,
$T_{\nu_{\mathcal{S}}}^{\ell}$ is the averaging operator with respect to
$\mathcal{S}_{\ell}$. At the level of functions we have

$(T_{\nu_{\mathcal{S}}}^{\ell}f)(h)=\frac{1}{|\mathcal{S}|^{\ell}}\sum_{w\in
S_{\ell}}f(w^{-1}g)\mathrm{.}$ (54)

Importantly, $\mathrm{gap}(\mathcal{S})$ can be interpreted as the exponential
rate of convergence of the (global) averaging operator $T_{\nu_{\mathcal{S}}}$
to $T_{\mu}$ in the operator norm with $\ell$ increasing. Indeed, due to left-
invariance of Haar measure

$T_{\nu_{\mathcal{S}}}T_{\mu}=T_{\mu}=T_{\mu}T_{\nu_{\mathcal{S}}}\mathrm{,}$
(55)

so we have

$||T_{\nu_{\mathcal{S}}}^{\ell}-T_{\mu}||_{op}=||(T_{\nu_{\mathcal{S}}}-T_{\mu})^{\ell}||_{op}\leq||(T_{\nu_{\mathcal{S}}}-T_{\mu})||_{op}^{\ell}=||\tilde{T}_{\nu_{\mathcal{S}}}||_{op}^{\ell}\mathrm{,}$
(56)

and using the notion of a spectral gap (42) we have

$||T_{\nu_{\mathcal{S}}}^{\ell}-T_{\mu}||_{op}\leq(1-\mathrm{gap}(\mathcal{S}))^{\ell}\leq
e^{-\ell\,\mathrm{gap}(\mathcal{S})}\mathrm{.}$ (57)

Thus, if the gap exists then $T_{\nu_{\mathcal{S}}}^{\ell}$ converges to
$T_{\mu}$ as $\ell\to\infty$ exponentially fast in the operator norm.
Moreover, the rate of convergence improves exponentially with
$\mathrm{gap}(\mathcal{S})$ increasing. This motivates us to study
$\mathrm{gap}(\mathcal{S})$.

##  3 Bound on gates efficiency from spectral gap

In [11] it has been shown in case of group $\mathrm{SU}(d)$ that if
$\mathcal{S}$ is universal and $T_{\nu_{\mathcal{S}}}$ has a spectral gap then
words of length
$\ell=\mathcal{O}\left(\mathrm{log}\left(\frac{1}{\epsilon}\right)\right)$
form an $\epsilon$-net.

In this section we present an alternative proof of this fact for $G_{d}$. By
$D(\cdot,\cdot)$ we denote a $G_{d}$-invariant metric on $G_{d}$ defined as
follows. For $g,h\in G_{d}$ let $\hat{g},\hat{h}\in\mathrm{U}(d)$ be the
corresponding representatives. Then

$D(g,h)\coloneqq\mathrm{inf}_{\theta\in[0,2\pi)}||e^{i\theta}\hat{g}-\hat{h}||_{op}\mathrm{.}$
(58)

Equivalently, we can take the infimum over representatives

$D(g,h)=\mathrm{inf}_{\hat{g},\hat{h}}||\hat{g}-\hat{h}||_{op}\mathrm{.}$ (59)

We introduce $B(x,r)$ as the closed ball in $G_{d}$ with radius $r$ centered
at $x$ with respect to $D$ and $B(r)$ is such ball centered at $\mathbb{I}$.

By $\mathrm{Vol}(\Omega)$ we mean the Haar volume of a subset $\Omega\subset
G_{d}$,

$\mathrm{Vol}(\Omega)=\int_{G_{d}}\mathbbm{1}_{\Omega}(g)d\mu(g)\mathrm{,}$
(60)

where $\mathbbm{1}_{\Omega}$ denotes the indicator function of $\Omega$.

We start with the following simple observation. Let $f\in L^{2}_{t}(G_{d})$,
$\int_{G_{d}}f(g)d\mu(g)=1$, and pick some region $\Omega\subseteq G_{d}$.
Since

$\mathrm{Vol}({\Omega})=\int_{\Omega}1d\mu(g)$ (61)

we have that

$\int_{\Omega}1d\mu(g)-\int_{\Omega}(T_{\nu_{\mathcal{S}},t}^{\ell}f)(g)d\mu(g)=\langle
1-T_{\nu_{\mathcal{S}},t}^{\ell}f|\mathbbm{1}_{\Omega}\rangle\leq||1-T_{\nu_{\mathcal{S}},t}^{\ell}f||_{2}\cdot\sqrt{\mathrm{Vol}({\Omega})}$
(62)

and

$||1-T_{\nu_{\mathcal{S}},t}^{\ell}f||_{2}=||(T_{\nu_{\mathcal{S}},t}^{\ell}-T_{\mu})f||_{2}\leq||(T_{\nu_{\mathcal{S}},t}^{\ell}-T_{\mu})||_{op}\cdot||f||_{2}\leq
e^{-\ell\,\mathrm{gap}_{t}({\mathcal{S}})}\cdot||f||_{2}\mathrm{,}$ (63)

where $T_{\mu}$ is a projector onto $L^{2}_{0}(G_{d})$ on $L^{2}_{t}(G_{d})$.
Thus,

$\int_{\Omega}\left(T_{\nu_{\mathcal{S}},t}^{\ell}f\right)(g)\geq\mathrm{Vol}({\Omega})-e^{-\ell\,\mathrm{gap}_{t}(\mathcal{S})}||f||_{2}\sqrt{\mathrm{Vol}({\Omega})}\mathrm{.}$
(64)

Clearly, analogous results are true for other averaging operators, in
particular for $T_{\nu_{\mathrm{S}}}$.

######  Theorem 3.

Assume $\mathcal{S}$ is such that $T_{\mathcal{S}}$ has a spectral gap. Then
$S_{\ell}$ is an $\epsilon$-net for every $\ell$

$\ell\geq\frac{\mathrm{dim}\,G_{d}}{\mathrm{gap}(\mathcal{S})}\mathrm{log}\left(\frac{1}{\epsilon}\right)+B\mathrm{.}$

###### Proof.

Pick an element $U_{0}\in G_{d}$ and a ball ${\Omega}=B(U_{0},\epsilon/2)$
centered at it. Pick $\ell$ such that there is no
$w_{\ell}\in\mathcal{S}_{\ell}$ which $\epsilon$-approximates $U_{0}$, i.e.
such that $D(w_{\ell},U_{0})\leq\epsilon$. Let $f$ be a normalized indicator
function of $B(\mathbb{I},\epsilon/2)$, i.e.

$f(x)=\frac{1}{\mathrm{Vol}(B(\mathbb{I},\epsilon/2))}\mathbbm{1}_{B(\mathbb{I},\epsilon/2)}(x)\mathrm{.}$
(65)

We have

$\int_{\Omega}\left(T_{\nu_{\mathcal{S}}}^{\ell}f\right)(g)d\mu(g)=\frac{1}{|\mathcal{S}|}\sum_{w_{\ell}\in\mathcal{S}^{\ell}}\int_{G_{d}}f(w_{\ell}^{-1}g)d\mu(g)$
(66)

but for each $g$ in ${\Omega}$

$D(w_{\ell}^{-1}g,\mathbb{I})=D(g,w_{\ell})>\epsilon/2\mathrm{,}$ (67)

hence

$\int_{\Omega}\left(T_{\nu_{\mathcal{S}}}^{\ell}f\right)(g)d\mu(g)=0$ (68)

Using (64) we get

$e^{-\ell\,\mathrm{gap}(\mathcal{S})}\geq\mathrm{Vol}({\Omega})\mathrm{,}$
(69)

since $||f||_{2}=1/\sqrt{\mathrm{Vol}({\Omega})}$. Hence, if

$e^{-\ell\,\mathrm{gap}(\mathcal{S})}<\mathrm{Vol}({\Omega})\mathrm{,}$ (70)

we get a contradiction, which means that $\mathcal{S}_{\ell}$ is an
$\epsilon$-net. On the other hand

$\mathrm{Vol}({\Omega})\leq C_{V}(\epsilon/2)^{\mathrm{dim}\,G_{d}}\mathrm{,}$
(71)

where $C_{V}$ is some group constant. Thus,

$\ell\geq\frac{\mathrm{dim}\,G_{d}}{\mathrm{gap}(\mathcal{S})}\mathrm{log}\left(\frac{1}{\epsilon}\right)+B\mathrm{,}$
(72)

with

$B=-\frac{\mathrm{log}(C_{V})-\mathrm{dim}\,G_{d}\cdot\mathrm{log}(2)}{\mathrm{gap}(\mathcal{S})}\mathrm{.}$
(73)

∎

We have $\mathrm{dim}\,G_{d}=d^{2}-1$ and in the case of $G_{d}$ can put
$C_{V}=(9.5)^{d^{2}-1}$, so

$B=-\frac{d^{2}-1}{\mathrm{gap}(\mathcal{S})}\mathrm{log}(4.75)\mathrm{.}$
(74)

The values of constant $C_{V}$ bounding the volume of a ball in various groups
can be obtained by techniques from [22].

Note that Theorem 3 cannot be stated in analogous form for the $t$-averaging
operators $T_{\nu_{\mathcal{S}},t}$, since the normalized indicator function
(65) does not belong to $L^{2}_{t}(G_{d})$ for any $t$ so we cannot write (68)
for $T_{\nu_{\mathcal{S}},t}$ instead of $T_{\nu_{\mathcal{S}}}$. However, by
considering appropriate approximations of Dirac delta by polynomials from
$L^{2}_{t}(G_{d})$, we can show that

$\int_{\Omega}\left(T_{\nu_{\mathcal{S}},t}^{\ell}f\right)(g)d\mu(g)$ (75)

is sufficiently small and hence obtain analogous results. In particular, it is
known that

$\ell\geq\frac{C\cdot\mathrm{log}\left(\frac{1}{\epsilon}\right)}{\mathrm{gap}_{r}(\mathcal{S})}\mathrm{,}$
(76)

where $r=D/\epsilon^{2(d^{2}-1)+2}$ and $C,D$ are some constants [20]. This
result has been improved in case of $\mathrm{U}(d)$ in [21], where

$\ell\geq\frac{(d^{2}-1)(2\mathrm{log}\left(\frac{1}{\epsilon}\right)+\mathrm{log}(4C_{b}^{3/2}d))+\mathrm{log}(32)}{\mathrm{gap}_{t}(\mathcal{S})}\mathrm{,}$
(77)

for some absolute constant $C_{b}$ and $t\geq
5d^{5/2}/\epsilon\cdot\tau(\epsilon,d)$, where $\tau(\epsilon,d)$ is

$\tau(\epsilon,d)=\mathrm{log}^{\frac{1}{2}}(6C_{b}/\epsilon)\cdot\sqrt{\frac{1}{32}\mathrm{log}^{\frac{1}{2}}(6C_{b}/\epsilon)+\mathrm{log}\left(\frac{d}{\epsilon}\cdot\mathrm{log}^{\frac{1}{2}}(6C_{b}/\epsilon)\right)}\mathrm{.}$
(78)

##  4 Calculable lower bound on spectral gap

In this section, we derive lower bounds on the spectral gap at scale $t$ for
$\mathcal{S}\subset G_{d}$, such that any two pairs in $\mathcal{S}$ (of gate
with its inverse) form an universal set themselves. This condition can be
verified numerically by known universality criteria, see e.g. [23].

Our bound for any $t$ can be calculated from the knowledge of certain gaps up
to some fixed $t_{0}=t_{0}(d)$ and is of the form

$\mathrm{gap}_{t}(\mathcal{S})\geq\alpha\cdot
g_{t_{0}}(\mathcal{S})\cdot\mathrm{log}(\beta t)^{-2c}\mathrm{,}$ (79)

where $\alpha,\beta,c>0$ are some specific calculable constants and
$g_{t_{0}}(\mathcal{S})$ can be determined numerically by calculating gaps of
certain sets derived from $\mathcal{S}$ up to some calculable scale $t_{0}$.

We study the action of the $t$-averaging operator wrt to $\mathcal{S}$,

$T_{\nu_{\mathcal{S}},t}\coloneqq\bigoplus_{\lambda\in\Lambda_{t}}\pi_{\lambda}(\nu_{S})\mathrm{,}$
(80)

acting on the Hilbert space

$\mathcal{H}_{t}=\bigoplus_{\lambda\in\Lambda_{t}}\mathcal{H}_{\lambda}\mathrm{.}$
(81)

By $S(\mathcal{H}_{\lambda})$ we denote the unit sphere in
$\mathcal{H}_{\lambda}$,

$S(\mathcal{H}_{\lambda})=\\{w\in\mathcal{H}_{\lambda}|\,||w||=1\\}\mathrm{.}$
(82)

We choose the orthonormal basis

$\\{w^{\lambda}_{ij}|\,1\leq i,j\leq d_{\lambda},\,\lambda\in\Lambda_{t}\\}$
(83)

of $\mathcal{H}_{t}$, induced by the basis (11). Clearly,
$||T_{\nu_{\mathcal{S},t}}||_{op}\leq 1$ and our goal is to improve this
bound. The irreps $\Lambda_{t}$ of $G_{d}$ can be divided into three disjoint
sets, based on the type of the representation of $\mathrm{U}(d)$ they come
from:

$\Lambda_{t}=\Lambda_{t,\mathbb{H}}\cap\Lambda_{t,\mathbb{R}}\cap\Lambda_{t,\mathbb{C}}\mathrm{,}$
(84)

where $\mathbb{H}$, $\mathbb{R}$ and $\mathbb{C}$ stands for quaternionic,
real and complex representations. In fact, $\Lambda_{t,\mathbb{H}}=\emptyset$
since quaternionic representations of $\mathrm{U}(d)$ do not contribute to
projective representations.

Since

$||\tilde{T}_{\nu_{\mathcal{S}},t}||_{op}=\mathrm{max}_{\lambda\in\tilde{\Lambda}_{t}}||\pi_{\lambda}(\nu_{\mathcal{S}})||_{op}\mathrm{,}$
(85)

we fix any $\lambda\in\tilde{\Lambda}_{t}$ and consider
$||\pi_{\lambda}(\nu_{\mathcal{S}})||_{op}$.

Additionally we assume $\mathcal{S}=\\{U_{1},\ldots,U_{k},U_{1}^{-1},\ldots
U_{k}^{-1}\\}$ is generic so that for each $1\leq i\neq j\leq k$, the set
$\\{U_{i}^{2},U_{j}^{2},U_{i}^{-2},U_{j}^{-2}\\}$ is a universal symmetric
set.
Strategy of the proof
Our strategy is to show that for any $\lambda\in\tilde{\Lambda}_{t}$, any
$w\in S(\mathcal{H}_{\lambda})$ and any generator $U_{m}\in\mathcal{S}$,
except for at least one, say $U_{k}$,

$||(\pi_{\lambda}(U_{i})+\pi_{\lambda}(U_{i}^{-1}))w||\leq 2-(b_{i}/2)^{2}$
(86)

for some coefficients $b_{i}^{2}=b_{i}^{2}(\lambda)>0$ which can be bounded by
gaps of certain subsets of the set
$\mathcal{S}^{2}=\\{U_{1}^{2},\ldots,U_{k}^{2},U_{1}^{-2},\ldots
U_{k}^{-2}\\}$ at some known scale $t_{0}$. Hence,

$||\pi_{\lambda}(\nu_{\mathcal{S}})w||\leq\frac{1}{|\mathcal{S}|}\left[\sum_{1\leq
i<k}||(\pi_{\lambda}(U_{i})+\pi_{\lambda}(U_{i}^{-1}))w||+2\right]\leq
1-\frac{1}{4|\mathcal{S}|}\sum_{i=1}^{|\mathcal{S}|/2-1}b_{i}^{2}(\lambda)\mathrm{,}$
(87)

which implies

$\mathrm{gap}_{t}(\mathcal{S})\geq\mathrm{min}_{\lambda\in\tilde{\Lambda}_{t}}\frac{1}{4|\mathcal{S}|}\sum_{i=1}^{|\mathcal{S}|/2-1}b_{i}^{2}(\lambda)>0\mathrm{.}$
(88)

This means that we can obtain a non-trivial lower bound on
$\mathrm{gap}_{t}(S)$ for any $t\geq t_{0}$. Crucially, the value of $t_{0}$
can be easily determined and is not large, so the numerical calculations of
the bound are feasible.
The main reasoning
Since $\pi_{\lambda}(g_{i})$ is unitary we have

$||(\pi_{\lambda}(g_{i})+\pi_{\lambda}(g_{i}^{-1}))w||^{2}=4-||(\pi_{\lambda}(g_{i})-\pi_{\lambda}(g_{i}^{-1}))w||^{2}$
(89)

for any $w\in S(\mathcal{H}_{\lambda})$. Let $\imath_{\lambda}$ denote the
Frobenius-Schur indicator of $\pi_{\lambda}$,

$\imath_{\lambda}=\int_{G_{d}}\chi_{\lambda}(g^{2})d\mu(g)=\begin{cases}-1,\quad\mathrm{if}\,\lambda\in\Lambda_{t,\mathbb{H}},\\\
0,\quad\mathrm{if}\,\lambda\in\Lambda_{t,\mathbb{C}}\mathrm{,}\\\
1,\quad\mathrm{if}\,\lambda\in\Lambda_{t,\mathbb{R}}\mathrm{.}\end{cases}\mathrm{.}$
(90)

Note that

$\int_{G_{d}}\pi_{\lambda}(g^{2})d\mu(g)=\frac{\imath_{\lambda}}{d_{\lambda}}\mathbb{I_{\lambda}}$
(91)

since the LHS is a self-intertwiner.

Observe that since $||\lambda||_{1}>0$, for any $i,j$ and $p,q$ we have

$\int_{G}\langle\pi_{\lambda}(g^{2})w_{ij}^{\lambda},w_{pq}^{\lambda}\rangle
d\mu(g)=\frac{\imath_{\lambda}}{d_{\lambda}}||w_{ij}^{\lambda}||^{2}\delta_{ip}\delta_{jq}\mathcal{.}$
(92)

Hence, for any $w\in S(\mathcal{H}_{\lambda})$

$\int_{G}\langle\pi_{\lambda}(g^{2})w,w\rangle
d\mu(g)=\frac{\mathrm{\imath_{\lambda}}}{d_{\lambda}}\mathrm{,}$ (93)

so for any $\lambda\in\Lambda_{t}$, there exists $h=h(w)\in G_{d}$ such that
$\mathfrak{Re}\langle\pi_{\lambda}(h^{2})w,w\rangle<\frac{\imath_{\lambda}}{d_{\lambda}}$
and

$||(\pi_{\lambda}(h)-\pi_{\lambda}(h^{-1}))w||>\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}\mathrm{.}$
(94)

Note that if $\lambda$ is quaternionic the bound is even better.

We want to connect $h^{2}$ with some square of a generator $g_{i}^{2}$ so that
the large value of above norm will propagate to large value of
$||(\pi_{\lambda}(g_{i}^{2})-\pi_{\lambda}(e))w||$. Let

$\mathcal{S}^{2}\coloneqq\\{U_{1}^{2},\ldots,U_{k}^{2},U_{1}^{-2},\ldots
U_{k}^{-2}\\}$ (95)

and by $\mathcal{S}^{2}_{j_{1}\ldots j_{m}}$ we denote the set
$\mathcal{S}^{2}$ without elements $U^{2}_{j_{1}},\ldots,U^{2}_{j_{m}}$ (and
their inverses),

$\mathcal{S}^{2}_{j_{1}\ldots
j_{m}}\coloneqq\mathcal{S}^{2}\setminus\\{U^{2}_{j_{1}},U^{-2}_{j_{1}}\ldots,U^{2}_{j_{m}},U^{-2}_{j_{m}}\\}\mathrm{.}$
(96)

By the assumption, each set $\mathcal{S}^{2}_{j_{1}\ldots j_{m}}$ is universal
for $1\leq m\leq k-2$. Consider any $\mathcal{S}^{2}_{j_{1}\ldots j_{m}}$ (we
allow $\mathcal{S}^{2}$ as the special case with $m=0$). We find an
$\epsilon_{j_{1}\ldots j_{m}}$-approximation of $h^{2}$ in terms of squares
generators, namely we write $\tilde{h}=g_{1}^{2}g_{2}^{2}\ldots
g_{\ell_{j_{1}\ldots j_{m}}}^{2}$ , where each
$g_{i}^{2}\in\mathcal{S}^{2}_{j_{1}\ldots j_{m}}$, so that
$D(h^{2},\tilde{h})<\epsilon$ and we specify $1>\epsilon_{j_{1}\ldots
j_{m}}>0$ later. We have

$\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}<||(\pi_{\lambda}(h^{2})-\pi_{\lambda}(e))w||\leq||(\pi_{\lambda}(e)-\pi_{\lambda}(\tilde{h}))w||+||(\pi_{\lambda}(\tilde{h})-\pi_{\lambda}(h^{2}))w||$
(97)

so

$\displaystyle||(\pi_{\lambda}(e)-\pi_{\lambda}(\tilde{h}))w||$
$\displaystyle\geq\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}-||(\pi_{\lambda}(\tilde{h})-\pi_{\lambda}(h^{2}))w||$
(98)
$\displaystyle\geq\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}-||\pi_{\lambda}(\tilde{h})-\pi_{\lambda}(h^{2})||_{op}\mathrm{.}$

From the unitary invariance of operator norm

$||\pi_{\lambda}(\tilde{h})-\pi_{\lambda}(h^{2})||_{op}=||\pi_{\lambda}(e)-\pi_{\lambda}(\bar{h})||_{op}\mathrm{,}$
(99)

where $\bar{h}=\tilde{h}^{-1}h^{2}$ and $D(e,\bar{h})<\epsilon_{j_{1}\ldots
j_{m}}$. Let us fix a maximal torus $T\subset G_{d}$ with Lie algebra
$\mathfrak{t}\subset\mathfrak{su}(d)$. We can write $\bar{h}=gtg^{-1}$, where
$t\in T$ and $g\in G$. Clearly,

$\mathrm{Spec}(\pi_{\lambda}(\bar{h}))=\mathrm{Spec}(\pi_{\lambda}(t))\mathrm{.}$
(100)

Let $\\{e^{i\gamma_{1}},\ldots,e^{i\gamma_{d_{\lambda}}}\\}$ be the spectrum
of $\pi_{\lambda}(t)$ and $\\{w_{1},\ldots,w_{d_{\lambda}}\\}$ be an
orthonormal basis of $\mathcal{H}_{\lambda}$ in which

$\pi_{\lambda}(t)w_{j}=e^{i\gamma_{j}}w_{j}$ (101)

for $1\leq j\leq d_{\lambda}$. By the definition of a real weight we have

$|\gamma_{j}|=|\langle\mu_{j},H\rangle|=|(H_{\mu_{j}},H)|\leq||\lambda||_{1}\cdot\mathrm{max}_{i}|\theta_{i}|$
(102)

for some weight $\mu_{j}$ of irrep $\pi_{\lambda}$ and
$H=\mathrm{log}(t)=\mathrm{diag}(i\theta_{1},\ldots,i\theta_{d})\in\mathfrak{t}$.
555 Note that $D(e,\bar{h})=D(e,t)<\epsilon_{j_{1}\ldots j_{m}}<1$ so
$\mathrm{log}(t)$ exists. We assume $\theta_{i}\in(-\pi,\pi]$ for each $i$.
Since $D(e,t)<\epsilon_{j_{1}\ldots j_{m}}$ we have

$|\theta_{i}|/\pi\leq\;|\mathrm{sin}(\theta_{i}/2)|<\epsilon_{j_{1}\ldots
j_{m}}/2$ (103)

for each $i$, so

$|\gamma_{j}|\leq\pi||\lambda||_{1}\epsilon_{j_{1}\ldots j_{m}}/2\mathrm{.}$
(104)

Finally,

$||\pi_{\lambda}(e)-\pi_{\lambda}(\bar{h})||_{op}=||\pi_{\lambda}(e)-\pi_{\lambda}(t)||_{op}\leq
2\,\mathrm{max}_{i}\,|\mathrm{sin(\gamma_{i}/2)}|\leq\mathrm{max}_{i}\,|\gamma_{i}|$
(105)

hence

$||\pi_{\lambda}(e)-\pi_{\lambda}(\bar{h})||_{op}\leq
C||\lambda||_{1}\cdot\epsilon_{j_{1}\ldots j_{m}}\mathrm{,}$ (106)

where $C=\pi/2$. Thus,

$||(\pi_{\lambda}(e)-\pi_{\lambda}(\tilde{h}))w||\geq\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}-C||\lambda||_{1}\cdot\epsilon_{j_{1}\ldots
j_{m}}\mathrm{.}$ (107)

We use triangle inequality to propagate the result into some generator.

$\displaystyle\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}-C||\lambda||_{1}\epsilon_{j_{1}\ldots
j_{m}}\leq||(\pi_{\lambda}(e)-\pi_{\lambda}(\tilde{h}))w||$ (108)
$\displaystyle=||(\pi_{\lambda}(e)-\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots
g_{\ell}^{2}))w||\leq||(\pi_{\lambda}(e)-\pi_{\lambda}(g_{1}^{2})))w||+||(\pi_{\lambda}(g_{1}^{2})-\pi_{\lambda}(g_{1}^{2}g_{2}^{2})))w||+\ldots$
$\displaystyle+||(\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots
g_{i-1}^{2})-\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots
g_{i}^{2})))w||+\ldots+||(\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots
g_{\ell-1}^{2})-\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots g_{\ell}^{2})))w||$

so there exists $i$ such that

$||(\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots
g_{i-1}^{2})-\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots g_{i}^{2})))w||\geq
b_{j_{1}\ldots j_{m}}(\lambda)\mathrm{,}$ (109)

where

$b_{j_{1}\ldots
j_{m}}(\lambda)=\frac{\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}-C||\lambda||_{1}\epsilon_{j_{1}\ldots
j_{m}}}{\ell_{j_{1}\ldots j_{m}}}$ (110)

and from the unitary invariance of operator norm

$||(\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots
g_{i-1}^{2})-\pi_{\lambda}(g_{1}^{2}g_{2}^{2}\ldots
g_{i}^{2})))w||=||(\pi_{\lambda}(e)-\pi_{\lambda}(g_{i}^{2})))w||$ (111)

Since $g_{i}^{2}$ is an element from $\mathcal{S}^{2}_{j_{1}\ldots j_{m}}$ and

$||(\pi_{\lambda}(e)-\pi_{\lambda}(g_{i}^{2}))w||=||(\pi_{\lambda}(e)-\pi_{\lambda}(g_{i}^{-2}))w||\mathrm{,}$
(112)

there exists $i_{q}$, where $1\leq q\leq m$, such that

$||(\pi_{\lambda}(e)-\pi_{\lambda}(U_{i_{q}}^{2}))w||\geq b_{j_{1}\ldots
j_{m}}(\lambda)\geq b_{m}(\lambda)\mathrm{,}$ (113)

where

$b_{m}(\lambda)\coloneqq\mathrm{min}_{i_{1},\ldots,i_{m}}b_{i_{1}\ldots
i_{m}}(\lambda)$ (114)

is the bound for the worst choice of $i_{1},\ldots,i_{m}$, which we denote
$\mathcal{S}^{2}_{m}$ 666Note that $b_{m}(\lambda)\geq b_{n}(\lambda)$ for
$m<n$.. The set $\mathcal{S}^{2}_{m}$ has the corresponding $\epsilon_{m}$ and
$\ell_{m}$ via (110).

We proceed as follows. First, we consider above procedure for
$\mathcal{S}^{2}$ and obtain

$||(\pi_{\lambda}(e)-\pi_{\lambda}(U_{i_{1}}^{2}))w||\geq
b_{0}(\lambda)\mathrm{,}$ (115)

for some $U_{i_{1}}^{2}\in\mathcal{S}^{2}$. Next, we repeat the argument for
$\mathcal{S}^{2}_{i_{1}}$ and get

$||(\pi_{\lambda}(e)-\pi_{\lambda}(U_{i_{2}}^{2}))w||\geq
b_{i_{1}}(\lambda)\geq b_{1}(\lambda)\mathrm{,}$ (116)

for some $U_{i_{2}}^{2}\in\mathcal{S}^{2}_{i_{1}}$. We proceed in this manner
until $m=k-2$, which gives

$||(\pi_{\lambda}(e)-\pi_{\lambda}(U_{i_{k-1}}^{2}))w||\geq
b_{i_{1}i_{2}\ldots i_{k-2}}(\lambda)\geq b_{k-2}(\lambda)\mathrm{,}$ (117)

for some $U_{i_{k-1}}^{2}\in\mathcal{S}^{2}_{i_{1}\ldots i_{k-2}}$.

This way we obtain bounds for each pair generators except for one pair
$\\{U^{2}_{i_{k}},U^{-2}_{i_{k}}\\}$, where $1\leq i_{k}\leq k$ is the
remaining index. Thus, using (89), for all $i_{m}$ with
$m\in\\{1,\ldots,k-1\\}$ we have

$||(\pi_{\lambda}(U_{i_{m}})+\pi_{\lambda}(U_{i_{m}}^{-1})))w||\leq\sqrt{4-b_{m-1}^{2}(\lambda)}$
(118)

provided that

$\epsilon_{m}\leq\frac{\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}}{C||\lambda||_{1}},\epsilon_{m}<1\mathrm{.}$
(119)

For $\ell_{m-1}\gg 1$, the good approximation is

$\sqrt{4-b^{2}_{m-1}(\lambda)}\leq
2-\left(\frac{b_{m-1}(\lambda)}{2}\right)^{2}\mathrm{.}$ (120)

Hence,

$\mathrm{gap}_{t}(\mathcal{S})\geq\mathrm{min}_{\lambda\in\tilde{\Lambda}_{t}}\frac{1}{8k}\sum_{m=0}^{k-2}b_{m}^{2}(\lambda)>0\mathcal{.}$
(121)

Using similar argument by considering only $\mathcal{S}^{2}_{i_{1}\ldots
i_{k-2}}$ and bounding all pairs simultaneously we have the following, weaker
bound

$\mathrm{gap}_{t}(\mathcal{S})\geq\mathrm{min}_{\lambda\in\tilde{\Lambda}_{t}}\frac{k-1}{8k}b_{k-2}^{2}(\lambda)>0\mathcal{.}$
(122)

Indeed, comparing (121) and (122) we have the inequality

$\frac{1}{8k}\sum_{m=0}^{k-2}b_{m}^{2}(\lambda)\geq\frac{k-1}{8k}b_{k-2}^{2}(\lambda)\mathrm{.}$
(123)

Moreover, the ratio between LHS and RHS of (123) is

$\frac{\frac{1}{k-1}\sum_{m=0}^{k-2}b_{m}^{2}(\lambda)}{b_{k-2}^{2}(\lambda)}\mathrm{,}$
(124)

i.e. it is ratio between the average of a nonincreasing sequence
$b_{0}^{2},b_{1}^{2},\ldots,b^{2}_{k-2}$ and its smallest element
$b^{2}_{k-2}$. Since we expect this sequence to (generically) quickly
decrease, we suppose that the bound (121) is (relatively) much better than
(122), at least generically.

It remains to somehow simultaneously bound the coefficients $b_{m}(\lambda)$
for all $\lambda\in\tilde{\Lambda}_{t}$. Since
$\ell_{m}\leq\mathrm{diam}_{\epsilon}(G,\mathcal{S}^{2}_{m})$, from (121),
(110) we obtain the bound for the gap from the diameter

$\mathrm{gap}_{t}(\mathcal{S})\geq\mathrm{min}_{\lambda\in\tilde{\Lambda}_{t}}\frac{1}{8k}\sum_{m=0}^{k-2}\left(\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}-C||\lambda||_{1}\epsilon_{m}(\lambda)\right)^{2}\frac{1}{\mathrm{diam}_{\epsilon_{m}(\lambda)}(G,\mathcal{S}^{2}_{m})^{2}}$
(125)

valid for

$0<\epsilon_{m}(\lambda)\leq\frac{\sqrt{2\left(1-\frac{\imath_{\lambda}}{d_{\lambda}}\right)}}{C||\lambda||_{1}},\epsilon_{m}(\lambda)<1\mathrm{,}$
(126)

which can be weakened to the following simplified bound

$\mathrm{gap}_{t}(\mathcal{S})\geq\frac{1}{8k}\sum_{m=0}^{k-2}\left(1-2Ct\epsilon_{m}\right)^{2}\frac{1}{\mathrm{diam}_{\epsilon_{m}}(G,\mathcal{S}^{2}_{m})^{2}}$
(127)

valid for

$0<\epsilon_{m}\leq\frac{1}{2Ct},\epsilon_{m}<1\mathrm{.}$ (128)

We have a trade-off between the contribution of $\epsilon_{m}$ to the
numerator of multiplicative term (the smaller the $\epsilon_{m}$ the better)
and to the diameter (the larger the $\epsilon_{m}$ the better).

Because we do not know how
$\mathrm{diam}_{\epsilon_{m}}(G,\mathcal{S}_{m}^{2})$ depends on
$\epsilon_{m}$, in order to proceed we can use Solovay-Kitaev theorem for
$\mathcal{S}^{2}_{m}$ to bound

$\mathrm{diam}_{\epsilon_{m}}(G,\mathcal{S}_{m}^{2})\leq
A_{m}\cdot\mathrm{log}^{c}\left(\frac{1}{c_{s}^{2}\epsilon_{m}}\right),\quad
A_{m}=\frac{1}{\left[2\mathrm{log}\left(\frac{1}{c_{s}\epsilon_{0,m}}\right)\right]^{c}}\ell_{0,m}$
(129)

where $c=\mathrm{log}(5)/\mathrm{log}(3/2)\approx 4$, $c_{s}$ is some constant
($c_{s}=d+2+\mathcal{O}(\epsilon)$), $\epsilon_{0,m}$ is the $\epsilon$ of
initial approximation in Solovay-Kitaev algorithm and $\ell_{0,m}$ is the word
length of this approximation. Thus,

$\mathrm{gap}_{t}(\mathcal{S})\geq\frac{1}{8k}\sum_{m=0}^{k-2}\left(\frac{1-2Ct\epsilon_{m}}{A_{m}}\right)^{2}\mathrm{log}^{-2c}(c_{s}^{-2}\epsilon_{m}^{-1})$
(130)

for any

$0<\epsilon_{m}\leq\frac{1}{2Ct},\epsilon_{m}<1\mathrm{.}$ (131)

We can bound $\ell_{0,m}$ by (77),

$\ell_{0,m}\geq\frac{(d^{2}-1)(2\mathrm{log}\left(\frac{1}{\epsilon_{0,m}}\right)+\mathrm{log}(4C_{b}^{3/2}d))+\mathrm{log}(32)}{\mathrm{gap}_{t_{0,m}}(\mathcal{S}^{2}_{m})}\mathrm{,}$
(132)

for $C_{b}=9\pi$ and $t_{0,m}\geq
5d^{5/2}/\epsilon_{0,m}\cdot\tau(\epsilon_{0,m},d)$.

For simplicity, we set the common $\epsilon_{0,m}=\epsilon_{0}$ and put
$\epsilon_{m}=1/(4Ct)$, which yields

$\mathrm{gap}_{t}(\mathcal{S})\geq\frac{1}{32k}\sum_{m=0}^{k-2}\frac{1}{A_{m}^{2}}\mathrm{log}^{-2c}(4c_{s}^{-2}Ct)=\frac{1}{32k}\sum_{m=0}^{k-2}\frac{1}{\ell_{0,m}^{2}}\left[2\mathrm{log}(c_{s}^{-1}\epsilon_{0}^{-1})\right]^{2c}\mathrm{log}^{-2c}(4c_{s}^{-2}Ct)\mathrm{,}$
(133)

and by setting the common scale $t_{0,m}=t_{0}\coloneqq
5d^{5/2}/{\epsilon_{0}}\cdot\tau(\epsilon_{0},d)$ and using (132) to set the
value of $\ell_{0,m}$ we obtain

$\mathrm{gap}_{t}(\mathcal{S})\geq\frac{1}{32k}\sum_{m=0}^{k-2}\frac{\mathrm{gap}^{2}_{t_{0}}(\mathcal{S}^{2}_{m})}{\left((d^{2}-1)(2\mathrm{log}(\epsilon_{0}^{-1})+\mathrm{log}(4C_{b}^{3/2}d))+\mathrm{log}(32)\right)^{2}}\left[\frac{2\mathrm{log}(c_{s}^{-1}\epsilon_{0}^{-1})}{\mathrm{log}(4c_{s}^{-2}Ct)}\right]^{2c}\mathrm{,}$
(134)

which can be rewritten as

$\mathrm{gap}_{t}(\mathcal{S})\geq\alpha\cdot
g_{t_{0}}(\mathcal{S})\cdot\mathrm{log}^{-2c}(\beta t)\mathrm{,}$ (135)

where $\alpha$ and $\beta$ are

$\alpha\coloneqq\frac{\left[2\mathrm{log}(c_{s}^{-1}\epsilon_{0}^{-1})\right]^{2c}}{16\cdot\left((d^{2}-1)(2\mathrm{log}(\epsilon_{0}^{-1})+\mathrm{log}(4C_{b}^{3/2}d))+\mathrm{log}(32)\right)^{2}}\mathrm{,}\quad\beta\coloneqq\frac{4C}{c_{s}^{2}}\mathrm{,}$
(136)

and

$g_{t_{0}}(\mathcal{S})\coloneqq\frac{1}{|\mathcal{S}|}\sum_{m=0}^{|\mathcal{S}|/2-2}\mathrm{gap}^{2}_{t_{0}}(\mathcal{S}^{2}_{m})\mathcal{.}$
(137)

Finally, we can redefine $\mathrm{gap}_{t_{0}}(\mathcal{S}^{2}_{m})$ to be the
smallest value of a gap at scale $t_{0}$ over all sets
$\mathcal{S}^{2}_{i_{1}\ldots i_{m}}$,

$\mathrm{gap}_{t_{0}}(\mathcal{S}^{2}_{m})\coloneqq\mathrm{argmin}_{i_{1},\ldots,i_{m}}\mathrm{gap}_{t_{0}}(\mathcal{S}^{2}_{i_{1}\ldots
i_{m}})$ (138)

and this way $g_{t_{0}}(\mathcal{S})$ can be determined numerically by the
calculations at scale

$t_{0}\coloneqq 5d^{5/2}/{\epsilon_{0}}\cdot\tau(\epsilon_{0},d)\mathrm{.}$
(139)

## Acknowledgments

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

## References

  * [1] E. Knill, R. Laflamme and W. H. Zurek  “Resilient Quantum Computation”  In _Science_ 279, 1998, pp. 342––345
  * [2] A. Y. Kitaev  “Fault-tolerant quantum computation by anyons”  In _Science_ 303, 2003, pp. 2–30
  * [3] D. Aharonov and M. Ben-Or  “Fault-Tolerant Quantum Computation with Constant Error Rate”  In _SIAM Journal on Computing_ 38, 2008, pp. 1207–1282
  * [4] A. W. Harrow and A. Montanaro  “Quantum Computational Supremacy”  In _Nature_ 549, 2017, pp. 203–209
  * [5] J. Preskill  “Quantum Computing in the NISQ era and beyond”  In _Quantum_ 2, 2018
  * [6] S. Boixo et al.  “Characterizing Quantum Supremacy in Near-Term Devices”  In _Nature Physics_ 14, 2018, pp. 595–600
  * [7] A. Sawicki and K. Karnas  “Universality of Single-Qudit Gates”  In _Annales Henri Poincaré_ 18, 2017, pp. 3515–3552
  * [8] A. Sawicki and K. Karnas  “Criteria for universality of quantum gates”  In _Physical Review A_ 95, 2017, pp. 062303
  * [9] H. Kesten  “Symmetric Random Walks on Groups”  In _Transactions of the American Mathematical Society_ 92, 1959, pp. 336–354
  * [10] A. Y. Kitaev, A. Shen and M. N. Vyalyi  “Classical and quantum computation”  Providence, Rhode Island: American Mathematical Society, 2002
  * [11] A. W. Harrow, B. Recht and I. L. Chuang  “Efficient Discrete Approximations of Quantum Gates”  In _Journal of Mathematical Physics_ 43, 2002, pp. 4445–4451
  * [12] J. Bourgain and A. Gamburd  “On the spectral gap for finitely-generated subgroups of SU(2)”  In _Inventiones Mathematicae_ 171, 2008, pp. 83––121
  * [13] J. Bourgain and A. Gamburd  “A spectral gap theorem in SU(d)”  In _Journal of the European Mathematical Society_ 14, 2012, pp. 1455–1511
  * [14] A. Lubotzky, R. Phillips and P. Sarnak  “Hecke operators and distributing points on the Sphere I”  In _Communications on Pure and Applied Mathematics. Supplement: Proceedings of the Symposium on Frontiers of the Mathematical Sciences: 1985._ 39, 1986, pp. S149–S186
  * [15] A. Lubotzky, R. Phillips and P. Sarnak  “Hecke operators and distributing points on S2. II”  In _Communications on Pure and Applied Mathematics_ 40, 1987, pp. 401–420
  * [16] A. Bocharov, Y. Gurevich and K. M. Svore  “Efficient decomposition of single-qubit gates into V basis circuits”  In _Physical Review A_ 88, 2013
  * [17] P. Selinger  “Efficient Clifford+T approximation of single-qubit operators”  In _Quantum Information and Computation_ 15, 2015, pp. 159–180
  * [18] P. Sarnak  “Letter to Scott Aaronson and Andy Pollington on the Solovay-Kitaev theorem”, 2015
  * [19] V. Kliuchnikov, D. Maslov and M. Mosca  “Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits”  In _IEEE Transactions on Computers_ 65, 2016, pp. 161–172
  * [20] P. P. Varjú  “Random walks in compact groups”  In _Documenta Mathematica_ 18, 2013, pp. 1137–1175
  * [21] 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
  * [22] S. J. Szarek  “Metric Entropy of Homogeneous Spaces”  In _Banach Center Publications_ 43, 1998
  * [23] A. Sawicki, L. Mattioli and Z. Zimborás  “How to check universality of quantum gates?”  In _arXiv:2111.03862_ , 2021