Craig Gidney
(Submitted on 15 Apr 2019)
We improve the space complexity of Karatsuba multiplication on a quantum computer from O(n1.427) to O(n) while maintaining O(nlg3) 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.
Explanatory Article:
A New Approach to Multiplication Opens the Door to Better Quantum Computers
No comments:
Post a Comment