Asymptotically Efficient Quantum Karatsuba Multiplication

2019/04/15 by Gidney, Craig · 2 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.1904.07356

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.

Cited by

• Asymptotic yet practical optimization of quantum circuits implementing GF(2^m) multiplication and division operations
• Quantum Arithmetic Algorithms: Implementation, Resource Estimation, and Comparison

Related

• Improved reversible and quantum circuits for Karatsuba-based integer\n multiplication
• Reducing the Complexity of Matrix Multiplication to O(N²log₂N) by an Asymptotically Optimal Quantum Algorithm
• Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count
• Quantum Advantage for All
• Introduction to Quantum Algorithms