Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IET Information Security

T‐depth reduction method for efficient SHA‐256 quantum circuit construction

Jongheon Lee, Sokjoon Lee, You-Seok Lee, Dooho Choi

Published Jun 28, 2022• 8 citations
Publisher

Abstract

Abstract To perform a quantum brute force attack on a cryptosystem based on Grover's algorithm, it is necessary to implement a quantum circuit of the cryptographic algorithm. Therefore, an efficient quantum circuit design of a given cryptographic algorithm is essential, especially in terms of quantum security analysis, and it is well known that T‐depth should be reduced for time complexity efficiency. In this paper, the authors propose a novel technique to reduce T‐depth (and T‐count) when some quantum circuits located in between two Toffoli‐gates are interchangeable with a controlled phase gate (CP gate), and the authors apply this technique to five types of quantum adders, reducing T‐depth by more than 33%. The authors also present new SHA‐256 quantum circuits which have a critical path with only three quantum adders while the critical paths of quantum circuits in the previous studies consist of seven or 10 quantum adders, and the authors also apply our technique to the proposed SHA‐256 quantum circuits. Four versions of SHA‐256 quantum circuit are presented. Among the previous results, T‐depth of the circuit with the smallest Width (the number of qubits) 801 was approximately 109,104. On the other hand, T‐depth of the proposed SHA‐256 quantum circuit with the Width 797 is 16,055, which is remarkably reduced by about 85%. Another proposed quantum circuit only requires 768 qubits, which is the smallest Width compared to the previous results to the best of our knowledge. Furthermore, one other version is the most time‐efficient circuit with an overall Toffoli‐depth (and T‐depth) that is less than 5000.

DOI
10.1049/ise2.12074

Related papers

Toffoli-depth reduction method preserving in-place quantum circuits and its application to SHA3-256

Jongheon Lee, Yousung Kang, You-Seok Lee +2 more

Abstract When implementing a quantum circuit for a desired reversible function, an attempt is made to design an accurate quantum circuit. Then, the quantum circuit is optimized based on a specific cost function, such as design cost, width (the number of qubits), depth, etc. In particular, if an in-place subcircuit itself can be optimized while maintaining its in-place property, it will be a very useful way to increase efficiency without changing the initial architecture of the entire quantum circuit. Furthermore, since its (clean) work qubits can easily be utilized in subsequent subroutines of the quantum circuit, it has an additional important advantage in terms of width. In this paper, for the first time to the best of our knowledge, we present a global Toffoli-depth reduction methodology for an in-place version reversible circuit in the case that the given input circuit is optimized with Toffoli-count. We mainly introduce a process to optimize the $$\chi $$ χ internal function block in SHA3-256 to explain our Toffoli-depth reduction approach preserving the in-place property, and hence, well-balanced five $$\chi $$ χ quantum circuits are induced in terms of its width and T-depth. And then, we apply these five $$\chi $$ χ circuits to design the entire SHA3-256 cryptosystem. One of the proposed SHA3-256 quantum circuits has a width of 1600 and a T-depth of 264, and this shows a result of 50% and 38.9% reduction compared to the previous circuit in terms of width and T-depth, respectively. Other versions of our SHA3-256 circuits just required 10–33 qubits per one T-depth compared to the previous results which require over 1800 qubits per T-depth, and so this means that our SHA3-256 circuits are well-balanced. Finally, we constructed Grover’s algorithm circuit using each version that realized SHA3-256. When output circuits for the presented method were used, quantum volume values of Grover’s algorithm circuits became 33 and 50 $$\%$$ % of the value when the input circuit was used.

Quantum Information Processing•Apr 18, 2024•6 citations

Grover on Scrypt

Gyeongju Song, Hwajeong Seo

This paper presents an optimized quantum circuit for the scrypt cryptographic algorithm. We applied various optimization techniques to reduce the DW cost, which is the product of the time and space complexity of quantum circuits. In our proposed method, the number of ancilla qubits was significantly reduced through the use of optimized inverse operations, while the depth was minimized by implementing parallel structures. For the SHA-256, we devised a structure that achieves a substantial reduction in the number of ancilla qubits with only a slight increase in quantum circuit depth. By cleaning the dirty ancilla qubits used in the previous round through inverse operations, we enabled their reuse in each subsequent round. Specifically, we reduced the number of 8128 ancilla qubits, achieving this with an increase of only 6 in the full depth of the quantum circuit. Additionally, within Salsa20/8 in SMix, we reused qubits through inverse operations and performed some operations in parallel to reduce both the number of qubits and the overall quantum circuit depth. Finally, our quantum circuit for scrypt demonstrates a significant reduction in the width (the number of qubits) with only a minimal increase in the full quantum circuit depth.

