Quantum Information & Computation
Volume 25, Issue 6
RESEARCH ARTICLE Open access

Optimal T-depth Quantum Circuits for Implementing Arbitrary Boolean Functions

Suman Dutta, Anik Basu Bhaumik, Anupam Chattopadhyay, Subhamoy Maitra

Author affiliations
  • Suman Dutta1
  • Anik Basu Bhaumik2
  • Anupam Chattopadhyay2
  • Subhamoy Maitra1
  1. Applied Statistics Unit, Indian Statistical Institute, Kolkata, West Bengal, India
  2. College of Computing and Data Science, Nanyang Technological University, Singapore, Singapore

pp. 586-597 · 10.2478/qic-2025-0032

Read PDF View on Reference Global
On this page

Abstract

In this paper, we present a generic construction for synthesizing an optimal T-depth quantum circuit for any arbitrary n -input, m -output Boolean function f: {0, 1 }n → {0, 1}m with algebraic degree k ≤ n, achieving an exact Toffoli (consequently T) depth of ⌈log2 k ⌉. This broadly generalizes the recent result establishing the optimal Toffoli (and T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). The optimality of T-depth in this initiative is considered in the context of implementing an n -MCT, assuming the decomposition via Clifford plus Toffoli gates. The key technique involves inspecting the Algebraic Normal Form (ANF) of the Boolean function. Obtaining a benchmark for the minimum T-depth of such circuits is crucial for the efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The broader implications of our results include a provable lower bounds on T-depth for S-box and block cipher implementations, such as AES. Finally, we also explain the impact of our result in identifying the T-depth for the generic cryptanalysis of block ciphers using Grover’s algorithm.
Open accessCC BY-NC-ND 4.0

Keywords

  • AES
  • block cipher
  • Boolean function
  • cryptanalysis
  • efficient circuit implementation
  • S-box synthesis
  • T-depth
  • universal gate sets

Suggested citation

Suman Dutta, Anik Basu Bhaumik, Anupam Chattopadhyay, Subhamoy Maitra (2025). Optimal T-depth Quantum Circuits for Implementing Arbitrary Boolean Functions. Quantum Information & Computation, 25(6), 586-597. https://doi.org/10.2478/qic-2025-0032

Download BibTeX

