Shor's algorithm on a nearest-neighbor machine

Elementary gates for quantum computation

Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311 · see citing works

Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works

A new quantum ripple-carry addition circuit

Cuccaro, S. A., Draper, T. G., Kutin, S. A., & Moulton, D. P. (2004) · arXiv · doi:10.48550/arxiv.quant-ph/0410184 · Cited by 344 · see citing works

Fast parallel circuits for the quantum Fourier transform

Cleve, R., & Watrous, J. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892140 · Cited by 223 · see citing works

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

Beauregard, S. (2003) · Quantum Information and Computation · doi:10.26421/qic3.2-8 · Cited by 206 · see citing works

Addition on a Quantum ComputerPreprint

Draper, T. G. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0008033 · Cited by 196 · see citing works

Parallel Quantum Computation and Quantum Codes

Moore, C., & Nilsson, M. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799355053 · Cited by 183 · see citing works

Fast quantum modular exponentiation

Van Meter, R., & Itoh, K. M. (2005) · Physical Review A · doi:10.1103/physreva.71.052320 · Cited by 181 · see citing works

A logarithmic-depth quantum carry-lookahead adder

Draper, T. G., Kutin, S., Rains, E. M., & Svore, K. M. (2006) · CaltechAUTHORS (California Institute of Technology) · doi:10.5555/2012086.2012090 · Cited by 146 · see citing works

Implementation of Shor's algorithm on a linear nearest neighbour qubit array

Fowler, A. G., Devitt, S. J., & Hollenberg, L. C. L. (2004) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011827.2011828 · Cited by 139 · see citing works

Fast versions of Shor's quantum factoring algorithm

Zalka, C. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9806084 · Cited by 73 · see citing works

A linear-size quantum circuit for addition with no ancillary qubits

Takahashi, Y., & Kunihiro, N. (2005) · Quantum Information and Computation · doi:10.26421/qic5.6-2 · Cited by 66 · see citing works

Architecture of a quantum multicomputer optimized for Shor's factoring algorithmPreprint

Meter, V., Doyle, R., ミーター, バ., & ドイル, ロ. (2006) · arXiv (Cornell University) · Cited by 38 · see citing works

ARCHITECTURE-DEPENDENT EXECUTION TIME OF SHOR'S ALGORITHM

Meter, R. V., Itoh, K. M., & Ladd, T. D. (2008) · doi:10.1142/9789812814623_0029 · Cited by 13 · see citing works

How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830 · see citing works

Toward the first quantum simulation with quantum speedup

Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551 · see citing works

Synthesis and optimization of reversible circuits—a survey

Saeedi, M., & Markov, I. L. (2013) · ACM Computing Surveys · doi:10.1145/2431211.2431220 · Cited by 294 · see citing works

Synthesis of quantum circuits for linear nearest neighbor architectures

Saeedi, M., Wille, R., & Drechsler, R. (2010) · Quantum Information Processing · doi:10.1007/s11128-010-0201-2 · Cited by 213 · see citing works

Compiler Design for Distributed Quantum Computing

Ferrari, D., Cacciapuoti, A. S., Amoretti, M., & Caleffi, M. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3053921 · Cited by 143 · see citing works

Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures

Shafaei, A., Saeedi, M., & Pedram, M. (2013) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/2463209.2488785 · Cited by 123 · see citing works

Factoring with qutrits: Shor's algorithm on ternary and metaplectic quantum architectures

Bocharov, A., Roetteler, M., & Svore, K. M. (2017) · Physical Review A · doi:10.1103/physreva.96.012306 · Cited by 112 · see citing works

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

Haner, T., Roetteler, M., & Svore, K. M. (2017) · Quantum Information and Computation · doi:10.26421/qic17.7-8-7 · Cited by 90 · see citing works

Requirements for fault-tolerant factoring on an atom-optics quantum computer

Devitt, S. J., Stephens, A. M., Munro, W. J., & Nemoto, K. (2013) · Nature Communications · doi:10.1038/ncomms3524 · Cited by 78 · see citing works

On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography

Cheung, D., Maslov, D., Mathew, J., & Pradhan, D. K. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-89304-2_9 · Cited by 68 · see citing works

