Quantum algorithms for number fields

doi:10.1002/prop.200610311

Return

Quantum algorithms for number fields

2006-08-01

PRE

Daniel Haase *

Helmut Maier

DOI：10.1002/prop.200610311

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

class number

regulator

number field

QFT

complexity

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.