{"id":"arxiv/2608.23929","url":"https://arxiv.org/abs/2608.23929","tags":["quant-ph","cs.CC","math.AG","math.NT"],"score":0,"title":"Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields","domain":"quant-ph","source":"arxiv","authors":["Yota Maeda","Hiroshi Yano"],"reviews":0,"subject":"quant-ph","summary":"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 $ρ$ 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-ρ} \\] with success probability $1-δ$. Provided that $ρ$ and $\\|U\\|_\\infty$ are…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}