# Quantum Circuit Design of Toom 3-Way Multiplication
## 4 Cost Analysis
### Space-Time Complexity Analysis
This is heavily contributed by the division operation (or the constant multiplication in our case) that exist in Toom-3, which requires quadratic number of gates for its operation. Note that we use the cost of (unoptimized) general constant multiplication circuit in the complexity calculation to show the worse scenario. For a non-asymptotic performance consideration, an optimization to reduce the gate count in the constant multiplication by roughly a half can be employed since the constant that we use is fixed (i.e., the reciprocal, 0101...011), eliminating the gates required for the case of bit \"0\". Then, the Toffoli count for the constant multiplication can be reduced to as low as \(4n(\tfrac{1}{2}n+2)=2n^{2}+8\). Regarding the possibility of employing other techniques to achieve a more efficient circuit, in classical computation, some authors proposed the division-free Toom-Cook multiplication, such as [18; 45]. The methods generally revised the inversion matrix of Toom-Cook, multiplying it by 3, which results in the absence of division operation but multiply all of the values in the interpolation steps. The division is then performed at the end of \begin{table}
\begin{tabular}{l c c c} \hline \hline
**Mult. Method** & **Toffoli Count** & **Qubit Count** & **Toffoli Depth** \\ \hline Schoolbook [8] & \(4n^{2}-3n\) & \(4n+1\) & \(4n^{2}-4n+1\) \\ [PERSON] [8] & \(42n^{\log_{2}3}\) & \(n\big{(}\tfrac{3}{2}\big{)}\big{(}\tfrac{\log 3}{2\log 3-\log 2}\big{)}\log_{2}n \approx n^{1.427}\) & \(n\big{(}\tfrac{3}{2}\big{)}^{\big{(}1-\tfrac{\log 3}{2\log 3-\log 2}\big{)}\log_{2}n }\approx n^{1.158}\) \\ [PERSON] [11] & \(49n^{\log_{6}16}\) & \(n\big{(}\tfrac{8}{3}\big{)}\big{(}\tfrac{\log 16}{\log 16-\log 6}\big{)}\log_{6}n \approx n^{1.404}\) & \(n\big{(}\tfrac{8}{3}\big{)}^{\big{(}1-\tfrac{\log 16}{2\log 16-\log 6}\big{)}\log_{6}n }\approx n^{1.143}\) \\ Toom-3 & \(8n^{2}+66n^{\log_{2}5}-\) & \(n\big{(}\tfrac{5}{3}\big{)}\big{(}\tfrac{\log 5}{2\log 5-\log 5}\big{)}\log_{3}n \approx n^{1.353}\) & \(n\big{(}\tfrac{5}{3}\big{)}^{\big{(}1-\tfrac{\log 5}{2\log 5-\log 3}\big{)}\log_{3}n }\approx n^{1.112}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Complexity of Several Quantum Multiplication Methods. \begin{table}
\begin{tabular}{l c c c} \hline \hline
**Mult. Method** & **Toffoli Count** & **Qubit Count** & **Toffoli Depth** \\ \hline Schoolbook [8] & \(O(n^{2})\) & \(O(n)\) & \(O(n^{2})\) \\ Karatsuba [8] & \(O(n^{\log_{2}3})\) & \(O(n^{1.427})\) & \(O(n^{1.158})\) \\ Toom-2.5 [11] & \(O(n^{\log_{6}16})\) & \(O(n^{1.404})\) & \(O(n^{1.143})\) \\ Toom-3 & \(O(n^{2})\) & \(O(n^{1.353})\) & \(O(n^{1.112})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Asymptotic Complexity of Several Quantum Multiplication Methods. the circuit or fed directly for the higher-level function such as a modular multiplication. However, our calculation finds this is unsuitable for quantum usage since it incurs even higher additional cost. In particular, there are numerous constant multiplications required for the coefficient multiplication, and there will still be a division at the end, which nullifies the advantage of the so-called division-free itself. Nonetheless, this approach may be advantageous if the multiplication is not a standalone operation but incorporated into a more advanced operation such as in modular exponentiation. In summary, Toom 3-way multiplication is competitive for achieving a lower asymptotic runtime and qubit count, with the tradeoff of higher number of Toffoli gates employed in the circuit. Nevertheless, division operation has been a bottleneck in lowering the Toffoli counts. Since higher-order Toom-Cook multiplication (e.g., Toom-4, Toom-5, etc.) also employ nontrivial divisions, it is essential to pursue a more efficient division method to enable further exploration in Toom-Cook multiplication, which we will investigate in the future research.