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:1207.6655 · Quantum Information and Computation

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

Paul Pham, Krysta M. Svore

Published Nov 1, 2013• 40 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic13.11-12-3

Related papers

A 2D Nearest-Neighbor Quantum Architecture for Factoring

Paul Pham, Krysta M. Svore

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.

Quantum Information and Computation•Jul 27, 2012•6 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

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

Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation

Zheyu Shen, Yusen Wu, Penghui Yao +2 more

Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy $ε$, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an $n$-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time $T\ge1$, with circuit depth $O(T\log(nT/ε))$ and gate count $O(nT\log(nT/ε))$. This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time $T$ in the stated regime and sufficiently small fixed error $ε$, any nearest-neighbor quantum circuit simulating these dynamics requires depth $Ω(\log n/\log\log n)$. This matches our $O(\log n)$ upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.

quant-pharXiv:2610.01839•Oct 2, 2026•0 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
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.
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 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 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.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy εεε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an nnn-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1T\ge1T≥1, with circuit depth O(Tlog⁡(nT/ε))O(T\log(nT/ε))O(Tlog(nT/ε)) and gate count O(nTlog⁡(nT/ε))O(nT\log(nT/ε))O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time TTT in the stated regime and sufficiently small fixed error εεε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn). This matches our O(log⁡n)O(\log n)O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
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.