|
related topics |
{algorithm, log, probability} |
{qubit, qubits, gate} |
{equation, function, exp} |
{state, states, entangled} |
{cos, sin, state} |
{operator, operators, space} |
{error, code, errors} |
{group, space, representation} |
{state, algorithm, problem} |
{phase, path, phys} |
|
Quantum Probabilistic Subroutines and Problems in Number Theory
A. Carlini, A. Hosoya
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/9907020
- categories:
- quant-ph
- comments:
- 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
- doi:
- 10.1103/PhysRevA.62.032312
- arxiv_id:
- quant-ph/9907020
- report_no:
- TIT/HEP-426/COSMO-94
- created:
- 1999-07-06
- updated:
- 2000-02-07
Full article ▸
|
|
related documents |
0410042v1 |
0304131v1 |
0403140v2 |
0010034v1 |
0607148v3 |
9802040v2 |
9903071v1 |
0207131v1 |
0511272v1 |
0505007v3 |
0201152v1 |
9905026v1 |
0504067v3 |
0302022v1 |
0206089v2 |
0210077v1 |
0011052v2 |
0408150v2 |
0612089v3 |
0303175v1 |
0010021v1 |
0008059v3 |
0106152v1 |
0306042v1 |
0109038v1 |
|