Quantum Probabilistic Subroutines and Problems in Number Theory

Abstract

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.

9 pages, RevTex, revised version, accepted for publication on PRA: improvement in use of memory space for quantum primality test algorithm further clarified and typos in the notation corrected

References in corpus (2)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing

Cited by in corpus (5)

• Decoherence on Grover's quantum algorithm: perturbative approach
• A quantum primality test with order finding
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Robustness of QMA against witness noise
• Frontier between separability and quantum entanglement in a many spin system