Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function

Abstract

Two quantum algorithms of finding the roots of a polynomial function f(x) = x (m) + a (m- 1) x (m- 1) + ... + a (1) x + a (0) are discussed by using the Bernstein-Vazirani algorithm. One algorithm is presented in the modulo 2. The other algorithm is presented in the modulo d. Here all the roots are in the integers Z. The speed of solving the problem is shown to outperform the best classical case by a factor of m in both cases.