Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computational and Mathematical Methods

Quantum approximate optimization of the coset leader problem for binary linear codes

Markel Epelde, Elías F. Combarro, I. F. Rúa

Published Oct 1, 2021• 2 citations
Publisher

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.

DOI
10.1002/cmm4.1196

Related papers

DECODING M-ARY LINEAR CODES WITH THE QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

Markel Epelde, Elías F. Combarro, I. F. R ́ua

Abstract The NP-hardness of the Minimum Distance Decoding Problem (MDDP) is the core of the McEliece cryptosystem. The difficulty of decoding a received word to the closest codeword in a given arbitrary code is key to its security. Related to the MDDP is the Coset Leader Problem (CLP), which consists in finding a word of a given syndrome and minimum Hamming weight. Both can be modelled as optimization problems, and solved using the Quantum Approximate Optimization Algorithm (QAOA), a well-known hybrid quantum- classical algorithm. In this paper, we model both the MDDP and CLP for linear codes over arbitrary m−ary alphabets, we make the theoretical analysis of the first level for the binary CLP problem, and introduce some experiments to test its performance. The experiments were carried out on both quantum computer simulators and real quantum devices, and use codes of different lengths and different depths of the QAOA.

Eurasian Journal of Mathematical and Computer Applications•Mar 1, 2022•0 citations

Syndrome decoding by quantum approximate optimization

Ching–Yi Lai, Kao-Yueh Kuo, Bo-Jyun Liao

Abstract The syndrome decoding problem is known to be NP-complete. The goal of the decoder is to find an error of low weight that corresponds to a given syndrome obtained from a parity-check matrix. We use the quantum approximate optimization algorithm (QAOA) to address the syndrome decoding problem with elegantly-designed reward Hamiltonians based on both generator and check matrices for classical and quantum codes.We evaluate the level-4 check-based QAOA decoding of the [7,4,3] Hamming code, as well as the level-4 generator-based QAOA decoding of the [[5,1,3]] quantum code.Remarkably, the simulation results demonstrate that the decoding performances match those of the maximum likelihood decoding. Moreover, we explore the possibility of enhancing QAOA by introducing additional redundant clauses to a combinatorial optimization problem while keeping the number of qubits unchanged. Finally, we study QAOA decoding of degenerate quantum codes.Typically, conventional decoders aim to find a unique error of minimum weight that matches a given syndrome. However, our observations reveal that QAOA has the intriguing ability to identify degenerate errors of comparable weight, providing multiple potential solutions that match the given syndrome with comparable probabilities.This is illustrated through simulations of the generator-based QAOA decoding of the [[9,1,3]] Shor code on specific error syndromes.

arXiv:2207.05942•Quantum Information Processing•Nov 1, 2024•8 citations

A quantum algorithm for syndrome decoding of classical error-correcting linear block codes

Mainak Bhattacharyya, Ankur Raina

Decoding of linear block codes using syndrome decoding and finding whether there exists a codeword of weight$w$in a set of codewords are known to belong to a class of NP-complete problems. For syndrome decoding of linear block codes, we provide an algorithm that gives a probabilistic solution with least Hamming weight. The algorithm can speed up this process significantly with the help of quantum search algorithm. For this, we make use of a search algorithm inspired from Grover's search. We also suggest a general approach for building a quantum circuit for syndrome detection. We test the algorithm in IBM Quantum Experience using qasm simulator and perform the complexity analysis identifying the algorithm's domain of utility.

IEEE/ACM Symposium on Edge Computing (SEC)•Dec 1, 2022•6 citations

Quantum Approximate Optimization for Decoding of Low-Density Parity-Check Codes

Krishnakanta Barik, Goutam Paul

