Title: Number-theoretic methods in quantum computing
| Speaker: | Peter Selinger |
| Affiliation: | Dalhousie University |
| Zoom: | Please email Emma Watson |
Abstract:
An important problem in quantum computing is the so-called \emph{approximate synthesis problem}: to find a quantum circuit, preferably as short as possible, that approximates a given target operation up to given $\epsilon$. For nearly two decades, from 1995 to 2012, 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/\epsilon))$, 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 decade, a new class of efficient algorithms has emerged that achieve circuit size $O(\log(1/\epsilon))$, thereby answering the above question positively. These new algorithms are not based 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 describe such an algorithm. In order to achieve optimal circuit sizes, the algorithm requires an oracle for integer factoring (such as a quantum computer); in the absence of a factoring oracle, the algorithm is still nearly optimal. Furthermore, termination of the algorithm is predicated on an unproven, but heuristically true, hypothesis about the distribution of prime numbers. A crucial element of the algorithm is the combination of computations in algebraic number fields (which are exact) with real-number computations (which can be done with variable precision).
This is joint work with Neil J. Ross.