Speaker: Jose Manuel Fernandez, Universite de Montreal
Time:    Tuesday, October 8, 2:30 p.m.
Place:   HP4369, School of Math and Stats, Carleton University
Title:   Quantum Arithmetics on Galois Fields

Abstract
Quantum computing owes much of its popularity and associated hype to
Shor's integer factoring algorithm, which unlike the fastest known
classical algorithms, uses a polynomial amount of quantum resources.  A
lesser known fact is that Shor also provided a polynomial algorithm for
solving the Discrete Log Problem.  Expressed in terms of quantum
circuits, both algorithms use a generic black box, which performs
exponentiation on the ring of integers modulo N and on a multiplicative
group, respectively.  From the beginning, it was known that by using the
universal prescription for transforming a generic classical into a
reversible one, and from there into a suitable quantum circuit, an at
most polynomial overhead in circuit size would result.  However, since
the current state-of-the-art quantum computing experiments only involve
a pyrrhic number of quantum bits, it becomes paramount to construct
quantum circuits to perform these operations in a manner as efficient as
possible, in particular as far as the number of qubits is concerned.  In
this talk, we will start by reviewing previous results on how to perform
modular arithmetic with quantum circuits.  We will then describe our
results on implementing Galois fields arithmetic in the three different
cases GF(p), GF(2^k), and the generic GF (p^k).  These improved
constructions allow us to describe a much more precise estimate of the
overall resources needed to implement Shor's algorithms for integer
factoring and solving the DLP on the multiplicative group of Galois Fields.

This is joint work with Stéphane Beauregard, Université de Montréal.