# Quantum Circuit Design of Toom 3-Way Multiplication
## 2 Related Work
### Toom-Cook Multiplication Method  
#### 2.2.1 General Toom-Cook Multiplication  
Toom-Cook multiplication algorithm [15; 16], sometimes referred interchangeably to as Toom-\(k\) or Toom \(k\)-way multiplication, is a method to reduce the complexity of a multiplication for larger numbers. Proposed by [PERSON] in 1963 [15], the algorithm is essentially a generalization of Karatsuba multiplication. While in Karatsuba, the operand input is split into half and the multiplication is performed using three submultiplications(along with its other sub operations, i.e., four additions/subtractions for Karatsuba case), Toom-Cook multiplication lets the number of splits \(k\) vary with operand bitlength \(n\), choosing increasingly larger \(k\) as \(n\) grows to obtain a lower complexity [32]. In 1966, [PERSON] [16] then showed in his dissertation that this method can be adapted to fast computer programs [32].  
The main idea of Toom-Cook algorithm is to treat the desired multiplication of two operands as a multiplication of two degree-\((n-1)\) polynomials, in which by utilizing the principle taken from linear algebra, can be done using only \((2n-1)\) coefficient multiplications. That is, any degree-\(n\) polynomial can be uniquely determined by its evaluation at \(n+1\) distinct points [33], which directly translates to the number of required multiplications. Hence, Toom-\(k\) splits the input operands into \(k\) parts and reduces the number of multiplications from \(k^{2}\) to \(2k-1\). That is, Toom-2.5 requires four evaluation points (i.e., four submultiplications) whereas Toom-3 requires five. Theoretically, a higher value of \(k\) yields lower time complexity in classical computers, which corresponds to lower circuit depth in quantum computation [34; 35]. However, since there is overhead from the suboperations apart from the multiplications itself, Toom-Cook multiplication will give faster runtime when \(n\) is sufficiently large [33].  
Toom-Cook, along with other fast multiplication method such as Karatsuba, is often used in a recursive manner [33], creating a tree structure. As an example, the fully recursive implementation of Toom-3 is as shown in Figure 1, where \(T\) denotes the Toom-3 multiplication, \(n\) represents the bit length for each level, and \(N\) indicates the total depth of the tree. Executing the full recursive multiplication (i.e., until the last branch, \(n=1\)) gives better time complexity but suffers from a much larger space usage. Since naive multiplication is more space efficient [8], for a balanced performance between space and time, one may select a crossover point in which the recursive call will halt and the naive multiplication will be used [13], in which the point is denoted as \(k\) in the figure.  
Note that in the case of quantum, the computation is not as straightforward and the resource counts can be higher since we need to deal with quantum-related property of the circuit, such as reversibility, which requires performing uncomputation to clear up garbage outputs, i.e., outputs that are neither one of the primary inputs nor a useful output but must exist in the quantum circuit to preserve reversibility [22]. Hence, resource consumption in quantum computation tends to be higher than the classical counterparts.