Electronics•Aug 10, 2024•1 citation

T-count optimization of approximate quantum Fourier transform

Byeongyong Park, Doyeol Ahn

The quantum Fourier transform (QFT) is a ubiquitous quantum operation that is used in numerous quantum computing applications. The major obstacle to constructing a QFT circuit is that numerous elementary gates are required. Among the elementary gates, T gates dominate the cost of fault-tolerant implementation. Currently, the smallest-known T-count required to construct an n-qubit QFT circuit approximated to error O(\varepsilon) is ~8nlog_2(n/\varepsilon). Moreover, the depth of T gates (T-depth) in the approximate QFT circuit is ~2nlog_2(n/\varepsilon). This approximate QFT circuit was constructed using Toffoli gates and quantum adders. In this study, we present a new n-qubit QFT circuit approximated to error O(\varepsilon). Our approximate QFT circuit shows a T-count of ~4nlog_2(n/\varepsilon) and a T-depth of ~nlog_2(n/\varepsilon). Toffoli gates, which account for half of the T-count in the approximate QFT circuit reported in the previous study, are unnecessary in our construction. Quantum adders, which dominate the leading order term of T-depth in our approximate QFT circuit, are arranged in parallel to reduce T-depth.

arXiv:2203.07739•Mar 15, 2022•1 citation

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

quant-pharXiv:2603.12917•Mar 16, 2026•0 citations

Constructing quantum circuits for Grover key search in MK-3 featuring 16-bit S-boxes

Haoyu Liao, Qing-bin Luo, Yuanmeng Zheng +2 more

Abstract Quantum computing poses a significant threat to modern cryptosystems, prompting nations to initiate the development of next-generation cryptographic algorithms where quantum security assessment constitutes a critical task. In this work, we present the first complete quantum attack circuit construction and security evaluation of quantum resistance for the authenticated encryption algorithm MK-3, which features 16-bit S-boxes. Firstly, we achieve breakthroughs in finite field arithmetic. The arrangement method of Toffoli gates in the subfield $$F_{2^4}$$ F 2 4 enables two types of optimized $$F_{2^8}$$ F 2 8 multiplication circuits to reduce DW-cost by at least 50%. For $$F_{2^8}$$ F 2 8 inversion, by proposing a new intermediate state uncomputing technique, the DW-cost of the inversion circuit is reduced by at least 40% compared with existing solutions. This can also be used to optimize the quantum circuits of block ciphers such as AES and SM4. Secondly, we propose three types of quantum circuits for MK-3’s 16-bit S-box. The basic circuit reduces multiplicative bit operations to 115, representing at least 20% reduction. We propose a more compact S-box structure, reducing the number of circuit qubits for two types of S-boxes from 52 to 40. Finally, we implement full-algorithm quantum attacks and conduct security evaluations for MK-3. Complete quantum circuits supporting 128-bit and 256-bit keys are constructed, enabling Grover key search attacks. Security assessments confirm the 128-bit version meets NIST Security Category 1 (with reasonable inference of achieving Category 2), while the 256-bit version satisfies the highest Category 5 standards, demonstrating resistance against large-scale quantum computing attacks. This work achieves the first quantum circuit implementation for 16-bit S-boxes and provides critical evaluation benchmarks for post-quantum cryptography standardization.

Cybersecurity•Jun 17, 2026•0 citations

Quantum Implementation and Analysis of SHA-2 and SHA-3

Kyungbae Jang, Sejin Lim, Yujin Oh +4 more

