A framework for approximating qubit unitaries - Kliuchnikov, V.; Bocharov, A.; Roetteler, M.; Yard, J.; Bocharov, Alex; Yard, Jon; Roetteler, Martin; Kliuchnikov, Vadym (2015)
We present an algorithm for eﬃciently approximating of qubit unitaries over gate sets derived from totally deﬁnite quaternion algebras. It 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 Cliﬀord+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Cliﬀord+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the ﬁrst 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.
arXiv preprint arXiv:1510.03888