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• 20 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•6 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•2 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

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

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.
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 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.