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/0205095

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

Published May 15, 2002• 18 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.quant-ph/0205095

Related papers

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

BeauregardStephane

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 0(n3lg(n)) elementary...

Quantum Information and Computation•Mar 1, 2003•10 citations

Factoring using 2n+2 qubits with Toffoli based modular multiplication

Thomas Häner, Martin Roetteler, Krysta M. Svore

We describe an implementation of Shor’s quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n 3 ) and O(n 3 log n), respectively. We thus achieve the same space and time costs as Takahashi et al. [1], while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of some faults in both, the logical level circuit and an actual quantum hardware implementation. Our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log n) and O(n), respectively.

arXiv:1611.07995•Quantum Information and Computation•May 1, 2017•90 citations

Shor's algorithm with fewer (pure) qubits

Christof Zalka

In this note we consider optimised circuits for implementing Shor's quantum factoring algorithm. First I give a circuit for which none of the about 2n qubits need to be initialised (though we still have to make the usual 2n measurements later on). Then I show how the modular additions in the algorithm can be carried out with a superposition of an arithmetic sequence. This makes parallelisation of Shor's algorithm easier. Finally I show how one can factor with only about 1.5n qubits, and maybe even fewer.

arXiv:quant-ph/0601097•Jan 15, 2006•20 citations

A quantum circuit for Shor's factoring algorithm using 2n+2 qubits

Yu Takahashi, Noboru Kunihiro

We construct a quantum circuit for Shor's factoring algorithm that uses 2n+2 qubits, where n is the length of the number to be factored. The depth and size of the circuit are O(n^3) and O(n^3\log n), respectively. The number of qubits used in the circuit is less than that in any other quantum circuit ever constructed for Shor's factoring algorithm. Moreover, the size of the circuit is about half the size of Beauregard's quantum circuit for Shor's factoring algorithm, which uses 2n+3 qubits.

Quantum Information and Computation•Mar 1, 2006•46 citations

A quantum circuit for shor's factoring algorithm using 2n + 2 qubits

TakahashiYasuhiro, KunihiroNoboru

We construct a quantum circuit for Shor's factoring algorithm that uses 2n + 2 qubits,where n is the length of the number to be factored. The depth and size of the circuitare O(n3) and O(n3 log n),...

Quantum Information and Computation•Mar 1, 2006•1 citation
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
We describe an implementation of Shor’s quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n 3 ) and O(n 3 log n), respectively. We thus achieve the same space and time costs as Takahashi et al. [1], while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of some faults in both, the logical level circuit and an actual quantum hardware implementation. Our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log n) and O(n), respectively.
In this note we consider optimised circuits for implementing Shor's quantum factoring algorithm. First I give a circuit for which none of the about 2n qubits need to be initialised (though we still have to make the usual 2n measurements later on). Then I show how the modular additions in the algorithm can be carried out with a superposition of an arithmetic sequence. This makes parallelisation of Shor's algorithm easier. Finally I show how one can factor with only about 1.5n qubits, and maybe even fewer.
We construct a quantum circuit for Shor's factoring algorithm that uses 2n+2 qubits, where n is the length of the number to be factored. The depth and size of the circuit are O(n^3) and O(n^3\log n), respectively. The number of qubits used in the circuit is less than that in any other quantum circuit ever constructed for Shor's factoring algorithm. Moreover, the size of the circuit is about half the size of Beauregard's quantum circuit for Shor's factoring algorithm, which uses 2n+3 qubits.