← Back to papers
Toward an optimal quantum algorithm for polynomial factorization over finite fields
Javad Doliskani·July 25, 2018·DOI: 10.26421/QIC19.1-2-1
Computer ScienceMathematicsPhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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}.