# Quantum Circuit Design of Toom 3-Way Multiplication
## 2 Related Work  
### Multiplication Methods in Quantum Computation  
Proposed multiplication methods in early quantum computation are mostly focused on the specific use in [PERSON]'s algorithm for factoring problem (i.e., that can be used for breaking the RSA cryptosystem). In that case, the aim is to build an efficient circuit that performs the modular exponentiation function \(|x\rangle\rightarrow|a^{x}\bmod N\rangle\), which essentially can be achieved by a sequence of modular multiplications. Additionally, the random value \(a\) and the modulus \(N\) are predetermined before running the algorithm, which translates to an exact sequence of underlying multiplication circuits. Hence, former methods mainly perform a multiplication by constant in a modular arithmetic fashion, requiring only one quantum input, such as [2,6,7]. Then, newer proposals offer more enhanced techniques by leveraging the specific property the constant to yield a more optimal circuit such as [4,5,24]. On the other hand, general multiplication with two quantum inputs (sometimes referred to as quantum-quantum multiplication [4]) have not been widely addressed. Just after the other variant of [PERSON]'s algorithm, i.e., for the elliptic curve discrete logarithm problem (ECDLP) that can crack the ECC cryptosystem, started to explicitly materialize in the literature by [PERSON] and [PERSON] [26], the need for quantum-quantum multiplier started to gain attention. The classically-inspired double-and-add method as first proposed in [26] becomes one of the earliest designs for such circuit. Later, the design is explicitly constructed by [PERSON] et al. [27], who also proposed their own multiplication method based on Montgomery multiplication. In [28], [PERSON] et al. improved the work of [27] to use a windowing approach and adaptive uncomputation placement to lower the overall depth of the elliptic curve scalar multiplication circuit. However, note that the multiplications for [PERSON]'s algorithm employ a modular arithmetic approach, which has slightly different characteristics compared to the nonmodular one. In terms of the nonmodular approach, the authors of [8] illustrated the standard case of two-inputs quantum multiplication using controlled addition circuit based on the popular Cuccaro adder [29], which scales to \(O(n^{2})\) in both Toffoli depth and size and scales linearly in space (i.e., qubit count) for \(n\)-bit operands. Earlier, [PERSON] et al. [13] provided the description of Karatsuba multiplication circuit whose main aim is for a classical reversible computation, but the authors also mentioned their secondary motivation, that is for possible implementation in quantum computers. Additionally, they analyzed four versions of Karatsuba algorithm based on the position of multiplication gates and the garbage disposal scheme. Their analysis shows that among the analyzed version, parallel multiplication approach using [PERSON]'s first scheme for garbage disposal gives the lower complexity: \(O(n)\) for time (depth), and \(O(n^{log_{2}3})\) for both space (qubit count) and gate size. Later, [PERSON] et al. [8] proposed their Karatsuba algorithm approach for quantum computation, which yields a lower cost depth and space compared to that of [13]. This is achieved by analyzing the method called the reversible pebble games to determine the most efficient number of recursion, which eventually yields a lower complexity: \(O(n^{1.158})\) and \(O(n^{1.427})\) for depth and space, respectively. Additionally, the author of [30] extends the reversible Karatsuba for binary finite fields. Following a similar analysis approach to [8], [PERSON] et al. [11] described the quantum circuit for Toom-Cook multiplication method, which is the generalization of Karatsuba algorithm and classically gives a lower complexity. Instead of leveraging Toom 3-way multiplication as the more commonly used algorithm, they proposed a quantum circuit for Toom 2.5-way to avoid division circuit.