Polynomial time quantum algorithm for the computation of the unit group of a number field

Abstract

We present a quantum algorithm for the computation of the irrational period lattice of a function on Zn which is periodic in a relaxed sense. This algorithm is applied to compute the unit group of finite extensions of Q. Execution time for fixed field degree over Q is polynomial in the discriminant of the field. Our algorithms generalize and improve upon Hallgren's work [9] for the one-dimensional case corresponding to real-quadratic fields.