{"id":"arxiv/2607.29453","url":"https://arxiv.org/abs/2607.29453","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Algorithms for Modular Factorials","domain":"quant-ph","source":"arxiv","authors":["Yann Tal"],"reviews":0,"subject":"quant-ph","summary":"We give a bounded-error quantum algorithm that, given a prime $p$, a divisor $q\\mid(p-1)$, and an integer $0<n<p$, computes $n!\\bmod p$ in expected time $\\widetilde{O}(q^c+\\sqrt{p/q})$ for some absolute constant $c\\ge 1$. When $p-1$ has a divisor of size $q\\approx p^{1/(2c+1)}$, this gives the exponent $c/(2c+1)<1/2$. To our knowledge, this is the first algorithm to break the exponent $1/2$ barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}