{
  "id": "math/0411623",
  "version": "v3",
  "published": "2004-11-28T21:11:48.000Z",
  "updated": "2005-11-30T03:18:29.000Z",
  "title": "Quantum computation of zeta functions of curves",
  "authors": [
    "Kiran S. Kedlaya"
  ],
  "comment": "17 pages; v3 (refereed version): minor corrections",
  "journal": "preprint; published version: Computational Complexity 15 (2006), 1-19.",
  "categories": [
    "math.NT"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2005-11-30T03:18:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11M38"
    ],
    "keywords": [
      "zeta function",
      "quantum computation",
      "produce provably random elements",
      "finite field",
      "quantum algorithm"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math.....11623K"
    }
  }
}