Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physics World

Remapping the quantum frontier

Christopher R. Monroe, Mikhail D. Lukin

Published Aug 1, 2008• 33 citations
Publisher

Abstract

In 1994 the mathematician Peter Shor, then working at AT&T Bell Laboratories in the US, applied quantum mechanics to an age-old problem in number theory and made a remarkable discovery. He showed that a computer that operates on and processes quantum systems could factor large integers exponentially faster than a conventional computer. This result attracted a lot of attention because the difficulty of factoring large numbers is what ensures the security of modern cryptography schemes – even the best conventional computer would take several thousand years to factor a number with more than about 150 digits. Shor's quantum factoring algorithm could, in principle, break such encryption standards – a possibility that led to an explosion of interest in quantum information science. Until then it was a field that had largely been a mere curiosity, despite notable contributions from the likes of Richard Feynman and David Deutsch.

DOI
10.1088/2058-7058/21/08/37

Related papers

An Introduction to Quantum Computing Algorithms

A. O. Pittenger

In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com­ puter. Since the difficulty of the factoring problem is crucial for the se­ curity of a public key encryption system, interest (and funding) in quan­ tum computing and quantum computation suddenly blossomed. Quan­ tum computing had arrived. The study of the role of quantum mechanics in the theory of computa­ tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]' [7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system.

Birkhäuser Boston eBooks•Jan 1, 2000•148 citations

Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers

E. Gerjuoy

The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.

arXiv:quant-ph/0411184•American Journal of Physics•May 13, 2005•101 citations

An introduction to quantum computing for non-physicists

Eleanor Gilbert Rieffel, Wolfgang Polak

Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers. In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques. The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.

arXiv:quant-ph/9809016•ACM Computing Surveys•Sep 1, 2000•476 citations

Shor Algorithm

Ray LaPierre

In 1994, a mathematician named Peter Shor surprised the world by publishing an efficient quantum algorithm for finding the prime factors of very large numbers, which is the basis for today’s data encryption. This discovery spurred the further development of quantum computing, making Shor’s algorithm one of the most important algorithms.

The Materials Research Society series•Oct 24, 2025•0 citations

Computation with quantum systems

David J. Wineland

Summary form only given. In 1994, Peter Shor showed that a computer based on the rules that govern quantum systems could efficiently factorize large numbers. Because of the implications of this idea on the security of data encryption, funding for the development of such a device increased significantly and sparked research for other applications of quantum information processing (QIP). Since then, the elementary logic operations and simple algorithms for such a device have been demonstrated, but building a useful quantum computer is an extremely daunting task due to the necessity of overcoming decoherence of the inherent large entangled quantum superposition states. Nevertheless, in the near term, the principles of QIP are finding applications in metrology (such as for atomic clocks) and may also provide a way to efficiently simulate other quantum systems of interest, a motivation that intrigued Richard Feynman in the early 1980's. A number of physical systems are currently considered for building a quantum computer; this talk will focus on the use of registers of atomic ions, but connections to other possible physical implementations are rather direct.

Conference digest•Jun 1, 2010•0 citations

Shor Algorithm

Ray LaPierre

In 1994, a mathematician named Peter Shor surprised the world by publishing an efficient quantum algorithm for finding the prime factors of very large numbers, which is the basis for today’s data encryption. This discovery spurred the further development of quantum computing, making Shor’s algorithm one of the most important algorithms.

The Materials Research Society series•Jan 1, 2021•14 citations
In 1994 the mathematician Peter Shor, then working at AT&T Bell Laboratories in the US, applied quantum mechanics to an age-old problem in number theory and made a remarkable discovery. He showed that a computer that operates on and processes quantum systems could factor large integers exponentially faster than a conventional computer. This result attracted a lot of attention because the difficulty of factoring large numbers is what ensures the security of modern cryptography schemes – even the best conventional computer would take several thousand years to factor a number with more than about 150 digits. Shor's quantum factoring algorithm could, in principle, break such encryption standards – a possibility that led to an explosion of interest in quantum information science. Until then it was a field that had largely been a mere curiosity, despite notable contributions from the likes of Richard Feynman and David Deutsch.
In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com­ puter. Since the difficulty of the factoring problem is crucial for the se­ curity of a public key encryption system, interest (and funding) in quan­ tum computing and quantum computation suddenly blossomed. Quan­ tum computing had arrived. The study of the role of quantum mechanics in the theory of computa­ tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]' [7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system.
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers. In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques. The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.
Summary form only given. In 1994, Peter Shor showed that a computer based on the rules that govern quantum systems could efficiently factorize large numbers. Because of the implications of this idea on the security of data encryption, funding for the development of such a device increased significantly and sparked research for other applications of quantum information processing (QIP). Since then, the elementary logic operations and simple algorithms for such a device have been demonstrated, but building a useful quantum computer is an extremely daunting task due to the necessity of overcoming decoherence of the inherent large entangled quantum superposition states. Nevertheless, in the near term, the principles of QIP are finding applications in metrology (such as for atomic clocks) and may also provide a way to efficiently simulate other quantum systems of interest, a motivation that intrigued Richard Feynman in the early 1980's. A number of physical systems are currently considered for building a quantum computer; this talk will focus on the use of registers of atomic ions, but connections to other possible physical implementations are rather direct.