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

Quantum Information Processing

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

Jongheon Lee, Yousung Kang, You-Seok Lee, Boheung Chung, Dooho Choi

Published Apr 18, 2024• 6 citations
Publisher

Abstract

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.

DOI
10.1007/s11128-024-04365-2

Related papers

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

Jongheon Lee, Sokjoon Lee, You-Seok Lee +1 more

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.

IET Information Security•Jun 28, 2022•9 citations

Improved Low-Depth SHA3 Quantum Circuit for Fault-Tolerant Quantum Computers

Gyeongju Song, Kyungbae Jang, Hwajeong Seo

To build a secure cryptography system in the post-quantum era, one must find the minimum security parameters against quantum attacks by estimating the quantum resources of a fault-tolerant quantum computer. In a fault-tolerant quantum computer, errors must reach an acceptable level for practical uses according to error detection and error correction processes. However, these processes utilize additional quantum resources. As the depth of the quantum circuit increases, the computation time per qubit increases together with the processing errors. Therefore, in terms of errors in quantum circuits, it is a fundamental requirement to reduce the depth by trading off the number of qubits. This paper proposes novel low-depth SHA3 quantum circuit implementations for fault-tolerant quantum computers to reduce errors. The proposed SHA3 quantum circuit was implemented with the aim of optimizing the quantum circuit depth through a trade-off between the number of qubits, the quantum gate, and the quantum depth in each function. Compared to other state-of-art techniques, the proposed method achieved T-depth and full-depth reductions of 30.3% and 80.05%, respectively. We believe that this work will contribute to the establishment of minimum security parameters for SHA3 in the quantum era.

Applied Sciences•Mar 10, 2023•14 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

Optimal T-depth Quantum Circuits for Implementing Arbitrary Boolean Functions

Suman Dutta, Anik Bhaumik, Anupam Chattopadhyay +1 more

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 ⌈log 2 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.

arXiv:2506.01542•Quantum Information and Computation•Dec 1, 2025•4 citations

Optimized Quantum Circuit Design and Grover Search Resource Estimation for the Camellia Block Cipher

Vandana B Patil

With the advancement of quantum computing, quantum circuit implementations of symmetric cryptographic algorithms are essential for evaluating their resistance to quantum attacks. As an ISO-standardized cipher, the efficient quantum circuit construction of Camellia is of great significance. Focusing on minimizing the DW-cost (qubits × Toffoli-depth) while balancing ancilla qubits and Toffoli-depth, this paper proposes an optimized quantum circuit design for Camellia. Specifically: (1) using a serial-multiplication and out-of-place inversion architecture under composite-field decomposition, combined with hierarchical screening for parallelizing bilinear multiplications, a compact in-place S-box quantum circuit is constructed with a DW-cost of 276, 28% lower than the state of the art; (2) a low-gate-count linear-layer circuit is obtained via heuristic search, and gate-sequence reordering then reduces the full depth from 9 to 7 without increasing the gate count; (3) Camellia-128/192/256 quantum circuits are constructed with DW-costs of 119,168, 257,664, and 257,664, achieving reductions of 48%, 52%, and 52% respectively over prior work. A pipelined Grover oracle is further designed and the total resources required for a full Grover search attacking Camellia are evaluated. For Camellia-128, the complete Grover search requires a T-depth of 2.10 × 2⁷⁶ and a total TDW-cost (qubits × T-depth) of 1.00 × 2⁸⁶, reducing T-depth by 75% and TDW-cost by 84% over prior work. The first full Grover search resource estimates for Camellia-192/256 are also presented, with T-depths of 7.20 × 2¹⁰⁸ and 8.11 × 2¹⁴⁰ and TDW-costs of 2.03 × 2¹²³ and 2.79 × 2¹⁵³, respectively. These results show that Grover's attack on Camellia requires fewer quantum resources than on AES at the 128-bit level, implying comparatively weaker post-quantum security at that key size, while the picture reverses at larger key sizes (Section 4).

Journal of Intelligent Decision Making and Information Science•Sep 16, 2026•0 citations

Improved Quantum Circuits via Intermediate Qutrits

Jonathan M. Baker, Casey Duckering, Pranav Gokhale +3 more

Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu trits . Past work with qutrits has demonstrated only constant factor improvements, owing to the log 2 (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla—a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70× improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor’s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.

ACM Transactions on Quantum Computing•Oct 29, 2020•20 citations
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.
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.
To build a secure cryptography system in the post-quantum era, one must find the minimum security parameters against quantum attacks by estimating the quantum resources of a fault-tolerant quantum computer. In a fault-tolerant quantum computer, errors must reach an acceptable level for practical uses according to error detection and error correction processes. However, these processes utilize additional quantum resources. As the depth of the quantum circuit increases, the computation time per qubit increases together with the processing errors. Therefore, in terms of errors in quantum circuits, it is a fundamental requirement to reduce the depth by trading off the number of qubits. This paper proposes novel low-depth SHA3 quantum circuit implementations for fault-tolerant quantum computers to reduce errors. The proposed SHA3 quantum circuit was implemented with the aim of optimizing the quantum circuit depth through a trade-off between the number of qubits, the quantum gate, and the quantum depth in each function. Compared to other state-of-art techniques, the proposed method achieved T-depth and full-depth reductions of 30.3% and 80.05%, respectively. We believe that this work will contribute to the establishment of minimum security parameters for SHA3 in the quantum era.
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.
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 ⌈log 2 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.
With the advancement of quantum computing, quantum circuit implementations of symmetric cryptographic algorithms are essential for evaluating their resistance to quantum attacks. As an ISO-standardized cipher, the efficient quantum circuit construction of Camellia is of great significance. Focusing on minimizing the DW-cost (qubits × Toffoli-depth) while balancing ancilla qubits and Toffoli-depth, this paper proposes an optimized quantum circuit design for Camellia. Specifically: (1) using a serial-multiplication and out-of-place inversion architecture under composite-field decomposition, combined with hierarchical screening for parallelizing bilinear multiplications, a compact in-place S-box quantum circuit is constructed with a DW-cost of 276, 28% lower than the state of the art; (2) a low-gate-count linear-layer circuit is obtained via heuristic search, and gate-sequence reordering then reduces the full depth from 9 to 7 without increasing the gate count; (3) Camellia-128/192/256 quantum circuits are constructed with DW-costs of 119,168, 257,664, and 257,664, achieving reductions of 48%, 52%, and 52% respectively over prior work. A pipelined Grover oracle is further designed and the total resources required for a full Grover search attacking Camellia are evaluated. For Camellia-128, the complete Grover search requires a T-depth of 2.10 × 2⁷⁶ and a total TDW-cost (qubits × T-depth) of 1.00 × 2⁸⁶, reducing T-depth by 75% and TDW-cost by 84% over prior work. The first full Grover search resource estimates for Camellia-192/256 are also presented, with T-depths of 7.20 × 2¹⁰⁸ and 8.11 × 2¹⁴⁰ and TDW-costs of 2.03 × 2¹²³ and 2.79 × 2¹⁵³, respectively. These results show that Grover's attack on Camellia requires fewer quantum resources than on AES at the 128-bit level, implying comparatively weaker post-quantum security at that key size, while the picture reverses at larger key sizes (Section 4).
Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu trits . Past work with qutrits has demonstrated only constant factor improvements, owing to the log 2 (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla—a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70× improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor’s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.