Quantum computers have the potential to solve a number of hard problems that are believed to be almost impossible to solve by classical computers. This observation has sparked a surge of research to apply quantum algorithms against the cryptographic systems to evaluate its quantum resistance. In assessing the security strength of the cryptographic algorithms against the upcoming quantum threats, it is crucial to precisely estimate the quantum resource requirement (generally in terms of circuit depth and quantum bit count). The National Institute of Standards and Technology by the US government specified five quantum security levels so that the relative quantum strength of a given cipher can be compared to the standard ones. There have been some progress in the NIST-specified quantum security levels for the odd levels (i.e., 1, 3 and 5), following the work of Jaques et al. (Eurocrypt’20). However, levels 2 and 4, which correspond to the quantum collision finding attacks for the SHA-2 and SHA-3 hash functions, quantum attack complexities are arguably not well-studied. This is where our article fits in. In this article, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.

IEEE Transactions on Emerging Topics in Computing•Mar 7, 2025•19 citations
Abstract To perform a quantum brute force attack on a cryptosystem based on Grover's algorithm, it is necessary to implement a quantum circuit of the cryptographic algorithm. Therefore, an efficient quantum circuit design of a given cryptographic algorithm is essential, especially in terms of quantum security analysis, and it is well known that T‐depth should be reduced for time complexity efficiency. In this paper, the authors propose a novel technique to reduce T‐depth (and T‐count) when some quantum circuits located in between two Toffoli‐gates are interchangeable with a controlled phase gate (CP gate), and the authors apply this technique to five types of quantum adders, reducing T‐depth by more than 33%. The authors also present new SHA‐256 quantum circuits which have a critical path with only three quantum adders while the critical paths of quantum circuits in the previous studies consist of seven or 10 quantum adders, and the authors also apply our technique to the proposed SHA‐256 quantum circuits. Four versions of SHA‐256 quantum circuit are presented. Among the previous results, T‐depth of the circuit with the smallest Width (the number of qubits) 801 was approximately 109,104. On the other hand, T‐depth of the proposed SHA‐256 quantum circuit with the Width 797 is 16,055, which is remarkably reduced by about 85%. Another proposed quantum circuit only requires 768 qubits, which is the smallest Width compared to the previous results to the best of our knowledge. Furthermore, one other version is the most time‐efficient circuit with an overall Toffoli‐depth (and T‐depth) that is less than 5000.
Abstract When implementing a quantum circuit for a desired reversible function, an attempt is made to design an accurate quantum circuit. Then, the quantum circuit is optimized based on a specific cost function, such as design cost, width (the number of qubits), depth, etc. In particular, if an in-place subcircuit itself can be optimized while maintaining its in-place property, it will be a very useful way to increase efficiency without changing the initial architecture of the entire quantum circuit. Furthermore, since its (clean) work qubits can easily be utilized in subsequent subroutines of the quantum circuit, it has an additional important advantage in terms of width. In this paper, for the first time to the best of our knowledge, we present a global Toffoli-depth reduction methodology for an in-place version reversible circuit in the case that the given input circuit is optimized with Toffoli-count. We mainly introduce a process to optimize the χ\chi χ χ internal function block in SHA3-256 to explain our Toffoli-depth reduction approach preserving the in-place property, and hence, well-balanced five χ\chi χ χ quantum circuits are induced in terms of its width and T-depth. And then, we apply these five χ\chi χ χ circuits to design the entire SHA3-256 cryptosystem. One of the proposed SHA3-256 quantum circuits has a width of 1600 and a T-depth of 264, and this shows a result of 50% and 38.9% reduction compared to the previous circuit in terms of width and T-depth, respectively. Other versions of our SHA3-256 circuits just required 10–33 qubits per one T-depth compared to the previous results which require over 1800 qubits per T-depth, and so this means that our SHA3-256 circuits are well-balanced. Finally, we constructed Grover’s algorithm circuit using each version that realized SHA3-256. When output circuits for the presented method were used, quantum volume values of Grover’s algorithm circuits became 33 and 50 %\%% % of the value when the input circuit was used.
This paper presents an optimized quantum circuit for the scrypt cryptographic algorithm. We applied various optimization techniques to reduce the DW cost, which is the product of the time and space complexity of quantum circuits. In our proposed method, the number of ancilla qubits was significantly reduced through the use of optimized inverse operations, while the depth was minimized by implementing parallel structures. For the SHA-256, we devised a structure that achieves a substantial reduction in the number of ancilla qubits with only a slight increase in quantum circuit depth. By cleaning the dirty ancilla qubits used in the previous round through inverse operations, we enabled their reuse in each subsequent round. Specifically, we reduced the number of 8128 ancilla qubits, achieving this with an increase of only 6 in the full depth of the quantum circuit. Additionally, within Salsa20/8 in SMix, we reused qubits through inverse operations and performed some operations in parallel to reduce both the number of qubits and the overall quantum circuit depth. Finally, our quantum circuit for scrypt demonstrates a significant reduction in the width (the number of qubits) with only a minimal increase in the full quantum circuit depth.
The quantum Fourier transform (QFT) is a ubiquitous quantum operation that is used in numerous quantum computing applications. The major obstacle to constructing a QFT circuit is that numerous elementary gates are required. Among the elementary gates, T gates dominate the cost of fault-tolerant implementation. Currently, the smallest-known T-count required to construct an n-qubit QFT circuit approximated to error O(\varepsilon) is ~8nlog_2(n/\varepsilon). Moreover, the depth of T gates (T-depth) in the approximate QFT circuit is ~2nlog_2(n/\varepsilon). This approximate QFT circuit was constructed using Toffoli gates and quantum adders. In this study, we present a new n-qubit QFT circuit approximated to error O(\varepsilon). Our approximate QFT circuit shows a T-count of ~4nlog_2(n/\varepsilon) and a T-depth of ~nlog_2(n/\varepsilon). Toffoli gates, which account for half of the T-count in the approximate QFT circuit reported in the previous study, are unnecessary in our construction. Quantum adders, which dominate the leading order term of T-depth in our approximate QFT circuit, are arranged in parallel to reduce T-depth.
We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of Θ(n)Θ(n)Θ(n) and depth of Θ(log⁡n)Θ(\log n)Θ(logn) over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from O(n3)\mathcal{O}(n^3)O(n3) to O(n2log⁡2n)\mathcal{O}(n^2 \log^2 n)O(n2log2n) without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.
Abstract Quantum computing poses a significant threat to modern cryptosystems, prompting nations to initiate the development of next-generation cryptographic algorithms where quantum security assessment constitutes a critical task. In this work, we present the first complete quantum attack circuit construction and security evaluation of quantum resistance for the authenticated encryption algorithm MK-3, which features 16-bit S-boxes. Firstly, we achieve breakthroughs in finite field arithmetic. The arrangement method of Toffoli gates in the subfield F24F_{2^4}F24​ F 2 4 enables two types of optimized F28F_{2^8}F28​ F 2 8 multiplication circuits to reduce DW-cost by at least 50%. For F28F_{2^8}F28​ F 2 8 inversion, by proposing a new intermediate state uncomputing technique, the DW-cost of the inversion circuit is reduced by at least 40% compared with existing solutions. This can also be used to optimize the quantum circuits of block ciphers such as AES and SM4. Secondly, we propose three types of quantum circuits for MK-3’s 16-bit S-box. The basic circuit reduces multiplicative bit operations to 115, representing at least 20% reduction. We propose a more compact S-box structure, reducing the number of circuit qubits for two types of S-boxes from 52 to 40. Finally, we implement full-algorithm quantum attacks and conduct security evaluations for MK-3. Complete quantum circuits supporting 128-bit and 256-bit keys are constructed, enabling Grover key search attacks. Security assessments confirm the 128-bit version meets NIST Security Category 1 (with reasonable inference of achieving Category 2), while the 256-bit version satisfies the highest Category 5 standards, demonstrating resistance against large-scale quantum computing attacks. This work achieves the first quantum circuit implementation for 16-bit S-boxes and provides critical evaluation benchmarks for post-quantum cryptography standardization.
Quantum computers have the potential to solve a number of hard problems that are believed to be almost impossible to solve by classical computers. This observation has sparked a surge of research to apply quantum algorithms against the cryptographic systems to evaluate its quantum resistance. In assessing the security strength of the cryptographic algorithms against the upcoming quantum threats, it is crucial to precisely estimate the quantum resource requirement (generally in terms of circuit depth and quantum bit count). The National Institute of Standards and Technology by the US government specified five quantum security levels so that the relative quantum strength of a given cipher can be compared to the standard ones. There have been some progress in the NIST-specified quantum security levels for the odd levels (i.e., 1, 3 and 5), following the work of Jaques et al. (Eurocrypt’20). However, levels 2 and 4, which correspond to the quantum collision finding attacks for the SHA-2 and SHA-3 hash functions, quantum attack complexities are arguably not well-studied. This is where our article fits in. In this article, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.