Number-theoretic methods in quantum computing.

by Peter Selinger

• When: Friday, 19/02/2021, between 1pm and 2pm EST (6pm - 7pm UTC)
• Where: Zoom (this presentation will be avaliable to AU affilated attendees only)

Abstract

An important problem in quantum computing is the so-called 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 so-called Solovay-Kitaev algorithm, which is based on geometric ideas. This algorithm produces circuits of size $O(\mathsf{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 this talk, I will answer this question positively, and report on a new class of efficient algorithms for solving the approximate synthesis problem. These algorithms are based on number theory, and are intimatedly related to classical results in number theory, such as which primes can be written as a sum of two squares. This is joint work with Neil J. Ross. No knowledge of quantum computing or number theory will be assumed.

Bio

Peter Selinger is a professor of mathematics at Dalhousie University in Halifax, Canada. He obtained his Ph.D. from the University of Pennsylvania in the 1990s under the supervision of Andre Scedrov. His main interest is the semantics of programming languages, and his particular niche is programming languages for quantum computing.