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

arXiv:2207.05942 · Quantum Information Processing

Syndrome decoding by quantum approximate optimization

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

Published Nov 1, 2024• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s11128-024-04568-7

Related papers

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

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

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.

Computational and Mathematical Methods•Oct 1, 2021•2 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

Optimal Single-Shot Decoding of Quantum Codes

Aldo Cumitini, Stefano Tinelli, Balázs Matuz +2 more

We discuss single-shot decoding of quantum Calderbank-Shor-Steane codes with faulty syndrome measurements. We state the problem as a joint source-channel coding problem. By adding redundant rows to the code’s parity-check matrix, we obtain an additional syndrome error correcting code which addresses faulty syndrome measurements. Thereby, the redundant rows are chosen to obtain good syndrome error correction capabilities while keeping the stabilizer weights low. Optimal joint decoding rules are derived which, though too complex for general codes, can be evaluated for short quantum codes.

arXiv:2310.18138•IEEE Communications Letters•Mar 21, 2024•0 citations

Quantum-Enhanced Belief Propagation for LDPC Decoding

Sheila M. Perez-Garcia, Ashley Montanaro

Decoding low-density parity-check codes is critical in many current technologies, such as fifth-generation (5G) wireless networks and satellite communications. The belief propagation algorithm allows for fast decoding due to the low density of these codes. However, there is scope for improvement to this algorithm both in terms of its computational cost when decoding large codes and its error-correcting abilities. Here, we introduce the quantum-enhanced belief propagation (QEBP) algorithm, in which the Quantum Approximate Optimization Algorithm (QAOA) acts as a pre-processing step to belief propagation. We perform exact simulations of syndrome decoding with QAOA, whose result guides the belief propagation algorithm, leading to faster convergence and a lower block error rate (BLER). In addition, through the repetition code, we study the possibility of having shared variational parameters between syndromes and, in this case, code lengths. We obtain a unique pair of variational parameters for level-1 QAOA by optimizing the probability of successful decoding through a transfer matrix method. Then, using these parameters, we compare the scaling of different QAOA post-processing techniques with code length.

arXiv:2412.08596•IEEE Transactions on Quantum Engineering•Jan 1, 2026•3 citations

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

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•7 citations
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.
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.
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.
We discuss single-shot decoding of quantum Calderbank-Shor-Steane codes with faulty syndrome measurements. We state the problem as a joint source-channel coding problem. By adding redundant rows to the code’s parity-check matrix, we obtain an additional syndrome error correcting code which addresses faulty syndrome measurements. Thereby, the redundant rows are chosen to obtain good syndrome error correction capabilities while keeping the stabilizer weights low. Optimal joint decoding rules are derived which, though too complex for general codes, can be evaluated for short quantum codes.
Decoding low-density parity-check codes is critical in many current technologies, such as fifth-generation (5G) wireless networks and satellite communications. The belief propagation algorithm allows for fast decoding due to the low density of these codes. However, there is scope for improvement to this algorithm both in terms of its computational cost when decoding large codes and its error-correcting abilities. Here, we introduce the quantum-enhanced belief propagation (QEBP) algorithm, in which the Quantum Approximate Optimization Algorithm (QAOA) acts as a pre-processing step to belief propagation. We perform exact simulations of syndrome decoding with QAOA, whose result guides the belief propagation algorithm, leading to faster convergence and a lower block error rate (BLER). In addition, through the repetition code, we study the possibility of having shared variational parameters between syndromes and, in this case, code lengths. We obtain a unique pair of variational parameters for level-1 QAOA by optimizing the probability of successful decoding through a transfer matrix method. Then, using these parameters, we compare the scaling of different QAOA post-processing techniques with code length.
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.
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.