Geodesic
Quantum computing
Documenta mathematica, ICM Berlin 1998, Vol. I (1998), pp. 467-486.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

The Church-Turing thesis says that a digital computer is a universal computational device; that is, it is able to simulate any physically realizable computational device. It has generally been believed that this simulation can be made efficient so that it entails at most a polynomial increase in computation time. This may not be true if quantum mechanics is taken into consideration. A quantum computer is a hypothetical machine based on quantum mechanics. We explain quantum computing, and give an algorithm for prime factorization on a quantum computer that runs asymptotically much faster than the best known algorithm on a digital computer. It is not clear whether it will ever be possible to build large-scale quantum computers. One of the main difficulties is in manipulating coherent quantum states without introducing errors or losing coherence. We discuss quantum error-correcting codes and fault-tolerant quantum computing, which can guarantee highly reliable quantum computation, given only moderately reliable quantum computing hardware.
Classification : 68Q05, 11Y05, 81P99
Keywords: computational complexity, prime factorization 
@article{DOCMA_1998__S10__a11,
     author = {Shor, Peter W.},
     title = {Quantum computing},
     journal = {Documenta mathematica},
     pages = {467--486},
     publisher = {mathdoc},
     volume = {ICM Berlin 1998, Vol. I},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DOCMA_1998__S10__a11/}
}
TY  - JOUR
AU  - Shor, Peter W.
TI  - Quantum computing
JO  - Documenta mathematica
PY  - 1998
SP  - 467
EP  - 486
VL  - ICM Berlin 1998, Vol. I
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DOCMA_1998__S10__a11/
LA  - en
ID  - DOCMA_1998__S10__a11
ER  - 
%0 Journal Article
%A Shor, Peter W.
%T Quantum computing
%J Documenta mathematica
%D 1998
%P 467-486
%V ICM Berlin 1998, Vol. I
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DOCMA_1998__S10__a11/
%G en
%F DOCMA_1998__S10__a11
Shor, Peter W. Quantum computing. Documenta mathematica, ICM Berlin 1998, Vol. I (1998), pp. 467-486. http://geodesic.mathdoc.fr/item/DOCMA_1998__S10__a11/