  We present an algorithm for efficiently approximating of qubit unitaries over
gate sets derived from totally definite quaternion algebras. It achieves
$\varepsilon$-approximations using circuits of length $O(\log(1/\varepsilon))$,
which is asymptotically optimal. The algorithm achieves the same quality of
approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253],
V-basis [arXiv:1303.1411] and Clifford+$\pi/12$ [arXiv:1409.3552], running on
average in time polynomial in $O(\log(1/\varepsilon))$ (conditional on a
number-theoretic conjecture). Ours is the first such algorithm that works for a
wide range of gate sets and provides insight into what should constitute a
"good" gate set for a fault-tolerant quantum computer.
