Efficient decomposition of single-qubit gates intoVbasis circuits

We develop efficient algorithms for compiling single-qubit unitary gates into circuits over the universal V basis. The V basis is an alternative universal basis to the more commonly studied basis consisting of Hadamard and /8 gates. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time in precision log (1/) and produces an approximation to a single-qubit unitary with a circuit depth 120. 16em{0ex}log₅ (2/). The second algorithm performs optimized direct search and yields circuits a factor of 3 to 4 times shorter than our first algorithm, but requires time exponential in log (1/) ; however, we show that in practice the runtime is reasonable for an important range of target precisions. Decomposing into the V basis may offer advantages when considering the fault-tolerant implementation of quantum circuits.