◐Attested & literatureAlgorithmsComputational number theory
The principal ideal problem in a real quadratic field
Given an invertible ideal I in a real quadratic field, determine whether there exists an α with I = αZ[√d] — that is, whether the ideal is principal — and if there is, find α.
principal ideal problemreal quadratic fieldideal classhidden subgroup problemperiod finding
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Given an invertible ideal I in a real quadratic field, determine whether there exists an α with I = αZ[√d] — that is, whether the ideal is principal — and if there is, find α. The principal ideal problem is solved with the same period-finding-over-the-reals machinery that gives the regulator, but in two dimensions rather than one. Where the regulator is the period of a function on the reals, deciding principality asks for the distance of a given ideal, which the paper handles on Z × R by analogy with Shor's discrete-logarithm algorithm — the two-dimensional version of the same construction. The paper is explicit that the object being sampled is not a group but, as it puts it, a group-like subset of the reals, modulo an irrational number, which is why the standard hidden-subgroup analysis does not apply unchanged.
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
The principal ideal problem is solved with the same period-finding-over-the-reals machinery that gives the regulator, but in two dimensions rather than one. Where the regulator is the period of a function on the reals, deciding principality asks for the distance of a given ideal, which the paper handles on Z × R by analogy with Shor's discrete-logarithm algorithm — the two-dimensional version of the same construction. The paper is explicit that the object being sampled is not a group but, as it puts it, a group-like subset of the reals, modulo an irrational number, which is why the standard hidden-subgroup analysis does not apply unchanged. 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: "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 Δ when the regulator is larger than some absolute constant, with success probability Ω(1/log Δ) per run; polynomially many repetitions in log Δ raise that to probability exponentially close to one..
Implementation
Unsupported
principal-ideal-problem.txt
ALGORITHM: The principal ideal problem in a real quadratic field
PROBLEM: Given an invertible ideal I in a real quadratic field, determine whether there exists an α with I = αZ[√d] — that is, whether the ideal is principal — and if there is, find α.
IDEA: The principal ideal problem is solved with the same period-finding-over-the-reals machinery that gives the regulator, but in two dimensions rather than one. Where the regulator is the period of a function on the reals, deciding principality asks for the distance of a given ideal, which the paper handles on Z × R by analogy with Shor's discrete-logarithm algorithm — the two-dimensional version of the same construction. The paper is explicit that the object being sampled is not a group but, as it puts it, a group-like subset of the reals, modulo an irrational number, which is why the standard hidden-subgroup analysis does not apply unchanged.
REPORTED COST: Polynomial in log Δ when the regulator is larger than some absolute constant, with success probability Ω(1/log Δ) per run; polynomially many repetitions in log Δ raise that to probability exponentially close to one.
BASIS: section 4, Theorem 3 of doi:10.1145/1206035.1206039: "The above algorithm approximates the distance of a principal ideal in time polynomial in log∆ when the regulator is larger than some absolute constant. The algorithm is successful with probability Ω(1/log(∆)). Polynomial in log∆ repetitions gives probability exponentially close to one."
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. Consult it for Theorem 3 specifically, which carries two conditions the regulator theorem does not — a lower bound on the regulator and a per-run success probability of only Ω(1/log Δ) — and for the two-dimensional analogue of the real hidden-subgroup construction that the principality test is built on.