Yota Maeda

It is unknown whether there exists a classical or quantum algorithm that, for a polynomial equation over $\mathbb{F}_q$, counts its zero set in time polynomial in $\log q$, or even approximates the number of solutions, except in low-dimensional or highly structured cases. In this work, we study quantum algorithms that approximate the number of solutions of Laurent polynomials. For a fixed Laurent polynomial $f$ in $n$ variables with $s$ monomials and full-rank support, which means the augmented exponent matrix has full column rank, we construct a quantum algorithm that, for a given $\varepsilon$, outputs an estimate $\widetilde N^*(f)$ of $N^*(f)$, the number of torus points on the associated toric hypersurface, such that \[ \Pr\Bigl[\bigl|\widetilde N^*(f)-N^*(f)\bigr| \le \varepsilon q^{n-s/2}\Bigr] \ge \tfrac23 \] in time $\mathrm{poly}(\log q,1/\varepsilon)$. To the best of our knowledge, this is the first $\mathrm{poly}(\log q, 1/\varepsilon)$-time quantum algorithm achieving an approximation guarantee beyond the general Lang–Weil scale for a nontrivial class of hypersurfaces over finite fields.