Number theoretic methods in quantum compiling

The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In this talk I will mainly focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. I will consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I will show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. I will also give a brief overview of how number theoretic methods extend to other problems related to building compilers for quantum computers.

Speaker Details

Vadym Kliuchnikov is a third year PhD student working with Michele Mosca at University of Waterloo and Institute for Quantum Computing, Canada. His research interests are related to practical aspects of quantum computing, namely what resources one needs to execute particular quantum algorithms for particular input size and how to reduce amount of resources needed. He enjoys bringing new tools from mathematics and computer science into the field of Quantum Computing and exploiting them in an unusual way. Vadym obtained MSc degree from the National Technical University of Ukraine, also known as “Kyiv Polytechnic Institute”, in Informatics in 2011, and a BSc degree in Applied Mathematics from the same university in 2009. He has also previously worked on problems related to the Theory of Stochastic Processes and Computer Vision.

Date:
Speakers:
Vadym Kliuchnikov
Affiliation:
University of Waterloo and Institute for Quantum Computing, Canada