Algorithms · Computational 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.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot 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 costQuantum 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.
- Papers1
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.
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 →
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..
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 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Superpolynomial
- Primary source on the speedup
- 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.
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which does not state it)
- Complexity 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".
- Circuit
- Not supplied
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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.
Where this sits
This record is named by the layer graph at:
- Finding a lattice of periods Method
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.
Related entries
References
- Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field
Sean Hallgren · 2005
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.