Paper 2022/620

Synthesizing Quantum Circuits of AES with Lower T-depth and Less Qubits

Zhenyu Huang, SKLOIS, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Siwei Sun, School of Cryptology, University of Chinese Academy of Sciences, Beijing, China, State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China

The significant progress in the development of quantum computers has made the study of cryptanalysis based on quantum computing an active topic. To accurately estimate the resources required to carry out quantum attacks, the involved quantum algorithms have to be synthesized into quantum circuits with basic quantum gates. In this work, we present several generic synthesis and optimization techniques for circuits implementing the quantum oracles of iterative symmetric-key ciphers that are commonly employed in quantum attacks based on Grover and Simon’s algorithms. Firstly, a general structure for implementing the round functions of block ciphers in-place is proposed. Then, we present some novel techniques for synthesizing efficient quantum circuits of linear and non-linear cryptographic building blocks. We apply these techniques to AES and systematically investigate the strategies for depth-width trade-offs. Along the way, we derive a quantum circuit for the AES S-box with provably minimal T-depth based on some new observations on its classical circuit. As a result, the T-depth and width (number of qubits) required for implementing the quantum circuits of AES are significantly reduced. Compared with the circuit proposed in EUROCRYPT 2020, the T-depth is reduced from 60 to 40 without increasing the width or 30 with a slight increase in width. These circuits are fully implemented in Microsoft Q# and the source code is publicly available. Compared with the circuit proposed in ASIACRYPT 2020, the width of one of our circuits is reduced from 512 to 371, and the Toffoli-depth is reduced from 2016 to 1558 at the same time. Actually, we can reduce the width to 270 at the cost of increased depth. Moreover, a full spectrum of depth-width trade-offs is provided, setting new records for the synthesis and optimization of quantum circuits of AES.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Quantum Circuit T-depth Grover’s Algorithm AES
Contact author(s)
huangzhenyu @ iie ac cn
sunsiwei @ ucas ac cn
2022-09-14: last of 2 revisions
2022-05-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhenyu Huang and Siwei Sun},
      title = {Synthesizing Quantum Circuits of AES with Lower T-depth and Less Qubits},
      howpublished = {Cryptology ePrint Archive, Paper 2022/620},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.