Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation. (Q1404927)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation.
scientific article

    Statements

    Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation. (English)
    0 references
    0 references
    25 August 2003
    0 references
    Using the formalism of algebraic number theory the problem of solving Pell's equation can be converted into the problem of determining the period of a function on the real numbers. The ``classical'' Shor's algorithm finds an integer period of a function using the series of quantum Fourier transform. The Hallgren's generalization of Shor's algorithm working with an irrational period on the abelian group of real numbers is considered in the paper. This generalization provides the computational solution of Pell's equation in polynomial time.
    0 references
    Quantum algorithms
    0 references
    Pell's equation
    0 references
    Quantum Fourier transform
    0 references
    period finding
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references