Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Wiley eBooks

Quantum Algorithms for Number Fields

Daniel Haase, Helmut Maier

Published Jan 26, 2007• 1 citation
Publisher

Abstract

This chapter contains sections titled: Introduction Outline of the Survey Why Number Fields? Some History of the Subject Geometry of Numbers Number Fields Lattices Integral Elements The Class Number The Regulator Complexity Results Reduction Reduced Ideals Infrastructure Geometric Interpretation of G Results from Analytic Number Theory Distribution of Prime Numbers Class Number Formulas Examples of Minima Distributions Computing the Regulator Real Quadratic Case Hallgren's Algorithm Generalization of the Weak Periodicity Condition Computation of Other Invariants The Principal Ideal Problem Computing the Class Number References

DOI
10.1002/9783527611065.ch18

Related papers

Quantum algorithms for number fields

D. Haase, Helmut Maier

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.

Fortschritte der Physik•Aug 1, 2006•3 citations

Isomorphism and Factorization – Classical and Quantum Algorithms

Sebastian Dörn, Daniel Haase, Jacobo Torán +1 more

This chapter contains sections titled: Introduction Factorization of Integers: Classical Algorithms Graph Isomorphism: Classical Algorithms Quantum Algorithms for Integer Factorization Quantum Approach to Graph Isomorphism Reductions of Integer Factorization and Graph Isomorphism to Ring Isomorphism References

Wiley eBooks•Mar 18, 2009•2 citations

Introduction and survey

Joachim Stolze, Dieter Suter

This chapter contains sections titled: Information computers and quantum mechanics Quantum computer basics History of quantum information processing

Wiley eBooks•May 26, 2004•0 citations

Quantum Algorithms for Unit Group and principal ideal problem

Hong Wang, Zhi Ma

Computing the unit group and solving the principal ideal problem for a number field are two of the main tasks in computational algebraic number theory. This paper proposes efficient quantum algorithms for these two problems when the number field has constant degree. We improve these algorithms proposed by Hallgren by using a period function which is not one-to-one on its fundamental period. Furthermore, given access to a function which encodes the lattice, a new method to compute the basis of an unknown real-valued lattice is presented.

arXiv:1004.1269•Apr 8, 2010•0 citations

Factorization

R. Mack, Wolfgang P. Schleich, Daniel Haase +1 more

This chapter contains sections titled: Introduction How to Factor Numbers How to Find the Period of a Function: The Magic Role of Entanglement Analogy with Atom Optics Exponential Growth of Hilbert Space as a Resource of Exponential Speedup Conclusions Modular Arithmetic Chinese Remainder Theorem Euler's Function Euclidean Algorithm Primitive Root Probability for Lucky Choice Elements of AtomOptics Factorization with a Gauss Sum due to its Periodicity References

Wiley eBooks•Mar 18, 2009•2 citations

Quantum Computation and BQP

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 16.1 The Class BQP, 16.2 Equations, Solutions, and Complexity, 16.3 A Circuit Labeling Algorithm, 16.4 Sum-Over-Paths and Polynomial Roots, 16.5 The Additive Polynomial Simulation, 16.6 Bounding BQP, 16.7 Problems, 16.8 Summary and Notes

•Jan 1, 2014•0 citations
This chapter contains sections titled: Introduction Outline of the Survey Why Number Fields? Some History of the Subject Geometry of Numbers Number Fields Lattices Integral Elements The Class Number The Regulator Complexity Results Reduction Reduced Ideals Infrastructure Geometric Interpretation of G Results from Analytic Number Theory Distribution of Prime Numbers Class Number Formulas Examples of Minima Distributions Computing the Regulator Real Quadratic Case Hallgren's Algorithm Generalization of the Weak Periodicity Condition Computation of Other Invariants The Principal Ideal Problem Computing the Class Number References
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.
Computing the unit group and solving the principal ideal problem for a number field are two of the main tasks in computational algebraic number theory. This paper proposes efficient quantum algorithms for these two problems when the number field has constant degree. We improve these algorithms proposed by Hallgren by using a period function which is not one-to-one on its fundamental period. Furthermore, given access to a function which encodes the lattice, a new method to compute the basis of an unknown real-valued lattice is presented.