EFFICIENT CLIFFORD plus 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 epsilon > 0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log(1/epsilon). If the operator to be approximated is a z-rotation, the resulting gate sequence has T-count K+4 log(2)(1/epsilon), where K is approximately equal to 10. We also prove a worst-case lower bound of K+4log(2)(1/epsilon), 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/epsilon). By contrast, the Solovay-Kitaev algorithm achieves T-count O(log(c)(1/epsilon)), where c is approximately 3.97.