Caltech Home > PMA Home > Calendar > IQI Weekly Seminar
open search form
Tuesday, February 09, 2016
3:00 PM - 4:00 PM
Annenberg 107

IQI Weekly Seminar

Compiling qubits
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