# Quantum Implementation of AIM: Aiming for Low-Depth
## 3 Quantum Circuit Implementation of AIM
### Mer  
Now that we have the necessary building blocks (multiplication and squaring), we can proceed with implementing the quantum circuit of Mer. As noted earlier, for the purpose of describing the quantum circuit of Mer, we primarily focus on the variant AIM-I, which consists of \(\mathsf{Mer}(3)\), \((27)\) (before LinearLayer), and \((5)\) (after LinearLayer).  
Algorithm 1 describes the quantum circuit implementation of \(\mathsf{Mer}(3)\). The notation CNOT128 of Algorithm 1 means the operation of CNOT gates for 128-qubit arrays. In the quantum implementation of \(\mathsf{Mer}(3)\), multiple (Mul, Reduction), and Squaring operations are performed. Additionally, \(\mathsf{CleanAncilla}\) initializes the ancilla qubits used in multiplication (4118) without significant overhead (overhead related to reuse is discussed in Section 3.3 of [23]). These initialized ancilla qubits are reused in subsequent multiplications.  
To optimize the quantum circuit of Mer, we combine \(\mathsf{Mer}(3)\) and \(\mathsf{Mer}(27)\) (before LinearLayer. \(\mathsf{Mer}(3)\) and \(\mathsf{Mer}(27)\) use the same input, and as there is a duplicated intermediate value between them, we utilize it. Algorithm 1 (\(\mathsf{Mer}(3)\)) copies the output right before finishing (lines 12 and 13) because the same value is used in \(\mathsf{Mer}(27)\). That is, instead of using multiplication and squaring to generate the same value in \(\mathsf{Mer}(27)\), we use a copy of the output from \(\mathsf{Mer}(3)\) as the input for \(\mathsf{Mer}(27)\) and continue with subsequent operations. As we can observe in Algorithm 2, the output of \(\mathsf{Mer}(3)\) is used as an input for \(\mathsf{Mer}(27)\). Thanks to this efficient sharing, we can conserve the quantum resources required for certain multiplications and squarings.  
Unsurprisingly, this method of efficient sharing is also applicable to AIM-III and AIM-V. Note that \(\mathsf{Mer}(5)\) (after LinearLayer) is implemented using the same mechanism as \(\mathsf{Mer}(3)\) and \(\mathsf{Mer}(27)\), but the sharing method is impossible due to the input being different. We omit the explanation of implementation for other variants (AIM-III and AIM-V) in this paper, but report the required quantum resources. Table 3 shows the quantum resources required for the quantum circuit implementations of \(\mathsf{Mers}\).  
```
1:\(x\)
2:\(x^{2^{3}-1}\), \(x^{2^{3}-1}\)(copy), \(ancilla\)
3://Allocate ancilla qubits for Mul
4:\(ancilla\leftarrow\) allocate 4118 qubits
5://Compute \(\text{\small Mer}(3)\)
6://Copy \(x\) to \(x1\)
7:\(x1\leftarrow\) allocate new 128 qubits
8:\(\text{\small CNOT}128(x,x1)\)
9:\(/x^{2^{2}-1}\)
10:\(x1\leftarrow\text{\small Squaring}(x1)\)
11:\(x2\leftarrow\text{\small Mul}(x,x1,ancilla)\)
12:\(x2\leftarrow\text{\small Reduction}(x2)\)
13:\(ancilla\leftarrow\text{\small CleanAncilla}(x,x1,ancilla)\)
14:\(/x^{2^{3}-1}\)
15:\(x2\leftarrow\text{\small Squaring}(x2)\)
16:\(out\leftarrow\text{\small Mul}(x,x2,ancilla)\)
17:\(out\leftarrow\text{\small Reduction}(out)\)
18:\(ancilla\leftarrow\text{\small CleanAncilla}(x,x2,ancilla)\)
```  
//Copy \(out\) to \(x3\) for Mer (27)
19:\(x3\leftarrow\) allocate new 128-qubit
20:\(\text{\small CNOT}128(out,x3)\)
21:return\(out\), \(x3\), \(ancilla\) ```
**Algorithm 1** Quantum circuit implementation of Mer(3).