Quantum algorithms for number fields
D. Haase, Helmut Maier · Fortschritte der Physik · 2006
Abstract This is a survey of recent results on quantum algorithms for the computation of invariants of number fields, namely the class number and the regulator. Most known classical algorithms for the computation of these values are of subexponential complexity and depend on the truth of a still unproven hypothesis of analytic number theory. We use an important number theoretic concept, Minkowski's Geometry of Numbers, to visualize these invariants, and describe the quantum algorithms developed by Hallgren, Schmidt and Vollmer which compute these invariants using a polynomial number of steps. Computational techniques in number fields, which are necessary to justify the classical part of these quantum algorithms, are the focus of the research of our project group, and are explained in detail.