Algorithms · Computational 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.
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 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 costQuantum 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.
- Papers1
A part this method uses, worked through
This page says generalizes the real-valued hidden subgroup framework
— here is a concrete, runnable instance of it.
Simon's algorithm with secret 11
2 input qubits, 1 ancilla, oracle f(x) = x₀ ⊕ x₁ (satisfies f(x) = f(x ⊕ s) for the secret s = 11).
Where it ends up
- 00025%
- 01125%
- 10025%
- 11125%
The two input qubits read 00 or 11, each equally likely, regardless of the ancilla: both satisfy y · s = 0 for the secret s = 11, exactly as Simon's algorithm predicts for any single run.
Open this part in StudioThe 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.
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 →
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..
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 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.
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which does not state it)
- Complexity 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."
- 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 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.
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. 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.