An Outlook for Quantum Computing [Point of View]

Maslov, D., Nam, Y., & Kim, J. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2884353 · Cited by 63 · see citing works

An efficient conversion of quantum circuits to a linear nearest neighbor architecture

Hirata, Y., Nakanishi, M., Yamashita, S., & Nakashima, Y. (2011) · Quantum Information and Computation · doi:10.26421/qic11.1-2-10 · Cited by 77 · see citing works

Harmony-search algorithm for 2D nearest neighbor quantum circuits realization

Alfailakawi, M. G., Ahmad, I., & Hamdan, S. (2016) · Expert Systems with Applications · doi:10.1016/j.eswa.2016.04.038 · Cited by 55 · see citing works

Realizing reversible circuits using a new class of quantum gates

Sasanian, Z., Wille, R., & Miller, D. M. (2012) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/2228360.2228368 · Cited by 54 · see citing works

Low-cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem

Nam, Y., & Maslov, D. A. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0152-0 · Cited by 41 · see citing works

A fast quantum circuit for addition with few qubits

Takahashi, Y., & Kunihiro, N. (2008) · Quantum Information and Computation · doi:10.26421/qic8.6-7-5 · Cited by 42 · see citing works

Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures

Pedram, M., & Shafaei, A. (2016) · IEEE Circuits and Systems Magazine · doi:10.1109/mcas.2016.2549950 · Cited by 41 · see citing works

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

Pham, P., & Svore, K. (2012) · Quantum information & computation · doi:10.26421/qic13.11-12-3 · Cited by 69 · see citing works

Fast quantum modular exponentiation architecture for Shor's factoring alogrithm

Pavlidis, A., & Gizopoulos, D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.7-8-8 · Cited by 38 · see citing works

Synthesis of Reversible Functions Beyond Gate Count and Quantum CostPreprint

Wille, R., Saeedi, M., & Drechsler, R. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1004.4609 · Cited by 38 · see citing works

A Layered Architecture for Quantum Computing Using Quantum DotsPreprint

Jones, N. C., Meter, R. V., Fowler, A. G., McMahon, P. L., Kim, J., Ladd, T. D., & Yamamoto, Y. (2010) · arXiv (Cornell University) · Cited by 38 · see citing works

Changing the Gate Order for Optimal LNN Conversion

Matsuo, A., & Yamashita, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29517-1_8 · Cited by 36 · see citing works

Line ordering of reversible circuits for linear nearest neighbor realization

Alfailakawi, M. G., Alterkawi, L., Ahmad, I., & Hamdan, S. (2013) · Quantum Information Processing · doi:10.1007/s11128-013-0601-1 · Cited by 34 · see citing works

Quantum Computing: Codebreaking and Beyond

Roetteler, M., & Svore, K. M. (2018) · IEEE Security & Privacy · doi:10.1109/msp.2018.3761710 · Cited by 30 · see citing works

High Performance Quantum Modular MultipliersPreprint

Rines, R., & Chuang, I. L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.01081 · Cited by 34 · see citing works

On the effect of quantum interaction distance on quantum addition circuitsPreprint

Choi, B.-S., & Meter, R. V. (2011) · Cited by 25 · see citing works

Microcoded Architectures for Ion-Tap Quantum Computers

Kreger-Stickles, L., & Oskin, M. (2008) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.2008.28 · Cited by 21 · see citing works

An O(m 2 )-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2 m ) a

Maslov, D., Mathew, J., Cheung, D., & Pradhan, D. K. (2009) · Explore Bristol Research · doi:10.5555/2011814.2011818 · Cited by 19 · see citing works

On the depth overhead incurred when running quantum algorithms on near-term quantum computers with limited qubit connectivity

Herbert, S. (2020) · Quantum Information and Computation · doi:10.26421/qic20.9-10-5 · Cited by 17 · see citing works

Optimal Quantum Circuits for Nearest-Neighbor ArchitecturesPreprint

Rosenbaum, D. J. (2012) · arXiv (Cornell University) · doi:10.4230/lipics.tqc.2013.294 · Cited by 18 · see citing works

Computation at a distancePreprint

