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

European Journal of Physics

Factoring 15 with a remote quantum computer: a complete guide for beginners

Jed Brody, Kristen Gram

Published Mar 12, 2024• 0 citations
Publisher

Abstract

Abstract We present, for the non-specialist, an experimental implementation of Shor’s factoring algorithm. We are unaware of any other single reference that explains, in a beginner-friendly way, complete circuits that implement Shor’s algorithm. We perform the experiment with IBM quantum processors, which are remotely accessible online for free. We reproducibly factor 15 with one 7-qubit processor (ibm_perth), while four other quantum processors exhibit excessive error.

DOI
10.1088/1361-6404/ad32dc

Related papers

Demonstration of Shor’s factoring algorithm for N === 21 on IBM quantum processors

Unathi Skosana, Mark Tame

We report a proof-of-concept demonstration of a quantum order-finding algorithm for factoring the integer 21. Our demonstration involves the use of a compiled version of the quantum phase estimation routine, and builds upon a previous demonstration. We go beyond this work by using a configuration of approximate Toffoli gates with residual phase shifts, which preserves the functional correctness and allows us to achieve a complete factoring of [Formula: see text]. We implemented the algorithm on IBM quantum processors using only five qubits and successfully verified the presence of entanglement between the control and work register qubits, which is a necessary condition for the algorithm's speedup in general. The techniques we employ may be useful in carrying out Shor's algorithm for larger integers, or other algorithms in systems with a limited number of noisy qubits.

arXiv:2103.13855•Scientific Reports•Aug 16, 2021•66 citations

Experimental study of Shor's factoring algorithm using the IBM Q Experience

Mirko Amico, Zain H. Saleem, Muir Kumph

We study the results of a compiled version of Shor's factoring algorithm on the ibmqx5 superconducting chip, for the particular case of $N=15$, 21, and 35. The semiclassical quantum Fourier transform is used to implement the algorithm with only a small number of physical qubits, and the circuits are designed to reduce the number of gates to the minimum. We use the square of the statistical overlap to give a quantitative measure of the similarity between the experimentally obtained distribution of phases and the predicted theoretical distribution of phases for different values of the period. This allows us to assign a period to the experimental data without the use of the continued fraction algorithm. A quantitative estimate of the error in our assignment of the period is then given by the overlap coefficient.

arXiv:1903.00768•Physical Review A•Jul 8, 2019•75 citations

Practical Challenges in Executing Shor's Algorithm on Existing Quantum Platforms

Paul Bagourd, Julian Jang-Jaccard, Vincent Lenders +3 more

Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.

quant-pharXiv:2512.15330•Dec 18, 2025•0 citations

Insights and Limitations of Shor’s Factorization Algorithm on IBM Real Quantum Computers

Camps Carmona, Adriano José, Manresa, Gerard De, Villarreal D’Angelo, Juan Manuel

