# Quantum Circuit Design of Toom 3-Way Multiplication
## 3 Proposed Method
### Quantum Circuit for Toom 3-Way Multiplication  
The high-level picture of the resulting quantum circuit is as illustrated in Figure 2. Similar to that of the classical circuit, the overall steps consist of splitting, evaluation of points, point-wise multiplication, interpolation, and recomposition. In the figures, each line corresponds to a quantum register with size displayed as subscripts of ket notation at the left side of the circuit. Meanwhile, the symbols inside the ket represent the input quantum state of each step. Additionally, the red triangles at each function blocks indicate the input and output of each corresponding operation. Specifically, triangles at the left of a block show where the input enters and triangles at the right side show where the output resides. Note that the ancillary registers are not shown for simplicity. For the sake of clarity, we break down the circuit for each part, as presented in Figures 3-6. Next, the point-wise multiplication is illustrated in Figure 5. Similar to the previous step, the submultiplication operations are also performed in parallel. This part is the core of a Toom-Cook multiplication circuit, which gives the advantage of reducing the depth of multiplication compared to the naive method. Subsequently, interpolation step is as illustrated in Figure 6.  
The outcomes of interpolation, i.e., A, B, C, D, E, are that each has the size of \(\frac{2n}{3}\)-bit. As for the recomposition (i.e., the final step), it essentially combines the interpolation results to yield the final result. Naively, it requires four \(\frac{2n}{3}\)-bit addition circuits. However, for those digits, the addition overlaps each other by \(\frac{n}{3}\) bits. We find that instead of performing a series of additions as described above, we can realign the intermediate output, resulting in two \(2n\)-bit numbers. That is, A, C, and E can be concatenated since they do not overlap each other; the case is similar for B and D. This method reduces the number of adder circuits to only one \(2n\)-bit adder, which in our calculation, is more efficient. Precisely, taking one \(n\)-bit adder's cost of \(2n\) for both Toffoli depth and count [8,11], the cost of four \(\frac{2n}{3}\)-bit additions are \(\frac{16}{3}n\) whereas it is only \(4n\) for one \(2n\)-bit adder. Figure 5: Quantum Circuit for Multiplication Part. Figure 6: Quantum Circuit for Interpolation Part. Circuit Components  
In general, six underlying operations are required for implementing the quantum Toom 3-way multiplication: copy, addition, subtraction, doubling/halving, division, and the underlying multiplication itself. Copy block is realized through a series of CNOT gates, targeting a series of \"fresh\" qubits initialized in state in \(|0\rangle\). These operations are required since once the quantum states are consumed, they cannot be used by other operations. Addition can be realized through any available addition circuit; in our case we choose the ripple-carry adder proposed by [PERSON] et al. [29]. One can use other existing adder variants, either another binary arithmetic-based adder such as proposed by [PERSON] et al. [36] or the Fourier-based arithmetic utilizing a set of rotation gates such as proposed by [PERSON] et al. [37]. Subsequently, subtraction is performed simply by the reversed adder (for the binary arithmetic approach) or by the corresponding inverse circuit (for Fourier-based circuit). Regarding the doubling and halving, they are used to efficiently realize multiplication or division by 2, similar to that in classical circuit. In quantum computing, they can be achieved quite easily and efficiently by a cyclic qubit shifts through a series of qubit swappings, either using CNOT gates [27] or via qubit relabeling [38; 39]. Additionally, since binary arithmetic is used in this paper, the radix or word size \(j\) is fixed to \(n/3\) rather than varying as previously shown in Equation (2).