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 Information and Computation

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

Yu Takahashi, Noboru Kunihiro

Published Mar 1, 2006• 46 citations
Publisher

Abstract

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.

DOI
10.26421/qic6.2-4

Related papers

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

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

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

A fast quantum circuit for addition with few qubits

Yasuhiro Takahashi, Noboru Kunihiro

We show how to construct a fast quantum circuit for computing the sum of two $n$-bit binary numbers with few qubits. The constructed circuit uses $O(n/\log n)$ ancillary qubits and its depth and size are $O(\log n)$ and $O(n)$, respectively. The number of ancillary qubits is asymptotically less than that in Draper et al.'s quantum carry-lookahead adder, and the depth and size are asymptotically the same as those of Draper et al.'s. Moreover, we show that the circuit is useful for constructing an efficient quantum circuit for Shor's factoring algorithm.

Quantum Information and Computation•Jul 1, 2008•42 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
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.
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 show how to construct a fast quantum circuit for computing the sum of two nnn-bit binary numbers with few qubits. The constructed circuit uses O(n/log⁡n)O(n/\log n)O(n/logn) ancillary qubits and its depth and size are O(log⁡n)O(\log n)O(logn) and O(n)O(n)O(n), respectively. The number of ancillary qubits is asymptotically less than that in Draper et al.'s quantum carry-lookahead adder, and the depth and size are asymptotically the same as those of Draper et al.'s. Moreover, we show that the circuit is useful for constructing an efficient quantum circuit for Shor's factoring algorithm.
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.