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

arXiv:1507.08852 · Science

Realization of a scalable Shor algorithm

Thomas Monz, Daniel Nigg, Esteban A. Martinez, Matthias F. Brandl, Philipp Schindler, Richard Rines, Shannon X. Wang, Isaac L. Chuang, R. Blatt

Published Mar 3, 2016• 486 citations
arXivHTMLPDF

Abstract

Certain algorithms for quantum computers are able to outperform their classical counterparts. In 1994, Peter Shor came up with a quantum algorithm that calculates the prime factors of a large number vastly more efficiently than a classical computer. For general scalability of such algorithms, hardware, quantum error correction, and the algorithmic realization itself need to be extensible. Here we present the realization of a scalable Shor algorithm, as proposed by Kitaev. We factor the number 15 by effectively employing and controlling seven qubits and four "cache qubits" and by implementing generalized arithmetic operations, known as modular multipliers. This algorithm has been realized scalably within an ion-trap quantum computer and returns the correct factors with a confidence level exceeding 99%.

DOI
10.1126/science.aad9480

Related papers

Realization of Shor's Algorithm at Room Temperature

Niklas Johansson, Jan-Åke Larsson

Shor's algorithm can find prime factors of a large number more efficiently than any known classical algorithm. Understanding the properties that gives the speedup is essential for a general and scalable construction. Here we present a realization of Shor's algorithm, that does not need any of the simplifications presently needed in current experiments and also gives smaller systematic errors than any former experimental implementation. Our realization is based on classical pass-transistor logic, runs at room temperature, and uses the same amount of resources as a scalable quantum computer. In this paper, the focus is not on the result of the factorization, but to compare our realization with current state-of-the-art experiment, factoring 15. Our result gives further insight to the resources needed for quantum computation, aiming for a true understanding of the subject.

arXiv:1706.03215•Jun 10, 2017•7 citations

Implementation of 5-Qubit approach-based Shor's Algorithm in IBM Qiskit

G. R. Mounica, G. Manimaran, Lauret Jerome +1 more

RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.

IEEE Pune Section International Conference (PuneCon)•Dec 16, 2021•17 citations

Shor's factorization algorithm

E. Desurvire

This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.

Cambridge University Press eBooks•Feb 19, 2009•0 citations

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored. Keywords: Factorization, quantum circuits, modular arithmetics

arXiv:quant-ph/0205095•May 15, 2002•18 citations

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

Edward 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•76 citations

Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers

Gerjuoy, E

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 (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) 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 can. It is made apparent that factoring $N$ generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.

•Nov 25, 2004•50 citations
Certain algorithms for quantum computers are able to outperform their classical counterparts. In 1994, Peter Shor came up with a quantum algorithm that calculates the prime factors of a large number vastly more efficiently than a classical computer. For general scalability of such algorithms, hardware, quantum error correction, and the algorithmic realization itself need to be extensible. Here we present the realization of a scalable Shor algorithm, as proposed by Kitaev. We factor the number 15 by effectively employing and controlling seven qubits and four "cache qubits" and by implementing generalized arithmetic operations, known as modular multipliers. This algorithm has been realized scalably within an ion-trap quantum computer and returns the correct factors with a confidence level exceeding 99%.
Shor's algorithm can find prime factors of a large number more efficiently than any known classical algorithm. Understanding the properties that gives the speedup is essential for a general and scalable construction. Here we present a realization of Shor's algorithm, that does not need any of the simplifications presently needed in current experiments and also gives smaller systematic errors than any former experimental implementation. Our realization is based on classical pass-transistor logic, runs at room temperature, and uses the same amount of resources as a scalable quantum computer. In this paper, the focus is not on the result of the factorization, but to compare our realization with current state-of-the-art experiment, factoring 15. Our result gives further insight to the resources needed for quantum computation, aiming for a true understanding of the subject.
RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.
This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.
We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored. Keywords: Factorization, quantum circuits, modular arithmetics
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.
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 (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) 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 can. It is made apparent that factoring NNN generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.