Tuesday, February 09, 2016
3:00 PM - 4:00 PM
IQI Weekly Seminar
Jon Yard, Microsoft,
The Solovay-Kitaev Theorem shows that any finite subset of SU(2) generating a dense subgroup can be used to epsilon-approximate an arbitrary qubit unitary with a quantum circuit of length O(polylog(1/epsilon)). Recent advances in quantum compiling achieved the same quality of approximation using circuits over special gate sets of length only O(log(1/epsilon)). In this talk, I will present a general algorithm for finding such approximations over a wide class of gate sets derived from maximal orders in totally-definite quaternion algebras over number fields. The algorithm achieves the same quality of approximation as previously-known algorithms for the Clifford+T, V-basis and Clifford+pi/12 gate sets and runs in poly(log(1/epsilon)) time, conditional on a plausible number-theoretic conjecture. This is the first such algorithm that works for such a wide range of gate sets.
Joint work with Vadym Kliuchnikov (arXiv:1504.04350) and also with VK, Alex Bocharov and Martin Roetteler (arXiv:1510.03888).
For more information, please contact Jackie O'Sullivan by phone at 626.395.4964 or by email at firstname.lastname@example.org.