# Quantum Circuit Design of Toom 3-Way Multiplication
## 4 Cost Analysis
### Space-Time Complexity Analysis  
The recursive approach intrinsic to the algorithm may result in an enormous space consumption (i.e., qubit count) if not bounded. To improve the asymptotic performance in terms of space, one can employ the so-called reversible pebble game. Introduced by [PERSON] [17] in 1989, the reversible pebble game is a modification of the traditional pebble game for use in the field of reversible computing, which allows analysis of time and space complexity as well as to achieve a time-efficient space-restricted computation [44]. This approach enables one to analyze techniques to minimize scratch space with the downside of needing to recompute intermediate results [8]. To calculate the optimized multiplication cost, we follow the steps presented in [8,11]. Additionally, the depth of our employed constant multiplication scales in linear fashion, similar to adder, thus treated similarly and omitted from the multiplication depth. In terms of the proposed Toom-3 circuit, the recursive implementation of five parallel multiplications forms a quinary tree structure. For an \(n\)-sized input at level \(l\), there are \(5^{l}\) nodes with size \(3^{-l}n\), with the total circuit cost of that level is \(n\left(\frac{5}{3}\right)^{l}\). Consequently, the cost of full quinary tree is as presented in Equation (26). \[n\sum_{i=0}^{N}\left(\frac{5}{3}\right)^{i},\quad N=\log_{3}n \tag{26}\]  
To achieve a balanced performance, we should seek the appropriate tree height \(k\) which makes the size of the below subtrees roughly equal to the tree above them. That is,  
\[n\sum_{i=0}^{N-k-1}\left(\frac{5}{3}\right)^{i}=\frac{1}{3^{N-k}}\sum_{i=0}^{k -1}\left(\frac{5}{3}\right)^{i} \tag{27}\]  
Similar to Equation (25), the geometric series identity allows us to obtain the bound:  
\[k\leq\frac{N}{2-\frac{\log 3}{\log 5}}\approx 0.759N \tag{28}\]  
Thus, the space can be reduced to:  
\[QC=O\left(n\left(\frac{5}{3}\right)^{\left(\frac{\log 5}{2\log 5-\log 3} \right)\log_{3}n}\right)\approx O(n^{1353}), \tag{29}\]  
which is lower than the original required space:  
\[n\sum_{k=0}^{\log_{3}n-1}\left(\frac{5}{3}\right)^{k}=n\left(\frac{1-\left( \frac{5}{3}\right)^{\log_{3}n}}{1-\frac{5}{3}}\right) \tag{30}\]  
which bounds to  
\[O(n^{\log_{3}5})\approx O(n^{1.465}). \tag{31}\]  
Subsequently, the time complexity is often considered as the Toffoli depth of the circuit [11,12]. In this case, it can be calculated as the product of number of subtrees \(S_{k}\) and its corresponding depth \(D_{k}\) at the \(k\)-th level [11]. Then, the overall Toffoli depth \(T_{d}\) is as presented in Equation (32). The complexity analysis of Toom 3-way multiplicationcircuit along with the comparison with similar methods is summarized in Table 1 and for asymptotic case is on Table 2.  
\[ \begin{split} S_{k}&=5\big{(}\tfrac{1-\tfrac{\log 5}{ 2\log 5-\log 3}}{2\log 5-\log 3}\big{)}\log_{3}n\\ D_{k}&=\frac{n}{3\big{(}\tfrac{1-\log 5}{ 2\log 5-\log 3}\big{)}\log_{3}n}\\ T_{d}&=S_{k}D_{k}=n\bigg{(}\frac{5}{3}\bigg{)}^{ \big{(}1-\tfrac{\log 5}{ 2\log 5-\log 3}\big{)}\log_{3}n}\approx n^{1.112}\end{split}  \tag{32}\]  
As shown in the figures, the resulting quantum circuit for Toom 3-way multiplication does give lower asymptotic Toffoli depth and qubit count compared to prior work. Specifically, in terms of Toffoli depth, the cost scales \(O(n^{1.112})\) to the multiplication length whereas Toom-2.5, Karatsuba, and naive schoolbook multiplication cost \(O(n^{1.143})\), \(O(n^{1.158})\) and \(O(n^{2})\), respectively. Similarly, the qubit count also tops Toom-2.5 and Karatsuba with \(O(n^{1.353})\) compared to \(O(n^{1.404})\) and \(O(n^{1.427})\), respectively. Note that for qubit count, schoolbook multiplication does incur a linear cost, meaning lower than all of the non-naive multiplications; this is expected since no parallelization is enacted. Nevertheless, in terms of Toffoli count, Toom-3 circuit still scales quadratically as in the naive method.