Skip to content
Preprint

Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields

Aug 2026 · 0 citations · 60 references
Physics Computer Science Mathematics

TL;DR

By exploiting a point-counting formula derived from character sums over finite fields, this work develops an alternative approach that efficiently approximates the number of points without assuming the existence of an oracle.

Abstract

We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $\rho$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-\rho} \] with success probability $1-\delta$. Provided that $\rho$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/\delta))$. It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in $\log q$. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes $\#$P-hard under randomized polynomial-time Turing reductions when the support matrix $U$ varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.

View source

Similar papers

Preprint Sep 2026

Galois groups of random polynomials of large degree

We study random polynomials of the form $R(x)=x^n+\omega_{n-1}x^{n-1}+\cdots+\omega_0$, where $\omega_0,\dots,\omega_{n-1}$ are independent, uniformly bounded integer-valued random variables, and $\omega_1,\dots,\omega_{n-1}$ have a fixed common law $\mu$. We prove (unconditionally) that, if the R\'{e}nyi entropy of or...

Guy Blachar, E. Breuillard, G. Kozma · 1 citation
Preprint Sep 2026

Resolving a conjecture on permutation polynomials over $\mathbb{F}_{2^n}$

Let $\delta\in\mathbb{F}_{2^n}$ satisfy $\operatorname{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(\delta)=1$. We study the permutation behavior of $$ f(x) = \left(\frac{1}{x^2+x+\delta}\right)^{2^k}+x $$ over $\mathbb{F}_{2^n}$. Helleseth and Zinoviev proved that $f(x)$ is a permutation for $k=0,1$, and remarked that numerica...

Yi Li · 0 citations
Preprint Aug 2026

Cyclotomic Newton Expansions and a Rank-Uniform Integer-Valued Newton Completion

Let $J_r^{SU(n)}(K;q)$ denote the reduced $SU(n)$ quantum invariant of a zero-framed knot $K$, colored by the $r$th symmetric power of the defining representation and normalized to be $1$ for the unknot. For every fixed $n\ge2$ we prove the Chen--Liu--Zhu cyclotomic expansion conjecture: there are unique coefficients $...

Hong-Huai Fang, Tian Zhou · 2 citations
Preprint Oct 2026

Quadratic distances in even dimensions over prime fields

Let $p$ be an odd prime, let $m\geq1$ be an integer, and let $Q$ be a nondegenerate quadratic form on $\mathbb F_p^{2m}$. For a nonempty set $E\subseteq\mathbb F_p^{2m}$, write $\Delta_Q(E)=\{Q(x-y):x,y\in E\}$. We prove that, whenever $|E|>p^m$, \[ |\Delta_Q(E)|\gg \min\left\{\frac{p}{L_E},\, \frac{|E|}{p^{m-1}L_E^2}\...

Thang Pham, Chun-Yen Shen, Dung The Tran et al. · 1 citation · ⚡1
Preprint Aug 2026

Quadratic Expansion over Prime Fields via Centered Collisions and Popular-Sum Amplification

Let $p$ be an odd prime, let $\varnothing\neq A\subseteq\mathbb F_p$ have cardinality $N$, and let $f\in\mathbb F_p[x,y]$ be a non-degenerate quadratic polynomial. Writing $S=|A+A|$ and $M=|f(A,A)|$, we prove the full-range trade-off $S^8M^6\gtrsim N^{17}(1+N^3/p^2)^{-3}$. Consequently, $\max\{|A+A|,|f(A,A)|\}\gtrsim \...

Zhi Yao · 0 citations
Preprint Sep 2026

Generalized Frobenius Partitions Modulo Powers of $2$

Let $c\phi_k(n)$ denote the number of $k$-colored generalized Frobenius partitions of $n$. We prove that, for every $m\geq2$ and every $k\equiv2\pmod{2^m}$, \[ \sum_{n\geq0}c\phi_k(n)q^n\equiv\frac{\varphi(q)\,(q^2;q^2)_\infty}{(q;q)_\infty^2}\sum_{n\geq0}c\phi_{k/2}(n)q^{2n}\pmod{2^m}, \] where $\varphi(q)$ is the cla...

Manjil P. Saikia · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.