Pith. sign in

REVIEW 6 minor 121 references

Quantum Arithmetic Circuits in Public-Key Cryptography

T0 review · 0 major / 6 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Resource-efficient quantum arithmetic circuits give a realistic basis for evaluating quantum attacks on RSA and ECC.

desk verdict Clean, up-to-date survey chapter that organizes known quantum arithmetic circuits and estimation tricks for RSA/ECC cryptanalysis; useful reference, zero new results. read the letter →

arxiv 2607.11713 v1 pith:32LB4RNF submitted 2026-07-13 quant-ph cs.ET

Siyi Wang , Kyungbae Jang , Hyunji Kim , Anik Basu Bhaumik , Anubhab Baksi , Hwajeong Seo , Anupam Chattopadhyay This is my paper
classification quant-phcs.ET
keywords QuantumComputingArithmeticCircuitErrorCorrectionCryptanalysisPublic-keyCryptographyShor'sAlgorithmMeasurement-basedUncomputationWindowed
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Shor’s algorithm threatens RSA and elliptic-curve cryptography, but its cost is dominated by quantum modular arithmetic—addition, multiplication, exponentiation, and point addition. This review shows how those building blocks can be made far cheaper by measurement-based uncomputation, conditionally clean ancillae, and windowed look-up tables that replace long sequences of multiplications with classical pre-computation. The same optimizations are then mapped through surface-code error correction to obtain concrete estimates of logical depth, qubit count, and physical runtime. A sympathetic reader cares because these numbers, not asymptotic big-O statements, decide when today’s public-key systems must be replaced and how large a quantum computer is actually required.

What carries the argument

Measurement-based uncomputation together with conditionally clean ancillae: temporary workspace qubits are cleaned by mid-circuit measurement and classical feedback (or restored under known conditions) instead of full reverse computation, cutting Toffoli count and depth; windowed look-up tables further collapse many controlled multiplications into single table loads.

What would settle it

Take the lowest-cost modular-exponentiation circuit cited for RSA-2048, re-compile it end-to-end with an open lattice-surgery tool that includes magic-state distillation and routing, and check whether the resulting physical-qubit and cycle counts still match the order-of-magnitude claims in the paper.

Watch

Extended reading notes

Core claim

When quantum arithmetic circuits for modular exponentiation and elliptic-curve point addition are redesigned with measurement-based uncomputation, conditionally clean ancillae, and windowed look-up arithmetic, the resulting Toffoli depth, qubit count, and surface-code resource estimates become a practical yardstick for the cryptanalytic power of large-scale quantum computers against RSA and ECC.

Load-bearing premise

The circuit costs quoted for the surveyed designs stay accurate once every circuit is fully compiled under one concrete surface-code lattice-surgery schedule and a realistic magic-state factory layout.

Editorial extensions

If this is right

  • Concrete physical-qubit and runtime numbers for factoring 2048-bit RSA and solving ECDLP become available under surface-code assumptions.
  • Post-quantum security parameters can be set against the best known quantum arithmetic costs rather than asymptotic lower bounds.
  • Any further reduction in magic-state distillation overhead translates directly into lower time-space volume for Shor’s algorithm.
  • Windowed classical–quantum trade-offs will continue to shrink quantum gate count at the price of classical pre-computation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same MBU-plus-windowing toolkit is portable to other arithmetic-heavy quantum algorithms such as quantum chemistry simulation or lattice-based cryptanalysis.
  • A single unified lattice-surgery compiler applied to all surveyed circuits may shrink some of the reported asymptotic gains and reveal which designs remain dominant.
  • Conditionally clean ancillae that enable sub-linear-depth adders could change the asymptotic scaling of modular exponentiation itself.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. This chapter surveys quantum arithmetic circuits for public-key cryptanalysis (RSA and ECC via Shor’s algorithm). It reviews Clifford+T designs for addition, subtraction, multiplication, division, modular exponentiation and elliptic-curve point addition, with emphasis on measurement-based uncomputation, conditionally clean ancillae and windowed LUT techniques. Tables 3–7 organize the literature by architecture and asymptotic cost; Sections 4–5 connect the circuits to concrete RSA/ECC resource estimates and surface-code runtime models (magic-state distillation, lattice surgery). The central claim is that these optimized building blocks plus standard fault-tolerant estimation pipelines supply a realistic basis for evaluating large-scale quantum cryptanalysis.

Significance. As a survey the work is useful: it consolidates a scattered literature on quantum adders, multipliers and modular arithmetic under a common set of metrics (Toffoli depth/count, qubit count) and correctly highlights the practical impact of MBU, conditionally clean ancillae and windowed arithmetic on RSA/ECC cost models. The explicit linkage of circuit-level optimizations to surface-code estimation tools (Qualtran, Azure estimator) and the tabulated asymptotic comparisons (especially Table 5 for Toom–Cook) give practitioners a convenient reference. No new theorems or machine-checked proofs are claimed; the contribution is organizational and pedagogical, which is appropriate for a handbook-style chapter.

minor comments (6)
  1. Figure 3 caption contains an editorial note (“Anubhab: We can redraw these diagrams in tikz”) that should be removed before publication.
  2. Table 1 gate drawings are incomplete or misaligned for several operators (Toffoli, CZ); a clean redraw would improve readability.
  3. Section 1.3, Step 4: the equality after applying Ug is written without intermediate algebra; a short expansion would help readers less familiar with measurement-based uncomputation.
  4. Inconsistent hyphenation and spacing appear throughout (e.g., “Inbrief,” “carry-lookahead” vs “Carry-Lookahead,” “Mu noz-Coreas”). A light copy-edit pass is needed.
  5. Section 5 cites external repositories and tools but does not give version numbers or commit hashes; adding them would improve reproducibility of the estimation pipeline description.
  6. A few self-citations of the authors’ own recent arXiv preprints (e.g., [117], [112]) are listed as 2025; ensure final bibliographic data are updated once DOIs appear.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: pure survey/overview with no derivation chain, fitted predictions, or load-bearing self-citation reductions.

