◐Attested & literatureAlgorithmsComputational number theory
The class group of a constant-degree number field
The class group of a number field is the finite abelian group of ideals modulo principal ideals. Computing it means computing the structure of that abelian group, not merely its order.
class groupnumber fieldideal class groupgeneralized riemann hypothesishidden subgroup problem
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
The class group of a number field is the finite abelian group of ideals modulo principal ideals. Computing it means computing the structure of that abelian group, not merely its order. The class group algorithm sits on top of the other two results in the same paper. Ideals have no unique representatives, which is what blocks a direct application of the standard finite-abelian-group hidden subgroup machinery, so the algorithm instead prepares a quantum superposition over all reduced ideals in an equivalence class, using the principal ideal algorithm as a subroutine, and that superposition serves as the unique encoding the standard machinery needs. Feeding those states into the usual abelian hidden subgroup algorithm and a Smith normal form decomposition then yields the group structure. A set of generators for the class group must be available before any of this runs, and that is the step where the generalized Riemann hypothesis enters.
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 class group algorithm sits on top of the other two results in the same paper. Ideals have no unique representatives, which is what blocks a direct application of the standard finite-abelian-group hidden subgroup machinery, so the algorithm instead prepares a quantum superposition over all reduced ideals in an equivalence class, using the principal ideal algorithm as a subroutine, and that superposition serves as the unique encoding the standard machinery needs. Feeding those states into the usual abelian hidden subgroup algorithm and a Smith normal form decomposition then yields the group structure. A set of generators for the class group must be available before any of this runs, and that is the step where the generalized Riemann hypothesis enters. 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 only comparison with classical work is structural: that the best classical algorithm for either the unit group or the class group solves both simultaneously, whereas the quantum algorithms here are layered, the class group one calling the previous two. No classical running time is stated anywhere. was read and makes no such claim. Reported cost: Quantum polynomial time for a number field of constant degree, assuming the generalized Riemann hypothesis. Both conditions are stated in the theorem itself and neither is dropped elsewhere in the paper..
Implementation
Unsupported
class-group-of-a-number-field.txt
ALGORITHM: The class group of a constant-degree number field
PROBLEM: The class group of a number field is the finite abelian group of ideals modulo principal ideals. Computing it means computing the structure of that abelian group, not merely its order.
IDEA: The class group algorithm sits on top of the other two results in the same paper. Ideals have no unique representatives, which is what blocks a direct application of the standard finite-abelian-group hidden subgroup machinery, so the algorithm instead prepares a quantum superposition over all reduced ideals in an equivalence class, using the principal ideal algorithm as a subroutine, and that superposition serves as the unique encoding the standard machinery needs. Feeding those states into the usual abelian hidden subgroup algorithm and a Smith normal form decomposition then yields the group structure. A set of generators for the class group must be available before any of this runs, and that is the step where the generalized Riemann hypothesis enters.
REPORTED COST: Quantum polynomial time for a number field of constant degree, assuming the generalized Riemann hypothesis. Both conditions are stated in the theorem itself and neither is dropped elsewhere in the paper.
BASIS: section 5, Theorem 3 of doi:10.1145/1060590.1060660: "The class group of a constant degree number field can be computed in quantum polynomial-time assuming the GRH."; the paper localises the assumption in section 1: "Our algorithms here do not use any assumptions, except for when computing the class group where the GRH is needed to compute a set of generators for the group", and again at the point of use in section 5: "Generators g1,...,gm for Cl can be chosen in polynomial-time assuming the GRH".
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. Consult it for section 5, where the GRH assumption is localised to choosing a generating set, and for the superposition over reduced ideals in an equivalence class that stands in for the unique encoding the abelian hidden subgroup machinery requires. Reading it beside the unit group record is the point: one theorem in this paper is unconditional and the other is not.