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 2D Nearest-Neighbor Quantum Architecture for Factoring

Paul Pham, Krysta M. Svore

Published Jul 27, 2012• 6 citations
OpenAlex

Abstract

We present a 2D nearest-neighbor quantum architecture for Shor’s factoring algorithm in polylogarithmic depth. Our implementation uses parallel phase estimation, constant-depth fanout and teleportation, and constant-depth carry-save modular addition. We derive asymptotic bounds on the circuit depth and width of our architecture and provide a comparison to all previous nearest-neighbor factoring implementations.

Related papers

A 2D nearest-neighbor quantum architecture for factoring in polylogarithmic depth

Paul Pham, Krysta M. Svore

We present a 2D nearest-neighbor quantum architecture for Shor's algorithm to factor an $n$-bit number in $O(\log^3n)$ depth. Our implementation uses parallel phase estimation, constant-depth fanout and teleportation, and constant-depth carry-save modular addition. We derive upper bounds on the circuit resources of our architecture under a new 2D model which allows a classical controller and parallel, communicating modules. We provide a comparison to all previous nearest-neighbor factoring implementations. Our circuit results in an exponential improvement in nearest-neighbor circuit depth at the cost of a polynomial increase in circuit size and width.

arXiv:1207.6655•Quantum Information and Computation•Nov 1, 2013•40 citations

Minimum Depth Quantum Modular Addition Through Carry-Save Architecture

Siyi Wang, Eugene Lim, Xiufan Li +2 more

Shor's factorization algorithm, as one of the most significant achievements in quantum computing, exhibits an exponential speedup compared to the corresponding classical algorithm. In Shor's factorization algorithm, modular exponentiation is one of the most computationally intensive components, which relies on the modular addition building block. This work aims to explore novel designs for enhancing the efficiency of quantum modular addition. In particular, we introduce a novel quantum modular addition framework based on carry-save architecture, which facilitates the conversion of multiple 2-addend quantum operations within modular addition into a single 3-addend operation, thereby reducing the computational depth. Compared to the most efficient existing quantum modular addition, our design has achieved an impressive result - a reduction in Toffoli Depth by up to 33.33%, while maintaining comparable Toffoli Count and Qubit Count. This research underscores the potential of carry-save architecture as a promising technique for accelerating quantum modular arithmetic as well as advancing the development of quantum computing in general.

IFIP/IEEE International Conference on Very Large Scale Integration•Oct 6, 2024•5 citations

The quantum Fourier transform on a linear nearest neighbor architecture

Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta

We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are $O(n)$ and $O(n\log n)$, respectively, where $n$ is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.

Quantum Information and Computation•May 1, 2007•37 citations

Optimal Quantum Circuits for Nearest-Neighbor Architectures

David J. Rosenbaum

We show that the depth of quantum circuits in the realistic architecture where a classical controller determines which local interactions to apply on the kD grid Z^k where k >= 2 is the same (up to a constant factor) as in the standard model where arbitrary interactions are allowed. This allows minimum-depth circuits (up to a constant factor) for the nearest-neighbor architecture to be obtained from minimum-depth circuits in the standard abstract model. Our work therefore justifies the standard assumption that interactions can be performed between arbitrary pairs of qubits. In particular, our results imply that Shor's algorithm, controlled operations and fanouts can be implemented in constant depth, polynomial size and polynomial width in this architecture. We also present optimal non-adaptive quantum circuits for controlled operations and fanouts on a kD grid. These circuits have depth Theta(sqrt[k](n)), size Theta(n) and width Theta(n). Our lower bound also applies to a more general class of operations.

arXiv:1205.0036•Leibniz international proceedings in informatics•Apr 30, 2012•17 citations

Fast quantum modular exponentiation architecture for Shor's factoring alogrithm

Archimedes Pavlidis, Dimitris Gizopoulos

We present a novel and efficient, in terms of circuit depth, design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the Quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a quantum modular multiplier which is the fundamental block for the modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about $2000n^2$ and requires $9n+2$ qubits, where $n$ is the number of bits of the classic number to be factored. The total quantum cost of the proposed design is $1600n^3$. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.

