# Depth-Optimized Quantum Circuit of Gauss-Jordan Elimination
## 1 Introduction  
[PERSON] [1] presented a quantum algorithm for attacking the ECC and RSA cryptosystems, which are based on the discrete logarithm and factoring problems. In [PERSON]'s paper [1], he demonstrated the potential to solve these problems faster (exponentially) than traditional classical algorithms. As a result, there is a necessity for cryptographic algorithms that can withstand both quantum and classical computing attacks. To address this, the National Institute of Standards and Technology (NIST) hosted the Post-Quantum Cryptography (PQC) standardization ([[https://csrc.nist.gov/projects/post-quantum-cryptography](https://csrc.nist.gov/projects/post-quantum-cryptography)]([https://csrc.nist.gov/projects/post-quantum-cryptography](https://csrc.nist.gov/projects/post-quantum-cryptography)) (accessed on 19 September 2024.)) in 2016.  
Error-correcting codes, originally conceived as a method for identifying and correcting corrupted information in communication channels, were formalized by [PERSON] [2]. There is growing interest in using them at the core of asymmetric cryptosystems. NIST considered code-based cryptographic algorithms as a potential alternative, advancing all code-based cryptographic methods to the fourth round of its competition ([[https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4](https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4)]([https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4](https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4)) (accessed on 19 September 2024.)). NIST specifically announced that one or more of the three code-based candidates--Classic McEliece [3], BIKE [4], and HQC [5]--are likely to be standardized as an alternative to lattice-based cryptographic techniques.  
As such, accurately assessing the computational complexity of potential quantum computer attacks on code-based cryptographic algorithms is essential for optimizing their parameters. The security of these algorithms fundamentally depends on the difficulty of solving the Syndrome Decoding Problem (SDP), which involves finding a solution to a system of linear equations with a predetermined number of non-zero components.  
The most well-known classical algorithm for solving the SDP, Information Set Decoding (ISD), still runs in exponential time. One of the prominent studies theorizing the potential speedup of ISD attacks using quantum computers was [6], which demonstrated asignificant reduction in computational requirements when [PERSON]'s algorithm [7] is applied. However, the work did not provide specific quantum circuits for ISD. As far as we know, the first quantum circuit implementation for ISD was presented in [8]. Very recently, the authors of [8] extended and improved their work in [9].  
Various modules are needed to construct a complete quantum circuit for ISD, including input preparation, Hamming-weight checking, and Gaussian elimination. Among these, Gaussian elimination is particularly crucial because it requires significant quantum resources but can be optimized through various designs and implementations. In this context, this work present a depth-optimized quantum circuit of Gauss-Jordan elimination in ISD.