Quantum computation of zeta functions of curves

详细信息    查看全文

• 作者：Kiran S. Kedlaya
• 关键词：Quantum computation ; zeta functions ; class groups ; algebraic curves ; finite fields ; cyclic resultants
• 刊名：Computational Complexity
• 出版年：2006
• 出版时间：May 2006
• 年：2006
• 卷：15
• 期：1
• 页码：1-19
• 全文大小：214 KB
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Computational Mathematics and Numerical Analysis
  
• 出版者：Birkh盲user Basel
• ISSN：1420-8954

文摘

We exhibit a quantum algorithm for determining the zeta function of a genus g curve over a finite field \mathbbF<sub>qsub> \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.