Quantum Probabilistic Subroutines and Problems in Number Theory

Details Quantum Probabilistic Subroutines and Problems in Number Theory Quantum Probabilistic Subroutines and Problems in Number Theory

1999-07-06

arxiv.org/abs/quant-ph/9907020v2

Physics

Quantum Physics

9 pages, RevTex, revised version, accepted for publication on PRA: improvement in use of memory space for quantum primality te

Scientific paper

10.1103/PhysRevA.62.032312

We present a quantum version of the classical probabilistic algorithms $\grave{a}$ la Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems 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 the asymptotic number of representations of an even integer as a sum of two primes.

Affiliated with

Also associated with

No associations

Rating

Quantum Probabilistic Subroutines and Problems in Number Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Probabilistic Subroutines and Problems in Number Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Probabilistic Subroutines and Problems in Number Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-604800