full rationale

The manuscript is an explicit review chapter (Abstract, Sections 1–6) that organizes previously published quantum arithmetic constructions (Tables 3–7), optimization techniques (MBU, conditionally clean ancilla, windowed LUTs), and surface-code estimation pipelines. It asserts no new asymptotic bounds, no parameter fits, and no uniqueness theorems. Self-citations (e.g., Wang et al. adders/multipliers, Jang et al. point addition) simply point to the authors’ earlier independent circuit papers that are externally published and falsifiable; they do not define or force the survey’s organizational claim that such circuits supply a realistic basis for RSA/ECC cryptanalysis. Section 5 sketches standard estimation methodology (code distance, magic-state factories, Qualtran/Azure tools) without re-deriving cited figures under a single closed model that would create circularity. Consequently the derivation chain is empty of circular steps; the paper is self-contained as a literature overview.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

As a literature review the paper inherits the standard axioms of the Clifford+T model, surface-code error correction and the hardness assumptions of RSA/ECC. It introduces no free parameters fitted to data and no new physical entities.

assumptions (3)
  • domain assumption Clifford+T is a universal fault-tolerant gate set and T-gate cost is dominated by magic-state distillation.
    Used throughout Sections 1–5 as the cost model for all circuit comparisons.
  • domain assumption Surface-code distance and distillation rounds can be chosen to meet any target logical error rate below threshold.
    Underpins the runtime-estimation methodology of Section 5.
  • standard math Measurement-based uncomputation and conditionally-clean ancillae correctly restore ancilla states without violating unitarity or the no-cloning theorem.
    Taken as established by the cited works of Gidney, Luongo et al. and used as optimization primitives.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Arithmetic Circuits in Public-Key Cryptography." pith.science (2026). https://pith.science/paper/32LB4RNF

@misc{pith2026260711713,
  author       = {Pith},
  title        = {Pith review of: Quantum Arithmetic Circuits in Public-Key Cryptography},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/32LB4RNF}},
  note         = {Machine review of arXiv:2607.11713}
}
read the original abstract

Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.

Figures

Figures reproduced from arXiv: 2607.11713 by the authors.

