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

Quantum circuit design for computer-assisted Shor's algorithm

Chi‐Chuan Hwang, Chu-Yuan Tseng, Cheng-Fang Su

Published Feb 11, 2022• 0 citations
Publisher

Abstract

In this paper, we successfully construct the universal quantum gate for Shor's algorithm and derive the cost of this quantum circuit to estimate the complexity. The circuit we design to implement Shor's algorithm's first complete quantum circuit rather than a simplified circuit. This is important that the quantum circuit design proposed in this paper can decompose larger composite numbers directly if the hardware can be improved in the future. Although the time and space complexity are still greater than traditional computers, it proves that Shor's algorithm can be implemented in quantum computers.

DOI
10.36227/techrxiv.19152632

Related papers

Quantum circuit design for computer-assisted Shor's algorithm

Chi‐Chuan Hwang, Chu-Yuan Tseng, Cheng-Fang Su

In this paper, we successfully construct the universal quantum gate for Shor’s algorithm and derive the cost of this quantum circuit to estimate the complexity. The circuit we design to implement Shor’s algorithm’s first complete quantum circuit rather than a simplified circuit. This is important that the quantum circuit design proposed in this paper can decompose larger composite numbers directly if the hardware can be improved in the future. Although the time and space complexity are still greater than traditional computers, it proves that Shor’s algorithm can be implemented in quantum computers.

•Feb 11, 2022•1 citation

Implementing Shor’s algorithm on Josephson charge qubits

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

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.

arXiv:quant-ph/0308171•Physical Review A•Jul 30, 2004•20 citations

Implementation of Shor's algorithm on a linear nearest neighbour qubit array

Austin G. Fowler, Simon J. Devitt, Lloyd C. L. Hollenberg

Shor's algorithm, which given appropriate hardware can factorise an integer $N$ in a time polynomial in its binary length $L$, has arguable spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just $2L+4$ qubits and to first order requires $8L^{4}$ gates arranged in a circuit of depth $32L^{3}$ -- identical to first order to that possible using an architecture that can interact arbitrary pairs of qubits.

•Jul 1, 2004•139 citations

Implementation of Shor's Algorithm on a Linear Nearest Neighbour Qubit Array

Austin G. Fowler, Simon J. Devitt, Lloyd C. L. Hollenberg

Shor's algorithm, which given appropriate hardware can factorise an integer $N$ in a time polynomial in its binary length $L$, has arguable spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just $2L+4$ qubits and to first order requires $8L^{4}$ gates arranged in a circuit of depth $32L^{3}$ -- identical to first order to that possible using an architecture that can interact arbitrary pairs of qubits.

arXiv:quant-ph/0402196•Feb 25, 2004•4 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

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
In this paper, we successfully construct the universal quantum gate for Shor's algorithm and derive the cost of this quantum circuit to estimate the complexity. The circuit we design to implement Shor's algorithm's first complete quantum circuit rather than a simplified circuit. This is important that the quantum circuit design proposed in this paper can decompose larger composite numbers directly if the hardware can be improved in the future. Although the time and space complexity are still greater than traditional computers, it proves that Shor's algorithm can be implemented in quantum computers.
In this paper, we successfully construct the universal quantum gate for Shor’s algorithm and derive the cost of this quantum circuit to estimate the complexity. The circuit we design to implement Shor’s algorithm’s first complete quantum circuit rather than a simplified circuit. This is important that the quantum circuit design proposed in this paper can decompose larger composite numbers directly if the hardware can be improved in the future. Although the time and space complexity are still greater than traditional computers, it proves that Shor’s algorithm can be implemented in quantum computers.
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.
Shor's algorithm, which given appropriate hardware can factorise an integer NNN in a time polynomial in its binary length LLL, has arguable spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just 2L+42L+42L+4 qubits and to first order requires 8L48L^{4}8L4 gates arranged in a circuit of depth 32L332L^{3}32L3 -- identical to first order to that possible using an architecture that can interact arbitrary pairs of qubits.
Shor's algorithm, which given appropriate hardware can factorise an integer NNN in a time polynomial in its binary length LLL, has arguable spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just 2L+42L+42L+4 qubits and to first order requires 8L48L^{4}8L4 gates arranged in a circuit of depth 32L332L^{3}32L3 -- identical to first order to that possible using an architecture that can interact arbitrary pairs of qubits.
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