Decoding Low-Density Parity-Check (LDPC) codes is a fundamental problem in coding theory, and Belief Propagation (BP) is one of the most popular methods for LDPC code decoding. However, BP may encounter convergence issues and suboptimal performance, especially for short-length codes and in high-noise channels. The Quantum Approximate Optimization Algorithm (QAOA) is a type of Variational Quantum Algorithm (VQA) designed to solve combinatorial optimization problems by minimizing a problem-specific cost function. In this paper, we present a QAOA-based decoding framework for LDPC codes by formulating a decoding cost function that incorporates both parity-check constraints and soft channel reliability information. The resulting optimization problem is solved using QAOA to search for low-energy configurations corresponding to valid codewords. We test the proposed method through extensive numerical experiments and compare its performance with BP decoding. The experimental results demonstrate that the QAOA-based decoder achieves a higher probability of correctly recovering the transmitted codeword than BP across multiple experimental settings.

quant-pharXiv:2602.21124•IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Feb 25, 2026•0 citations

Channel Decoding with Quantum Approximate Optimization Algorithm

Toshiki Matsumine, Toshiaki Koike–Akino, Ye Wang

Motivated by the recent advancement of quantum processors, we investigate quantum approximate optimization algorithm (QAOA) to employ quasi-maximum-likelihood (ML) decoding of classical channel codes. QAOA is a hybrid quantum-classical variational algorithm, which is advantageous for the near-term noisy intermediate-scale quantum (NISQ) devices, where the fidelity of quantum gates is limited by noise and de-coherence. We first describe how to construct Ising Hamiltonian model to realize quasi-ML decoding with QAOA. For level-1 QAOA, we derive the systematic way to generate theoretical expressions of cost expectation for arbitrary binary linear codes. Focusing on [7], [4] Hamming code as an example, we analyze the impact of the degree distribution in associated generator matrix on the quantum decoding performance. The excellent performance of higher-level QAOA decoding is verified when Pauli rotation angles are optimized through meta-heuristic variational quantum eigensolver (VQE). Furthermore, we demonstrate the QAOA decoding performance in a real quantum device.

arXiv:1903.02537•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•31 citations

Quantum approximate optimization for hard problems in linear algebra

Ajinkya Borle

The quantum approximate optimization algorithm (QAOA) by Farhi et al. is a quantum computational framework for solving quantum or classical optimization tasks. Here, we explore using QAOA for binary linear least squares (BLLS); a problem that can serve as a building block of several other hard problems in linear algebra, such as the non-negative binary matrix factorization (NBMF) and other variants of the non-negative matrix factorization (NMF) problem. Most of the previous efforts in quantum computing for solving these problems were done using the quantum annealing paradigm. For the scope of this work, our experiments were done on noiseless quantum simulators, a simulator including a device-realistic noise-model, and two IBM Q 5-qubit machines. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where trial solutions can be obtained directly as samples, rather than being amplitude-encoded in the quantum wavefunction. Our numerics show that even for a small number of steps, simulated annealing can outperform QAOA for BLLS at a QAOA depth of $p\leq3$ for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on cloud-based quantum computers.

