Quantum Gauss-Jordan Elimination for Code in Quantum
Kyungbae Jang, Hyunji Kim, Hwajeong Seo · 2022
Quantum computers can efficiently model and solve certain problems on their own. Already in various fields, quantum computing is expected to outperform classical computers. In this flow, it is important to quantize classical arithmetic to achieve the benefits of quantum computing. In this paper, we efficiently implement quantum Gauss-Jordan elimination for binary matrix. Quantum Gauss-Jordan is required to accelerate Information Set Decoding, a cryptanalysis algorithm for code-based post-quantum ciphers, with Grover’s algorithm. In our understanding, the most important module when implementing ISD as a quantum version is quantum Gauss-Jordan elimination. We implement quantum Gauss-Jordan using only quantum gates (e.g., X, CX, CCX, and Swap) that replace classical operations. Finally, we analyze the quantum resources required for our implementation. For the simulation and resource estimation of our work, the quantum programming tool ProjectQ is used.