We present an algorithm for efficiently approximating qubit unitaries over gate sets derived from totally definite quaternion algebras. The algorithm achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T and a few other gate sets. Moreover, the algorithm to compile the efficient approximation is efficient as well: its running time is polynomial in O(log(1/ε)), conditional on a number-theoretic conjecture. Our algorithm works for a wide range of gate sets and might provide insight into what should constitute a "good" gate set for a fault-tolerant quantum computer.
Based on joint work with Alex Bocharov, Vadym Kliuchnikov, and Jon Yard: http://arxiv.org/abs/1510.03888
