  An important task required to build a scalable, fault-tolerant quantum
computer is to efficiently represent an arbitrary single-qubit rotation by
fault-tolerant quantum operations. Traditionally, the method for decomposing a
single-qubit unitary into a discrete set of gates is Solovay-Kitaev
decomposition, which in practice produces a sequence of depth
O(\log^c(1/\epsilon)), where c~3.97 is the state-of-the-art. The proven lower
bound is c=1, however an efficient algorithm that saturates this bound is
unknown. In this paper, we present an alternative to Solovay-Kitaev
decomposition employing state distillation techniques which reduces c to
between 1.12 and 2.27, depending on the setting. For a given single-qubit
rotation, our protocol significantly lowers the length of the approximating
sequence and the number of required resource states (ancillary qubits). In
addition, our protocol is robust to noise in the resource states.
