Factoring using $2n+2$ qubits with Toffoli based modular multiplication
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · cited 2× · see citing works
“…using 2n + 2 qubits with Toffoli based modular multiplication Thomas Häner∗ Station Q Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA and Institute for Theoretical Physics, ETH Zurich, 8093 Zurich, Switzerland Martin Roetteler† and Krysta M.…”
MethodElementary 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 · cited 4× · see citing works
“for the multiply-controlled-NOT using just one borrowed dirty ancilla qubit [8].”
BackgroundMethodInfluentialSemiclassical Fourier Transform for Quantum Computation
Griffiths, R. B., & Niu, C.-S. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.3228 · Cited by 431 · 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 · cited 1× · see citing works
“At the core of Shor’s algorithm lies a modular exponentiation of a constant a by a superposition of values x stored in a register of 2n quantum bits (qubits), where n = dlog2Ne.”
BackgroundFast 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 · cited 1× · see citing works
“This is the same size as the Fourier addition circuit [4], unless one uses an approximate version of the quantum Fourier transform bringing the size down to O ( n log ) [9]. at a We improve our construction to arrive size in O ( n log n ) in the next subsection.”
MethodCircuit 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
LIQUi|>: A Software Design Architecture and Domain-Specific Language for Quantum ComputingPreprint
Wecker, D., & Svore, K. M. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.4467 · Cited by 201 · see citing works
Self-citationAddition on a Quantum ComputerPreprint
Draper, T. G. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0008033 · Cited by 196 · cited 5× · see citing works
“[1] features the lowest known number of qubits and uses Draper’s addition in Fourier space [4], allowing factoring to be achieved using only 2n + 2 qubits at the cost of a circuit size in Θ(n(3) log n) or even Θ(n(4)) when using exact quantum Fourier transforms (QFT).”
BackgroundMethodInfluentialFast 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
Optimal ancilla-free Clifford+T approximation of z-rotations
Ross, N. J., & Selinger, P. (2016) · Quantum Information and Computation · doi:10.26421/qic16.11-12-1 · Cited by 178 · see citing works
Approximate quantum Fourier transform and decoherence
Barenco, A., EKERT, A. K., Suominen, K., & Törmä, P. (1996) · Physical Review A · doi:10.1103/physreva.54.139 · Cited by 175 · cited 1× · see citing works
“Since the approximation cutoff is introduced at m ∈ Θ(log n ), the smallest Fourier angles are θ m ∈ Θ( 12 m ) [15].”
qHiPSTER: The Quantum High Performance Software Testing EnvironmentPreprint
Smelyanskiy, M., Sawaya, N. P. D., & Aspuru‐Guzik, A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1601.07195 · Cited by 173 · cited 1× · see citing works
“…functional simulation may be possible for arbitrary circuits up to almost 50 qubits with high-performance simulators run on super-computers [17, 18], simulating a moderately-sized future quantum computer with just 100 qubits is not feasible on a (future) classical computer due to the…”
BackgroundQuantum addition circuits and unbounded fan-out
Takahashi, Y., Tani, S., & Kunihiro, N. (2010) · Quantum Information and Computation · doi:10.26421/qic10.9-10-12 · Cited by 136 · cited 2× · see citing works
“[5], on Cuccaro [5] Takahashi [6] Draper [4] Our adder Table I. Costs associated with various implementations of addition | a (cid:105) (cid:55)→ | a + c of a value a by a classical constant c . the other hand, yield circuits with as few as 3 n + O (1) qubits and O ( n 3 ) size. circuits Such…”
BackgroundEfficient Clifford+T approximation of single-qubit operators
Selinger, P. (2015) · Quantum Information and Computation · doi:10.26421/qic15.1-2-10 · Cited by 131 · see citing works
Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits
Kliuchnikov, V., Maslov, D., & Mosca, M. (2015) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2409842 · Cited by 95 · see citing works
Electronic Design Automation for Integrated Circuits Handbook
Scheffer, L., Lavagno, L., & Martin, G. E. (2006) · PORTO@Iris · Cited by 75 · see citing works
High Performance Emulation of Quantum Circuits
Häner, T., Steiger, D. S., Smelyanskiy, M., & Troyer, M. (2016) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2016.73 · Cited by 65 · see citing works
Efficient synthesis of probabilistic quantum circuits with fallback
Bocharov, A., Roetteler, M., & Svore, K. M. (2015) · Physical Review A · doi:10.1103/physreva.91.052317 · Cited by 59 · see citing works
Self-citationA quantum circuit for Shor's factoring algorithm using 2n+2 qubits
Takahashi, Y., & Kunihiro, N. (2006) · Quantum Information and Computation · doi:10.26421/qic6.2-4 · Cited by 47 · see citing works
Shor's algorithm on a nearest-neighbor machine
Kutin, S. A. (2006) · arXiv · doi:10.48550/arxiv.quant-ph/0609001 · Cited by 47 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of universal Repeat- Until-Success circuits. Physical Review Letters, 114:080502, 2015.
- N. Cody Jones. Novel constructions for the fault-tolerant Toffoli gate. Physical Review A, 87:022328, 2013.
Cited by
Sorted by citations
Quantum computational supremacy
Harrow, A. W., & Montanaro, A. (2017) · Nature · doi:10.1038/nature23458 · Cited by 823 · 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
“2016 [16] 2n+ 2 52n(3) +O(n(2)) 64n(3) lgn+O(n(3)) 580 5200 19000 230 2800 13000 (ours) 2019 3n + 0.”
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
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145 · 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
“[23], Takahashi [44] 2n+ 6 (qubits) 160n(3) a ∼ n× (6 log2(n))”
BackgroundMethodInfluentialSelf-citationHigh-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
Kim, Y., Morvan, A., Nguyen, L. B., Naik, R., Jünger, C., Chen, L., Kreikebaum, J. M., Santiago, D., & Siddiqi, I. A. (2022) · Nature Physics · doi:10.1038/s41567-022-01590-3 · Cited by 97 · see citing works
A survey on implementations of homomorphic encryption schemes
Doan, T. V. T., Messai, M., Gavin, G., & Darmont, J. (2023) · The Journal of Supercomputing · doi:10.1007/s11227-023-05233-z · Cited by 101 · see citing works
“[78] 2016 O(n(3) log n) 2n+2 Gidney [79] 2017 O(n(3) log n) 2n+1”
Hamiltonian simulation algorithms for near-term quantum hardware
Clinton, L., Bausch, J., & Cubitt, T. S. (2021) · Nature Communications · doi:10.1038/s41467-021-25196-0 · Cited by 80 · see citing works
Kim, P., Han, D., & Jeong, K. C. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-2107-3 · Cited by 80 · see citing works
“There is one more type of qubit not falling into above categories; a borrowed qubit [29].”
BackgroundTrading T gates for dirty qubits in state preparation and unitary synthesis
Low, G. H., Kliuchnikov, V., & Schaeffer, L. (2024) · Quantum · doi:10.22331/q-2024-06-17-1375 · Cited by 89 · see citing works
Time-sliced quantum circuit partitioning for modular architectures
Baker, J. M., Duckering, C., Hoover, A., & Chong, F. T. (2020) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3387902.3392617 · Cited by 73 · see citing works
“The Generalized Toffoli gate (CnU ) is an n-controlled U gate for any single qubit unitary U and is well studied [8, 21, 25, 28, 50, 72].”
BackgroundMartin, M. J., Hughes, C., Moreno, G., Jones, E. B., Sickinger, D., Narumanchi, S. V. J., & Grout, R. (2022) · IEEE Transactions on Sustainable Computing · doi:10.1109/tsusc.2022.3190242 · Cited by 56 · see citing works
“For any given value of f, b, or np, the shares of the power used (1) between the electronics Fe, (2) to cool the low-temperate electronics inside the cryostat Flte, (3) to maintain the cryostat at temperature because of external heat transfer Fo, and (4) for external cooling Fext can be determined.”
BackgroundMethodOptimizing Resource Efficiencies for Scalable Full-Stack Quantum Computers
Fellous-Asiani, M., Chai, J. H., Thonnart, Y., Ng, H. K., Whitney, R. S., & Auffèves, A. (2023) · PRX Quantum · doi:10.1103/prxquantum.4.040319 · Cited by 63 · see citing works
“For example, another recent implementation of the protocol to crack RSA-n encryption [121] less logical qubits, at the cost of a larger logical depth.”
BackgroundPrimitive quantum gates for dihedral gauge theories
Alam, M. S., Hadfield, S., Lamm, H., & Li, A. C. Y. (2022) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.105.114501 · Cited by 49 · see citing works
ReQWIRE: Reasoning about Reversible Quantum Circuits
Rand, R. W., Paykin, J., Lee, D.-H., & Zdancewic, S. (2019) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.287.17 · Cited by 45 · see citing works
Programming quantum computers using design automation
Soeken, M., Häner, T., & Roetteler, M. (2018) · Design, Automation, and Test in Europe · doi:10.23919/date.2018.8341993 · Cited by 44 · see citing works
“Recently, precise cost estimates to implement Shor’s algorithm for factoring [3] and elliptic curve dlog [4] were obtained, based on implementing and testing large-scale Toffoli networks.”
MethodSelf-citationQuantum Circuits for Floating-Point Arithmetic
Häner, T., Soeken, M., Roetteler, M., & Svore, K. M. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-99498-7_11 · Cited by 44 · see citing works
Self-citationZulehner, A., & Wille, R. (2019) · Design, Automation, and Test in Europe · doi:10.23919/date.2019.8714836 · Cited by 41 · see citing works
“For example, the realization proposed in [26] requires n + 1 such working qubits—resulting in a total number of 2n + 2 qubits for factoring an n-bit number.”
BackgroundConstrained optimization via quantum Zeno dynamics
Herman, D., Shaydulin, R., Sun, Y., Chakrabarti, S., Hu, S., Minssen, P., Rattew, A. G., Yalovetzky, R., & Pistoia, M. (2023) · Communications Physics · doi:10.1038/s42005-023-01331-9 · Cited by 43 · see citing works
Estimating Quantum Speedups for Lattice Sieves
Albrecht, M. R., Gheorghiu, V., Postlethwaite, E. W., & Schanck, J. M. (2020) · International Conference on the Theory and Application of Cryptology and Information Security · doi:10.1007/978-3-030-64834-3_20 · Cited by 58 · see citing works
“We use the H¨aner–Roetteler–Svore [26] carry bit circuit for implementing the comparison.”
InfluentialQuantum algorithms for typical hard problems: a perspective of cryptanalysis
Suo, J., Wang, L., Yang, S., Zheng, W., & Zhang, J. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02673-x · Cited by 40 · see citing works
“[28] 2016 (n3 log n) 2n + 2 Gidney [23] 2017 (n3 log n) 2n + 1”
Gouzien, É., Ruiz, D., Régent, F.-M. L., Guillaud, J., & Sangouard, N. (2023) · Physical Review Letters · doi:10.1103/physrevlett.131.040602 · Cited by 37 · see citing works
Efficient verification of boson sampling
Chabaud, U., Grosshans, F., Kashefi, E., & Markham, D. (2021) · Quantum · doi:10.22331/q-2021-11-15-578 · Cited by 37 · see citing works
“com compelling evidence of quantum speedup, the experimental requirements associated with such a demonstration preclude its realisation in the near future [9].”
BackgroundLarge-Scale Simulation of Shor’s Quantum Factoring Algorithm
Willsch, D., Willsch, M., Jin, F., Raedt, H. A. D., & Michielsen, K. F. L. (2023) · Mathematics · doi:10.3390/math11194222 · Cited by 34 · see citing works
“5 [12] 6 [15] 7 [18] 8 [21] 9 [24] 10 [27] 11 [30] 12 [33] 13 [36] 14 [39] 15 [42] 16 [45] 17 [48] 18 [51] 19 [54] 20 [57] 21 [60] 22 [63] 23 [66] 24 [69] 25 [72] 26 [75] 27 [78] 28 [81] 29 [84] Number of qubits n required for iterative Shor [conventional Shor] 0 % 25 % 50 % 75 % 100 %”
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
Self-citationAn improved QFT-based quantum comparator and extended modular arithmetic using one ancilla qubit
Yuan, Y., Wang, C., Wang, B., Chen, Z., Dou, M., Wu, Y.-C., & Guo, G. (2023) · New Journal of Physics · doi:10.1088/1367-2630/acfd52 · Cited by 26 · see citing works
“So most approaches[3, 4, 16, 17, 23] still require n ancilla qubits with Toffoli gates.”
MethodInfluentialQuantum Accelerated Computer Architectures
Riesebos, L., Fu, X., Mouedenne, A. A., Lao, L., Varsamopoulos, S., Ashraf, I., van Someren, J., Khammassi, N., Almudéver, C. G., & Bertels, K. (2019) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2019.8702488 · Cited by 24 · see citing works
Enhanced Machine Learning using Quantum Computing
Jhanwar, A., & Nene, M. J. (2021) · International Conference on Electronics and Sustainable Communication Systems (ICESC) · doi:10.1109/icesc51422.2021.9532638 · Cited by 24 · see citing works
“This proved a major breakthrough in breaking public-key crypto systems based on integer factorization method [16], [17].”
Forecasting timelines of quantum computingPreprint
Sevilla, J., & Riedel, C. J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.05045 · Cited by 21 · see citing works
“Next we observe that the number of logical qubits needed to run Shor’s algorithm to break RSA 2048 has been estimated at ∼ 4098 logical qubits (Gidney and Eker, 2019; Hner et al., 2016; Roetteler et al., 2017).”
BackgroundEfficient and fail-safe quantum algorithm for the transport equation
Schalkers, M. A., & Möller, M. (2024) · Journal of Computational Physics · doi:10.1016/j.jcp.2024.112816 · Cited by 22 · see citing works
“…the qubits encoding | i ⟩ have not changed. addition Multiple realizations of quantum and subtraction operations are described in the literature [HRS17; TTK09; CDK98; Dra98] and can be used for the comparison operation, all having their own complexities and required ancillae associated to them.”
Leveraging State Sparsity for More Efficient Quantum Simulations
Jaques, S., & Häner, T. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3491248 · Cited by 19 · see citing works
Improved Quantum Circuits via Intermediate Qutrits
Baker, J. M., Duckering, C., Gokhale, P., Brown, N. C., Brown, K. R., & Chong, F. T. (2020) · ACM Transactions on Quantum Computing · doi:10.1145/3406309 · Cited by 17 · see citing works
Knapsack Problem variants of QAOA for battery revenue optimisationPreprint
de la Grand'rive, P. D., & Hullo, J.-F. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.02210 · Cited by 15 · see citing works
“Addition subroutine Different papers have been published to describe the computation of an addition on a quantum computer [14] [9].”
MethodHigh-fidelity transmon-coupler-activated CCZ gate on fluxonium qubits
Simakov, I. A., Mazhorin, G. S., Moskalenko, I. N., Seidov, S. S., & Besedin, I. S. (2024) · Physical Review Applied · doi:10.1103/physrevapplied.21.044035 · Cited by 14 · see citing works
Quantum Computing for Military Applications
Neumann, N. M. P., van Heesch, M. P. P., Phillipson, F., & Smallegange, A. A. P. (2021) · International Conference on Military Communications and Information Systems (ICMCIS) · doi:10.1109/icmcis52405.2021.9486419 · Cited by 13 · see citing works
Hangleiter, D., Carolan, J., & Thébault, K. P. Y. (2022) · Springer eBooks · doi:10.1007/978-3-030-87216-8 · Cited by 14 · see citing works
Space-Efficient and Noise-Robust Quantum Factoring
Ragavan, S., & Vaikuntanathan, V. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68391-6_4 · Cited by 11 · see citing works
Parallel quantum addition for Korean block ciphers
Jang, K., Song, G., Kim, H., Kwon, H., Kim, H., & Seo, H. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03714-3 · Cited by 14 · see citing works
“In the key schedule of LEA-128, K [0] , K [1] , K [2], and K [3] are independent of each other.”
BackgroundMethodInfluentialOptimized Implementation of Quantum Binary Field Multiplication with Toffoli Depth One
Jang, K., Kim, W., Lim, S., Kang, Y., Yang, Y., & Seo, H. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-25659-2_18 · Cited by 11 · see citing works
Reducing the Number of Qubits in Quantum Factoring
Chevignard, C., Fouque, P.-A., & Schrottenloher, A. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01878-6_13 · Cited by 11 · see citing works
“Many authors have designed circuits optimizing either its qubit or gate count [3,35,33,21,15].”
BackgroundThamaraimanalan, T., Singh, B., Mohankumar, M., & Korada, S. K. (2024) · International Conference on Advanced Computing and Communication Systems (ICACCS) · doi:10.1109/icaccs60874.2024.10717174 · Cited by 9 · see citing works
“The algorithm operates by utilizing the QFT, a pivotal component in its efficiency [7], [10], [12].”
MethodA Survey on Implementations of Homomorphic Encryption SchemesPreprint
Doan, T. V. T., Messai, M., Gavin, G., & Darmon, J. (2022) · Research Square · doi:10.21203/rs.3.rs-2018739/v1 · Cited by 10 · see citing works
T-depth Reduction Method for Efficient SHA-256 Quantum Circuit Construction
Lee, J., Lee, S., Lee, Y.-S., & Choi, D. (2022) · International Conference on Information Security and Cryptology · doi:10.1049/ise2.12074 · Cited by 11 · see citing works
“This is because the circuits presented in [9, 10] are circuits in which Toffoli-count can be reduced.”
BackgroundMethodInfluentialImproved Quantum Analysis of SPECK and LowMC (Full Version)
Jang, K., Baksi, A., Kim, H., Seo, H., & Chattopadhyay, A. (2022) · IACR Cryptology ePrint Archive · doi:10.1007/978-3-031-22912-1_23 · Cited by 16 · see citing works
“As a matter of fact, it is well-known that certain public-key systems would face major problem [37,10,33,19,20,16] against an adversary equipped with a quantum computer.”
BackgroundA Survey on Implementations of Homomorphic Encryption SchemesPreprint
Doan, T. V. T., Messai, M., Gavin, G., & Darmont, J. (2022) · Research Square · doi:10.21203/rs.3.rs-2018739/v2 · Cited by 9 · see citing works
Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion
Jang, K., Kim, W., Lim, S.-J., Kang, Y., Yang, Y., & Seo, H. (2023) · Italian National Conference on Sensors · doi:10.3390/s23063156 · Cited by 7 · see citing works
Quantum mean estimation for lattice field theory
Gustafson, E., Lamm, H., & Unmuth-Yockey, J. (2023) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.107.114511 · Cited by 7 · see citing works
Quantum Period Finding is Compression Robust
May, A., & Schlieper, L. (2022) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.v2022.i1.183-211 · Cited by 7 · see citing works
Efficient and Fail-Safe Collisionless Quantum Boltzmann MethodPreprint
Schalkers, M. A., & Möller, M. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4353577 · Cited by 7 · see citing works
Ancilla-Free Quantum Adder with Sublinear Depth
Remaud, M., & Vandaele, V. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-97063-4_11 · Cited by 6 · see citing works
“We start from the constant adder with one dirty ancilla proposed by Häner et al. [11]: where | g ⟩ is a dirty ancilla qubit.”
InfluentialDesign automation for quantum architectures
Roetteler, M., Svore, K., Wecker, D., & Wiebe, N. (2017) · Design, Automation and Test in Europe · doi:10.23919/date.2017.7927196 · Cited by 10 · see citing works
Self-citationQuantum‐resistant anonymous identity‐based encryption with trable identities
Liu, Z., Tseng, Y., Tso, R., Mambo, M., & Chen, Y. (2021) · IET Information Security · doi:10.1049/ise2.12049 · Cited by 6 · see citing works
Feasibility Analysis of Cracking RSA with Improved Quantum Circuits of the Shor’s Algorithm
Liu, X., Yang, H., & Yang, L. (2021) · Security and Communication Networks · doi:10.1155/2023/2963110 · Cited by 8 · see citing works
“…the number of qubits to 2 n + 2 with comparator in modular addtion operation, which is the lowest known number of qubits so far; H¨aner et al.[12] constructed a quantum circuit of Shor’s algorithm with 2 n + 2 qubits as well based on a purely Toffoli-based adder which eliminats most of the…”
MethodAdvantages 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
“More recent work also eliminates the substantial overhead from the quantum Fourier transform required for this type of adder by constructing a purely Toffoli-based network of depth O ( n ) [32].”
BackgroundHow to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7 · see citing works
“5 n logical qubits [Zal06; Bea03; HRS16; Gid17].”
One Additional Qubit is Enough: Encoded Embeddings for Boolean Components in Quantum Circuits
Zulehner, A., Niemann, P., Drechsler, R., & Wille, R. (2019) · IEEE International Symposium on Multiple-Valued Logic · doi:10.1109/ismvl.2019.00009 · Cited by 3 · see citing works
“Since it is very complex to determine a sequence of quantum operations (also denoted quantum gates) that realize the desired functionality (a process termed synthesis [8], [9]), the Boolean function to be realized is usually decomposed into several (not necessarily reversible) sub-functions [10]–[12].”
BackgroundMethodSimulation of Modular Exponentiation Circuit for Shor's Algorithm in Qiskit
Larasati, H. T., & Kim, H. (2020) · International Conference on Telecommunication Systems, Services, and Applications · doi:10.1109/tssa51342.2020.9310794 · Cited by 5 · see citing works
“However, the classically-inspired circuit has advantages over the Fourier-based [2] due to its efficiency in testing and debugging, and no overhead from single-qubit rotation synthesis when error correction is taken into account [11].”
BackgroundConcrete analysis of approximate ideal-SIVP to decision ring-LWE reduction
Koblitz, N., Samajder, S., Sarkar, P., & Singha, S. (2022) · Advances in Mathematics of Communications · doi:10.3934/amc.2022082 · Cited by 5 · see citing works
Quantum Minimum Searching Algorithm and Circuit Implementation
Kang, Y., & Heo, J. (2020) · International Conference on Information and Communication Technology Convergence (ICTC) · doi:10.1109/ictc49870.2020.9289455 · Cited by 5 · see citing works
“The constant adder in [6] computes r = c + b where c is a constant and b is a variable.”
BackgroundMethodSingle-Trace Side-Channel Attacks on NTRU Implementation
Rabas, T., Buček, J., & Lórencz, R. (2024) · SN Computer Science · doi:10.1007/s42979-023-02493-7 · Cited by 4 · see citing works
“To break 2048-bit RSA keys with Shor’s algorithm, one needs 4098 logical qubits [3] constructed from non-ideal physical qubits.”
Performance Evaluation of Shor Algorithm on Simulated Quantum Hardware with Circuit Level Analysis
Thamaraimanalan, T., Haldorai, A., Ramu, A., & Mariyappan, K. (2025) · Journal of Machine and Computing · doi:10.53759/7669/jmc202505152 · Cited by 3 · see citing works
Ghost factors in Gauss-sum factorization with transmon qubits
Zaw, L. H., Tan, Y. P., Nguyen, L. H., Budoyo, R. P., Park, K. H., Koh, Z. Y., Landra, A., Hufnagel, C., Yap, Y. S., Koh, T. S., et al. (2021) · Physical Review A · doi:10.1103/physreva.104.062606 · Cited by 3 · see citing works
$$T{-}depth$$ Reduction Method for Efficient $$SHA{-}256$$ Quantum Circuit Construction
Lee, J., Lee, S., Lee, Y.-S., & Choi, D. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-08896-4_20 · Cited by 3 · see citing works
Distributed Shor’s Algorithm with Sequential Quantum Teleportation
Jiang, J., Wang, T.-Y., Huang, W., & Zhang, J.-Z. (2023) · IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE) · doi:10.1109/ecice59523.2023.10383099 · Cited by 2 · see citing works
Multiplexed Quantum Communication with Surface and Hypergraph Product Codes
Nishio, S., Connolly, N., Piparo, N. L., Munro, W. J., Scruby, T. R., & Nemoto, K. (2025) · Quantum · doi:10.22331/q-2025-01-28-1613 · Cited by 2 · see citing works
“Quantum computers are expected to solve problems that are intractable using classical computation [1, 2], but these powerful quantum algorithms require high qubit counts and deep circuits to solve problems of interesting size [3, 4].”
The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
Kahanamoku–Meyer, G. D., Ragavan, S., Vaikuntanathan, V., & Kirk, K. V. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718273 · Cited by 2 · see citing works
“We use † to denote the fact that [40] is an interactive protocol in which the quantum computer is not required to actually factor the number.”
The Special Case of Cyclotomic Fields in Quantum Algorithms for Unit Groups
Barbulescu, R., & Poulalion, A. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-37679-5_10 · Cited by 1 · see citing works
Schmidt, M., Kole, A., Wichette, L., Drechsler, R., Kirchner, F., & Mounzer, E. (2025) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2025.3610800 · Cited by 2 · see citing works
“Most previous research on implementing Shor’s algorithm has focused on optimizing low-level modular arithmetic circuits, particularly modular addition and multiplication [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15].”
Space-Efficient and Noise-Robust Quantum Factoring
Ragavan, S., & Vaikuntanathan, V. (2026) · Journal of Cryptology · doi:10.1007/s00145-026-09572-x · Cited by 1 · see citing works
“We begin by stating our main theorem for qubit complexity, and compare the result to Regev [Reg23] and optimizations of Shor’s algorithm [Sho97, BCDP96, VBE96, Bea03, HRS17, TK06, Gid17, Gid19a, KMY24].”
InfluentialA novel hybrid quantum-classical proof-of-work protocol for Blockchain mining
Alharbi, N., & Moulahi, T. (2026) · Quantum Information Processing · doi:10.1007/s11128-026-05089-1 · Cited by 1 · see citing works
“The objective of the study [26] is to use a Toffoli-based modular multiplication circuit to construct Shor’s quantum method for factoring n-bit integers using 2n + 2 qubits.”
Borrowing Dirty Qubits in Quantum Programs
Su, B., Zhou, L., Feng, Y., & Ying, M. (2026) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3779212.3790134 · Cited by 1 · see citing works
“For the first requirement, the toggling trick [17] enables information to be propagated independently of a qubit’s Cuccaro et al. [9] Takahashi et al. [36] Draper [11] Häner et al. [17] Remaud and Vandaele [32] Size 𝛩 ( 𝑛 ) 𝛩 ( 𝑛 ) 𝛩 ( 𝑛 2 ) initial state.”
InfluentialAn improved circuit for Shor’s factoring algorithm using $$2n+2$$ qubits
Song, X., & Liangsen, W. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04159-y · Cited by 1 · see citing works
Large-Scale Simulation of Shor's Quantum Factoring AlgorithmPreprint
Willsch, D., Willsch, M., Jin, F., Raedt, H. A. D., & Michielsen, K. F. L. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2308.05047 · Cited by 1 · see citing works
“5 [12] 6 [15] 7 [18] 8 [21] 9 [24] 10 [27] 11 [30] 12 [33] 13 [36] 14 [39] 15 [42] 16 [45] 17 [48] 18 [51] 19 [54] 20 [57] 21 [60] 22 [63] 23 [66] 24 [69] 25 [72] 26 [75] 27 [78] 28 [81] 29 [84] Number of qubits n required for iterative Shor [conventional Shor] 0 % 25 % 50 % 75 % 100 %”
Combining Operations in DD-Based Simulation
Zulehner, A., & Wille, R. (2020) · Springer eBooks · doi:10.1007/978-3-030-41753-6_6
Truncated phase-based quantum arithmetic: Error propagation and resource reduction
White, G. A. L., Hill, C. D., & Hollenberg, L. C. L. (2023) · Physical Review A · doi:10.1103/physreva.108.052608
Introduction: A New Instrument of Science?
Hangleiter, D., Carolan, J., & Thébault, K. P. Y. (2022) · Springer eBooks · doi:10.1007/978-3-030-87216-8_1
Zulehner, A., & Wille, R. (2020) · Springer eBooks · doi:10.1007/978-3-030-41753-6_10
Single-Trace Attack on NTRU Decryption with Machine Learning and Template Profiling
Rabas, T., Buček, J., & Lórencz, R. (2023) · Euromicro Conference on Digital System Design (DSD) · doi:10.1109/dsd60849.2023.00027
“To break RSA keys of size 2048 bits with Shor’s algorithm one needs 4098 logical qubits [1] that are to be constructed from physical qubits.”
MethodHybrid Approach to Public-Key Algorithms in the Near-Quantum Era
Cinal, A., Wechta, G., & Wroński, M. (2024) · International Conference on Conceptual Structures · doi:10.1007/978-3-031-63778-0_27
“Another commonly found measure of complexity is the number of Toffoli gates or the associated Toffoli-depth [19, 27].”
RSA Quantum Cryptanalysis: A Thorough Exploration of n–Bit Attacks and Emerging Factoring Techniques
Wardhani, R. W., Putranto, D. S. C., & Kim, H. (2025) · Lecture notes in computer science · doi:10.1007/978-981-96-5566-3_11
Coherence and decoherence in generalized Shor’s algorithm
叶, L. 琳. Y., Wu, Z., & 周, N. 南. Z. (2026) · Chinese Physics B · doi:10.1088/1674-1056/ae445e
Construction and optimization of quantum modular exponentiation circuits based on the V gate
Zhang, X., Rong, X., & Li, Z. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04968-3
“In 2017, Häner et al. leveraged the concept of “dirty ancilla” qubits—i.e., the reuse of existing qubits—to reduce the total qubit count to 3 n + 1, although the quantum cost increased to Q ( n 3 logn ) [12].”
Engineering Long-Range and Multibody Interactions via Global Kinetic Constraints
Wu, R., Yang, B., Claeys, P. W., & Zhao, H. (2026) · Physical Review Letters · doi:10.1103/4l1s-kkw7
Shor’s Quantum Algorithm for Solving the Binary ECDLP: A Survey
Taguchi, R., & Takayasu, A. (2025) · Mathematics for industry · doi:10.1007/978-981-96-1218-5_7
Quantum Carry-Save Modular Addition with Optimized Depth and Resource Utilization
Wang, S., Lim, E., Li, X., Feng, J., & Chattopadhyay, A. (2026) · IFIP advances in information and communication technology · doi:10.1007/978-3-032-09575-6_2
An Optimization of Shor's Algorithm Based on Quantum Parallelism
Zhu, S., & Yuan, M. (2026) · Lecture notes in electrical engineering · doi:10.1007/978-981-95-3320-6_53
Post-Quantum Cryptography: can Classical Algorithms Resist Quantum Attacks
Phuong, D. D. X., & Son, P. T. (2025) · RIVF International Conference on Computing and Communication Technologies (RIVF) · doi:10.1109/rivf68649.2025.11365084
“As shown in Table I [4], [5], [6], the quantum resource estimates demonstrate that even moderate-scale quantum computers would render classical public-key systems insecure.”
Optical computing implementation of Shor's factorization algorithm
Chen, S., Chen, H., Tang, X., Sun, Y., & Zhang, X. (2026) · Physical Review A · doi:10.1103/4sc8-5gmk
Formal Verification of Quantum Ancilla Safety
Li, J., Mei, J., Fang, W. S., & Guan, J. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-32537-2_16
“Arithmetic and control logic: adders [10], Bridge GHZ [12] (Appendix A.1), and multi-controlled-X (MCX), including a clean safe version generated by Reqomp [21] and a dirty safe MCX implementation [7].”
Taherdoost, H. (2026) · Cryptography · doi:10.3390/cryptography10040053
“It turns a problem that was thought to need O(2 {n/2} ) classical operations into one that can be solved in O(n 3 ) quantum operations (or O(n 2 log n log log n) with optimized arithmetic), which breaks the computational security guarantee completely instead of just halving the exponent [63,64].”
Baradziej, S. (2026) · Frontiers in Computer Science · doi:10.3389/fcomp.2026.1914634
Gidney, C. (2019) · arXiv · doi:10.48550/arxiv.1905.07682 · Cited by 11 · see citing works
“Modular exponentiation is typically implemented using a series of controlled modular multiplications [14, 15, 9, 6].”
Method
- Authors
- Haner, T., Roetteler, M., & Svore, K. M.
- Affiliations
- Microsoft (United States) (US)
- Venue
- Quantum Information and Computation
- Publisher
- Rinton Press
- Published
- 2017-05
- Volume
- 17
- Issue
- 7&8
- Pages
- 673-684
- ISSN
- 1533-7146 (ISSN-L)
- OpenAlex
- W2953275663
- Cited by
- 90
- References
- 20
- Citations by year
- 2026: 11 · 2025: 10 · 2024: 7 · 2023: 18 · 2022: 14 · 2021: 7 · 2020: 9 · 2019: 7 · 2018: 4 · 2017: 3
- FWCI
- 3.75
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Quantum Information and Computation (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Keywords
- Shor's algorithm, integer factorization, Toffoli gate, modular multiplication, quantum circuit design, qubit count reduction, fault location, circuit depth
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
