Quantum Circuit Design for Integer Multiplication Based on Schönhage–Strassen Algorithm

Abstract

Quantum arithmetic circuits have attracted extensive attention recently since it plays fundamental roles in many applications of quantum computing. Specifically, quantum circuits for integer multiplication are of great significance to various quantum algorithms, including Shor’s integer factorization and discrete logarithm algorithm. In this article, we design a family of quantum circuits for integer multiplication based on the famous classical integer multiplication algorithm, Schönhage–Strassen algorithm. We have made slight modifications to the algorithm to simplify its quantum circuit implementation. As a result, the quantum circuit we designed has gate depth <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\log ^{2} n)$ </tex-math></inline-formula> . To the best of our knowledge, this is the first poly-logarithmic depth quantum circuit for integer multiplication which keeps the circuit size and the number of ancillary qubits subquadratic. Our design has size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n\log n\log \log n)$ </tex-math></inline-formula> counted by elementary quantum gates which is the same as the time complexity of the Schönhage–Strassen algorithm, and it consumes <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n\log n\log \log n)$ </tex-math></inline-formula> clean ancillary qubits. In addition, we also utilize a weaker version of Schönhage–Strassen algorithm to give a family of circuits which has depth at the same order <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\log ^{2} n)$ </tex-math></inline-formula> but with significantly smaller constants, while still keeping the size and number of ancillary qubits subquadratic.