caa a22 4500 467909571 CHVBK 20180406152845.0 cr unu---uuuuu 170328e20060501xx s 000 0 eng 10.1007/s00037-006-0204-7 doi (NATIONALLICENCE)springer-10.1007/s00037-006-0204-7 Kedlaya Kiran Department of Mathematics, Massachusetts Institute of Technology, Room 2-165, 77 Massachusetts Avenue, 02139, Cambridge, MA, U.S.A aut Quantum computation of zeta functions of curves [Elektronische Daten] [Kiran Kedlaya] Abstract.: We exhibit a quantum algorithm for determining the zeta function of a genus g curve over a finite field $$ \mathbb{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. Birkhäuser Verlag, Basel, 2006 Quantum computation nationallicence zeta functions nationallicence class groups nationallicence algebraic curves nationallicence finite fields nationallicence cyclic resultants nationallicence 81P68 nationallicence 11G20 nationallicence 14G10 nationallicence computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/1(2006-05-01), 1-19 1016-3328 15:1<1 2006 15 37 https://doi.org/10.1007/s00037-006-0204-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-006-0204-7 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Kedlaya Kiran Department of Mathematics, Massachusetts Institute of Technology, Room 2-165, 77 Massachusetts Avenue, 02139, Cambridge, MA, U.S.A aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/1(2006-05-01), 1-19 1016-3328 15:1<1 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer