# Quantum Implementation of AIM: Aiming for Low-Depth
## 3 Quantum Circuit Implementation of AIM
### LinearLayer  
In the LinearLayer operation, either four (for AIM-I and -III) or six (for AIM-V) matrix-vector multiplications are performed. The binary matrices of sizes \(128\times 128\), \(192\times 192\), and \(256\times 256\) for AIM-I, -III, and -V, respectively, are generated using the hash values (SHAKE-128 for AIM-I, and SHAKE-256 for AIM-III and -V). The output of Mer is used as the input vector, and it is multiplied by the binary matrices. Since the initial vector (input of hash) is public, these binary matrices are constant. Therefore, the matrix-vector multiplication corresponds to a classical-quantum (matrix-vector) implementation that does not require a SHAKE-128 or SHAKE-256 quantum circuit. In other words, a quantum circuit for this matrix-vector multiplication can be efficiently designed using the classical values of the generated matrices. We adopt a naive approach for the quantum circuit implementation of matrix-vector multiplication, rather than the PLU decomposition. An in-place implementation based on PLU decomposition increases the depth due to the execution of CNOT gates in limited space (fewer qubits) without using additional qubits. On the other hand, we allocate a new 128, 192, or 256-qubit output vector (AIM-I, -III, and -V, respectively) and perform CNOT gates between the input vector and output vector where the value of the matrix is 1. This method (out-of-place) requires additional qubits, but the depth decreases due to \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Component** & **\#CNOT** & **\#1 qCliff** & **\#T** & **\(T\)-Depth *** & **\#Qubit** & **Full Depth** \\ \hline \(\text{\small Mer}(3)\) & 68,636 & 8748 & 30,618 & 8 & 8882 & 411 \\ \(\text{\small Mer}(27)\) & 226,224 & 26,244 & 91,854 & 16 & 13,840 & 2488 \\ \(\text{\small Mer}(5)\) & 115,385 & 13,122 & 45,927 & 12 & 6957 & 678 \\ \(\text{\small Mer}(29)\) & 780,375 & 91,854 & 321,489 & 32 & 67,005 & 6547 \\ \(\text{\small Mer}(53)\) & 1,037,702 & 118,098 & 413,343 & 32 & 86,833 & 14,482 \\ \hline \hline \end{tabular}  
* **: Toffoli depth one has a 7-depth of four.**  
\end{table} 
Table 3: Quantum resources required for the Mer of AIM-I. the execution of CNOT gates in the increased space. Actually, opting for the out-of-place method, which allocates output qubits rather than the in-place method where the input is transformed into the output, represents our design philosophy. ```
1:\(x^{2^{2}-1}(x3)\)
2:\(x^{2^{2}-1}\),ancilla //Compute Mer(27) //Copy \(x3\) to \(x4\)
3:\(x4\leftarrow\)allocate new 128 qubits
4:\(\text{CNOT128($x3$, $x4$)}\)
5:\(//x^{2^{6}-1}\)
6:for\(i=0\) to \(2\)do
7:\(x4\leftarrow\)Squaring(\(x4\))
8:endfor
9:\(x5\leftarrow\)Mul(\(x3\), \(x4\),ancilla)
10:\(x5\leftarrow\)Reduction(\(x5\))
11:\(ancilla\leftarrow\)CleanAncilla(\(x3\), \(x4\),ancilla) //Copy \(x5\) to \(x6\)
12:\(x6\leftarrow\)allocate new 128 qubits
13:endfor
14:\(x7\leftarrow\)Mul(\(x5\), \(x6\),ancilla)
15:\(x7\leftarrow\)Reduction(\(x7\))
16:\(ancilla\leftarrow\)CleanAncilla(\(x5\), \(x6\),ancilla) //Copy \(x7\) to \(x8\)
17:\(x8\leftarrow\)allocate new 128 qubits
18:\(\text{CNOT128($x7$, $x8$)}\)
19:\(/x^{2^{4}-1}\)
20:for\(i=0\) to \(11\)do
21:\(x8\leftarrow\)Squaring(\(x8\))
22:endfor
23:\(x9\leftarrow\)Mul(\(x7\), \(x8\),ancilla)
24:\(x9\leftarrow\)Reduction(\(x9\))
25:\(ancilla\leftarrow\)CleanAncilla(\(x7\), \(x8\),ancilla) //\(/x^{2^{27}-1}\)
26:for\(i=0\) to \(2\)do
27:\(x9\leftarrow\)Squaring(\(x9\))
28:endfor
29:\(out\leftarrow\)Mul(\(x3\), \(x9\),ancilla)
30:\(out\leftarrow\)Reduction(\(out\))
31:\(ancilla\leftarrow\)CleanAncilla(\(x3\), \(x9\),ancilla)
```  
**Algorithm 2** Quantum circuit implementation of Mer(27). One more thing to note is that for the last matrix-vector multiplication, instead of allocating a new output vector, we use the final output vector from the previous matrix-vector multiplication. This implementation is possible due to the XOR operations between the resulting vectors after the LinearLayer is performed.