◐Attested & literatureAlgorithmsComputational number theory
The unit group of a constant-degree number field
The unit group of a number field is the set of invertible algebraic integers inside it. By Dirichlet's unit theorem it is, up to a root of unity, free abelian of a rank determined by the field's real and complex embeddings, so computing it means finding a fundamental system of units.
unit groupnumber fielddirichlet unit theoremlattice basishidden subgroup problem
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
The unit group of a number field is the set of invertible algebraic integers inside it. By Dirichlet's unit theorem it is, up to a root of unity, free abelian of a rank determined by the field's real and complex embeddings, so computing it means finding a fundamental system of units. Hallgren generalizes the real-valued hidden subgroup framework of his Pell's equation paper from one dimension to r dimensions, for constant r, recasting the unit group computation as finding the basis of an unknown real-valued lattice — the logarithmic embedding of the unit group. The algorithm Fourier samples a function that hides that lattice and uses a zero-filling trick, padding the Fourier domain, to recover enough of the dual lattice from a constant number of samples, then inverts to obtain a basis for the lattice itself. Reaching the lattice at all requires computing reduced ideals near arbitrary points, which the paper obtains from a classical subroutine. The unit group algorithm is the base of a stack: the paper's principal ideal algorithm uses it, and its class group algorithm uses both.
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 generalizes the real-valued hidden subgroup framework of his Pell's equation paper from one dimension to r dimensions, for constant r, recasting the unit group computation as finding the basis of an unknown real-valued lattice — the logarithmic embedding of the unit group. The algorithm Fourier samples a function that hides that lattice and uses a zero-filling trick, padding the Fourier domain, to recover enough of the dual lattice from a constant number of samples, then inverts to obtain a basis for the lattice itself. Reaching the lattice at all requires computing reduced ideals near arbitrary points, which the paper obtains from a classical subroutine. The unit group algorithm is the base of a stack: the paper's principal ideal algorithm uses it, and its class group algorithm uses both. 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. Not stated by the primary source — the full text of doi:10.1145/1060590.1060660 as published on the author's page — abstract and sections 1 through 6, acknowledgments and references, all ten pages. The paper compares itself with classical work only structurally, not by cost: it observes that factoring reduces to Pell's equation, which is a special case of computing the unit group, while a reduction in the other direction is not known and appears more difficult, and that the best classical algorithm for either the unit group or the class group solves both at once. No classical running time is stated anywhere, in L-notation or otherwise, unlike the companion Pell paper which does state one. was read and makes no such claim. Reported cost: Quantum polynomial time, for a number field of constant degree. The paper states the bound as a theorem in exactly those terms and gives no exponent, and the degree appears as a restriction rather than as a parameter of the bound..
Implementation
Unsupported
unit-group-of-a-number-field.txt
ALGORITHM: The unit group of a constant-degree number field
PROBLEM: The unit group of a number field is the set of invertible algebraic integers inside it. By Dirichlet's unit theorem it is, up to a root of unity, free abelian of a rank determined by the field's real and complex embeddings, so computing it means finding a fundamental system of units.
IDEA: Hallgren generalizes the real-valued hidden subgroup framework of his Pell's equation paper from one dimension to r dimensions, for constant r, recasting the unit group computation as finding the basis of an unknown real-valued lattice — the logarithmic embedding of the unit group. The algorithm Fourier samples a function that hides that lattice and uses a zero-filling trick, padding the Fourier domain, to recover enough of the dual lattice from a constant number of samples, then inverts to obtain a basis for the lattice itself. Reaching the lattice at all requires computing reduced ideals near arbitrary points, which the paper obtains from a classical subroutine. The unit group algorithm is the base of a stack: the paper's principal ideal algorithm uses it, and its class group algorithm uses both.
REPORTED COST: Quantum polynomial time, for a number field of constant degree. The paper states the bound as a theorem in exactly those terms and gives no exponent, and the degree appears as a restriction rather than as a parameter of the bound.
BASIS: section 3.2, Theorem 1 of doi:10.1145/1060590.1060660: "Algorithm 3.1 computes the unit group of a constant degree number field in quantum polynomial-time."; the abstract states the same scope for both results in the paper: "We give polynomial-time quantum algorithms for computing the unit group and class group when the number field has constant degree."
PRIMARY SOURCE: Sean Hallgren (2005), Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field — https://doi.org/10.1145/1060590.1060660
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
Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field2005 · 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. Consult it for the two separate reasons the constant-degree restriction exists, for the well-conditioned-lattice hypothesis attached to Theorem 1, and for the sentence in section 1 that separates this result from the class group one — the algorithms use no assumptions except when computing the class group, where the GRH is needed.