Figure 1
Figure 1. Example of Single-qubit Measurement-based Uncomputation 1.4 Conditionally Clean Ancilla In quantum circuit design, ancilla qubits can be used as temporary workspace to reduce the number of gates. Nevertheless, allocating clean ancilla is expen￾sive, since each clean ancilla requires a dedicated qubit. To address this problem, conditionally clean ancilla [75,57,24] has been introduced as a hybrid quantum resource bri… view at source ↗
Figure 2
Figure 2. Quantum C 4X Gate Implementations 2 Computation-based Quantum Arithmetic In fault-tolerant quantum computing, the Clifford+T gate set serves as the stan￾dard universal basis for circuit design. Accordingly, this chapter focuses on the design of Clifford+T-based quantum arithmetic circuits. 2.1 Basic Arithmetic Operations Addition Addition is one of the most fundamental operations in quantum com￾puting. Similar to th… view at source ↗
Figure 3
Figure 3. Structures of n-bit Quantum Subtractor.Anubhab: We can redraw these dia￾grams in tikz 1. Ripple-Borrow Subtraction. Building upon the quantum half-subtractor and full-subtractor, the ripple-borrow approach offers a straightforward method for constructing an n-bit quantum subtractor. This approach has been widely adopted in existing designs [15,101,99]. As illustrated in [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

121 extracted references · 10 canonical work pages

  1. [1]

    Nature 614(7949), 676–681 (2023)

    Suppressing quantum errors by scaling a surface code logical qubit. Nature 614(7949), 676–681 (2023)

    2023

  2. [2]

    Nature638(8052), 920–926 (2025)

    Quantum error correction below the surface code threshold. Nature638(8052), 920–926 (2025)

    2025

  3. [3]

    arXiv preprint arXiv:1209.6348 (2012) 6 https://github.com/seokhyung-lee/msd-magic-state-prep-cycle-simulation Quantum Arithmetic Circuits in Public-Key Cryptography 21

    Amento, B., Steinwandt, R., Roetteler, M.: Efficient quantum circuits for binary elliptic curve arithmetic: reducing t-gate complexity. arXiv preprint arXiv:1209.6348 (2012) 6 https://github.com/seokhyung-lee/msd-magic-state-prep-cycle-simulation Quantum Arithmetic Circuits in Public-Key Cryptography 21

    arXiv 2012

  4. [4]

    In: International Conference on Selected Areas in Cryptography

    Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on sha-2 and sha-3. In: International Conference on Selected Areas in Cryptography. pp. 317–337. Springer (2016)

    2016

  5. [5]

    Microprocessors and Microsystems51, 366–385 (2017)

    AnanthaLakshmi, A., Sudha, G.F.: A novel power efficient 0.64-gflops fused 32-bit reversible floating point arithmetic unit architecture for digital signal processing applications. Microprocessors and Microsystems51, 366–385 (2017)

    2017

  6. [6]

    Cryptology ePrint Archive (2020)

    Banegas, G., Bernstein, D.J., Van Hoof, I., Lange, T.: Concrete quantum crypt- analysis of binary elliptic curves. Cryptology ePrint Archive (2020)

    2020

  7. [7]

    Physical Review A54(2), 1034 (1996)

    Beckman, D., Chari, A.N., Devabhaktuni, S., Preskill, J.: Efficient networks for quantum factoring. Physical Review A54(2), 1034 (1996)

    1996

  8. [8]

    Ibm Journal of Research and Development17, 525–532 (1973),https://api.semanticscholar.org/ CorpusID:14641793

    Bennett, C.H.: Logical reversibility of computation. Ibm Journal of Research and Development17, 525–532 (1973),https://api.semanticscholar.org/ CorpusID:14641793

    1973

Show all 121 references
  1. [9]

    Cryptology ePrint Archive, Paper 2025/1832 (2025), https://eprint.iacr.org/2025/1832

    Bhaumik, A.B., Dutta, S., Wang, S., Baksi, A., Jang, K., Saha, A., Seo, H., Chattopadhyay, A.: Can quantum break ZUC? only with a million qubits and a billion years to spare. Cryptology ePrint Archive, Paper 2025/1832 (2025), https://eprint.iacr.org/2025/1832

    2025

  2. [10]

    Blunt, N.S., Gehér, G.P., Moylett, A.E.: Compilation of a simple chemistry ap- plication to quantum error correction primitives. Phys. Rev. Res.6, 013325 (Mar 2024).https://doi.org/10.1103/PhysRevResearch.6.013325,https:// link.aps.org/doi/10.1103/PhysRevResearch.6.013325

    2024 doi

  3. [11]

    Bombin, H., Martin-Delgado, M.A.: Topological quantum distillation. Phys. Rev. Lett.97, 180501 (Oct 2006).https://doi.org/10.1103/PhysRevLett.97. 180501,https://link.aps.org/doi/10.1103/PhysRevLett.97.180501

    2006 doi

  4. [12]

    Physical Review A86(5) (Nov 2012).https://doi.org/10.1103/physreva.86.052329,http:// dx.doi.org/10.1103/PhysRevA.86.052329

    Bravyi, S., Haah, J.: Magic-state distillation with low overhead. Physical Review A86(5) (Nov 2012).https://doi.org/10.1103/physreva.86.052329,http:// dx.doi.org/10.1103/PhysRevA.86.052329

    2012 doi

  5. [13]

    Physical Review A—Atomic, Molecular, and Optical Physics 71(2), 022316 (2005)

    Bravyi, S., Kitaev, A.: Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A—Atomic, Molecular, and Optical Physics 71(2), 022316 (2005)

    2005

  6. [14]

    Nature 584(7821), 368–372 (2020)

    Campagne-Ibarcq, P., Eickbusch, A., Touzard, S., Zalys-Geller, E., Frattini, N.E., Sivak, V.V., Reinhold, P., Puri, S., Shankar, S., Schoelkopf, R.J., et al.: Quan- tum error correction of a qubit encoded in grid states of an oscillator. Nature 584(7821), 368–372 (2020)

    2020

  7. [15]

    Electronics Let- ters38(22), 1343–1344 (2002)

    Cheng, K.W., Tseng, C.C.: Quantum full adder and subtractor. Electronics Let- ters38(22), 1343–1344 (2002)

    2002

  8. [16]

    Transactions of the American Mathematical Society142, 291–314 (1969)

    Cook, S.A., Aanderaa, S.O.: On the minimum computation time of functions. Transactions of the American Mathematical Society142, 291–314 (1969)

    1969

  9. [17]

    Physical Review A100(3), 032328 (2019)

    Cross, A.W., Bishop, L.S., Sheldon, S., Nation, P.D., Gambetta, J.M.: Validating quantum computers using randomized model circuits. Physical Review A100(3), 032328 (2019)

    2019

  10. [18]

    Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple- carry addition circuit (2004)

    2004

  11. [19]

    In: Proceedings of the SC ’23 Workshops of The International Confer- ence on High Performance Computing, Network, Storage, and Analysis

    van Dam, W., Mykhailova, M., Soeken, M.: Using Azure Quantum Resource Estimator for Assessing Performance of Fault Tolerant Quantum Computa- tion. In: Proceedings of the SC ’23 Workshops of The International Confer- ence on High Performance Computing, Network, Storage, and Ana...

    2023 doi

  12. [20]

    In: 2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID)

    Das, R., Chattopadhyay, A., Rahaman, H.: Optimizing quantum circuits for mod- ular exponentiation. In: 2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID). pp. 407–412. IEEE (2019)

    2019

  13. [21]

    IEEE Transactions on Quantum Engineering 1, 1–13 (2020)

    Di Matteo, O., Gheorghiu, V., Mosca, M.: Fault-tolerant resource estimation of quantum random-access memories. IEEE Transactions on Quantum Engineering 1, 1–13 (2020)

    2020

  14. [22]

    Quantum Information and Computation6(07 2004).https: //doi.org/10.26421/QIC6.4-5-4

    Draper, T., Kutin, S., Rains, E., Svore, K.: A logarithmic-depth quantum carry- lookahead adder. Quantum Information and Computation6(07 2004).https: //doi.org/10.26421/QIC6.4-5-4

    2004 doi

  15. [23]

    Dutta, S., Bhattacharjee, D., Chattopadhyay, A.: Quantum circuits for toom-cook multiplication. Phys. Rev. A98, 012311 (Jul 2018).https:// doi.org/10.1103/PhysRevA.98.012311,https://link.aps.org/doi/10.1103/ PhysRevA.98.012311

    2018 doi

  16. [24]

    Dutta, S., Wang, S., Baksi, A., Chattopadhyay, A., Maitra, S.: Exact space- depth trade-offs in multicontrolled toffoli decomposition. Phys. Rev. A111, 052611 (May 2025).https://doi.org/10.1103/PhysRevA.111.052611,https: //link-aps-org.remotexs.ntu.edu.sg/doi/10.1103/PhysRevA....

    2025 doi

  17. [25]

    Earle, J.G.: Latched carry save adder circuit for multipliers (Sep 5 1967), uS Patent 3,340,388

    1967

  18. [26]

    Nature566(7745), 513–517 (2019)

    Flühmann, C., Nguyen, T.L., Marinelli, M., Negnevitsky, V., Mehta, K., Home, J.: Encoding a qubit in a trapped-ion mechanical oscillator. Nature566(7745), 513–517 (2019)

    2019

  19. [27]

    Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N.: Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A86, 032324 (Sep 2012).https://doi.org/10.1103/PhysRevA.86.032324,https://link. aps.org/doi/10.1103/PhysRevA.86.032324

    2012 doi

  20. [28]

    In: Journal of Physics: Conference Series

    Gayathri, S., Kumar, R., Dhanalakshmi, S.: Efficient floating-point division quan- tum circuit using newton-raphson division. In: Journal of Physics: Conference Series. vol. 2335, p. 012058. IOP Publishing (2022)

    2022

  21. [29]

    Electronics10(6), 703 (2021)

    Gayathri, S., Kumar, R., Dhanalakshmi, S., Dooly, G., Duraibabu, D.B.: T-count optimized quantum circuit designs for single-precision floating-point division. Electronics10(6), 703 (2021)

    2021

  22. [30]

    Gheorghiu, V., Mosca, M.: Quantum resource estimation for large scale quantum algorithms. Future Generation Computer Systems162, 107480 (2025).https://doi.org/https://doi.org/10.1016/j.future.2024.107480, https://www.sciencedirect.com/science/article/pii/S0167739X24004308

    2025 doi

  23. [31]

    Quantum2, 74 (Jun 2018).https://doi.org/10.22331/q-2018-06-18-74,https://doi.org/ 10.22331/q-2018-06-18-74

    Gidney, C.: Halving the cost of quantum addition. Quantum2, 74 (Jun 2018).https://doi.org/10.22331/q-2018-06-18-74,https://doi.org/ 10.22331/q-2018-06-18-74

    2018 doi

  24. [32]

    arXiv preprint arXiv:1905.08488 (2019)

    Gidney, C.: Approximate encoded permutations and piecewise quantum adders. arXiv preprint arXiv:1905.08488 (2019)

    1905 arXiv

  25. [33]

    arXiv preprint arXiv:1904.07356 (2019)

    Gidney, C.: Asymptotically efficient quantum karatsuba multiplication. arXiv preprint arXiv:1904.07356 (2019)

    1904 arXiv

  26. [34]

    arXiv preprint arXiv:1905.07682 (2019)

    Gidney, C.: Windowed quantum arithmetic. arXiv preprint arXiv:1905.07682 (2019)

    1905 arXiv

  27. [35]

    arXiv preprint arXiv:2507.23079 (2025)

    Gidney, C.: A classical-quantum adder with constant workspace and linear gates. arXiv preprint arXiv:2507.23079 (2025)

    2025 arXiv

  28. [36]

    arXiv preprint arXiv:2505.15917 (2025) Quantum Arithmetic Circuits in Public-Key Cryptography 23

    Gidney, C.: How to factor 2048 bit rsa integers with less than a million noisy qubits. arXiv preprint arXiv:2505.15917 (2025) Quantum Arithmetic Circuits in Public-Key Cryptography 23

    arXiv

  29. [37]

    Gidney, C.: Constructing large increment gates.https://algassert.com/ circuits/2015/06/12/Constructing-Large-Increment-Gates.html(June 2015), blog: Algorithmic Assertions

    2015

  30. [38]

    Quantum5, 433 (2021)

    Gidney, C., Ekerå, M.: How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits. Quantum5, 433 (2021)

  31. [39]

    Goldschmidt, R.E.: Applications of division by convergence. Ph.D. thesis, Mas- sachusetts Institute of Technology (1964)

    1964

  32. [40]

    Gossett, P.: Quantum carry-save arithmetic (1998)

    1998

  33. [41]

    Gottesman, D., Kitaev, A., Preskill, J.: Encoding a qubit in an oscillator. Phys. Rev. A64, 012310 (Jun 2001).https://doi.org/10.1103/PhysRevA.64.012310, https://link.aps.org/doi/10.1103/PhysRevA.64.012310

    2001 doi

  34. [42]

    In: Pro- ceedings of the twenty-eighth annual ACM symposium on Theory of computing

    Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Pro- ceedings of the twenty-eighth annual ACM symposium on Theory of computing. pp. 212–219 (1996)

    1996

  35. [43]

    arXiv preprint arXiv:2510.23212 (2025)

    Gu, Q., Ye, H., Chen, J., Ma, X.: Resource analysis of shor’s elliptic curve al- gorithm with an improved quantum adder on a two-dimensional lattice. arXiv preprint arXiv:2510.23212 (2025)

    2025

  36. [44]

    In: International conference on post- quantum cryptography

    Häner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M.: Improved quantum circuits for elliptic curve discrete logarithms. In: International conference on post- quantum cryptography. pp. 425–444. Springer (2020)

    2020

  37. [45]

    arXiv preprint arXiv:1611.07995 (2016)

    Häner, T., Roetteler, M., Svore, K.M.: Factoring using 2n+ 2 qubits with toffoli based modular multiplication. arXiv preprint arXiv:1611.07995 (2016)

    2016 arXiv

  38. [46]

    arXiv preprint arXiv:1805.12445 (2018)

    Häner, T., Roetteler, M., Svore, K.M.: Optimizing quantum circuits for arith- metic. arXiv preprint arXiv:1805.12445 (2018)

    2018 arXiv

  39. [47]

    org/abs/2409.04643

    Harrigan, M.P., Khattar, T., Yuan, C., Peduri, A., Yosri, N., Malone, F.D., Bab- bush, R., Rubin, N.C.: Expressing and analyzing quantum algorithms with qual- tran (2024).https://doi.org/10.48550/arXiv.2409.04643,https://arxiv. org/abs/2409.04643

    2024 doi arXiv

  40. [48]

    Computer Systems Library, Standard University, Tech

    Harris, D., Oberman, S., Horowitz, M.: Srt division: Architectures, models, and implementations. Computer Systems Library, Standard University, Tech. Rep (1998)

    1998

  41. [49]

    In: Proceedings of the 40th ACM/SIGAPP Symposium on Applied Computing

    Hwang, S., Seo, H., Kim, Y.: Can less accurate be more accurate? surpass- ing exact multiplier with approximate design on nisq quantum computers. In: Proceedings of the 40th ACM/SIGAPP Symposium on Applied Computing. p. 590–591. SAC ’25, Association for Computing Machinery, Ne...

    2025 doi

  42. [50]

    Jang, K., Kim, W., Lim, S., Kang, Y., Yang, Y., Seo, H.: Optimized implementa- tionofquantumbinaryfieldmultiplicationwithtoffolidepthone.In:International Conference on Information Security Applications. pp. 251–264. Springer (2022)

    2022

  43. [51]

    Sensors23(6), 3156 (2023)

    Jang, K., Kim, W., Lim, S., Kang, Y., Yang, Y., Seo, H.: Quantum binary field multiplication with optimized toffoli depth and extension to quantum inversion. Sensors23(6), 3156 (2023)

    2023

  44. [52]

    IACR Transactions on Cryptographic Hardware and Embedded Systems2025(2), 781–804 (2025)

    Jang,K.,Srivastava,V.,Baksi,A.,Sarkar,S.,Seo,H.:Newquantumcryptanalysis of binary elliptic curves. IACR Transactions on Cryptographic Hardware and Embedded Systems2025(2), 781–804 (2025)

    2025

  45. [53]

    The Journal of Supercomputing72, 1477–1493 (2016)

    Jayashree, H., Thapliyal, H., Arabnia, H.R., Agrawal, V.K.: Ancilla-input and garbage-output optimized design of a reversible quantum integer multiplier. The Journal of Supercomputing72, 1477–1493 (2016)

    2016

  46. [54]

    IEEE transactions on computers44(8), 1064–1065 (2002) 24 Wang et al

    Kaliski, B.S.: The montgomery inverse and its applications. IEEE transactions on computers44(8), 1064–1065 (2002) 24 Wang et al

    2002

  47. [55]

    In: Doklady Akademii Nauk

    Karatsuba, A.A., Ofman, Y.P.: Multiplication of many-digital numbers by au- tomatic computers. In: Doklady Akademii Nauk. vol. 145, pp. 293–294. Russian Academy of Sciences (1962)

    1962

  48. [56]

    Quantum Information Processing14, 2373–2386 (2015)

    Kepley, S., Steinwandt, R.: Quantum circuits for f _ 2ˆ n f 2 n-multiplication with subquadratic gate count. Quantum Information Processing14, 2373–2386 (2015)

    2015

  49. [57]

    arXiv preprint arXiv:2407.17966 (2024)

    Khattar, T., Gidney, C.: Rise of conditionally clean ancillae for optimizing quan- tum circuits. arXiv preprint arXiv:2407.17966 (2024)

    2024 arXiv

  50. [58]

    Cryptology ePrint Archive (2025)

    Kim, H., Lim, S., Jang, K., Wang, S., Baksi, A., Chattopadhyay, A., Seo, H.: Tree-based quantum carry-save adder. Cryptology ePrint Archive (2025)

    2025

  51. [59]

    Quantum Information Processing 23(10), 330 (2024)

    Kim, S., Kim, I., Kim, S., Hong, S.: Toffoli gate count optimized space-efficient quantum circuit for binary field multiplication. Quantum Information Processing 23(10), 330 (2024)

    2024

  52. [60]

    arXiv preprint arXiv:2110.08973 (2021)

    Kornerup, N., Sadun, J., Soloveichik, D.: Tight bounds on the spooky peb- ble game: Recycling qubits with measurements. arXiv preprint arXiv:2110.08973 (2021)

    2021 arXiv

  53. [61]

    Nature pp

    Lacroix, N., Bourassa, A., Heras, F.J., Zhang, L.M., Bausch, J., Senior, A.W., Edlich, T., Shutty, N., Sivak, V., Bengtsson, A., et al.: Scaling and logic in the color code on a superconducting quantum processor. Nature pp. 1–3 (2025)

    2025

  54. [62]

    Laflamme, R., Miquel, C., Paz, J.P., Zurek, W.H.: Perfect quantum er- ror correcting code. Phys. Rev. Lett.77, 198–201 (Jul 1996).https:// doi.org/10.1103/PhysRevLett.77.198,https://link.aps.org/doi/10.1103/ PhysRevLett.77.198

    1996 doi

  55. [63]

    Applied Sciences11(9), 3752 (2021)

    Larasati, H.T., Awaludin, A.M., Ji, J., Kim, H.: Quantum circuit design of toom 3-way multiplication. Applied Sciences11(9), 3752 (2021)

    2021

  56. [64]

    ACM Transactions on Quantum Computing5(4) (Oct 2024).https://doi.org/10

    Leblond, T., Dean, C., Watkins, G., Bennink, R.: Realistic cost to execute prac- tical quantum circuits using direct clifford+t lattice surgery compilation. ACM Transactions on Quantum Computing5(4) (Oct 2024).https://doi.org/10. 1145/3689826,https://doi-org.remotexs.ntu.edu.s...

    2024 doi

  57. [65]

    PRX Quantum6, 030317 (Jul 2025).https://doi.org/10.1103/ch5r-cnfq,https://link.aps.org/doi/10

    Lee, S.H., Thomsen, F., Fazio, N., Brown, B.J., Bartlett, S.D.: Low-overhead magic state distillation with color codes. PRX Quantum6, 030317 (Jul 2025).https://doi.org/10.1103/ch5r-cnfq,https://link.aps.org/doi/10. 1103/ch5r-cnfq

    2025 doi

  58. [66]

    Nature Physics16(5), 509–513 (2020)

    Lescanne, R., Villiers, M., Peronnin, T., Sarlette, A., Delbecq, M., Huard, B., Kontos, T., Mirrahimi, M., Leghtas, Z.: Exponential suppression of bit-flips in a qubit encoded in an oscillator. Nature Physics16(5), 509–513 (2020)

    2020

  59. [67]

    Science China Physics, Mechanics & Astronomy 65(6), 260311 (2022)

    Li, H.S., Fan, P., Xia, H., Long, G.L.: The circuit design and optimization of quantum multiplier and divider. Science China Physics, Mechanics & Astronomy 65(6), 260311 (2022)

    2022

  60. [68]

    ACM Jour- nal on Emerging Technologies in Computing Systems (JETC)11(1), 1–20 (2014)

    Lin, C.C., Chakrabarti, A., Jha, N.K.: Qlib: Quantum module library. ACM Jour- nal on Emerging Technologies in Computing Systems (JETC)11(1), 1–20 (2014)

    2014

  61. [69]

    Quantum 3, 205 (Dec 2019).https://doi.org/10.22331/q-2019-12-02-205,http://dx

    Litinski, D.: Magic state distillation: Not as costly as you think. Quantum 3, 205 (Dec 2019).https://doi.org/10.22331/q-2019-12-02-205,http://dx. doi.org/10.22331/q-2019-12-02-205

    2019 doi

  62. [70]

    In: 2025 62nd ACM/IEEE Design Automation Conference (DAC)

    Luongo, A., Miti, A.M., Narasimhachar, V., Sireesh, A.: Measurement-based uncomputation of quantum circuits for modular arithmetic. In: 2025 62nd ACM/IEEE Design Automation Conference (DAC). pp. 1–7. IEEE (2025)

    2025

  63. [71]

    In: 2025 62nd ACM/IEEE Design Automation Conference (DAC)

    Luongo, A., Narasimhachar, V., Sireesh, A.: Optimizing windowed arithmetic for quantum attacks against rsa-2048. In: 2025 62nd ACM/IEEE Design Automation Conference (DAC). pp. 1–7. IEEE (2025) Quantum Arithmetic Circuits in Public-Key Cryptography 25

  64. [72]

    arXiv preprint arXiv:1202.6614 (2012)

    Markov, I.L., Saeedi, M.: Constant-optimized quantum circuits for modular mul- tiplication and exponentiation. arXiv preprint arXiv:1202.6614 (2012)

    2012 arXiv

  65. [73]

    IEEE Transactions on Computers68(5), 729–739 (2018)

    Muñoz-Coreas, E., Thapliyal, H.: Quantum circuit design of a t-count optimized integer multiplier. IEEE Transactions on Computers68(5), 729–739 (2018)

    2018

  66. [74]

    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023)

    Nie, J., Zhu, Q., Li, M., Sun, X.: Quantum circuit design for integer multiplication based on schönhage-strassen algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023)

    2023

  67. [75]

    arXiv preprint arXiv:2402.05053 (2024)

    Nie, J., Zi, W., Sun, X.: Quantum circuit for multi-qubit toffoli gate with optimal resource. arXiv preprint arXiv:2402.05053 (2024)

    2024 arXiv

  68. [76]

    Nature536(7617), 441–445 (2016)

    Ofek, N., Petrenko, A., Heeres, R., Reinhold, P., Leghtas, Z., Vlastakis, B., Liu, Y., Frunzio, L., Girvin, S.M., Jiang, L., et al.: Extending the lifetime of a quantum bit with error correction in superconducting circuits. Nature536(7617), 441–445 (2016)

    2016

  69. [77]

    Physical Review A107(4), 042621 (2023)

    Orts, F., Filatovas, E., Ortega, G., SanJuan-Estrada, J., Garzón, E.: Improving the number of t gates and their spread in integer multipliers on quantum com- puting. Physical Review A107(4), 042621 (2023)

    2023

  70. [78]

    Journal of Systems and Software p

    Orts,F.,Paulavičius,R.,Filatovas,E.:Quantumcircuitoptimizationofaninteger divider. Journal of Systems and Software p. 112091 (2024)

    2024

  71. [79]

    arXiv preprint arXiv:1706.03419 (2017)

    Parent, A., Roetteler, M., Mosca, M.: Improved reversible and quantum cir- cuits for karatsuba-based integer multiplication. arXiv preprint arXiv:1706.03419 (2017)

    2017 arXiv

  72. [80]

    IEEE Access11, 21848–21862 (2023)

    Putranto, D.S.C., Wardhani, R.W., Larasati, H.T., Kim, H.: Space and time- efficient quantum multiplier in post quantum cryptography era. IEEE Access11, 21848–21862 (2023)

    2023

  73. [81]

    Nature482(7385), 382–385 (2012)

    Reed,M.D.,DiCarlo,L.,Nigg,S.E.,Sun,L.,Frunzio,L.,Girvin,S.M.,Schoelkopf, R.J.: Realization of three-qubit quantum error correction with superconducting circuits. Nature482(7385), 382–385 (2012)

    2012

  74. [82]

    In: International Conference on Reversible Computation

    Remaud, M., Vandaele, V.: Ancilla-free quantum adder with sublinear depth. In: International Conference on Reversible Computation. pp. 137–154. Springer (2025)

    2025

  75. [83]

    Communications of the ACM21(2), 120–126 (1978)

    Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signa- tures and public-key cryptosystems. Communications of the ACM21(2), 120–126 (1978)

    1978

  76. [84]

    In: International Conference on the Theory and Application of Cryptology and Information Security

    Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates for computing elliptic curve discrete logarithms. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 241–270. Springer (2017)

    2017

  77. [85]

    US Patent 2,96630(1957)

    Rosenberger, G.B.: Simultaneous carry adder. US Patent 2,96630(1957)

    1957

  78. [86]

    International Journal of Theoretical Physics60, 1–13 (08 2021).https://doi.org/10.1007/ s10773-021-04864-3

    S S, G., Kumar, R., Samiappan, D., Kaushik, B.K., Haghparast, M.: T-count optimized wallace tree integer multiplier for quantum computing. International Journal of Theoretical Physics60, 1–13 (08 2021).https://doi.org/10.1007/ s10773-021-04864-3

    2021

  79. [87]

    Sajadimanesh, S., Atoofian, E.: Implementation of a quantum division circuit on noisy intermediate-scale quantum devices using dynamic cir- cuits and approximate computing. Phys. Rev. A109, 052601 (May 2024).https://doi.org/10.1103/PhysRevA.109.052601,https://link.aps. org/doi...

    2024 doi

  80. [88]

    Sajadimanesh, S., Faye, J.P.L., Atoofian, E.: Practical approximate quantum mul- tipliersfornisqdevices.In:Proceedingsofthe19thACMInternationalConference on Computing Frontiers. pp. 121–130 (2022) 26 Wang et al

    2022

  81. [89]

    Nature645(8081), 620–625 (Jul 2025).https://doi.org/10.1038/s41586-025-09367-3,http:// dx.doi.org/10.1038/s41586-025-09367-3

    Sales Rodriguez, P., Robinson, J.M., Jepsen, P.N., He, Z., Duckering, C., Zhao, C., Wu, K.H., Campo, J., Bagnall, K., Kwon, M., Karolyshyn, T., Weinberg, P., Cain, M., Evered, S.J., Geim, A.A., Kalinowski, M., Li, S.H., Manovitz, T., Amato-Grill, J., Basham, J.I., Bernstein, L...

    2025 doi

  82. [90]

    Schlegel, D.S., Minganti, F., Savona, V.: Quantum error correction us- ing squeezed schrödinger cat states. Phys. Rev. A106, 022431 (Aug 2022).https://doi.org/10.1103/PhysRevA.106.022431,https://link.aps. org/doi/10.1103/PhysRevA.106.022431

    2022 doi

  83. [91]

    Physical Review A—Atomic, Molecular, and Optical Physics78(1), 012337 (2008)

    Shaw, B., Wilde, M.M., Oreshkov, O., Kremsky, I., Lidar, D.A.: Encoding one logical qubit into six physical qubits. Physical Review A—Atomic, Molecular, and Optical Physics78(1), 012337 (2008)

    2008

  84. [92]

    Review of scientific instruments21(8), 687–693 (1950)

    Shaw, R.F.: Arithmetic operations in a binary computer. Review of scientific instruments21(8), 687–693 (1950)

    1950

  85. [93]

    Proceedings of 35th Annual Symposium on Foundations of Computer Science (10 1996).https://doi.org/10.1109/SFCS.1994.365700

    Shor,P.:Algorithmsforquantumcomputation:Discretelogarithmsandfactoring. Proceedings of 35th Annual Symposium on Foundations of Computer Science (10 1996).https://doi.org/10.1109/SFCS.1994.365700

    1996 doi

  86. [94]

    Electronic Computers, IRE Trans- actions onEC-9, 226 – 231 (07 1960).https://doi.org/10.1109/TEC.1960

    Sklansky, J.: Conditional-sum addition logic. Electronic Computers, IRE Trans- actions onEC-9, 226 – 231 (07 1960).https://doi.org/10.1109/TEC.1960. 5219822

    1960 doi

  87. [95]

    Steane, A.M.: Error correcting codes in quantum theory. Phys. Rev. Lett.77, 793–797 (Jul 1996).https://doi.org/10.1103/PhysRevLett.77.793,https:// link.aps.org/doi/10.1103/PhysRevLett.77.793

    1996 doi

  88. [96]

    Quantum Info

    Takahashi, Y., Kunihiro, N.: A linear-size quantum circuit for addition with no ancillary qubits. Quantum Info. Comput.5(6), 440–448 (sep 2005)

    2005

  89. [97]

    Quantum Information and Computation8, 636–649 (07 2008).https://doi.org/ 10.26421/QIC8.6-7-5

    Takahashi, Y., Kunihiro, N.: A fast quantum circuit for addition with few qubits. Quantum Information and Computation8, 636–649 (07 2008).https://doi.org/ 10.26421/QIC8.6-7-5

    2008 doi

  90. [98]

    Quantum Information and Computation10(10 2009).https://doi

    Takahashi, Y., Tani, S., Kunihiro, N.: Quantum addition circuits and unbounded fan-out. Quantum Information and Computation10(10 2009).https://doi. org/10.26421/QIC10.9-10-12

    2009 doi

  91. [99]

    In: Transactions on Computational Science XXVII, pp

    Thapliyal, H.: Mapping of subtractor and adder-subtractor circuits on reversible quantum gates. In: Transactions on Computational Science XXVII, pp. 10–34. Springer (2016)

    2016

  92. [100]

    IEEE transactions on emerging topics in computing9(2), 1045–1056 (2019)

    Thapliyal, H., Munoz-Coreas, E., Varun, T., Humble, T.S.: Quantum circuit de- signs of integer division optimizing t-count and t-depth. IEEE transactions on emerging topics in computing9(2), 1045–1056 (2019)

    2019

  93. [101]

    Thapliyal, H., Ranganathan, N.: Design of efficient reversible binary subtractors basedonanewreversiblegate.In:2009IEEEcomputersocietyannualsymposium on VLSI. pp. 229–234. IEEE (2009) Quantum Arithmetic Circuits in Public-Key Cryptography 27

    2009

  94. [102]

    arXiv preprint arXiv:1910.02849 (2019)

    Van Hoof, I.: Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic toffoli gate count. arXiv preprint arXiv:1910.02849 (2019)

    1910 arXiv

  95. [103]

    Physical Re- view A71(5), 052320 (2005)

    Van Meter, R., Itoh, K.M.: Fast quantum modular exponentiation. Physical Re- view A71(5), 052320 (2005)

    2005

  96. [104]

    Physical Review A54(11 1995).https://doi.org/10.1103/ PhysRevA.54.147

    Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arith- metic operations. Physical Review A54(11 1995).https://doi.org/10.1103/ PhysRevA.54.147

    1995

  97. [105]

    Jour- nal of Physics A: Mathematical and General34(35), 7067 (2001)

    Viola, L., Knill, E., Laflamme, R.: Constructing qubits in physical systems. Jour- nal of Physics A: Mathematical and General34(35), 7067 (2001)

    2001

  98. [106]

    IEEE Transactions on electronic Computers (1), 14–17 (1964)

    Wallace, C.S.: A suggestion for a fast multiplier. IEEE Transactions on electronic Computers (1), 14–17 (1964)

    1964

  99. [107]

    Science China Information Sciences59(02 2016).https://doi

    Wang, F., Luo, M., Li, H., Qu, Z., Wang, X.: Improved quantum ripple-carry addition circuit. Science China Information Sciences59(02 2016).https://doi. org/10.1007/s11432-015-5411-x

    2016 doi

  100. [108]

    Wang, S.: Innovative design and optimization of arithmetic circuits in quantum computing. Ph.D. thesis, Nanyang Technological University (2025)

    2025

  101. [109]

    Scientific Reports13(09 2023).https://doi.org/10

    Wang, S., Baksi, A., Chattopadhyay, A.: A higher radix architecture for quantum carry-lookahead adder. Scientific Reports13(09 2023).https://doi.org/10. 1038/s41598-023-41122-4

    2023

  102. [110]

    In: IFIP/IEEE International Con- ference on Very Large Scale Integration-System on a Chip

    Wang, S., Chattopadhyay, A.: Efficient depth optimization in quantum addition and modular arithmetic with ling structure. In: IFIP/IEEE International Con- ference on Very Large Scale Integration-System on a Chip. pp. 73–89. Springer (2023)

    2023

  103. [111]

    In: VLSI-SoC (2023)

    Wang, S., Chattopadhyay, A.: Reducing depth of quantum adder using ling struc- ture. In: VLSI-SoC (2023)

    2023

  104. [112]

    In: Proceedings of the Great Lakes Symposium on VLSI 2025

    Wang,S.,Dutta,S.,Lee,W.J.B.,Feng,J.,Fang,X.,Chattopadhyay,A.:Reducing t-depth and t-count in quantum multiplication using compressor primitives. In: Proceedings of the Great Lakes Symposium on VLSI 2025. pp. 35–40 (2025)

    2025

  105. [113]

    Philosophical Transactions A 383(2288), 20230392 (2025)

    Wang, S., Li, X., Lee, W.J.B., Deb, S., Lim, E., Chattopadhyay, A.: A com- prehensive study of quantum arithmetic circuits. Philosophical Transactions A 383(2288), 20230392 (2025)

    2025

  106. [114]

    In: 2024 IEEE International Sympo- sium on Circuits and Systems (ISCAS)

    Wang, S., Lim, E., Chattopadhyay, A.: Boosting the efficiency of quantum divider through effective design space exploration. In: 2024 IEEE International Sympo- sium on Circuits and Systems (ISCAS). pp. 1–5. IEEE (2024)

    2024

  107. [115]

    In: 2024 IFIP/IEEE 32nd International Conference on Very Large Scale Integration (VLSI-SoC)

    Wang, S., Lim, E., Li, X., Feng, J., Chattopadhyay, A.: Minimum depth quan- tum modular addition through carry-save architecture. In: 2024 IFIP/IEEE 32nd International Conference on Very Large Scale Integration (VLSI-SoC). pp. 1–6. IEEE (2024)

    2024

  108. [116]

    In: IFIP/IEEE International Conference on Very Large Scale Integration-System on a Chip

    Wang, S., Lim, E., Li, X., Feng, J., Chattopadhyay, A.: Quantum carry-save modular addition with optimized depth and resource utilization. In: IFIP/IEEE International Conference on Very Large Scale Integration-System on a Chip. pp. 17–32. Springer (2024)

    2024

  109. [117]

    ACM Transactions on Quantum Computing6(3), 1–16 (2025)

    Wang, S., Mondal, A., Chattopadhyay, A.: Optimal toffoli-depth quantum adder. ACM Transactions on Quantum Computing6(3), 1–16 (2025)

    2025

  110. [118]

    IEEE Access12, 8806–8821 (2024)

    Wardhani, R.W., Putranto, D.S.C., Kim, H.: High-and half-degree quantum mul- tiplication for post-quantum security evaluation. IEEE Access12, 8806–8821 (2024)

    2024

  111. [119]

    Quantum Information Processing21(5), 182 (2022) 28 Wang et al

    Yuan, S., Gao, S., Wen, C., Wang, Y., Qu, H., Wang, Y.: A novel fault-tolerant quantum divider and its simulation. Quantum Information Processing21(5), 182 (2022) 28 Wang et al

    2022

  112. [120]

    arXiv preprint quant-ph/9806084 (1998)

    Zalka, C.: Fast versions of shor’s quantum factoring algorithm. arXiv preprint quant-ph/9806084 (1998)

    1998 arXiv

  113. [121]

    Zhang, J., Cho, S.M., Lee, C., Seo, S.H.: Optimized quantum folding barrett reductionforquantummodularmultipliers.ScientificReports15(1),22808(2025)

    2025

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.