Paper 2023/146

Optimized Quantum Implementation of AES

Abstract

This work researches the implementation of the AES family with Pauli-X gates, CNOT gates and Toffoli gates as the underlying quantum logic gate set. First, the properties of quantum circuits are investigated, as well as the influence of Pauli-X gates, CNOT gates and Toffoli gates on the performance of the circuits constructed with those gates. Based on these properties and the observations on the hardware circuits built by Boyar \emph{et al.} and Zou \emph{et al.}, it is possible to construct quantum circuits for AES's Substitution-box (S-box) and its inverse (S-box$^{-1}$) by rearranging the classical implementation to three parts. Since the second part is treated as a 4-bit S-box in this paper and can be dealt with by existing tools, a heuristic is proposed to search optimized quantum circuits for the first and the third parts. In addition, considering the number of parallelly executed S-boxes, the trade-offs between the qubit consumption and $T\cdot M$ values for the round function and key schedule of AES are studied. As a result, quantum circuits of AES-128, AES-192 and AES-256 can be constructed with 269, 333 and 397 qubits, respectively. If more qubits are allowed, quantum circuits that outperform state-of-the-art schemes in the metric of $T\cdot M$ value for the AES family can be reported, and it needs only 474, 538 and 602 qubits for AES-128, AES-192 and AES-256, respectively.