1212.6253 (Peter Selinger)

Efficient Clifford+T approximation of single-qubit operators    [PDF]

Peter Selinger

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+4log_2(1/epsilon), where K is approximately equal to 11. 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 z-rotations. For an arbitrary member of SU(2), we achieve approximations with T-count 3K+12log_2(1/epsilon). By contrast, the Solovay-Kitaev algorithm achieves T-count O(log^c(1/epsilon)), where c is approximately 3.97.

View original: http://arxiv.org/abs/1212.6253