Quantum Shor’s algorithm offers an exponential speedup over classical methods for integer factorization, a central problem to modern cryptography, and the implica- tions of Shor’s algorithm in factoring large numbers. The algorithm leverages on quantum parallelism to compute the period of a modular exponentiation function, employ- ing the Inverse Quantum Fourier Transform (IQFT) to extract periodicity, and classical post-processing to derive the factors. This final report of the Quantum Engineer- ing post-graduate course of the Fundacio Polit ́ enica de ` Catalunya, presents the main findings encountered in the implementation and benchmarking of Schor’s algorithm in real IBM quantum computers. To accomplish this, we created a command line tool made in Python, that allows the integration of the circuits implementing the Shor’s algorithm with the overall set of configuration parameters needed to perform the benchmark. In this report, we first provide an overview of the quantum factoring problem, followed by a detailed description of Shor’s algorithm, and its implementation using the Qiskit Python library. The circuit depth and noise effects are analyzed across different backend types, also different values for the optimization level and approximation degrees are configured when performing the circuit transpilation. As mentioned earlier different backend types were utilized for performance comparison, namely backend class with or without a noise model (AerSim), a fake backend class provided by the Qiskit library (fake provider), and the real quantum hardware (IBM Quantum Processing Units in January- June 2025).The study follows by analyzing the different error mitigation techniques: dynamic decoupling, Pauli twirling, the SABRE Optimization (Stochastic Algorithm for Quantum Boolean Optimization and Routing), and any combination of them. Once the optimum configuration is found, the maximum number that can be reasonably factorized with success is explored. Finally, the main conclusions, findings, and possible future research lines are presented, including the factorization of a N ≈ 1000 if appropriate parameters of the algorithm are selected.

•Jan 1, 2025•0 citations

Shor's Algorithm for Factoring Large Integers

Carlile Lavor, L. R. U. MANSSUR, Renato Portugal

This work is a tutorial on Shor's factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra.

arXiv:quant-ph/0303175•Mar 29, 2003•10 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.

Quantum Information and Computation•Mar 1, 2003•207 citations
Abstract We present, for the non-specialist, an experimental implementation of Shor’s factoring algorithm. We are unaware of any other single reference that explains, in a beginner-friendly way, complete circuits that implement Shor’s algorithm. We perform the experiment with IBM quantum processors, which are remotely accessible online for free. We reproducibly factor 15 with one 7-qubit processor (ibm_perth), while four other quantum processors exhibit excessive error.
We report a proof-of-concept demonstration of a quantum order-finding algorithm for factoring the integer 21. Our demonstration involves the use of a compiled version of the quantum phase estimation routine, and builds upon a previous demonstration. We go beyond this work by using a configuration of approximate Toffoli gates with residual phase shifts, which preserves the functional correctness and allows us to achieve a complete factoring of [Formula: see text]. We implemented the algorithm on IBM quantum processors using only five qubits and successfully verified the presence of entanglement between the control and work register qubits, which is a necessary condition for the algorithm's speedup in general. The techniques we employ may be useful in carrying out Shor's algorithm for larger integers, or other algorithms in systems with a limited number of noisy qubits.
We study the results of a compiled version of Shor's factoring algorithm on the ibmqx5 superconducting chip, for the particular case of N=15N=15N=15, 21, and 35. The semiclassical quantum Fourier transform is used to implement the algorithm with only a small number of physical qubits, and the circuits are designed to reduce the number of gates to the minimum. We use the square of the statistical overlap to give a quantitative measure of the similarity between the experimentally obtained distribution of phases and the predicted theoretical distribution of phases for different values of the period. This allows us to assign a period to the experimental data without the use of the continued fraction algorithm. A quantitative estimate of the error in our assignment of the period is then given by the overlap coefficient.
Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.
Quantum Shor’s algorithm offers an exponential speedup over classical methods for integer factorization, a central problem to modern cryptography, and the implica- tions of Shor’s algorithm in factoring large numbers. The algorithm leverages on quantum parallelism to compute the period of a modular exponentiation function, employ- ing the Inverse Quantum Fourier Transform (IQFT) to extract periodicity, and classical post-processing to derive the factors. This final report of the Quantum Engineer- ing post-graduate course of the Fundacio Polit ́ enica de ` Catalunya, presents the main findings encountered in the implementation and benchmarking of Schor’s algorithm in real IBM quantum computers. To accomplish this, we created a command line tool made in Python, that allows the integration of the circuits implementing the Shor’s algorithm with the overall set of configuration parameters needed to perform the benchmark. In this report, we first provide an overview of the quantum factoring problem, followed by a detailed description of Shor’s algorithm, and its implementation using the Qiskit Python library. The circuit depth and noise effects are analyzed across different backend types, also different values for the optimization level and approximation degrees are configured when performing the circuit transpilation. As mentioned earlier different backend types were utilized for performance comparison, namely backend class with or without a noise model (AerSim), a fake backend class provided by the Qiskit library (fake provider), and the real quantum hardware (IBM Quantum Processing Units in January- June 2025).The study follows by analyzing the different error mitigation techniques: dynamic decoupling, Pauli twirling, the SABRE Optimization (Stochastic Algorithm for Quantum Boolean Optimization and Routing), and any combination of them. Once the optimum configuration is found, the maximum number that can be reasonably factorized with success is explored. Finally, the main conclusions, findings, and possible future research lines are presented, including the factorization of a N ≈ 1000 if appropriate parameters of the algorithm are selected.