# Quantum Circuit Design of Toom 3-Way Multiplication
## 2 Related Work
### Toom-Cook Multiplication Method
#### 2.2.2 Toom 3-Way Multiplication  
Toom 3-way multiplication splits a large integer multiplication to five smaller multiplications, then carries out the operations per part. The general method to implement  
Figure 1: Recursion tree structure of the Toom-3 Multiplication.  
Toom 3-way multiplication method is by: (1) splitting the inputs (i.e., the numbers to be multiplied or input operands) \(x\) and \(y\), each into three smaller parts of length \(\frac{y}{3}\), then (2) evaluating each of them on the five predetermined evaluation points, here we use \(\{0,1,-1,-2,\infty\}\); (3) performing point-wise multiplication, continued by (4) interpolation, then at the end, carrying out (5) recomposition to form the final result.  
Here, we briefly describe the notation used in this paper to avoid confusion. \(x\) denotes the full digit input; \(x_{0},x_{1},x_{2}\) represent the split inputs, whereas \(x(0)\), \(x(1)\), \(x(-1)\), \(x(-2)\), and \(x(\infty)\) indicate the result of evaluating \(x\) for the corresponding evaluation points. Likewise, the notation of \(y\) is identical to that of \(x\).  
For the first step, the splitting of Toom 3-way multiplication can be done as follows:  
\[\begin{split} x&=x_{2}2^{2j}+x_{1}2^{j}+x_{0}\\ y&=y_{2}2^{2j}+y_{1}2^{j}+y_{0}\end{split} \tag{1}\]  
with radix \(j\) is precomputed as  
\[j=\max\biggl{\{}\left\lfloor\frac{\lceil log_{2}x\rceil}{3}\right\rfloor, \left\lfloor\frac{\lceil log_{2}y\rceil}{3}\right\rfloor\biggr{\}} \tag{2}\]  
For the second step, evaluation of point \(x\) is:  
\[\begin{split} x(0)&=x_{0}\\ x(1)&=x_{2}+x_{1}+x_{0}\\ x(-1)&=x_{2}-x_{1}+x_{0}\\ x(-2)&=4x_{2}-2x_{1}+x_{0}\\ x(\infty)&=x_{2}\end{split} \tag{3}\]  
Similarly, evaluation of point \(y\) is described below:  
\[\begin{split} y(0)&=y_{0}\\ y(1)&=y_{2}+y_{1}+y_{0}\\ y(-1)&=y_{2}-y_{1}+y_{0}\\ y(-2)&=4y_{2}-2y_{1}+y_{0}\\ y(\infty)&=y_{2}\end{split} \tag{4}\]  
Subsequently, one round (nonrecursive) of Toom 3-way multiplication uses five multiplications with smaller bit length. Multiplying each part of Equations (3) and (4) (i.e., point-wise), the result of each part is as presented in Equation (5), indicated as the notion \(P\), \(Q\), \(R\), \(S\), and \(T\).  
\[\begin{split} P&=x_{0}y_{0}\\ Q&=(x_{2}+x_{1}+x_{0})(y_{2}+y_{1}+y_{0})\\ R&=(x_{2}-x_{1}+x_{0})(y_{2}-y_{1}+y_{0})\\ S&=(4x_{2}-2x_{1}+x_{0})(4y_{2}-2y_{1}+y_{0})\\ T&=x_{2}y_{2}\end{split} \tag{5}\]\[\begin{pmatrix}E\\ D\\ C\\ B\\ A\end{pmatrix}=\begin{pmatrix}1&0&0&0&0\\ 1&1&1&1&1\\ 1&-1&-1&1&1\\ 1&-2&4&-8&16\\ 0&0&0&0&1\end{pmatrix}^{-1}\begin{pmatrix}P\\ Q\\ R\\ S\\ T\end{pmatrix} \tag{6}\] \[=\begin{pmatrix}1&0&0&0&0\\ 1&\frac{1}{3}&-1&\frac{1}{5}&-2\\ -1&\frac{1}{2}&1&0&-1\\ -\frac{1}{2}&\frac{1}{6}&\frac{1}{2}&-\frac{1}{6}&2\\ 0&0&0&0&1\end{pmatrix}\begin{pmatrix}P\\ Q\\ R\\ S\\ T\end{pmatrix}\]  
Next, interpolation is the reverse of the point-wise multiplication results, which can be presented in a matrix form as presented in Equation (6). Then, the result of interpolation steps, here indicated as A, B, C, D, and E, follows the mathematical equation as presented in Equations (7)-(11).  
\[A =T \tag{7}\] \[B =-\frac{1}{2}P+\frac{1}{6}Q+\frac{1}{2}R-\frac{1}{6}S+2T\] (8) \[C =-P+\frac{1}{2}Q+\frac{1}{2}R-T\] (9) \[D =\frac{1}{2}P+\frac{1}{3}Q-R+\frac{1}{6}S-2T\] (10) \[E =P \tag{11}\]  
Then, the final multiplication result can be obtained as:  
\[xy =A2^{4j}+B2^{3j}+C2^{2j}+D2^{j}+E \tag{12}\]