Polynomial time quantum algorithm for the computation of the unit group of a number field
Arthur R. Schmidt, Ulrich Vollmer · 2005
We present a quantum algorithm for the computation of the irrational period lattice of a function on Z 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 [Hal02] for the one-dimensional case corresponding to real-quadratic fields.