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:quant-ph/0308171 · Physical Review A

Implementing Shor’s algorithm on Josephson charge qubits

Juha J. Vartiainen, A. O. Niskanen, Mikio Nakahara, Martti M. Salomaa

Published Jul 30, 2004• 23 citations
arXivHTMLPDF

Abstract

We investigate the physical implementation of Shor's factorization algorithm on a Josephson charge qubit register. While we pursue a universal method to factor a composite integer of any size, the scheme is demonstrated for the number 21. We consider both the physical and algorithmic requirements for an optimal implementation when only a small number of qubits are available. These aspects of quantum computation are usually the topics of separate research communities; we present a unifying discussion of both of these fundamental features bridging Shor's algorithm to its physical realization using Josephson junction qubits. In order to meet the stringent requirements set by a short decoherence time, we accelerate the algorithm by decomposing the quantum circuit into tailored two- and three-qubit gates and we find their physical realizations through numerical optimization.

DOI
10.1103/physreva.70.012319

Related papers

Method to Factorize Fifteen with Josephson Charge Qubits

Juha J. Vartiainen, A. O. Niskanen, Mikio Nakahara +1 more

We investigate both the physical and algorithmic requirements for an implementation of Shor's factorization algorithm on a hypothetical Josephson charge qubit register. We represent an implementation which is optimal for small number of available qubits, but still provides a general method to factorize integer without a prior knowledge of the number to be factorized. Furthermore, our strategy is easily generalized to other realizations and parameter values. In order to meet the stringent requirements set by short decoherence time, we accelerate the algorithm by decomposing it into tailored two- and three-qubit gates and find their physical realizations through the numerical optimization.

•Aug 29, 2003•0 citations

Near term implementation of Shor's Algorithm using Qiskit

Casimer M. DeCusatis, Emily Mcgettrick

Although the fundamental principles of quantum computing have been known for decades, it is only within the past few years that practical quantum computers have become available. Since these systems are limited to a small number of qubits, they cannot demonstrate quantum advantage for many practical problems. Accordingly, there has been an effort to develop near term implementations of algorithms purely for research and education. In this paper, we discuss a near term implementation of Shor's Algorithm using the Qiskit language on an IBM Q System One quantum computer. We extend currently available documentation by providing a full circuit diagram for Shor's Algorithm including gates specific to the implementation using Qiskit. We present an implementation capable of factoring small two-digit prime numbers, and discuss the limitations of noise when using real quantum computers vs. simulations.

IEEE Annual Computing and Communication Workshop and Conference (CCWC)•Jan 27, 2021•9 citations

Circuit implementation of Shor's algorithm for the factorization of small integers in Qiskit

Iheb Eddine Gharbi, Amor Gueddana, Hichem Eleuch +1 more

To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.

Quantum Communications and Quantum Imaging•Aug 13, 2024•3 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.

arXiv:quant-ph/0205095•Quantum Information and Computation•Mar 1, 2003•299 citations

Enhanced Security Algorithm for Integer Factorization in Quantum Computing: Optimizing Shor’s Algorithm

Rashmi Kuksal, Sumit Chaudhary, Ashish Bhatt

With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.

International Conference on Innovative Mechanisms for Industry Applications•Oct 1, 2026•0 citations

On quantum computing with macroscopic Josephson qubits

Jie Han, Pieter P. Jonker

The achievements of quantum computation theory, e.g. Shor's factoring algorithm, motivate efforts to realize quantum computers. Among systems proposed for quantum computing, macroscopic superconducting circuits of Josephson junctions appear promising for integration in electronic circuits and large-scale applications. Recently, a superconducting tunnel junction circuit was designed and a sufficiently high quality factor of quantum coherence has been obtained. This indicates that decoherence need not be among the obstacles in building quantum computers with macroscopic Josephson circuits. In this paper we present the setup of some elementary quantum logic with macroscopic Josephson qubits, strengthened by some simulation work, and then study the feasibility of implementing Shor's quantum factoring algorithm on them. It is shown that it would be eventually possible to build a 2-dimensional Josephson qubit array, possibly accompanied by classical computing components, capable of performing useful quantum computations.

IEEE Conference on Nanotechnology (IEEE NANO)•Jun 25, 2003•5 citations
We investigate the physical implementation of Shor's factorization algorithm on a Josephson charge qubit register. While we pursue a universal method to factor a composite integer of any size, the scheme is demonstrated for the number 21. We consider both the physical and algorithmic requirements for an optimal implementation when only a small number of qubits are available. These aspects of quantum computation are usually the topics of separate research communities; we present a unifying discussion of both of these fundamental features bridging Shor's algorithm to its physical realization using Josephson junction qubits. In order to meet the stringent requirements set by a short decoherence time, we accelerate the algorithm by decomposing the quantum circuit into tailored two- and three-qubit gates and we find their physical realizations through numerical optimization.
We investigate both the physical and algorithmic requirements for an implementation of Shor's factorization algorithm on a hypothetical Josephson charge qubit register. We represent an implementation which is optimal for small number of available qubits, but still provides a general method to factorize integer without a prior knowledge of the number to be factorized. Furthermore, our strategy is easily generalized to other realizations and parameter values. In order to meet the stringent requirements set by short decoherence time, we accelerate the algorithm by decomposing it into tailored two- and three-qubit gates and find their physical realizations through the numerical optimization.
Although the fundamental principles of quantum computing have been known for decades, it is only within the past few years that practical quantum computers have become available. Since these systems are limited to a small number of qubits, they cannot demonstrate quantum advantage for many practical problems. Accordingly, there has been an effort to develop near term implementations of algorithms purely for research and education. In this paper, we discuss a near term implementation of Shor's Algorithm using the Qiskit language on an IBM Q System One quantum computer. We extend currently available documentation by providing a full circuit diagram for Shor's Algorithm including gates specific to the implementation using Qiskit. We present an implementation capable of factoring small two-digit prime numbers, and discuss the limitations of noise when using real quantum computers vs. simulations.
To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.
With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.
The achievements of quantum computation theory, e.g. Shor's factoring algorithm, motivate efforts to realize quantum computers. Among systems proposed for quantum computing, macroscopic superconducting circuits of Josephson junctions appear promising for integration in electronic circuits and large-scale applications. Recently, a superconducting tunnel junction circuit was designed and a sufficiently high quality factor of quantum coherence has been obtained. This indicates that decoherence need not be among the obstacles in building quantum computers with macroscopic Josephson circuits. In this paper we present the setup of some elementary quantum logic with macroscopic Josephson qubits, strengthened by some simulation work, and then study the feasibility of implementing Shor's quantum factoring algorithm on them. It is shown that it would be eventually possible to build a 2-dimensional Josephson qubit array, possibly accompanied by classical computing components, capable of performing useful quantum computations.