  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}.
