Algorithms · Computational number theory
Estimating Gauss sums over finite fields and rings
Given the specification of a nontrivial multiplicative character χ and an additive character indexed by β over a finite field F_{p^r}, estimate the angle γ modulo 2π in the Gauss sum G(F_{p^r}, χ, β) = √(p^r) · e^(iγ). The same question is then asked for Dirichlet characters over Z/nZ.
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 arXiv:quant-ph/0207131 — abstract, sections 1 through 8 and the conclusion. Section 5 raises the classical question and answers it with a reduction rather than a bound: "Although we are not able to prove that this is hard, we can give the following reduction, which indicates that a classical polynomial time algorithm is unlikely." Section 8 then leaves it open: "For the results of this article it remains therefore an important open question if Gauss sum estimation is hard classically, even under the assumption that factoring and discrete logarithms are easy." No classical running time is stated anywhere in the text. was read and makes no such claim
- Reported costO((1/ε) · polylog(p^r)) time to estimate the angle to within ε over a finite field F_{p^r}, and O((1/ε) · polylog(n)) over Z/nZ, with the norm |G(Z/nZ, χ, β)| determinable in polylog(n) time. The Jacobi-sum corollary carries the same O((1/ε) · polylog(p^r)) bound.
- Papers1
A part this method uses, worked through
This page says Shor's discrete-logarithm algorithm
— here is a concrete, runnable instance of it.
Order-finding for 7 mod 15
3 counting qubits, 4 work qubits, finding the order of 7 modulo 15 (the order is 4: 7⁴ mod 15 = 1).
Where it ends up
- 00010006%
- 00010106%
- 00011006%
- 00011106%
- 12 more outcomes75%
The counting register reads 000, 010, 100 or 110, each equally likely, corresponding to the four powers k = 0, 1, 2, 3 of the order r = 4; the work register ends entangled with the counting outcome, holding one of 1, 7, 4 or 13. Repeating this and applying the continued-fractions step of the full algorithm to a nonzero outcome recovers the order r = 4 exactly.
Open this part in StudioA part this method uses, worked through
This page says amplitude amplification
— here is a concrete, runnable instance of it.
Grover's algorithm finds |101⟩
3 qubits, searching for |101⟩ among 8 states, with 2 Grover iterations.
Where it ends up
- 10195%
- 0001%
- 1101%
- 0011%
- 4 more outcomes3%
Measuring gives 101, the marked state, with high probability.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioGiven the specification of a nontrivial multiplicative character χ and an additive character indexed by β over a finite field F_{p^r}, estimate the angle γ modulo 2π in the Gauss sum G(F_{p^r}, χ, β) = √(p^r) · e^(iγ). The same question is then asked for Dirichlet characters over Z/nZ. The specification of the character lets the algorithm build the state |χ⟩ efficiently, using Shor's discrete-logarithm algorithm together with a phase-kickback trick and amplitude amplification. Applying the finite-field quantum Fourier transform to |χ⟩ and then the phase change |y⟩ → χ²(y)|y⟩ produces an eigenrelation in which the Gauss sum divided by √(p^r) appears as the eigenvalue. Preparing a superposition of |χ⟩ with a stale component turns that eigenvalue into a relative phase e^(iγ), which standard phase estimation reads out with O(1/ε) samples. The same machinery, applied to Dirichlet characters and combined with a reduction to primitive characters through the Chinese remainder theorem, extends the result from finite fields to Z/nZ, and a corollary covers Jacobi sums.
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 specification of the character lets the algorithm build the state |χ⟩ efficiently, using Shor's discrete-logarithm algorithm together with a phase-kickback trick and amplitude amplification. Applying the finite-field quantum Fourier transform to |χ⟩ and then the phase change |y⟩ → χ²(y)|y⟩ produces an eigenrelation in which the Gauss sum divided by √(p^r) appears as the eigenvalue. Preparing a superposition of |χ⟩ with a stale component turns that eigenvalue into a relative phase e^(iγ), which standard phase estimation reads out with O(1/ε) samples. The same machinery, applied to Dirichlet characters and combined with a reduction to primitive characters through the Chinese remainder theorem, extends the result from finite fields to Z/nZ, and a corollary covers Jacobi sums. 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 arXiv:quant-ph/0207131 — abstract, sections 1 through 8 and the conclusion. Section 5 raises the classical question and answers it with a reduction rather than a bound: "Although we are not able to prove that this is hard, we can give the following reduction, which indicates that a classical polynomial time algorithm is unlikely." Section 8 then leaves it open: "For the results of this article it remains therefore an important open question if Gauss sum estimation is hard classically, even under the assumption that factoring and discrete logarithms are easy." No classical running time is stated anywhere in the text. was read and makes no such claim. Reported cost: O((1/ε) · polylog(p^r)) time to estimate the angle to within ε over a finite field F_{p^r}, and O((1/ε) · polylog(n)) over Z/nZ, with the norm |G(Z/nZ, χ, β)| determinable in polylog(n) time. The Jacobi-sum corollary carries the same O((1/ε) · polylog(p^r)) 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 arXiv:quant-ph/0207131 — abstract, sections 1 through 8 and the conclusion. Section 5 raises the classical question and answers it with a reduction rather than a bound: "Although we are not able to prove that this is hard, we can give the following reduction, which indicates that a classical polynomial time algorithm is unlikely." Section 8 then leaves it open: "For the results of this article it remains therefore an important open question if Gauss sum estimation is hard classically, even under the assumption that factoring and discrete logarithms are easy." No classical running time is stated anywhere in the text. was read and makes no such claim
- Reported cost
- O((1/ε) · polylog(p^r)) time to estimate the angle to within ε over a finite field F_{p^r}, and O((1/ε) · polylog(n)) over Z/nZ, with the norm |G(Z/nZ, χ, β)| determinable in polylog(n) time. The Jacobi-sum corollary carries the same O((1/ε) · polylog(p^r)) bound.
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which does not state it)
- Complexity basis
- section 4, Theorem 1 of arXiv:quant-ph/0207131: "The time complexity of this algorithm is bounded by O( 1/ε · polylog(p^r))."; section 7, Theorem 2: "The time complexity of this algorithm is bounded by O( 1/ε · polylog(n)). Also the norm |G(Z/nZ, χ, β)| can be determined in polylog(n) time."; section 4.1, Corollary 1, for Jacobi sums: "…with expected error ε with time complexity O( 1/ε · polylog(p^r))." The introduction states the same bound in the general form O( 1/ε · polylog|R|).
- 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: Estimating Gauss sums over finite fields and rings
PROBLEM: Given the specification of a nontrivial multiplicative character χ and an additive character indexed by β over a finite field F_{p^r}, estimate the angle γ modulo 2π in the Gauss sum G(F_{p^r}, χ, β) = √(p^r) · e^(iγ). The same question is then asked for Dirichlet characters over Z/nZ.
IDEA: The specification of the character lets the algorithm build the state |χ⟩ efficiently, using Shor's discrete-logarithm algorithm together with a phase-kickback trick and amplitude amplification. Applying the finite-field quantum Fourier transform to |χ⟩ and then the phase change |y⟩ → χ²(y)|y⟩ produces an eigenrelation in which the Gauss sum divided by √(p^r) appears as the eigenvalue. Preparing a superposition of |χ⟩ with a stale component turns that eigenvalue into a relative phase e^(iγ), which standard phase estimation reads out with O(1/ε) samples. The same machinery, applied to Dirichlet characters and combined with a reduction to primitive characters through the Chinese remainder theorem, extends the result from finite fields to Z/nZ, and a corollary covers Jacobi sums.
REPORTED COST: O((1/ε) · polylog(p^r)) time to estimate the angle to within ε over a finite field F_{p^r}, and O((1/ε) · polylog(n)) over Z/nZ, with the norm |G(Z/nZ, χ, β)| determinable in polylog(n) time. The Jacobi-sum corollary carries the same O((1/ε) · polylog(p^r)) bound.
BASIS: section 4, Theorem 1 of arXiv:quant-ph/0207131: "The time complexity of this algorithm is bounded by O( 1/ε · polylog(p^r))."; section 7, Theorem 2: "The time complexity of this algorithm is bounded by O( 1/ε · polylog(n)). Also the norm |G(Z/nZ, χ, β)| can be determined in polylog(n) time."; section 4.1, Corollary 1, for Jacobi sums: "…with expected error ε with time complexity O( 1/ε · polylog(p^r))." The introduction states the same bound in the general form O( 1/ε · polylog|R|).
PRIMARY SOURCE: Wim van Dam, Gadiel Seroussi (2002), Efficient Quantum Algorithms for Estimating Gauss Sums — https://arxiv.org/abs/quant-ph/0207131
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:
- Estimate the eigenphase of a unitary Slot
Takes A circuit for U that can be applied as controlled U^(2^j), a preparation routine for a state whose overlap with the target eigenvector is not negligible, the number of bits of the phase wanted, and the failure probability that may be tolerated. Returns An estimate of the eigenphase to the requested number of bits, with the failure probability it was obtained at, plus the two costs that actually differ between routes: how many ancillas were held at once, and how many sequential rounds were run.
Related entries
- Discrete logarithm on a quantum computer
Algorithms
- Shor period finding
Algorithms
- Quantum Fourier Transform
Algorithms
References
- Efficient Quantum Algorithms for Estimating Gauss Sums
Wim van Dam, Gadiel Seroussi · 2002
Primary source, and the source of this record's cost claim. It is also the document that shows the Zoo's speedup class for this entry is not the paper's: section 5 offers a reduction rather than a hardness proof, and section 8 names classical hardness of Gauss sum estimation as an open question. Consult it for the character specification the algorithm needs as input and for the eigenrelation the phase estimation is run against.