Premium
Quantum algorithms for number fields
Author(s) -
Haase D.,
Maier H.
Publication year - 2006
Publication title -
fortschritte der physik
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.469
H-Index - 71
eISSN - 1521-3978
pISSN - 0015-8208
DOI - 10.1002/prop.200610311
Subject(s) - computation , quantum algorithm , quantum computer , minkowski space , geometry of numbers , focus (optics) , class (philosophy) , mathematics , algorithm , complexity class , quantum , quantum complexity theory , field (mathematics) , algebraic number field , algebra over a field , time complexity , discrete mathematics , computer science , pure mathematics , quantum mechanics , geometry , artificial intelligence , physics , optics
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.