Algorithms · Computational number theory
Zeta function of a curve over a finite field
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.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupStated 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 costPolynomial 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.
- Papers1
A part this method uses, worked through
This page says Shor-type Fourier-sampling method
— 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 StudioGiven 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.
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 →
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..
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
- 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.
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which states it)
- 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
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: 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.
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.
Related entries
- Shor period finding
Algorithms
- Group order and membership for black-box groups
Algorithms
- Ideals in a finite black-box ring
Algorithms
References
- Quantum computation of zeta functions of curves
Kiran S. Kedlaya · 2004
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.