arXiv:1904.07356quant-ph
Asymptotically Efficient Quantum Karatsuba Multiplication
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
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.
I wrote the paper that this article is describing [1], and can answer questions. The paper is probably more approachable than you think. Basically I rewrite code like `let intermediate_value = recursive_call(...)` into code like `output += recursive_call(...)`, which allows you…
StrilancView on HNParent context