KR-20260067078-A - METHOD FOR PERFORMING GAUSSIAN ELIMINATION ON A QUANTUM CIRCUIT AND QUNTUM CIRCUIT THEREOF

Abstract

The present invention relates to a method for performing Gaussian elimination on a quantum circuit and a quantum circuit for performing the same. In the present invention, a quantum circuit is disclosed in which a plurality of pivot elements are copied using a plurality of auxiliary qubits, and then swap and erase steps are processed in parallel for multiple elements. The present invention makes it possible to present a quantum circuit implementation of Gauss-Jordan erasure, which is one of the important modules in responding to ISD attacks.

Inventors

• 서화정
• 장경배

Assignees

• 한성대학교 산학협력단

Dates

Publication Date

20260512

Application Date

20241105

Claims (6)

1. A method for performing Gaussian elimination on a quantum circuit for an n×n matrix H (containing n syndrome values), Step 1, which sets the counter variable i to 0, and - Swap Stage - The second step of setting the counter variable j=0, and A third step of copying H i,j to a first group of auxiliary qubits consisting of (n+1-i) auxiliary qubits, and A fourth step of performing a controlled-swap operation on elements in the i-th row and elements in the (i+1-j)-th row simultaneously in parallel using the first group auxiliary qubit, and - In the second step, using the first group auxiliary qubit, the syndrome value of the i-th row is controlled-swap with the syndrome value of the (i+1-j)-row. Step 5, which resets the first group auxiliary qubit, and Step 6, which involves increasing j by 1 and performing steps 3 through 5 until j reaches (n-2-i), and - Elimination Stage - Step 7, which initializes the counter variable j to 0, and Step 8, which copies the i-th column of matrix H to the second group auxiliary qubit, and - Exclude H i,j in Step 8 - Step 9, which repeats Step 8 until j is (n-1-i) after increasing j by 1, and Step 10, which initializes the counter variable j to 0, and Step 11, which copies the i-th row of matrix H to the third group auxiliary qubit, and - Exclude H i,j in Step 11 - Step 12, which repeats Step 11 until j is (n-2-i) after increasing j by 1, and Step 13, which performs controlled elimination operations on H ((i+1)~n), 0~((n-1)≠i) simultaneously in parallel using the second group auxiliary qubit and the third group auxiliary qubit, and Step 14, which initializes the second group auxiliary qubit and the third group auxiliary qubit, and A method for performing Gaussian elimination on a quantum circuit for an n×n matrix H (containing n syndrome values) characterized by including a 15th step of repeating steps 2 through 14 up to i=(n-2) after increasing i by 1.
2. In paragraph 1, A method for performing Gaussian elimination on a quantum circuit for a matrix H of size n×n (including n syndrome values) characterized in that at least one of the above-mentioned third step, third step, and eleventh step is performed by exponential copying.
3. In any one of paragraphs 1 to 3, A method for performing Gaussian elimination on a quantum circuit for an n×n matrix H (including n syndrome values) characterized in that the above-mentioned 4th stage controlled swap is performed with Toffoli (1st group auxiliary qubit, (i+1+j)th row of matrix H, i-th row of matrix H).
4. In any one of paragraphs 1 to 3, A method for performing Gaussian elimination on a quantum circuit for an n×n matrix H (including n syndrome values ) characterized in that the Controlled elimination operation of the above 13th step is performed as Toffoli(first group auxiliary qubit + i-th column of matrix H, second group auxiliary qubit + i-th row of matrix H, H ((i+1)~n), 0~((n-1)≠i) ).
5. A quantum circuit for Gaussian elimination that performs a swap operation on the Hi,j pivot qubit of an n×n matrix H (containing n syndrome values), A CNOT gate that copies H i,j to a first group of auxiliary qubits consisting of (n+1-i) auxiliary qubits, and Toffoli (first group auxiliary qubit, (i+1+j)th row of H matrix, i-th row of H matrix) gates that simultaneously perform controlled swaps in parallel and Here, j is a natural number from 0 to (n-2-i), and i is a natural number up to n. A quantum circuit for Gaussian elimination characterized by including a CNOT gate that resets the first group auxiliary qubit.
6. A quantum circuit for Gaussian erasure that performs an erasure operation on the Hi,j pivot qubit of an n×n matrix H (containing n syndrome values), A CNOT gate that copies the i-th column of matrix H to the second group auxiliary qubit, excluding H i,j , and - j is equipped with a CNOT gate that copies to the second group auxiliary qubits by incrementing from 0 by 1 up to (n-1-i) - A CNOT gate that copies the i-th row of matrix H to the third group auxiliary qubit, excluding H i,j , and - j is equipped with a CNOT gate that increments from 0 by 1 up to a number (n-2-i) as a third-group auxiliary qubit - Toffoli gates that simultaneously perform erasure operations (first group auxiliary qubit, (i+1+j)th row of H matrix, i-th row of H matrix) and Here, j is a natural number from 0 to (n-2-i), and i is a natural number up to n. A quantum circuit for Gaussian erasure that performs an erasure operation on a Hi,j pivot qubit, characterized by including a CNOT gate that initializes a second group auxiliary qubit and a third group auxiliary qubit.

