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

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.