Attested & literatureAlgorithmsComputational number theory2026-08-12

Zeta function of a curve over a finite field

zeta functionalgebraic curveclass groupblack box grouporder finding

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

Given a curve C of genus g over a finite field F_q, compute the numerator P(t) of its zeta function Z(C,t) = P(t)/((1−t)(1−qt)), a polynomial of degree 2g with integer coefficients, in time polynomial in g and log q jointly rather than in one at the expense of the other. Kedlaya reduces the problem to computing the order of the degree-zero divisor class group Cl(C_n) for several small n, and then recovers the coefficients of P(t) from those orders through the Newton-Girard identities — an effectivization of a theorem of Fried on cyclic resultants. Each group order is obtained by presenting Cl(C_n) as a black box group with unique encodings, its elements being reduced effective divisors supplied by an effective Riemann-Roch theorem, and then invoking Watrous's quantum algorithm for the order of a black box abelian group, itself a Shor-type Fourier-sampling method. A generating set for Cl(C) is produced by a Monte Carlo procedure that samples random points and divisors on the curve, and the correctness of that sampling is controlled by the Riemann hypothesis for curves, which bounds the point counts. The paper is a reduction of a number-theoretic problem to an abelian hidden-subgroup routine rather than a new quantum primitive.

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 →

Where this sits

This record is named by the layer graph at:

Recover the period of a periodic function Slot
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

Kedlaya reduces the problem to computing the order of the degree-zero divisor class group Cl(C_n) for several small n, and then recovers the coefficients of P(t) from those orders through the Newton-Girard identities — an effectivization of a theorem of Fried on cyclic resultants. Each group order is obtained by presenting Cl(C_n) as a black box group with unique encodings, its elements being reduced effective divisors supplied by an effective Riemann-Roch theorem, and then invoking Watrous's quantum algorithm for the order of a black box abelian group, itself a Shor-type Fourier-sampling method. A generating set for Cl(C) is produced by a Monte Carlo procedure that samples random points and divisors on the curve, and the correctness of that sampling is controlled by the Riemann hypothesis for curves, which bounds the point counts. The paper is a reduction of a number-theoretic problem to an abelian hidden-subgroup routine rather than a new quantum primitive. This record's speedup class, "Superpolynomial", is a secondary source's classification of the approximation and simulation algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "For g fixed, the approach introduced by Schoof [22] ... gives an algorithm which is polynomial in log(q) but exponential in g ... imitating Dwork's proof ... yields an algorithm which is polynomial in p, g and logp(q), as observed by Lauder and Wan [15]. However, a single algorithm for computing P(t) in time polynomial both in g and log(q) remains elusive.". Reported cost: Polynomial in g and log q jointly. The paper states this as a theorem for computing the numerator P(t), and states the subroutine bounds separately: Watrous's black-box group order routine runs in time polynomial in mn, and the class number #Cl(C_e) is computable in time polynomial in g, log q and e. No exponent or constant factor is given..

Implementation

FrameworkUnsupported

zeta-function-of-a-curve.txt

ALGORITHM: Zeta function of a curve over a finite field
PROBLEM: Given a curve C of genus g over a finite field F_q, compute the numerator P(t) of its zeta function Z(C,t) = P(t)/((1−t)(1−qt)), a polynomial of degree 2g with integer coefficients, in time polynomial in g and log q jointly rather than in one at the expense of the other.
IDEA: Kedlaya reduces the problem to computing the order of the degree-zero divisor class group Cl(C_n) for several small n, and then recovers the coefficients of P(t) from those orders through the Newton-Girard identities — an effectivization of a theorem of Fried on cyclic resultants. Each group order is obtained by presenting Cl(C_n) as a black box group with unique encodings, its elements being reduced effective divisors supplied by an effective Riemann-Roch theorem, and then invoking Watrous's quantum algorithm for the order of a black box abelian group, itself a Shor-type Fourier-sampling method. A generating set for Cl(C) is produced by a Monte Carlo procedure that samples random points and divisors on the curve, and the correctness of that sampling is controlled by the Riemann hypothesis for curves, which bounds the point counts. The paper is a reduction of a number-theoretic problem to an abelian hidden-subgroup routine rather than a new quantum primitive.
REPORTED COST: Polynomial in g and log q jointly. The paper states this as a theorem for computing the numerator P(t), and states the subroutine bounds separately: Watrous's black-box group order routine runs in time polynomial in mn, and the class number #Cl(C_e) is computable in time polynomial in g, log q and e. No exponent or constant factor is given.
BASIS: abstract of arXiv:math/0411623: "We exhibit a quantum algorithm for determining the zeta function of a genus g curve over a finite field Fq, which is polynomial in g and log(q)."; section 1, Theorem 1: "There is a quantum algorithm for computing the numerator P(t) of the zeta function, which is polynomial time in g, log(q)."; section 7, Proposition 11: "there exists a quantum algorithm to compute #Cl(Ce) in time polynomial in g, log(q), e."; section 3, Lemma 2, for the subroutine: "there is a quantum algorithm, running in time polynomial in mn, for computing the order of G".
PRIMARY SOURCE: Kiran S. Kedlaya (2004), Quantum computation of zeta functions of curves — https://arxiv.org/abs/math/0411623

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

