A Note on a Quantitative Form of the Solovay-Kitaev Theorem

Abstract

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 $\epsilon >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 $\epsilon >0$ small enough, we define $t_{\epsilon }$ as the minimum reduced word length such that every point of $SU(2)$ lies within a ball of radius $\epsilon$ 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 )\to (1,\infty )$ satisfying ${\lim }_{\epsilon \to 0+}\frac{\log (f(t_{\epsilon }))}{t_{\epsilon }}$ exists with value $0$. Assume that the inequality $\epsilon ⩽f(t_{\epsilon })\cdot 5^{\frac{-t_{\epsilon }}{6-3\delta }}$ holds. Then $K(T)⩽2-\delta$. Our conjecture implies the following: Let $\nu (5^{t_{\epsilon }})$ denote the set of integer solutions of the quadratic form: $x_1^2+x_2^2+x_3^2+x_4^2=5^{t_{\epsilon }}$. Let $M\equiv M_{S^3}(\mathcal{N})$ denote the covering radius of the points $\mathcal{N}=\nu (5^{t_{\epsilon }})\cup \nu (5^{t_{\epsilon }-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(\epsilon )=6\cdot 5^{t_{\epsilon }}-2$.

arXiv commentThe work in this paper appears in: S. B. Damelin, Whitney extensions of smooth near isometries, shortest paths, BMO, equidistribution, clustering and non-rigid alignment of data in Euclidean space, John Wiley & Sons 2024

Cited by in corpus (1)

• Certifying Numerical Decompositions of Compact Group Representations