REVIEW 2 cited by
Asymptotically Efficient Quantum Karatsuba Multiplication
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Asymptotically Efficient Quantum Karatsuba Multiplication
read the original abstract
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.
Forward citations
Cited by 2 Pith papers
-
Strategic Plan for Neutral Atom Quantum Computation
If qubit-count growth (~1.8x/yr) and gate-error reduction (~0.62x/yr) continue, neutral-atom quantum computers could reach practical quantum advantage within a decade, this roadmap projects.
-
Quantum Arithmetic Circuits in Public-Key Cryptography
A structured survey of optimized quantum adders, multipliers, modular exponentiation and point-addition circuits for public-key cryptanalysis, plus fault-tolerant resource estimation techniques.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.