Quantum versions of classical randomized algorithms

Alberto Carlini, Akio Hosoya

Risultato della ricerca: Contributo su rivistaArticolo in rivistapeer review

Abstract

We present a quantum version of the classical probabilistic algorithms a' la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the 'prime number theorem' and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.

Lingua originaleInglese
pagine (da-a)495-500
Numero di pagine6
RivistaProgress of Theoretical Physics Supplement
Numero di pubblicazione138
DOI
Stato di pubblicazionePubblicato - 2000
Pubblicato esternamente

Fingerprint

Entra nei temi di ricerca di 'Quantum versions of classical randomized algorithms'. Insieme formano una fingerprint unica.

Cita questo