◐Attested & literatureAlgorithmsComputational 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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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. 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.
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 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.
How it works
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..
Implementation
Unsupported
gauss-sum-estimation.txt
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 withO(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 inpolylog(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.
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
Efficient Quantum Algorithms for Estimating Gauss Sums2002 · Wim van Dam, Gadiel Seroussi
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.