The problem of finding good approximations of arbitrary 1-qubit gates is identical to that of finding a dense group generated by a universal subset of $SU(2)$ to approximate an arbitrary element of $SU(2)$. The Solovay-Kitaev Theorem is a well-known theorem that guarantees the existence of a finite sequence of 1-qubit quantum gates approximating an arbitrary unitary matrix in $SU(2)$ within specified accuracy $\varepsilon > 0$. In this note we study a quantitative description of this theorem in the following sense. We will work with a universal gate set $T$, a subset of $SU(2)$ such that the group generated by the elements of $T$ is dense in $SU(2)$. For $\varepsilon > 0$ small enough, we define $t_{ \varepsilon}$ as the minimum reduced word length such that every point of $SU(2)$ lies within a ball of radius $\varepsilon$ centered at the points in the dense subgroup generated by $T$. For a measure of efficiency on T, which we denote $K(T)$, we prove the following theorem: Fix a $\delta$ in $[0, \frac{ 2}{ 3}]$. Choose $f: (0, \infty) \rightarrow (1, \infty)$ satisfying $\lim_{ \varepsilon\to 0+}\dfrac{ \log(f(t_{ \varepsilon}))}{ t_{ \varepsilon}}$ exists with value $0$. Assume that the inequality $\varepsilon \leqslant f(t_{ \varepsilon})\cdot 5^{ \frac{ -t_{ \varepsilon}}{ 6-3\delta}}$ holds. Then $K(T) \leqslant 2-\delta$. Our conjecture implies the following: Let $\nu(5^{ t_{ \varepsilon}})$ denote the set of integer solutions of the quadratic form: $x_1^2+x_2^2+x_3^2+x_4^2=5^{ t_{ \varepsilon}}$. Let $M\equiv M_{ S^3}(\mathcal{ N})$ denote the covering radius of the points $\mathcal{ N}=\nu(5^{ t_{ \varepsilon}})\cup\nu(5^{ t_{ \varepsilon}-1})$ on the sphere $S^{ 3}$ in $\mathbb{ R}^{ 4}$. Then $M \sim f(\log N)N^{ \frac{ -1}{ 6-3\delta}}$. Here $N\equiv N(\varepsilon)=6\cdot5^{ t_{ \varepsilon}}-2$.
Categories: math.QA quant-ph