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.
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.
MD5 and SHA-1 are widely studied hash functions in cryptanalysis, owing to their well-structured round functions and historical significance in cryptography. This paper presents improved quantum circuit implementations of MD5 and SHA-1 specifically optimized for quantum cryptanalysis. We reduce the quantum implementation cost of auxiliary functions and eliminate the use of ancilla qubits, while reducing circuit depth (the number of sequential gate layers) by parallelizing multiple additions in the round operations of MD5 and SHA-1. Additionally, the quantum implementations of MD5 and SHA-1 are optimized by considering a fixed input size under the attack scenario. The proposed implementations achieve a 63% improvement in the depth - qubit count metric for MD5 and a 27% improvement for SHA-1 compared to previous works. By providing reduced quantum resources, this work establishes an improved baseline for the quantum cryptanalysis of MD5 and SHA-1. We analyze quantum attacks on MD5 and SHA-1, showing that the preimage attacks require a full depth of 279 and 296 for MD5 and SHA-1, respectively, while the collision attacks require a full depth of 254 and 264. For a realistic evaluation, we also estimate the quantum resources for fault-tolerant quantum computation, including the number of physical qubits and the runtime, to break MD5 and SHA-1.
Fault-tolerant quantum computers rely on Quantum Error-Correcting Codes (QECCs) to protect information from noise. However, no single error-correcting code supports a fully transversal and therefore fault-tolerant implementation of all gates required for universal quantum computation. Code switching addresses this limitation by moving quantum information between different codes that, together, support a universal gate set. Unfortunately, each switch is costly-adding time and space overhead and increasing the logical error rate. Minimizing the number of switching operations is, therefore, essential for quantum computations using code switching. In this work, we study the problem of minimizing the number of code switches required to run a given quantum circuit. We show that this problem can be solved efficiently in polynomial time by reducing it to a minimum-cut instance on a graph derived from the circuit. Our formulation is flexible and can incorporate additional considerations, such as reducing depth overhead by preferring switches during idle periods or biasing the compilation to favor one code over another. To the best of our knowledge, this is the first automated approach for compiling and optimizing code-switching-based quantum computations at the logical level.
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 χ χ internal function block in SHA3-256 to explain our Toffoli-depth reduction approach preserving the in-place property, and hence, well-balanced five χ χ quantum circuits are induced in terms of its width and T-depth. And then, we apply these five χ χ 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 computing has made significant advancements in the last years in both hardware and software. Unfortunately, the currently available Noisy Intermediate-Scale Quantum (NISQ) hardware is still heavily affected by noise. Many optimization techniques have been developed to reduce the negative effects thereof, which, however, only works up to a certain point. Therefore, scaling quantum applications from currently considered small research examples to industrial applications requires error-correction techniques to execute quantum circuits in a fault-tolerant fashion and enter the Fault-Tolerant Quantum Computing (FTQC) era. These error-correction techniques introduce dramatic qubit overheads, leading to the requirement of tens of thousands of qubits already for toy-sized examples. Hence, quantum circuit optimization that reduces qubit overheads when shifting from the NISQ to the FTQC era is essential. This raises the question, whether we need to start from scratch, or whether current state-of-the-art optimization techniques can be used as a basis for this. To approach this question, this work investigates the effects of different optimization passes on a representative selection of quantum circuits. Since hardly any tools to automatically design and evaluate FTQC quantum circuits exist yet, we utilize resource estimation to compare the (potential) benefits gained by applying NISQ quantum circuit optimization to estimated FTQC resource requirements. The Results indicate that, indeed, the estimated resource requirements for FTQC can be improved by applying NISQ quantum circuit optimization techniques. At the same time, more detailed investigations show what techniques lead to more benefits for FTQC compared to others, providing guidelines for the transfer of NISQ optimization techniques to the FTQC era.
This paper explores the optimization of quantum circuits for Argon2, a memory-hard function used in password hashing applications. With the rise of quantum computers, the security of classical cryptographic systems is at risk. This paper emphasizes the need to accurately measure the quantum security strength of cryptographic schemes through highly optimized quantum circuits for the target cryptography algorithm. The proposed method focuses on two perspectives: qubit reduction (qubit-optimized quantum circuit) and depth reduction (depth-optimized quantum circuit). The qubit-optimized quantum circuit was designed to find a point where an appropriate inverse is possible and reuses the qubit through the inverse to minimize the number of qubits. The start and end points of the inverse are determined by identifying a point where qubits can be reused with minimal computation. The depth-optimized quantum circuit reduces the depth of the quantum circuit by using the minimum number of qubits necessary without performing an inverse operation. The trade-off between qubit and depth is confirmed by modifying the internal structure of the circuits and the quantum adders. The qubit optimization achieved up to a 12,229 qubit reduction, while the depth optimization resulted in an approximately 196,741 (approximately 69.02%) depth reduction. In conclusion, this research demonstrates the importance of implementing and analyzing quantum circuits from multiple optimization perspectives. The results contribute to the post-quantum strength analysis of Argon2 and provide valuable insights for future research on optimized quantum circuit design, considering the appropriate trade-offs of quantum resources in response to advancements in quantum computing technology.
The need to consider fault-tolerant quantum circuits is essential due to the intrinsic fragility of quantum systems. Recent studies have focused on optimizing complexity, resource utilization, and error resilience to enhance execution efficiency on quantum hardware. This paper performs a comparative analysis of fault-tolerant implementation approaches for quantum circuit design, emphasizing resource optimization, scalability, and error resilience. This paper illustrates recent designs that include enhanced Toffoli gate decompositions with reduced T-depths and resource-effective designs, demonstrating the tradeoffs among T-depth, T-gate count, and ancilla usage. These insights facilitate developing effective, scalable, and reliable quantum computing solutions, which are essential for both near-term quantum computation and future advancements.