# Quantum Circuit Design of Toom 3-Way Multiplication
## 1 Introduction
In their paper, they stated that the primary reason why they utilize the less familiar Toom 2.5-way rather than the more commonly-used Toom 3-way multiplication is to avoid employing the nontrivial division circuit required by the latter method, which they argued to induce higher cost. Nevertheless, we believe that it would be beneficial to examine the Toom 3-way multiplication for the use in quantum computation for several reasons. First, Toom 3-way multiplication is classically known to yield lower computational complexity than Toom 2.5-way and more often found in the software implementation [11; 18], such as in the GNU multi-precision library [19]. In addition, considering the mathematical equations, most of the higher-order Toom-Cook multiplications make use of some nontrivial divisions. If such operation needs to be completely avoided, this may hinder the advancement for higher-order Toom-\(k\) for the quantum case. In contrast, analyzing its cost in the quantum case can provide insights and open the possibility to the higher Toom-\(k\) multiplication. Additionally, despite the view that division circuit is expensive, there have been several attempts to achieve relatively efficient quantum dividers, either for binary integer [20; 21; 22] or floating point arithmetic case [23]. Furthermore, the nontrivial division operation inherent to Toom 3-way (and higher order) multiplication is not a general one; instead, it uses exact integer division, which we later found to enable some further optimization to the circuit. In particular, for the case of division by 3 as in Toom-3, we may treat it as a constant multiplication by the reciprocal of 3. Using the constant multiplication circuit by [24], we find that Toom 3-way multiplication still give lower asymptotic Toffoli depth and space compared to [11] but with a higher cost in the number of Toffoli gates. In this paper, we investigate Toom 3-way multiplication for the use in quantum computation. In particular, we provide the quantum circuit for the Toom-3 multiplication. Moreover, we adopt the classical sequencing from [PERSON] [25] for our circuit construction steps, which results in a lower number of operation and primarily, the reduction of nontrivial division to only one for each multiplication step. Furthermore, we propose to regard the exact division by 3 circuit as a constant multiplication by reciprocal to enable employing a more efficient quantum subroutine proposed by [24]. Subsequently, we analyze the complexity of the circuit in terms of recursive approach, as in [8,11]. The result of analysis shows that even though the division circuit required in Toom-3 does contributes to a higher Toffoli count, it still acquires better asymptotic complexity in terms of Toffoli depth and qubit count, hence still giving a competitive advantage compared to existing multiplication algorithms. The contribution of this paper can be summarized as follows:  
* We design the quantum circuit for Toom-3 multiplication which minimizes the division circuit from four to only one by employing the classical sequence proposed by [PERSON] [25]. * We propose to use a constant multiplication circuit to perform the division by 3 operation. In particular, the division is treated as a constant multiplication by reciprocal. * We analyze the complexity of the circuit, which shows that the proposed quantum circuit for Toom-3 still has a competitive advantage in terms of Toffoli depth and qubit count. The remainder of the paper is summarized as follows. Section 2 describes the existing quantum multiplication methods as well as the brief theoretical aspects of classical Toom 3-way multiplication. Subsequently, Section 3 details our proposed methods whereas Section 4 contains the complexity analysis of the proposed Toom 3-way multiplication, along with its comparison with existing methods and some discussions. Lastly, Section 5 concludes the paper.