Quantum computation of zeta functions of curves2004 · Kiran S. Kedlaya

Primary source, and the source of this record's cost claim. Consult it for the reduction from the zeta function to a sequence of class numbers, for the 16g < q^(1/2) hypothesis under which the generator-finding lemmas are proved, and for the analytic-number-theory result imported in section 8 to remove that hypothesis. It is also where the 2g oracle calls and the difficulty of verifying a black-box group order are discussed.

arxiv.org/abs/math/0411623 ↗

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement and speedup class were checked against the Quantum Algorithm Zoo's entry "Zeta Functions" (Approximation and Simulation Algorithms); the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (abstract of arXiv:math/0411623: "We exhibit a quantum algorithm for determining the zeta function of a genus g curve over a finite field Fq, which is polynomial in g and log(q)."; section 1, Theorem 1: "There is a quantum algorithm for computing the numerator P(t) of the zeta function, which is polynomial time in g, log(q)."; section 7, Proposition 11: "there exists a quantum algorithm to compute #Cl(Ce) in time polynomial in g, log(q), e."; section 3, Lemma 2, for the subroutine: "there is a quantum algorithm, running in time polynomial in mn, for computing the order of G".). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record: nothing was constructed, compiled, simulated or run, and no zeta function was computed here. The headline theorem is stated unconditionally, but the machinery that finds a generating set is proved only under the assumption 16g < q^(1/2), and lifting that restriction to obtain the general theorem imports an external prime-gap result from analytic number theory, a theorem of Harman, rather than deriving it — so the general statement rests on a separately published result whose effective constants the author notes seem to be new to that paper. The author is himself uneasy about this route, calling the resulting lemma awkwardly intricate and remarking that in practice a generating set is quite likely to come from any reasonably arbitrary process. The result covers curves only; the paper says that varieties of fixed higher dimension seem to pose more serious challenges and leaves them as an open question. The algorithm makes 2g calls to the quantum oracle and the paper describes breaking that barrier as requiring a fundamental new idea. It also notes that while the exponent of a black box group is easy to verify, it is less clear how to verify its order efficiently, so the output is not accompanied by a cheap classical check. The complexity is asymptotic and no gate count, qubit count or constant factor is stated. The classical comparison quoted above is against the best algorithms the author names, Schoof and Lauder-Wan, not against a proved lower bound, and the paper does not use the word superpolynomial.

Facts

Record type: Literature reference
Speedup class (secondary source): Superpolynomial
Primary source on the speedup: Stated by the primary source: "For g fixed, the approach introduced by Schoof [22] ... gives an algorithm which is polynomial in log(q) but exponential in g ... imitating Dwork's proof ... yields an algorithm which is polynomial in p, g and logp(q), as observed by Lauder and Wan [15]. However, a single algorithm for computing P(t) in time polynomial both in g and log(q) remains elusive."
Reported cost: Polynomial in g and log q jointly. The paper states this as a theorem for computing the numerator P(t), and states the subroutine bounds separately: Watrous's black-box group order routine runs in time polynomial in mn, and the class number #Cl(C_e) is computable in time polynomial in g, log q and e. No exponent or constant factor is given.
Secondary source for the speedup class: Quantum Algorithm Zoo — "Zeta Functions"
Section it is filed under: Approximation and Simulation Algorithms
Complexity basis: abstract of arXiv:math/0411623: "We exhibit a quantum algorithm for determining the zeta function of a genus g curve over a finite field Fq, which is polynomial in g and log(q)."; section 1, Theorem 1: "There is a quantum algorithm for computing the numerator P(t) of the zeta function, which is polynomial time in g, log(q)."; section 7, Proposition 11: "there exists a quantum algorithm to compute #Cl(Ce) in time polynomial in g, log(q), e."; section 3, Lemma 2, for the subroutine: "there is a quantum algorithm, running in time polynomial in mn, for computing the order of G".
Circuit: Not supplied

Source

Quantum computation of zeta functions of curves ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply