Asymptotically Efficient Quantum Karatsuba Multiplication

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.

10 pages, 2 figures, code in ancillary files

Cited by in corpus (6)

• Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
• A Derivative-free Method for Quantum Perceptron Training in Multi-layered Neural Networks
• Fast digital methods for adiabatic state preparation
• Windowed quantum arithmetic
• Resource Estimation of Quantum Multiplication Algorithms
• Approximate encoded permutations and piecewise quantum adders