◐Attested & literatureAlgorithmsComputational number theory
Pell's equation by computing the regulator
Given a positive non-square integer d, Pell's equation is x² − dy² = 1 and the goal is to find all integer solutions. The least solution can have exponentially many bits, so it cannot be written down; the computational problem is instead to compute the integer part of the regulator R = ln(x₁ + y₁√d), from which the solution can be recovered.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Given a positive non-square integer d, Pell's equation is x² − dy² = 1 and the goal is to find all integer solutions. The least solution can have exponentially many bits, so it cannot be written down; the computational problem is instead to compute the integer part of the regulator R = ln(x₁ + y₁√d), from which the solution can be recovered. Hallgren extends the hidden subgroup problem from finite groups to the group of real numbers. The regulator is an irrational period of a function defined on reduced ideals through a distance function, so the task becomes period finding where the period is not an integer and the group is not discrete. A discretized, pseudo-periodic version of that function is Fourier sampled twice over Z_q, and the two integer outputs are combined by a continued-fraction expansion to recover an integer close to the irrational period. Classical ideal composition and reduction on reduced quadratic ideals supply the function evaluations, which the paper shows can be done in time polynomial in log Δ. The framework is Shor's, applied to a group-like subset of the reals rather than to a group.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Takes A circuit evaluating f on a superposition of inputs, the promise that f is periodic, the kind of object its period is (an integer in a finite cyclic group, an irrational real, a lattice of rank r), and — where the period is not an integer — the precision wanted. Returns The period: an exact integer where the group is finite, or an approximation to the requested precision together with the classical post-processing that turned the measured samples into it.
How it works
Hallgren extends the hidden subgroup problem from finite groups to the group of real numbers. The regulator is an irrational period of a function defined on reduced ideals through a distance function, so the task becomes period finding where the period is not an integer and the group is not discrete. A discretized, pseudo-periodic version of that function is Fourier sampled twice over Z_q, and the two integer outputs are combined by a continued-fraction expansion to recover an integer close to the irrational period. Classical ideal composition and reduction on reduced quadratic ideals supply the function evaluations, which the paper shows can be done in time polynomial in log Δ. The framework is Shor's, applied to a group-like subset of the reals rather than to a group. This record's speedup class, "Superpolynomial", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "The best algorithm for factoring integers has expected time L(1/3,b) for some constant b [LL93]. Assuming the GRH, the best algorithms for Pell's equation and the principal ideal problem have expected time L(1/2,b′), for some constant b′, so there is a sub-exponential gap between the best known classical algorithms.". Reported cost: Polynomial in log Δ and log δ, where Δ is the quadratic discriminant and δ the precision to which the regulator is approximated, with probability exponentially close to one..
Implementation
Unsupported
pell-equation-regulator.txt
ALGORITHM: Pell's equation by computing the regulator
PROBLEM: Given a positive non-square integer d, Pell's equation is x² − dy² =1 and the goal is to find all integer solutions. The least solution can have exponentially many bits, so it cannot be written down; the computational problem is instead to compute the integer part of the regulator R =ln(x₁ + y₁√d), from which the solution can be recovered.
IDEA: Hallgren extends the hidden subgroup problem from finite groups to the group of real numbers. The regulator is an irrational period of a function defined on reduced ideals through a distance function, so the task becomes period finding where the period is not an integer and the group is not discrete. A discretized, pseudo-periodic version of that function is Fourier sampled twice over Z_q, and the two integer outputs are combined by a continued-fraction expansion to recover an integer close to the irrational period. Classical ideal composition and reduction on reduced quadratic ideals supply the function evaluations, which the paper shows can be done in time polynomial in log Δ. The framework is Shor's, applied to a group-like subset of the reals rather than to a group.
REPORTED COST: Polynomial in log Δ and log δ, where Δ is the quadratic discriminant and δ the precision to which the regulator is approximated, with probability exponentially close to one.
BASIS: section 3.2, Theorem 2 of the J. ACM version (doi:10.1145/1206035.1206039): "There is a polynomial-time quantum algorithm that, given a quadratic discriminant ∆, approximates the regulator to within δ of the associated order O in time polynomial in log∆ and logδ with probability exponentially close to one."; the supporting evaluation bound is section 2, Theorem 1, which states that the discretized function can be evaluated in time polynomial in log∆ with high probability.
PRIMARY SOURCE: Sean Hallgren (2007), Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem — https://doi.org/10.1145/1206035.1206039
This is a literature reference record, not an executable circuit.
A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Quantum vs classical
Classical baseline
Compare Computational number theory with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem2007 · Sean Hallgren
Primary source, and the source of this record's cost claim. The full text is freely available from the author's page at the Pennsylvania State University; the version read for this record is the longer journal manuscript, whose own footnote says a preliminary version appeared at STOC 2002, which is the version the Quantum Algorithm Zoo cites. Consult it for the extension of the hidden subgroup problem to the reals, for the two Fourier samplings combined by continued fractions, and for the open question in section 3.1 about whether a fixed precision suffices for all ideals.