Number-theoretic methods in quantum computing
Peter Selinger - Dalhousie University
Oct. 3, 2025, 1:30 p.m. - Oct. 3, 2025, 1:30 p.m.
ENGMD 279
Hosted by: Brigitte Pientka
In 1754, Pierre de Fermat (who is famous for Fermat's Last Theorem) figured out which integers can be written a sum of two squares. More than 250 years later, his methods have found a new application in computer science, specifically in quantum computing. The approximate synthesis problem is to find a quantum circuit, preferably as short as possible, that approximates a given target operation up to a given precision. Until 2012, the standard solution to this problem was the so-called Solovay-Kitaev algorithm, which is based on geometric ideas. It produces circuits of size O(log^c(1/epsilon)), where c is a constant approximately equal to 3.97. It used to be an open problem whether the exponent c could be reduced to 1. The answer is yes. In this talk, I will report on a class of efficient algorithms for approximate synthesis, based on number theory that might have looked familiar to Fermat. This is joint work with Neil J. Ross. No knowledge of quantum computing or number theory required.
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. Peter’s passion for teaching and commitment to students was in 2023 recoginzed by the Faculty of Science Award for Excellence in Teaching at Dalhousie University.
