WADT'22 - 26th International Workshop on Algebraic Development Techniques 2022

Aveiro, 28 - 30 June 2022

Plenary Talk: Number-theoretic methods in quantum computing

Abstract: An important problem in quantum computing is the so-called approximate synthesis problem: to find a circuit, preferably as short as possible, that approximates a given unitary operator up to a given epsilon. Until 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 approximately 3.97. In 2012, a new class of approximate synthesis algorithms was discovered that are based on ideas from algebraic number theory. These algorithms achieve circuit size O(log(1/epsilon)). In certain important cases, such as the commonly used Clifford+T gate set, one can even find algorithms that are optimal in an absolute sense: the algorithm finds the shortest circuit whatsoever for the given problem instance. I will review some 400-year-old number theory and explain how it can be used to solve the approximate synthesis problem. This is joint work with Neil J. Ross.

Peter Selinger (Dalhousie University)

Peter Selinger is a Professor of Mathematics and Computer Science at Dalhousie University. He received his PhD from the University of Pennsylvania in 1997. His main research interest is the semantics of programming languages, and specifically the theory of programming languages for quantum computing, which he helped pioneer. More recently, he also became interested in the application of number-theoretic methods to unitary approximation problems. He is an editor of the journal Logical Methods in Computer Science and a founder of the workshop series Quantum Physics and Logic. He has served on numerous program committees, and has given plenary lectures at international conferences including MFPS, TLCA, CTCS, FLOPS, POPL, WoLLIC, and TYPES.

Program of WADT'22

New!!! Timetable of WADT'22

Previous Editions

Steering Committee

Program Committee

The conference is supported by CIDMA through the Portuguese Foundation for Science and Technology, reference UIDB/04106/2020