Abstract: The synthesis problem for boolean circuits is the following:
given a boolean function on n bits, find a boolean circuit that
implements the function and is preferably as small as possible. The
synthesis problem for quantum circuits is analogous: given a unitary
operator in n qubits, find a quantum circuit (preferably as small as
possible) that implements the given operator, either exactly or up to
a given epsilon. In this talk, I will focus on the approximate
synthesis problem for single-qubit operators over the Clifford+T gate
set. Until 2012, the standard solution to this problem was the
Solovay-Kitaev algorithm, which achieves gate counts of
O(log^c(1/epsilon)), where c is a constant approximately equal to
4. It is also known that 3 log(1/epsilon) is a lower bound for the
gate count. It was long an open question whether the exponent c could
be reduced to 1. I will talk about a new class of algorithms that
emerged in 2012, and which achieves gate counts of between
3 log(1/epsilon) and 9 log(1/epsilon) for this problem, and which
achieves optimal gate counts if the unitary operator to be
approximated is diagonal. Unlike the Solovay-Kitaev algorithm, which
is based on geometry, the new algorithms are based on algebraic number
theory. No knowledge of quantum computing or number theory will be
assumed.