# Quantum Circuit Design of Toom 3-Way Multiplication
## 1 Introduction  
Quantum arithmetic circuits are considered as the basic building blocks to realize various quantum algorithms [1, 2]. After the prominent proposal of [PERSON]'s algorithm [3] in 1994 which shows the apparent advantage of quantum computers in cracking the existing cryptosystems (i.e., Rivest-Shamir-Adleman (RSA) and elliptic curve-based cryptography (ECC)), substantial research efforts have been made to design an efficient quantum circuit for modular exponentiation operation, which is the essential component of the algorithm. Thus, various proposed methods have focused on building such specialized circuit and its underlying components, such as adder, modular adder, and modular multiplier by a constant [2, 4, 5, 6, 7], tailored to certain characteristics of modular arithmetic operations for achieving further simplifications [8]. However, as researchers explore wider area of studies, many other quantum algorithms being discovered require a more general arithmetic approach. Among other components, integer multiplication is one of the essential functions that also underlies a more complex operation, such as the polynomial multiplication. In fact, various quantum algorithms, such as the one proposed by [PERSON] et al. for nonlinear structures [9], Fourier Transform computation [10], as well as matrix inversion, can be reduced to an integer multiplication [8]. Adapted from classical approach, quantum integer multiplication can be simply realized using the naive schoolbook multiplication algorithm [8, 11], which takes only around \(4n+1\) qubits, with \(n\) representing the operand length. However, the depth of the circuitscales quadratically to \(n\), which would be unfavorable for large numbers since circuit depth directly affects the runtime and also correlates to error rates [12]. Thus, a few proposals [8; 11; 13] have explored other multiplication algorithms which traditionally offers better asymptotic time complexity, i.e., classical Karatsuba [14] and Toom-Cook multiplication [15; 16] for use in quantum computation. Karatsuba multiplication itself is a fast multiplication technique proposed by [PERSON] in 1962 which splits an \(n\)-digit multiplication into three submultiplications and some additions whereas Toom-Cook, or Toom-\(k\) multiplication, is the generalization of Karatsuba algorithm to \(k\) smaller multiplications for achieving an even lower asymptotic complexity than Karatsuba. Classically, higher \(k\) yields better complexity for sufficiently large integers. Earlier, [PERSON] et al. [13] analyzed the reversible Karatsuba circuit for the use in either classical reversible or quantum computation. Their work shows that the reversible version of Karatsuba is still able to maintain asymptotically lower runtime than the naive multiplication. To be precise, their analysis for sequential approach shows a similar complexity for depth, space (qubit count), and circuit size, i.e., \(O(n^{\log_{2}3})\approx O(n^{1.585})\). Subsequently, [PERSON] et al. [8] improved the work of [13] and presented a more comprehensive discussion from the quantum computation's viewpoint. Beside providing the corresponding quantum circuit, the authors of [8] explained the method to optimize the algorithm's recursive implementation to yield an optimal time-space trade off, namely via the reversible pebble games. First introduced by [PERSON] [17] for classical reversible computation, employing this approach further reduces the depth and space to \(O(n^{1.158})\) and \(O(n^{1.427})\), respectively, while circuit size remains. In terms of Toom-Cook multiplication, there has only been one proposal to examine this algorithm in the quantum realm, that is by [PERSON] et al. [11]. Presenting the circuit for Toom-2.5 and conducting analysis similar to [8], they obtained the asymptotic complexity for depth, space, and size of \(O(n^{1.143})\), \(O(n^{1.404})\), and \(O(n^{1.547})\), which outperforms the quantum Karatsuba circuit of [8; 13].