# Quantum Implementation of AIM: Aiming for Low-Depth
## 4 Post-Quantum Security Evaluation of AIM  
In this section, we discuss the post-quantum security of AIM. In a nutshell, we estimate the cost of [PERSON]'s key search for AIM and compare the cost with the costs of [PERSON]'s key search for AES variants. The costs for the AES variants we use to evaluate post-quantum security are NIST estimates [10; 11]. These estimates draw from the work of [PERSON] et al. [16] and [PERSON] et al. [14]. Additionally, we also consider the work of [PERSON] et al. [13], which currently provides the lowest cost for evaluation (since the estimates of [11] based on [14] are lower bound). As explained in Section 2.1, [PERSON]'s key search for a cipher using a \(k\)-bit key involves approximately \(\sqrt{2^{k}}\) iterations of Grover oracle and diffusion operator. Tight analysis of the [PERSON] search algorithm [27] suggests that the optimal number of iterations is \(\lfloor\frac{\pi}{4}\sqrt{2^{k}}\rfloor\), and we estimate the cost based on this. When estimating the cost of [PERSON]'s key search, we ignore the diffusion operator, as its overhead can be considered negligible (as is performed in most related studies [13; 14]). Therefore, we estimate the cost based only on the oracle. The Grover oracle consists of the AIM quantum circuit for encryption, an \(n\)-controlled NOT gate (\(n\) is the ciphertext size) for comparing the ciphertext (with known ciphertext), and the reverse operation of the previously executed AIM quantum circuit for the next iteration. The \(n\)-controlled NOT gate is estimated to be \((32\cdot n-64)\)\(T\) gates using the \begin{table}
\begin{tabular}{c c c c} \hline \hline
**LinearLayer** & **\#CNOT** & **\#Qubit** & **Full Depth** \\ \hline AIM-I (\(n=128\)) & 16,889 & 640 & 426 \\ AIM-III (\(n=192\)) & 37,657 & 960 & 632 \\ AIM-V (\(n=256\)) & 99,352 & 1792 & 1015 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Quantum resources required for the LinearLayer of AIM. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Cipher** & **\#CNOT** & **\#1 qCliff** & **\#T** & **T-Depth * & **\#Qubit** & **Full Depth** & \(\mathbf{TD\times M}\) & \(\mathbf{FD\times M}\) \\ \hline AIM-I & 358,754 & 39,430 & 137,781 & 36 & 25,299 & 3499 & 227,691 & 88,521,201 \\ AIM-III & 1,144,536 & 132,785 & 464,373 & 48 & 88,395 & 8583 & 1,060,740 & 758,694,285 \\ AIM-V & 1,486,100 & 157,588 & 551,124 & 44 & 108,072 & 16,857 & 1,188,792 & 1,821,769,704 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Quantum resources required for the AIM quantum circuits. decomposition method in [28]. Thus, the cost of [PERSON]'s key search for AIM is estimated as \(\lfloor\frac{\pi}{4}\sqrt{2^{k}}\rfloor\times(32\cdot 128-64)\)\(T\) gates \(+\lfloor\frac{\pi}{4}\sqrt{2^{k}}\rfloor\times(2\times A_{cost})\) where \(A_{cost}\) indicates cost of AIM. Since the iterations are sequential, the number of qubits does not increase from Table 5, but only one decision qubit to check the ciphertext (with known ciphertext) is added. Table 6 shows the costs of [PERSON]'s key search for AIM. In addition, we include the metrics \(TD^{2}\times M\) and \(FD^{2}\times M\) in Table 6. [PERSON]'s key search suffers from extreme depth, making it difficult to execute. Therefore, performing a parallel search to reduce the depth is more practical. However, the efficiency of parallelizing [PERSON]'s search is very poor (see Section 2.3). The reason is that to reduce the depth by \(S\), \(S^{2}\) [PERSON] instances must be executed in parallel [14; 20], resulting in a qubit count increase in \(S\). Therefore, when considering parallel search, the metrics that need to be optimized are \(TD^{2}\times M\) and \(FD^{2}\times M\). This is why minimizing the depth is clearly advantageous for quantum circuits of target ciphers for [PERSON]'s key search. We compare [PERSON]'s key search cost for AES variants to evaluate the post-quantum security of AIM. Table 7 provides a birds-eye view of our discussion of post-quantum security for AIM.