Quantum Mechanical Algorithm for Solving Quadratic Residue Equation

We propose a quantum mechanical algorithm for solving quadratic residue equation z ²=b (mod M) based on Grover quantum search. The quantum algorithm will take O( ?Msqrt{M} ) steps for finding the solutions to the equation by exploiting the properties of quantum superposition and interference effect, while classical algorithm to the same problem will take O(M) steps. The success probability of the algorithm approaches to unity and the cost of the algorithm mainly depends on the calculations of quadratic residue modulo M and the number of iterations. Furthermore, we show that the algorithm can be used to solve the prime factorization problem, and the computing complexity is O( ?Nsqrt{N} ).