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•23 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

Streamlining Shor's algorithm for potential hardware savings

Yunseong Nam, R. Blümel

We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to $N=557\phantom{\rule{0.16em}{0ex}}993$ with up to $n=39$ qubits, we confirm earlier, smaller-$n$ results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-$n$ implementations of quantum computers.

Physical Review A•Jun 26, 2013•7 citations

Quantum Factoring Algorithm: Resource Estimation and Survey of Experiments

Noboru Kunihiro

Abstract It is known that Shor’s algorithm can break many cryptosystems such as RSA encryption, provided that large-scale quantum computers are realized. Thus far, several experiments for the factorization of the small composites such as 15 and 21 have been conducted using small-scale quantum computers. In this study, we investigate the details of quantum circuits used in several factoring experiments. We then indicate that some of the circuits have been constructed under the condition that the order of an element modulo a target composite is known in advance. Because the order must be unknown in the experiments, they are inappropriate for designing the quantum circuit of Shor’s factoring algorithm. We also indicate that the circuits used in the other experiments are constructed by relying considerably on the target composite number to be factorized.

Mathematics for industry•Oct 22, 2020•2 citations

Investigating the practical implementation of Shor's algorithm

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

The publication in 1994 of Shor's algorithm, which allows factorization of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jan 1, 2005•0 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.
We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to N=557993N=557\phantom{\rule{0.16em}{0ex}}993N=557993 with up to n=39n=39n=39 qubits, we confirm earlier, smaller-nnn results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-nnn implementations of quantum computers.
Abstract It is known that Shor’s algorithm can break many cryptosystems such as RSA encryption, provided that large-scale quantum computers are realized. Thus far, several experiments for the factorization of the small composites such as 15 and 21 have been conducted using small-scale quantum computers. In this study, we investigate the details of quantum circuits used in several factoring experiments. We then indicate that some of the circuits have been constructed under the condition that the order of an element modulo a target composite is known in advance. Because the order must be unknown in the experiments, they are inappropriate for designing the quantum circuit of Shor’s factoring algorithm. We also indicate that the circuits used in the other experiments are constructed by relying considerably on the target composite number to be factorized.
The publication in 1994 of Shor's algorithm, which allows factorization of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.