Quantum computation of zeta functions of curves (Q2506162): Difference between revisions

The author exhibits a quantum algorithm for determining the zeta function of a genus \(g\) curve \(C\) over a finite field \(k=\mathbb{F}_q\), which is polynomial time in \(g\) and \(\log q\). The best current classical algorithm to obtain this result is only polynomial in \(g\) and in \(\log(q)\) for a fixed characteristic \(p\). The algorithm is based on a result of \textit{J. Watrous} [Proc. 33rd annual ACM symposium on theory of computing (STOC 2001), Hersonissos, Crete, Greece, July 6--8, 2001. (2001; Zbl 1074.68500)] which gives a quantum algorithm to compute the order of a group knowing its Monte Carlo black box group presentation. It relies also on some effective elementary algebraic geometry results (mainly Riemann-Roch theorem) to produce provably random elements of the Jacobian -- which will turn out to be a generator set-- and a final trick to recover the Weil polynomial in terms of the order of the group of rational points of the Jacobian of \(C\) over \(2g\) extensions. An interesting question raised in the article is to know if one could do less than these \(2g\) extensions. Indeed, this question is related to the recovering of a (reciprocal, even degree) polynomial \(P\) of degree \(d\) from enough of its cyclic resultants. A conjecture of Sturmfels and Zworski assures that the first \(d/2+1\) resultants should suffice for \(P\) generic.