Quantum multiplication algorithm based on the convolution theorem
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
The problem of efficient multiplication of large numbers has been a long-standing challenge in classical computation and has been extensively studied for centuries. It appears that the existing classical algorithms are close to their theoretical limit and offer little room for further enhancement. However, with the advent of quantum computers and the need for quantum algorithms that can perform multiplication on quantum hardware, a new paradigm emerges. In this paper, inspired by the Strassen method that relies on the convolution theorem and classical Fast Fourier Transform, we propose a quantum version of this algorithm that can perform multiplication with some advantages over the modern classical multiplication algorithms by using quantum resources. We demonstrate how the quantum version of the convolution theorem can offer significant improvements to multiplication algorithms in terms of accuracy, exponential reduction of space complexity and (probabilistic) enhancement of time efficiency. The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.