Description

Method for performing Gaussian elimination on a quantum circuit and a quantum circuit performing the same The present invention relates to a method for performing Gaussian elimination on a quantum circuit and a quantum circuit for performing the same. More specifically, the invention relates to a method for performing Gaussian elimination on a quantum circuit that simultaneously processes swap operations and removal operations in parallel, and a quantum circuit for performing the same. Shor proposed quantum algorithms to attack RSA and ECC cryptographic systems based on factorization and discrete logarithm problems. Shor's algorithms demonstrated the potential to solve these problems exponentially faster than existing classical algorithms. Consequently, there was a need for cryptographic algorithms capable of withstanding both classical and quantum computing attacks. To address this, the National Institute of Standards and Technology (NIST) began the standardization of Post-Quantum Cryptography (PQS) in 2016. Error-correcting codes, originally designed as a method to detect and correct corrupted information in noisy communication channels, were formulated by Shannon. There is growing interest in using them at the core of asymmetric encryption systems. NIST considers code-based encryption algorithms potential alternatives and has advanced all code-based encryption technologies to the fourth round of competition. In particular, NIST announced that it is highly likely that at least one of the three code-based candidates—Classic McEllis, BIKE, and HQC—will be standardized as an alternative to lattice-based encryption algorithms. Therefore, in order to fine-tune the parameters of these encryption algorithms, it is important to accurately assess the computational complexity of attacks on code-based encryption algorithms with the help of quantum computers. The robustness of code-based encryption algorithms depends on the difficulty of the Syndrome Decryption Problem (SDP). This problem can be summarized as finding a solution to a set of linear equations with fixed non-zero elements. Information Set Decoding (ISD), the most well-known classical algorithm for solving SDPs, still runs in exponentially short time. One prominent study that theorized the potential speed enhancement of ISD attacks using quantum computers is the research by Bernstein, D.J. et al., which demonstrated that computational requirements are significantly reduced when Grover's algorithm is applied. However, this study did not provide a specific quantum circuit for ISD. The first implementation of a quantum circuit for ISD was presented by Perriello, S et al. Very recently, Perriello, S et al. have expanded and improved upon their work. Various modules are required to construct a complete quantum circuit for ISD, including input preparation, Hamming weight checks, and Gaussian elimination. Among these, Gaussian elimination is particularly important because, while it requires significant quantum resources, it can be optimized through various designs and implementations. In this context, there is a need for deeply optimized quantum circuits for Gaussian-Jordan elimination in ISD. FIG. 1 is a quantum gate used in the present invention. FIG. 2 is a conventional quantum circuit configuration diagram implementing a swap operation. FIG. 3 is a quantum circuit diagram of an embodiment according to the present invention that performs a swap step in parallel in Gaussian-Jordan elimination. FIG. 4 is an explanatory diagram illustrating exponential copying according to the present invention. FIG. 5 is a quantum circuit diagram of an embodiment according to the present invention that performs the erasure step in parallel in Gaussian erasure. The terms used in this invention are used merely to describe specific embodiments and are not intended to limit the invention. Singular expressions include plural expressions unless the context clearly indicates otherwise. In this specification, terms such as "comprising" or "having" are intended to indicate the existence of the features, numbers, steps, actions, components, parts, or combinations thereof described in the specification, and should be understood as not precluding the existence or addition of one or more other features, numbers, steps, actions, components, parts, or combinations thereof. In addition, in this specification, the phrase “on or above” means being located above or below the target part, and does not necessarily mean being located on the upper side with respect to the direction of gravity. Furthermore, when a part such as a region or plate is said to be “on or above” another part, this includes not only cases where it is in contact with or spaced apart from the other part “immediately on or above” the other part, but also cases where there is another part in between. In addition, when a component is described in this specification as being "connected" or "connected" to another component, it shoul