4
[1904.07356] Asymptotically Efficient Quantum Karatsuba Multiplication
source link: https://arxiv.org/abs/1904.07356
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 15 Apr 2019]
Asymptotically Efficient Quantum Karatsuba Multiplication
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.
Comments:
10 pages, 2 figures, code in ancillary files
Subjects:
Quantum Physics (quant-ph)
Cite as:
arXiv:1904.07356 [quant-ph]
(or
arXiv:1904.07356v1 [quant-ph] for this version)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK