  We present a decomposition technique that uses non-deterministic circuits to
approximate an arbitrary single-qubit unitary to within distance $\epsilon$ and
requires significantly fewer non-Clifford gates than existing techniques. We
develop "Repeat-Until-Success" (RUS) circuits and characterize unitaries that
can be exactly represented as an RUS circuit. Our RUS circuits operate by
conditioning on a given measurement outcome and using only a small number of
non-Clifford gates and ancilla qubits. We construct an algorithm based on RUS
circuits that approximates an arbitrary single-qubit $Z$-axis rotation to
within distance $\epsilon$, where the number of $T$ gates scales as
$1.26\log_2(1/\epsilon) - 3.53$, an improvement of roughly three-fold over
state-of-the-art techniques. We then extend our algorithm and show that a
scaling of $2.4\log_2(1/\epsilon) - 3.28$ can be achieved for arbitrary
unitaries and a small range of $\epsilon$, which is roughly twice as good as
optimal deterministic decomposition methods.

Quantum Physics