Quantum probabilistic subroutines and problems in number theory - art. no.032312

We present a quantum version of the classical probabilistic algorithms as s tudied by Rabin. The quantum algorithm is based on the essential use of Gro ver's operator for the quantum search of a database and of Shor's Fourier t ransform for extracting the periodicity of a function, and their combined u se in the counting algorithm originally introduced by Brassard et al. One o f the main features of our quantum probabilistic algorithm is its full unit arity and reversibility, which would make its use possible as part of large r and mole complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problem s in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about t he asymptotic number of representations of an even integer as a sum of two primes.