Events
Fall 2016

Speaker:

Peter Selinger (Dalhousie University)

Location:

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.