Open Lecture — Number-Theoretic Methods in Quantum Computing

An important problem in quantum computing is the so-called approximate synthesis problem: to find a quantum circuit, preferably as small as possible, that approximates a given target operation up to a given accuracy ε.  For nearly two decades, the standard solution to this problem was the Solovay-Kitaev algorithm, which is based on geometric ideas. This algorithm produces circuits of size O(log^c(1/ε)), where c is a constant approximately equal to 3.97. It was a long-standing open problem whether the exponent c could be reduced to 1.

In the last few years, a new class of efficient algorithms has emerged that achieve circuit size O(log(1/ε)), thereby answering the above question positively.  These new algorithms are based not on geometry, but on number theory.  In certain important cases, such as the commonly used Clifford+T gate set, one can even find algorithms that are optimal, i.e., they always find the shortest possible sequence of gates.  I will give an overview of these developments, which have already reduced the resources required for (future) practical quantum computation by at least 2-3 orders of magnitude.