Physics – Quantum Physics
Scientific paper
2003-02-18
Physics
Quantum Physics
31 pages. Latex
Scientific paper
Pell's equation is x^2-d*y^2=1 where d is a square-free integer and we seek positive integer solutions x,y>0. Let (x',y') be the smallest solution (i.e. having smallest A=x'+y'sqrt(d)). Lagrange showed that every solution can easily be constructed from A so given d it suffices to compute A. It is known that A can be exponentially large in d so just to write down A we need exponential time in the input size log d. Hence we introduce the regulator R=ln A and ask for the value of R to n decimal places. The best known classical algorithm has sub-exponential running time O(exp(sqrt(log d)), poly(n)). Hallgren's quantum algorithm gives the result in polynomial time O(poly(log d),poly(n)) with probability 1/poly(log d). The idea of the algorithm falls into two parts: using the formalism of algebraic number theory we convert the problem of solving Pell's equation into the problem of determining R as the period of a function on the real numbers. Then we generalise the quantum Fourier transform period finding algorithm to work in this situation of an irrational period on the (not finitely generated) abelian group of real numbers. These notes are intended to be accessible to a reader having no prior acquaintance with algebraic number theory; we give a self contained account of all the necessary concepts and we give elementary proofs of all the results needed. Then we go on to describe Hallgren's generalisation of the quantum period finding algorithm, which provides the efficient computational solution of Pell's equation in the above sense.
No associations
LandOfFree
Notes on Hallgren's efficient quantum algorithm for solving Pell's equation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Notes on Hallgren's efficient quantum algorithm for solving Pell's equation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Notes on Hallgren's efficient quantum algorithm for solving Pell's equation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-502218