dorsal/arxiv
View SchemaNotes on Hallgren's efficient quantum algorithm for solving Pell's equation
| Authors | Richard Jozsa |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0302134 |
| URL | https://arxiv.org/abs/quant-ph/0302134 |
Abstract
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.
{
"annotation_id": "6bed605f-f423-4f27-bdb2-b6e67563ba31",
"date_created": "2026-03-02T18:01:56.065000Z",
"date_modified": "2026-03-02T18:01:56.065000Z",
"file_hash": "8013f61eb13f9b8bfd5b2a79437ba6a57f0b03d1049c70cc3d10ad03b50675e7",
"private": false,
"record": {
"abstract": "Pell\u0027s equation is x^2-d*y^2=1 where d is a square-free integer and we seek\npositive integer solutions x,y\u003e0. Let (x\u0027,y\u0027) be the smallest solution (i.e.\nhaving smallest A=x\u0027+y\u0027sqrt(d)). Lagrange showed that every solution can easily\nbe constructed from A so given d it suffices to compute A. It is known that A\ncan be exponentially large in d so just to write down A we need exponential\ntime in the input size log d. Hence we introduce the regulator R=ln A and ask\nfor the value of R to n decimal places. The best known classical algorithm has\nsub-exponential running time O(exp(sqrt(log d)), poly(n)). Hallgren\u0027s quantum\nalgorithm gives the result in polynomial time O(poly(log d),poly(n)) with\nprobability 1/poly(log d). The idea of the algorithm falls into two parts:\nusing the formalism of algebraic number theory we convert the problem of\nsolving Pell\u0027s equation into the problem of determining R as the period of a\nfunction on the real numbers. Then we generalise the quantum Fourier transform\nperiod finding algorithm to work in this situation of an irrational period on\nthe (not finitely generated) abelian group of real numbers.\n These notes are intended to be accessible to a reader having no prior\nacquaintance with algebraic number theory; we give a self contained account of\nall the necessary concepts and we give elementary proofs of all the results\nneeded. Then we go on to describe Hallgren\u0027s generalisation of the quantum\nperiod finding algorithm, which provides the efficient computational solution\nof Pell\u0027s equation in the above sense.",
"arxiv_id": "quant-ph/0302134",
"authors": [
"Richard Jozsa"
],
"categories": [
"quant-ph"
],
"title": "Notes on Hallgren\u0027s efficient quantum algorithm for solving Pell\u0027s equation",
"url": "https://arxiv.org/abs/quant-ph/0302134"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "884329bf-d86b-4800-9e0f-783d7c142063",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}