•Nov 1, 2021•25 citations
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.
Abstract The NP-hardness of the Minimum Distance Decoding Problem (MDDP) is the core of the McEliece cryptosystem. The difficulty of decoding a received word to the closest codeword in a given arbitrary code is key to its security. Related to the MDDP is the Coset Leader Problem (CLP), which consists in finding a word of a given syndrome and minimum Hamming weight. Both can be modelled as optimization problems, and solved using the Quantum Approximate Optimization Algorithm (QAOA), a well-known hybrid quantum- classical algorithm. In this paper, we model both the MDDP and CLP for linear codes over arbitrary m−ary alphabets, we make the theoretical analysis of the first level for the binary CLP problem, and introduce some experiments to test its performance. The experiments were carried out on both quantum computer simulators and real quantum devices, and use codes of different lengths and different depths of the QAOA.
Abstract The syndrome decoding problem is known to be NP-complete. The goal of the decoder is to find an error of low weight that corresponds to a given syndrome obtained from a parity-check matrix. We use the quantum approximate optimization algorithm (QAOA) to address the syndrome decoding problem with elegantly-designed reward Hamiltonians based on both generator and check matrices for classical and quantum codes.We evaluate the level-4 check-based QAOA decoding of the [7,4,3] Hamming code, as well as the level-4 generator-based QAOA decoding of the [[5,1,3]] quantum code.Remarkably, the simulation results demonstrate that the decoding performances match those of the maximum likelihood decoding. Moreover, we explore the possibility of enhancing QAOA by introducing additional redundant clauses to a combinatorial optimization problem while keeping the number of qubits unchanged. Finally, we study QAOA decoding of degenerate quantum codes.Typically, conventional decoders aim to find a unique error of minimum weight that matches a given syndrome. However, our observations reveal that QAOA has the intriguing ability to identify degenerate errors of comparable weight, providing multiple potential solutions that match the given syndrome with comparable probabilities.This is illustrated through simulations of the generator-based QAOA decoding of the [[9,1,3]] Shor code on specific error syndromes.
Decoding of linear block codes using syndrome decoding and finding whether there exists a codeword of weightwwwin a set of codewords are known to belong to a class of NP-complete problems. For syndrome decoding of linear block codes, we provide an algorithm that gives a probabilistic solution with least Hamming weight. The algorithm can speed up this process significantly with the help of quantum search algorithm. For this, we make use of a search algorithm inspired from Grover's search. We also suggest a general approach for building a quantum circuit for syndrome detection. We test the algorithm in IBM Quantum Experience using qasm simulator and perform the complexity analysis identifying the algorithm's domain of utility.
Decoding Low-Density Parity-Check (LDPC) codes is a fundamental problem in coding theory, and Belief Propagation (BP) is one of the most popular methods for LDPC code decoding. However, BP may encounter convergence issues and suboptimal performance, especially for short-length codes and in high-noise channels. The Quantum Approximate Optimization Algorithm (QAOA) is a type of Variational Quantum Algorithm (VQA) designed to solve combinatorial optimization problems by minimizing a problem-specific cost function. In this paper, we present a QAOA-based decoding framework for LDPC codes by formulating a decoding cost function that incorporates both parity-check constraints and soft channel reliability information. The resulting optimization problem is solved using QAOA to search for low-energy configurations corresponding to valid codewords. We test the proposed method through extensive numerical experiments and compare its performance with BP decoding. The experimental results demonstrate that the QAOA-based decoder achieves a higher probability of correctly recovering the transmitted codeword than BP across multiple experimental settings.
Motivated by the recent advancement of quantum processors, we investigate quantum approximate optimization algorithm (QAOA) to employ quasi-maximum-likelihood (ML) decoding of classical channel codes. QAOA is a hybrid quantum-classical variational algorithm, which is advantageous for the near-term noisy intermediate-scale quantum (NISQ) devices, where the fidelity of quantum gates is limited by noise and de-coherence. We first describe how to construct Ising Hamiltonian model to realize quasi-ML decoding with QAOA. For level-1 QAOA, we derive the systematic way to generate theoretical expressions of cost expectation for arbitrary binary linear codes. Focusing on [7], [4] Hamming code as an example, we analyze the impact of the degree distribution in associated generator matrix on the quantum decoding performance. The excellent performance of higher-level QAOA decoding is verified when Pauli rotation angles are optimized through meta-heuristic variational quantum eigensolver (VQE). Furthermore, we demonstrate the QAOA decoding performance in a real quantum device.
The quantum approximate optimization algorithm (QAOA) by Farhi et al. is a quantum computational framework for solving quantum or classical optimization tasks. Here, we explore using QAOA for binary linear least squares (BLLS); a problem that can serve as a building block of several other hard problems in linear algebra, such as the non-negative binary matrix factorization (NBMF) and other variants of the non-negative matrix factorization (NMF) problem. Most of the previous efforts in quantum computing for solving these problems were done using the quantum annealing paradigm. For the scope of this work, our experiments were done on noiseless quantum simulators, a simulator including a device-realistic noise-model, and two IBM Q 5-qubit machines. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where trial solutions can be obtained directly as samples, rather than being amplitude-encoded in the quantum wavefunction. Our numerics show that even for a small number of steps, simulated annealing can outperform QAOA for BLLS at a QAOA depth of p≤3p\leq3p≤3 for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on cloud-based quantum computers.