A new quantum ripple-carry addition circuit
Open accessAbstract
We present a new linear-depth ripple-carry quantum addition circuit. Previous addition circuits required linearly many ancillary qubits; our new adder uses only a single ancillary qubit. Also, our circuit has lower depth and fewer gates than previous ripple-carry adders.
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Using Cuccaro et al.'s adder, each n-bit addition has a Toffoli count and measurement depth of 2n.
“Using Cuccaro et al.'s adder [18], each n -bit addition has a Toffoli count and measurement depth of 2 n .”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [18]
Section 3 (p. 4) gives the optimized n-bit adder a Toffoli count of 2n−1 and a circuit depth of 2n+4, both approximately 2n but not exactly 2n. It reports Toffoli time-slices, not measurement depth, so the measurement-depth attribution is unsupported. (LLM, conf=0.87)
Experimental — accuracy not yet measuredA controlled non-modular addition can be performed in 4n Toffolis, significantly cheaper than the 10n assumed for a controlled modular adder.
“It is possible to perform a controlled non-modular addition in 4 n Toffolis [18, 32], significantly cheaper than the 10 n we assumed for a controlled modular adder.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [18]
The Introduction (p. 1) describes a non-modular ripple-carry adder using 2n + O(1) Toffoli gates, and Section 3 (p. 4) gives its exact count as 2n−1. The paper does not give a 4n Toffoli count for a controlled version. The 10n figure in the citing sentence is the citing authors’ stated assumption, not a result attributed to this source. (LLM, conf=0.82)
Experimental — accuracy not yet measuredUse of the poly-depth ADDER is better in saving work space, whereas the log-depth ADDER could shorten the execution time.
“Use of the poly-depth ADDER is better in saving work space, whereas the log-depth ADDER could shorten the execution time.”
From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [54]
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
No references could be resolved yet.
Research works printed but not linked: 3
- [2][2] Thomas G. Draper, Addition on a quantum computer , quant-ph/0008033. - · arXiv
- [3][3] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, and Krysta M. Svore, A logarithmicdepth quantum carry-lookahead adder , EQIS, 2004, quant-ph/0406142. - · arXiv
- [4][4] Vlatko Vedral, Adriano Barenco, and Artur Ekert, Quantum networks for elementary arithmetic operations , quant-ph/9511018. · arXiv
Cited by
Sorted by citations
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · 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
Halving the cost of quantum addition
Gidney, C. (2018) · Quantum · doi:10.22331/q-2018-06-18-74 · Cited by 279 · see citing works
Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
Berry, D. W., Gidney, C., Motta, M., McClean, J. R., & Babbush, R. (2019) · Quantum · doi:10.22331/q-2019-12-02-208 · Cited by 222 · see citing works
QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation
Li, A., Stein, S., Krishnamoorthy, S., & Ang, J. (2023) · ACM Transactions on Quantum Computing · doi:10.1145/3550488 · Cited by 183 · see citing works
Grover Adaptive Search for Constrained Polynomial Binary Optimization
Gilliam, A., Woerner, S., & Gonciulea, C. (2021) · Quantum · doi:10.22331/q-2021-04-08-428 · Cited by 153 · see citing works
Faster quantum chemistry simulation on fault-tolerant quantum computers
Cody Jones, N., Whitfield, J. D., McMahon, P. L., Yung, M.-H., Meter, R. V., Aspuru-Guzik, A., & Yamamoto, Y. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/11/115023 · Cited by 145 · see citing works
A logarithmic-depth quantum carry-lookahead adder
Draper, T. G., Kutin, S. A., Rains, E. M., & Svore, K. M. (2006) · Quantum Information and Computation · doi:10.26421/qic6.4-5-4 · Cited by 101 · see citing works
Self-citationFactoring 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
“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.”
BackgroundKim, P., Han, D., & Jeong, K. C. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-2107-3 · Cited by 80 · see citing works
“Use of the poly-depth ADDER is better in saving work space, whereas the log-depth ADDER could shorten the execution time.”
MethodInfluentialImproved Quantum Circuits for Elliptic Curve Discrete Logarithms
Häner, T., Jaques, S., Naehrig, M., Roetteler, M., & Soeken, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-44223-1_23 · Cited by 76 · 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
Self-citationFast 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
Gate-based quantum computing for protein design
Khatami, M. H., Mendes, U. C., Wiebe, N., & Kim, P. M. (2023) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1011033 · Cited by 26 · see citing works
The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
Allcock, J., Vangone, A., Meyder, A., Adaszewski, S., Strahm, M., Hsieh, C.-Y., & Zhang, S. (2022) · Frontiers in Drug Discovery · doi:10.3389/fddsv.2022.908870 · Cited by 12 · see citing works
Flexible layout of surface code computations using AutoCCZ states
Gidney, C., & Fowler, A. G. (2019) · arXiv · doi:10.48550/arxiv.1905.08916 · Cited by 12 · see citing works
- Authors
- Cuccaro, S. A., Draper, T. G., Kutin, S. A., & Moulton, D. P.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2004
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- quant-ph/0410184
- OpenAlex
- W1629802966
- Cited by
- 344
- References
- 0
- Citations by year
- 2026: 8 · 2025: 10 · 2024: 33 · 2023: 32 · 2022: 34 · 2021: 27 · 2020: 31 · 2019: 13 · 2018: 13 · 2017: 11 · 2016: 14 · 2015: 13 · 2014: 23 · 2013: 15 · 2012: 18
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (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 › Computational Theory and Mathematics › Quantum-Dot Cellular Automata
- Keywords
- quantum arithmetic, quantum circuit design
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