Quantum Information and Computation•May 1, 2014•38 citations

Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm

Archimedes Pavlidis, Dimitris Gizopoulos

We present a novel and efficient in terms of circuit depth design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a generic modular quantum multiplier which is the fundamental block for modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about $2000n^{2}$ and requires $9n+2$ qubits, where $n$ is the number of bits of the classical number to be factored. The total quantum cost of the proposed design is $1600n^{3}$. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.

arXiv:1207.0511•Jul 2, 2012•13 citations
We present a 2D nearest-neighbor quantum architecture for Shor’s factoring algorithm in polylogarithmic depth. Our implementation uses parallel phase estimation, constant-depth fanout and teleportation, and constant-depth carry-save modular addition. We derive asymptotic bounds on the circuit depth and width of our architecture and provide a comparison to all previous nearest-neighbor factoring implementations.
We present a 2D nearest-neighbor quantum architecture for Shor's algorithm to factor an nnn-bit number in O(log⁡3n)O(\log^3n)O(log3n) depth. Our implementation uses parallel phase estimation, constant-depth fanout and teleportation, and constant-depth carry-save modular addition. We derive upper bounds on the circuit resources of our architecture under a new 2D model which allows a classical controller and parallel, communicating modules. We provide a comparison to all previous nearest-neighbor factoring implementations. Our circuit results in an exponential improvement in nearest-neighbor circuit depth at the cost of a polynomial increase in circuit size and width.
Shor's factorization algorithm, as one of the most significant achievements in quantum computing, exhibits an exponential speedup compared to the corresponding classical algorithm. In Shor's factorization algorithm, modular exponentiation is one of the most computationally intensive components, which relies on the modular addition building block. This work aims to explore novel designs for enhancing the efficiency of quantum modular addition. In particular, we introduce a novel quantum modular addition framework based on carry-save architecture, which facilitates the conversion of multiple 2-addend quantum operations within modular addition into a single 3-addend operation, thereby reducing the computational depth. Compared to the most efficient existing quantum modular addition, our design has achieved an impressive result - a reduction in Toffoli Depth by up to 33.33%, while maintaining comparable Toffoli Count and Qubit Count. This research underscores the potential of carry-save architecture as a promising technique for accelerating quantum modular arithmetic as well as advancing the development of quantum computing in general.
We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are O(n)O(n)O(n) and O(nlog⁡n)O(n\log n)O(nlogn), respectively, where nnn is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.
We show that the depth of quantum circuits in the realistic architecture where a classical controller determines which local interactions to apply on the kD grid Z^k where k >= 2 is the same (up to a constant factor) as in the standard model where arbitrary interactions are allowed. This allows minimum-depth circuits (up to a constant factor) for the nearest-neighbor architecture to be obtained from minimum-depth circuits in the standard abstract model. Our work therefore justifies the standard assumption that interactions can be performed between arbitrary pairs of qubits. In particular, our results imply that Shor's algorithm, controlled operations and fanouts can be implemented in constant depth, polynomial size and polynomial width in this architecture. We also present optimal non-adaptive quantum circuits for controlled operations and fanouts on a kD grid. These circuits have depth Theta(sqrt[k](n)), size Theta(n) and width Theta(n). Our lower bound also applies to a more general class of operations.
We present a novel and efficient, in terms of circuit depth, design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the Quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a quantum modular multiplier which is the fundamental block for the modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about 2000n22000n^22000n2 and requires 9n+29n+29n+2 qubits, where nnn is the number of bits of the classic number to be factored. The total quantum cost of the proposed design is 1600n31600n^31600n3. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.
We present a novel and efficient in terms of circuit depth design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a generic modular quantum multiplier which is the fundamental block for modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about 2000n22000n^{2}2000n2 and requires 9n+29n+29n+2 qubits, where nnn is the number of bits of the classical number to be factored. The total quantum cost of the proposed design is 1600n31600n^{3}1600n3. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.