The DOI matches its DataCite record.
Asymptotically Efficient Quantum Karatsuba Multiplication
Open accessAbstract
We improve the space complexity of Karatsuba multiplication on a quantum computer from $O(n^{1.427})$ to $O(n)$ while maintaining $O(n^{\lg 3})$ gate complexity. We achieve this by ensuring recursive calls can add their outputs directly into subsections of the output register. This avoids the need to store, and uncompute, intermediate results. This optimization, which is analogous to classical tail-call optimization, should be applicable to a wide range of recursive quantum algorithms.
Overview
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
Verification
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?
Oblivious carry runways split registers into independent pieces that can be worked on in parallel when performing additions.
“We use oblivious carry runways [33] to split registers into independent pieces that can be worked on in parallel when performing additions.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [33]
Construction (pp. 3–4) describes padding words to stop carries from crossing word boundaries, allowing additions to be scoped to sections of a register. It does not identify this mechanism as “oblivious carry runways” or say that the resulting pieces can be worked on in parallel during additions. (LLM, conf=0.84)
Experimental — accuracy not yet measuredOblivious carry runways allow large additions to be performed piecewise in parallel by terminating carries into appropriately placed runways at the end of each piece.
“Runways allow large additions to be performed piecewise, with each piece being worked on in parallel, by terminating carries into appropriately placed runways at the end of each piece.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [33]
Section 2 (pp. 3–4) describes padding words to terminate carries and confine additions to specified sections. It does not describe these as oblivious carry runways or say that the pieces of a large addition are worked on in parallel. (LLM, conf=0.85)
Experimental — accuracy not yet measuredAttempting to fix the problem of naive translation of Karatsuba multiplication can result in the space complexity increasing, though it is possible to solve this problem.
“Attempting to fix this problem can result in the space complexity increasing [65], though it is possible to solve this problem [34].”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [34]
Circuits using oblivious carry runways approximate the original circuit, and increasing the runway length c_pad exponentially suppresses the approximation error.
“As with the coset representation of modular integers, circuits using oblivious carry runways approximate the original circuit instead of perfectly reproducing it. But, as we will discuss later, increasing the runway length c pad exponentially suppresses the approximation error.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [33]
Section 2 (pp. 4–5) discusses padding to contain carries in Karatsuba multiplication, but does not describe oblivious carry runways or an approximation error. Searches for “oblivious carry runways,” “c_pad,” and exponential error suppression found no passage addressing the claim. (LLM, conf=0.76)
Experimental — accuracy not yet measuredThe approximation error introduced by using oblivious carry runways and the coset representation can be bounded by analyzing them as approximate encoded permutations.
“We bound the approximation error introduced by using oblivious carry runways and the coset representation of modular integers by analyzing them as approximate encoded permutations [33].”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [33]
Section 2 (pp. 3–5) describes padding words to stop carries in a Karatsuba multiplication construction, not oblivious carry runways or a coset representation. Searches for those terms and for approximate encoded permutations found no passage analyzing or bounding the claimed approximation error. (LLM, conf=0.76)
Experimental — accuracy not yet measured
The computations using oblivious carry runways and the coset representation of modular integers are approximations rather than exact, and the approximation error can be bounded using concepts and results from [33].
“Because we are using oblivious carry runways and the coset representation of modular integers, the computations we perform are not exact. Rather, they are approximations. This is not a problem in practice, as we may bound the approximation error using concepts and results from [33].”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [33]
Section 2 (pp. 4–5) describes padding bits to contain carries in a Karatsuba multiplication construction, while Section 4 (p. 7) says the analyzed case is multiplication of two quantum integers, not controlled modular multiplication. Searches for oblivious carry runways, coset representations, and approximation-error bounds found no passage addressing the claim. (LLM, conf=0.76)
Experimental — accuracy not yet measuredWith padding/runway length c_pad and runway separation c_sep, the deviation per addition is at most n/(c_sep 2^{c_pad}); deviation is subadditive under composition, so the deviation of the entire modular exponentiation is at most the number of lookup additions times the deviation per addition.
“When using a padding/runway length of c pad , and a runway separation of c sep , the deviation per addition is at most n/ ( c sep 2 c pad ) . Deviation is subadditive under composition, so the deviation of the entire modular exponentiation process is at most the number of lookup additions times the deviation per addition.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [33]
Split into 2 atoms — 0 confirmed, 0 partially supported, 0 disputed, 0 misattributed, 2 unverifiable. Expand the claim to see per-atom verdicts.
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 5
- [1][1] Charles H Bennett. Logical reversibility of computation. IBM journal of Research and Development , 17(6):525-532, 1973. -
- [2][2] Charles H Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing , 18(4):766-776, 1989. -
- [3][3] Anatolii Alekseevich Karatsuba and Yu P Ofman. Multiplication of many-digital numbers by automatic computers. In Doklady Akademii Nauk , volume 145, pages 293-294. Russian Academy of Sciences, 1962. -
- [4][4] Alex Parent, Martin Roetteler, and Michele Mosca. Improved reversible and quantum circuits for karatsuba-based integer multiplication. arXiv preprint arXiv:1706.03419 , 2017. - · arXiv
- [5][5] R Portugal, CMH Figueiredo, et al. Reversible karatsubas algorithm. Journal of Universal Computer Science , 12(5):499-511, 2006.
Cited by
Sorted by citations
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
Self-citation
Metadata
- Authors
- Gidney, C.
- Affiliations
- Google (United States) (US)
- Corresponding author
- Gidney, Craig
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2019
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1904.07356
- OpenAlex
- W2937261435
- Cited by
- 18
- References
- 0
- Citations by year
- 2026: 1 · 2024: 2 · 2023: 7 · 2022: 3 · 2020: 3 · 2019: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Keywords
- Karatsuba multiplication, quantum algorithms, asymptotic complexity, space complexity, gate complexity, large integer multiplication
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