References (31)

  1. R. P. Feynman (1986). Quantum mechanical computers. Foundations of Physics, 16, pp. 507–531.DOI: 10.1007/BF01886518Google Scholar
  2. D. Deutsch and R. Jozsa (1992). Rapid solution of problems by quantum computation, Proceedings of the Royal Society A: Mathematical. Physical and Engineering Sciences, 439 (1907), pp. 553–558.DOI: 10.1098/rspa.1992.0167Google Scholar
  3. L. K. Grover (1996). A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), pp. 212–219.DOI: 10.1145/237814.237866Google Scholar
  4. D. R. Simon (1997). On the power of quantum computation, SIAM Journal on Computing, 26(5), pp. 1474–1483.DOI: 10.1137/S0097539796298637Google Scholar
  5. P. W. Shor (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), pp. 1484–1509.DOI: 10.1137/S0097539795293172Google Scholar
  6. C. Jones (2013). Low-overhead constructions for the fault-tolerant Toffoli gate. Phys. Rev. A, 87(2), 022328.DOI: 10.1103/PhysRevA.87.022328Google Scholar
  7. S. Bravyi and A. Kitaev (2005). Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71(2), 022316.DOI: 10.1103/PhysRevA.71.022316Google Scholar
  8. P. Selinger (2013). Quantum circuits of T-depth one. Phys. Rev. A, 87(4), 042302.DOI: 10.1103/PhysRevA.87.042302Google Scholar
  9. M. Amy, D. Maslov, M. Mosca and M. Roetteler (2013). A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32(6), pp. 818–830.DOI: 10.1109/TCAD.2013.2244643Google Scholar
  10. C. Gidney and M. Ekera (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433.DOI: 10.22331/q-2021-04-15-433Google Scholar
  11. C. Gidney (2025). How to factor 2048 bit RSA integers with less than a million noisy qubits, arXiv: 2505.15917.Google Scholar
  12. S. Dutta, S. Wang, A. Baksi, A. Chattopadhyay and S. Maitra (2025). Exact space-depth trade-offs in multicontrolled Toffoli decomposition, Phys. Rev. A, 111, 052611.DOI: 10.1103/PhysRevA.111.052611Google Scholar
  13. S. Jaques, M. Naehrig, M. Roetteler and F. Virdia (2020). Implementing Grover oracles for quantum key search on AES and LowMC, Advances in Cryptology – EUROCRYPT 2020. LNCS, vol. 12106, pp. 280–310.DOI: 10.1007/978-3-030-45724-2_10Google Scholar
  14. Z. Huang and S. Sun (2022). Synthesizing quantum circuits of AES with lower T-depth and less qubits, Advances in Cryptology – ASIACRYPT 2022. LNCS, vol. 13793, pp. 614–644.DOI: 10.1007/978-3-031-22969-5_21Google Scholar
  15. Q. Liu, B. Preneel, Z. Zhao and M. Wang (2023). Improved quantum circuits for AES: reducing the depth and the number of qubits, Advances in Cryptology – ASIACRYPT 2023. LNCS, vol. 14440, pp. 67–98.DOI: 10.1007/978-981-99-8727-6_3Google Scholar
  16. M. Zhang, T. Shi, W. Wu and H. Sui (2024). Optimized quantum circuit of AES with interlacing-uncompute structure. IEEE Transactions on Computers, vol. 73, no. 11, pp. 2563–2575.DOI: 10.1109/TC.2024.3449094Google Scholar
  17. H. Shi and X. Feng (2024). Quantum circuits of AES with a low-depth linear layer and a new structure, Advances in Cryptology – ASIACRYPT 2024. LNCS, vol. 15491, pp. 358–395.DOI: 10.1007/978-981-96-0944-4_12Google Scholar
  18. Z. Huang, F. Zhang and D. Lin (2025). Constructing quantum implementations with the minimal T-depth or minimal width and their applications, Advances in Cryptology – EUROCRYPT 2025. LNCS, vol. 15601, pp. 155–185.DOI: 10.1007/978-3-031-91107-1_6Google Scholar
  19. K. Jang, A. Baksi, H. Kim, G. Song, H. Seo and A. Chattopadhyay (2025). Quantum analysis of AES, IACR Communications in Cryptology, 2(1).DOI: 10.62056/ay11zo-3yGoogle Scholar
  20. C. Gidney (2018). Halving the cost of quantum addition. Quantum, 2, pp. 74–79.DOI: 10.22331/q-2018-06-18-74Google Scholar
  21. C. Gidney and A. G. Fowler (2019). Flexible layout of surface code computations using autoCCZ states, arXiv: 1905.08916.Google Scholar
  22. M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen and M. Zohner (2015). Ciphers for MPC and FHE, Advances in Cryptology – EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454.DOI: 10.1007/978-3-662-46800-5_17Google Scholar
  23. A. Baksi, S. Bhasin, J. Breier, M. Khairallah, T. Peyrin, S. Sarkar and S. M. Sim (2021). DEFAULT: cipher level resistance against differential fault attack, Advances in Cryptology – ASIACRYPT 2021. LNCS, vol. 13091, pp. 124–156.DOI: 10.1007/978-3-030-92075-3_5Google Scholar
  24. S. Banik, S. K. Pandey, T. Peyrin, Y. Sasaki, S. M. Sim and Y. Todo (2017). GIFT: a small present, CHES 2017. LNCS, vol. 10529, pp. 321–345.DOI: 10.1007/978-3-319-66787-4_16Google Scholar
  25. A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, et al. (2007). PRESENT: an ultra-lightweight block cipher, CHES 2007. LNCS, vol. 4727, pp. 450–466.DOI: 10.1007/978-3-540-74735-2_31Google Scholar
  26. J. Borghoff, A. Canteaut, T. Güneysu, E. B. Kavun, M. Knezevic, L. R. Knudsen, et al. (2012). PRINCE – a low-latency block cipher for pervasive computing applications, Advances in Cryptology – ASIACRYPT 2012. LNCS, vol. 7658, pp. 208–225.DOI: 10.1007/978-3-642-34961-4_14Google Scholar
  27. C. Dobraunig, M. Eichlseder, F. Mendel and M. Schläffer (2021). Ascon v1.2: lightweight authenticated encryption and hashing. J Cryptol, 34, 33.DOI: 10.1007/s00145-021-09398-9Google Scholar
  28. J. Daemen and V. Rijmen (2002). The design of Rijndael, Springer, Information Security and Cryptography.DOI: 10.1007/978-3-662-04722-4Google Scholar
  29. Y. Yuan, W. Wu, T. Shi, L. Zhang and Y. Zhang (2024). A framework to improve the implementations of linear layers, IACR Transactions on Symmetric Cryptology, 2024(2), pp. 322–347.DOI: 10.46586/tosc.v2024.i2.322-347Google Scholar
  30. T. Häner and M. Soeken (2022). Lowering the T-depth of quantum circuits via logic network optimization. ACM Transactions on Quantum Computing, 3(2), art. no. 6, pp. 1–15.DOI: 10.1145/3501334Google Scholar
  31. G. Leander and A. May (2017). Grover meets Simon – quantumly attacking the FX-construction, Advances in Cryptology – ASIACRYPT 2017. LNCS, vol. 10625, pp. 161–178.DOI: 10.1007/978-3-319-70697-9_6Google Scholar