# Quantum Implementation of AIM: Aiming for Low-Depth
## 3 Quantum Circuit Implementation of AIM
### Binary Field Multiplication and Squaring  
The component that requires the most quantum resources in the quantum circuit implementation of AIM is \(\text{Mer}(e)\). \(\text{Mer}(e)\) computes the exponentiation \(x^{2^{e}-1}\) on a binary field, so quantum circuits of binary multiplication and squaring are required for quantum implementation. We adopt the method in [23] for implementing quantum binary multiplication in \(\text{Mer}(e)\). In short, the authors of [23] employ the Karatsuba algorithm to implement quantum multiplication. They apply the Karatsuba algorithm recursively until the size of the divided multiplications is \(1\times 1\). The key approach they use is to prepare all operands for multiplications in advance by allocating additional ancilla qubits. As a result, all multiplications are executed simultaneously. This multiplication method has a Toffoli depth of 1 for arbitrary field sizes by generating all products in parallel and has the lowest full depth compared to other binary multiplication techniques. A disadvantage of the quantum binary multiplication in [23] is that it requires many ancilla qubits. However, we note that the burden of qubit allocation can be reduced by reusing the ancilla qubits used in the previous multiplication when the multiplication is not stand-alone (Section 3.3 in [23]). Since \(\text{Mer}(e)\) is composed of multiple multiplications (i.e., not stand-alone), we can effectively reduce the burden on qubit count while reducing the depth of the multiplication. To be specific, in \(\text{Mer}(e)\), we reuse ancilla qubits from the initial multiplication in subsequent multiplications. Table 1 shows the quantum resources required for quantum multiplication of binary fields \(\mathbb{F}_{2^{128}}/(x^{128}+x^{7}+x^{2}+x+1)\), \(\mathbb{F}_{2^{192}}/(x^{192}+x^{7}+x^{2}+x+1)\), and \(\mathbb{F}_{2^{26}}/(x^{256}+x^{1}0+x^{5}+x^{2}+1)\) (defined binary fields in AIM-I, -III, and -V, respectively) using the method in [23].  
Figure 1: Encryption process of AIM; \(e_{1}\), \(e_{2}\), \(e_{3}\), and \(e_{*}\) indicate the input values.  
As mentioned earlier, thanks to the reuse of ancilla qubits in the method presented in [23], we effectively reduce the number of qubits required for multiplications. Of the 6561, 15,309, and 19,683 qubits in Table 1, only 2443, 5387, and 7073 qubits are required for multiplications excluding the first multiplication in \(\mathsf{Mer}\), as 4118, 9922, and 12,610 of the ancilla qubits can be reused.  
While various methods to implement multiplication in quantum (and classical as well) are actively being investigated [23; 24; 25; 26], squaring has no room for optimization or improvement due to its inherent simplicity. The quantum implementation of squaring is simpler and less costly than that of multiplication, as in classical implementation. Squaring only requires modular reduction in the input to the squared result, without the need to generate product terms, so it can be implemented with only CNOT gates.  
Since modular reduction is a linear operation, an in-place implementation using PLU decomposition is possible. However, for simplicity, we implement modular reduction naively rather than using PLU decomposition. As a result, in addition to the input qubits, our squaring quantum circuit requires a few ancilla qubits (3 or 5) for temp values. Actually, this increase in the number of qubits is negligible in our implementation, which already uses many ancilla qubits. The required quantum resources for the squaring quantum circuit of \(\mathbb{F}_{2^{128}}/\left(x^{128}+x^{7}+x^{2}+x+1\right)\), \(\mathbb{F}_{2^{192}}/\left(x^{192}+x^{7}+x^{2}+x+1\right)\), and \(\mathbb{F}_{2^{26}}/\left(x^{256}+x^{10}+x^{5}+x^{2}+1\right)\) are shown in Table 2.