Kutin, S., Moulton, D. P., & Smithline, L. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0701194 · Cited by 15 · see citing works

Efficient quantum computing between remote qubits in linear nearest neighbor architectures

Kumar, P. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0485-5 · Cited by 10 · see citing works

Microcoded Architectures for Ion-Tap Quantum Computers

Kreger-Stickles, L., & Oskin, M. (2008) · ACM SIGARCH Computer Architecture News · doi:10.1145/1394608.1382136 · Cited by 10 · see citing works

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2n)

Rötteler, M., & Steinwandt, R. (2014) · Quantum Information and Computation · doi:10.26421/qic14.9-10-11 · Cited by 11 · see citing works

Constant-Factor Optimization of Quantum Adders on 2D Quantum Architectures

Saeedi, M., Shafaei, A., & Pedram, M. (2013) · International Workshop on Reversible Computation · doi:10.1007/978-3-642-38986-3_6 · Cited by 6 · see citing works

An n-bit general implementation of Shor's quantum period-finding algorithm

Davies, J. T. A., Rickerd, C. J., Grimes, M. A., & Güney, D. Ö. (2016) · Quantum Information and Computation · doi:10.26421/qic16.7-8-6 · Cited by 7 · see citing works

Advantages of a modular high-level quantum programming framework

Steiger, D. S., Häner, T., & Troyer, M. (2019) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2019.02.003 · Cited by 6 · see citing works

Effects of Interaction Distance on Quantum Addition CircuitsPreprint

Choi, B.-S., & Meter, R. V. (2008) · arXiv (Cornell University) · Cited by 6 · see citing works

A 2D Nearest-Neighbor Quantum Architecture for FactoringPreprint

Pham, P., & Svore, K. M. (2012) · arXiv (Cornell University) · Cited by 6 · see citing works

How to factor 2048 bit RSA integers with less than a million noisy qubits

Gidney, C. (2025) · arXiv · Cited by 7 · see citing works

Matrix Product Operator Simulations of Quantum Algorithms

Woolfe, K. J. (2015) · Minerva Access (University of Melbourne) · Cited by 6 · see citing works

Threats Related to the Use of Quantum Effects in Cryptography

Cherepnev, M. A., & Gracheva, S. S. (2024) · INFORMACIONNYE TEHNOLOGII · doi:10.17587/it.30.417-424 · Cited by 4 · see citing works

Assertion-based optimization of Quantum programs

Häner, T., Hoefler, T., & Troyer, M. (2020) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000457964 · Cited by 5 · see citing works

Quantum Computation and Isomorphism Testing

Rosenbaum, D. J. (2015) · ResearchWorks at the University of Washington (University of Washington) · Cited by 3 · see citing works

Using non-ideal gates to implement universal quantum computing between uncoupled qubits

Kumar, P., & Skinner, S. R. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0444-1 · Cited by 1 · see citing works

Efficient quantum circuits for arithmetic operations and their applications

高橋, 康. (2008) · Medical Entomology and Zoology · Cited by 1 · see citing works

General logical linear nearest neighbor (LLNN) architecture for fault-tolerant quantum computation

Mudbhari, P. K. (2008) · Holmes Museum Of Anthropology (Wichita State University) · Cited by 1 · see citing works

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)Preprint

Roetteler, M., & Steinwandt, R. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.1161

Implementation of Shor's Algorithm on a Linear Nearest Neighbour Qubit ArrayPreprint

Fowler, A. G., Devitt, S. J., & Hollenberg, L. C. L. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0402196 · Cited by 4 · see citing works

Abstract

Pham, P., & Svore, K. M. (2012)

c ○ Rinton Press A 2D NEAREST-NEIGHBOR QUANTUM ARCHITECTURE FOR FACTORING IN POLYLOGARITHMIC DEPTH

Paul Pham, A., & Svore, K. M. (2012)

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

Pham, P., & Svore, K. (2012) · Quantum information & computation · doi:10.26421/qic13.11-12-3 · Cited by 69 · see citing works

A 2D Nearest-Neighbor Quantum Architecture for FactoringPreprint

Pham, P., & Svore, K. M. (2012) · arXiv (Cornell University) · Cited by 6 · see citing works