Peter Selinger (Dalhousie University)
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.
Light refreshments will be served before the lecture at 3:30 p.m.