Ulrich Vollmer (Technische Universität Darmstadt),

Quantum Computational Number Theory

Abstract The last 20 years witnessed the birth of a new computing paradigm that employs the quantum nature of the microcosm. This talk will explain how quantum computation can be modeled, and applied to solve number-theoretic problems.

For classical computers we have the Turing machine model. At any given moment in time such machine is in exactly one observable state which can be represented by a bit string. The "program" defines how the machine transforms from one to the next state.

Quantum computers also have observable basis states that can be represented by bit strings. At any moment, a quantum computer can be in not only one, but a superposition of all these states any of which could be observed. The probability with which each basis state is observed is a function of the total state of the machine. A step in a "program" affects all basis states at once, and hence the probability of each to be seen at the end of the computation. Thus, a Quantum computer can be seen as a machine allowing vastly parallel computation.

The question arises whether this parallel computing power can be harnessed to solve problems that are inaccessible to traditional computers. There is no definite answer to this question yet. We do have, however, polynomial time quantum algorithms for factoring large integers, computing discrete logarithms in general groups, and computing units in number fields. For all of these problems, no classical polynomial time algorithms are known.

The talk will give a not overly formal introduction into quantum computation. We show how to represent the state space of a quantum computer, the transformations it is allowed to pass through, process and effect of observation. Quantum circuits are used to model a quantum computational device, and it is shown how classical computations can be performed with such circuitry.

We then turn to the hitherto most productive idea in quantum computation which is to use the Discrete Fourier Transform to obtain periods of polynomial time computable periodic functions.

This is shown in a progression from the simple determination of the order of an element in a general group, the computation of the discrete logarithm, up to the computation of the period lattice of a (possibly only loosely) periodic function. As an application, an algorithm is presented that applies the latter technique to obtain generators for the unit group of a number field.