We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree n over a finite field F_q, the average-case complexity of our algorithm is an expected O(n^{1 + o(1)} \log^{2 + o(1)}q) bit operations. Only for a negligible subset of polynomials of degree $n$ our algorithm has a higher complexity of O(n^{4/3 + o(1)} \log^{2 + o(1)}q) bit operations. This breaks the classical 3/2-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.
We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree n over a finite field F_q, the average-case complexity of our algorithm is an expected O(n^{1 + o(1)} \log^{2 + o(1)}q) bit operations. Only for a negligible subset of polynomials of degree n our algorithm has a higher complexity of O(n^{4/3 + o(1)} \log^{2 + o(1)}q) bit operations. This breaks the classical 3/2-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.
We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree n over a finite field $\F_q$, the average-case complexity of our algorithm is an expected O(n1+o(1)log2+o(1)q) bit operations. Only for a negligible subset of polynomials of degree n our algorithm has a higher complexity of O(n4/3+o(1)log2+o(1)q) bit operations. This breaks the classical 3/2-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.
How many quantum queries are required to determine the coefficients of a degree- d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields F q , R and C . We show that k C and 2 k C queries suffice to achieve probability 1 for C and R , respectively, where k C = ⌈ ( 1 / ( n + 1 ) ) ( n + d d ) ⌉ except for d =2 and four other special cases. For F q , we show that ⌈( d /( n + d ))( n + d d ) ⌉ queries suffice to achieve probability approaching 1 for large field order q . The classical query complexity of this problem is ( n + d d ) , so our result provides a speed-up by a factor of n +1, ( n +1)/2 and ( n + d )/ d for C , R and F q
In this note we study the number of quantum queries required to identify an unknown multilinear polynomial of degree d in n variables over a finite field F_q. Any bounded-error classical algorithm for this task requires Omega(n^d) queries to the polynomial. We give an exact quantum algorithm that uses O(n^(d-1)) queries for constant d, which is optimal. In the case q=2, this gives a quantum algorithm that uses O(n^(d-1)) queries to identify a codeword picked from the binary Reed-Muller code of order d.
We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial f(x)=∑j=1sajxuj∈Fq[x1±1,…,xn±1], let U be its augmented support matrix whose columns are (1,uj) with rank ρ and N(f):=#{x∈(Fq×)n∣f(x)=0} be its torus point count. Our first main result is a quantum algorithm that outputs N(f) satisfying ∣N(f)−N(f)∣≤εqn+s/2−ρ with success probability 1−δ. Provided that ρ and ∥U∥∞ are bounded, the algorithm runs in both classical bit and quantum gate complexity poly(n,s,logq,1/ε,log(1/δ)). 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 logq. 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.
We give a bounded-error quantum algorithm that, given a prime p, a divisor q∣(p−1), and an integer 0<n<p, computes n!modp in expected time O(qc+p/q) for some absolute constant c≥1. When p−1 has a divisor of size q≈p1/(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 polynomial dependence on q and logp. We further extend the same asymptotic bound to the computation of n!modp2, uniformly over 0≤n<p2. At n=p−1, this determines the Wilson quotient p(p−1)!+1(modp). We conjecture that the condition q∣(p−1) is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.