Paper detail

Efficient Clifford+T approximation of single-qubit operators

We give an efficient randomized algorithm for approximating an arbitrary element of $SU(2)$ by a product of Clifford+$T$ operators, up to any given error threshold $ε>0$. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in $\log(1/ε)$. If the operator to be approximated is a $z$-rotation, the resulting gate sequence has $T$-count $K+4\log_2(1/ε)$, where $K$ is approximately equal to $10$. We also prove a worst-case lower bound of $K+4\log_2(1/ε)$, where $K=-9$, so that our algorithm is within an additive constant of optimal for certain $z$-rotations. For an arbitrary member of $SU(2)$, we achieve approximations with $T$-count $K+12\log_2(1/ε)$. By contrast, the Solovay-Kitaev algorithm achieves $T$-count $O(\log^c(1/ε))$, where $c$ is approximately $3.97$.