We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree n over a finite field Fq, the average-case complexity of our algorithm is an exp...
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}.
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}.
For general max-k-XORSAT with k≥3, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless P=NP: approximating beyond the random-assignment value of 1/2 is NP-hard. The picture changes when each variable appears in at most D constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order 1/D. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-Ek-LINSAT(q,r) with bounded degree D and over arbitrary finite fields Fq, proving that it is NP-hard to exceed r/q+Oq,r(1/D). These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on (k,D)-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic 1/DlogD barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the 1/D scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.
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 work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case NP search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field F2 drawn from a specified distribution. In particular, for any d≥2, we design a distribution of degree up to d polynomials {pi(x1,…,xn)}i∈[m] for m<n over F2 for which we show that there is an expected polynomial-time quantum algorithm that provably simultaneously solves {pi(x1,…,xn)=yi}i∈[m] for a random vector (y1,…,ym). On the other hand, while solutions exist with high probability, we conjecture that for constant d>2, it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.
Abstract Primitive polynomials over finite fields are crucial resources with broad applications across various domains in computer science, including classical pseudo‐random number generation, coding theory, and post‐quantum cryptography. Nevertheless, the pursuit of an efficient classical algorithm for generating random primitive polynomials over finite fields remains an ongoing challenge. In this work, it shows how this problem can be solved efficiently with the help of quantum computers. Moreover, the designs of specific quantum circuits to implement them are also presented. The research paves the way for the rapid and real‐time generation of random primitive polynomials in diverse quantum communication and computation applications.