  We exhibit a quantum algorithm for determining the zeta function of a genus g
curve over a finite field F_q, which is polynomial in g and log(q). This
amounts to giving an algorithm to produce provably random elements of the class
group of a curve, plus a recipe for recovering a Weil polynomial from enough of
its cyclic resultants. The latter effectivizes a result of Fried in a
restricted setting.
