Quantum approximate optimization of the coset leader problem for binary linear codes. Issue 6 (11th October 2021)

• Record Type: Journal Article
• Authors: Epelde, Markel; Combarro, Elías F.; Rúa, Ignacio F.
• Is Part Of: Computational and mathematical methods. Volume 3:Issue 6(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2021-10-11
• Subjects: coset leader problem -- quantum approximate optimization algorithm -- syndrome decoding problem; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Periodicals; Numerical analysis; Mathematics -- Data processing; Periodicals; 004.0151
• DOI: 10.1002/cmm4.1196
• Languages: English
• ISSNs: 2577-7408

Abstract

Abstract: The security of a broad family of coding‐based cryptographic techniques relies on the hardness of the Syndrome Decoding Problem (SDP). In this problem, the aim is to find a word with a given syndrome and of Hamming weight smaller than a prefixed bound. If this last condition is replaced by "of minimum weight, " then we have the Coset Leader Problem (CLP), being Finding Low Weight Codewords (FLWC) a particular case (when the zero syndrome is considered). An algorithm that has been proposed in order to obtain approximate solutions of problems of these kind (NP‐complete) is the Quantum Approximate Optimization Algorithm (QAOA), a variational hybrid quantum‐classical algorithm. In this paper, we apply the QAOA to the CLP for binary linear codes. We model the problem, make the theoretical analysis the case of the first level, and introduce some experiments to test its performance. The experiments have been carried out on quantum computer simulators with codes of different lengths and QAOA of different depth.