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:2604.24633

Optimization Using Locally-Quantum Decoders

Noah Shutty, Avijit Mandal, Seyoon Ragavan, Quentin Buzet, André Chailloux, Nicholas C. Rubin, Abid Khan, Sami Boulebnane, Ruslan Shaydulin, John Azariah, Stephen P. Jordan

quant-phSubmitted Apr 27, 2026• Announced Apr 28, 2026• 0 citations
v1 · Apr 27, 2026v2 · Jul 2, 2026
arXivHTMLPDF

Abstract

It was pointed out in [JSW+25] that widely-studied optimization problems such as D-regular max-k-XORSAT can be reduced to decoding of LDPC codes, using quantum algorithms related to Regev's reduction. LDPC codes have very good decoders, such as Belief Propagation (BP), and this therefore makes D-regular max-k-XORSAT an enticing target for this class of quantum algorithms. However, BP was found insufficient to achieve quantum advantage. Here, we develop an intrinsically quantum decoding technique, which decodes classical LDPC codes subject to coherent superpositions of bit flip errors. For average-case instances of D-regular max-k-XORSAT drawn from Gallager's ensemble, this quantum decoder strongly outperforms classical belief propagation at many values of k and D. For some (k,D) the approximate optima achievable using this decoder surpass both Prange's algorithm and simulated annealing. However, we stop short of achieving quantum advantage because we identify an enhancement to Prange's algorithm that recovers a precise tie, much as a precise tie was observed between the standard version of Prange's algorithm and a more limited version of locally-quantum decoding in [CT24].

Comments
38 pages

Related papers

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

Breaking the Orthogonality Barrier in Quantum LDPC Codes

Kenta Kasai

Classical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular $[[9216,4612, \leq 48]]$ quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as $10^{-8}$ on the depolarizing channel with error probability $4 \%$.

quant-pharXiv:2601.08824•Quantum•Jan 14, 2026•0 citations

The closed-branch decoder for quantum LDPC codes

Antonio deMarti iOlius, Josu Etxezarreta Martínez

Quantum error correction is the building block for constructing fault-tolerant quantum processors that can operate reliably even if its constituting elements are corrupted by decoherence. In this context, real-time decoding is a necessity for implementing arbitrary quantum computations on the logical level. In this work, we present a new decoder for Quantum Low Density Parity Check (QLDPC) codes, named the closed-branch decoder, with a worst-case complexity loosely upper bounded by $\mathcal{O}(n\text{max}_{\text{gr}}\text{max}_{\text{br}})$, where $\text{max}_{\text{gr}}$ and $\text{max}_{\text{br}}$ are tunable parameters that pose the accuracy versus speed trade-off of decoding algorithms. For the best precision, the $\text{max}_{\text{gr}}\text{max}_{\text{br}}$ product increases exponentially as $\propto dj^d$, where $d$ indicates the distance of the code and $j$ indicates the average row weight of its parity check matrix. Nevertheless, we numerically show that considering small values that are polynomials of the code distance are enough for good error correction performance. The decoder is described to great extent and compared with the Belief Propagation Ordered Statistics Decoder (BPOSD) operating over data qubit, phenomenological and circuit-level noise models for the class of Bivariate Bicycle (BB) codes. The results showcase a promising performance of the decoder, obtaining similar results with much lower complexity than BPOSD when considering the smallest distance codes, but experiencing some logical error probability degradation for the larger ones. Ultimately, the performance and complexity of the decoder depends on the product $\text{max}_{\text{gr}}\text{max}_{\text{br}}$, which can be considered taking into account benefiting one of the two aspects at the expense of the other.

arXiv:2402.01532•Feb 2, 2024•0 citations

Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes

Avijit Mandal, Christophe Piveteau, Joseph M. Renes +1 more

Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels, where $q$ is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity. For regular ensembles with $d_v\geq3$, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-$\ell$ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable $\ell=Θ(\log\log N)$, a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.

quant-pharXiv:2609.05857•Sep 8, 2026•0 citations

The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction

Agathe Blanvillain, André Chailloux, Jean–Pierre Tillich

We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.

arXiv:2509.24796•IEEE Transactions on Information Theory•May 5, 2026•0 citations

Decimation Strategies for Belief Propagation Decoding of Quantum LDPC Codes

Masoumeh Alinia, David G. M. Mitchell, Hanwen Yao +1 more

Due to code degeneracy and the graph structure of quantum low-density parity-check (QLDPC) codes, the performance of conventional belief propagation (BP) decoding can be poor. Recently, belief propagation guided decimation (BPGD) has shown promise to combat these challenges. In this paper, we investigate various decimation approaches to improve the error correcting performance and convergence speed of BPGD. We first consider soft decimation, where the BP equations are modified via several tuneable parameters. This approach exhibits linear complexity relative to the length of the block code and is shown to outperform hard decimation approaches for careful selection of the algorithm parameters. We then combine the approaches in a "soft-hard" BPGD variant, where hard decisions are periodically made and those symbols are permanently fixed throughout the remainder of the decoding process. Simulation results show that further performance improvement can be observed in this case at the cost of increasing the algorithmic complexity.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•1 citation
It was pointed out in [JSW+25] that widely-studied optimization problems such as D-regular max-k-XORSAT can be reduced to decoding of LDPC codes, using quantum algorithms related to Regev's reduction. LDPC codes have very good decoders, such as Belief Propagation (BP), and this therefore makes D-regular max-k-XORSAT an enticing target for this class of quantum algorithms. However, BP was found insufficient to achieve quantum advantage. Here, we develop an intrinsically quantum decoding technique, which decodes classical LDPC codes subject to coherent superpositions of bit flip errors. For average-case instances of D-regular max-k-XORSAT drawn from Gallager's ensemble, this quantum decoder strongly outperforms classical belief propagation at many values of k and D. For some (k,D) the approximate optima achievable using this decoder surpass both Prange's algorithm and simulated annealing. However, we stop short of achieving quantum advantage because we identify an enhancement to Prange's algorithm that recovers a precise tie, much as a precise tie was observed between the standard version of Prange's algorithm and a more limited version of locally-quantum decoding in [CT24].
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.
Classical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular [[9216,4612,≤48]][[9216,4612, \leq 48]][[9216,4612,≤48]] quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as 10−810^{-8}10−8 on the depolarizing channel with error probability 4%4 \%4%.
Quantum error correction is the building block for constructing fault-tolerant quantum processors that can operate reliably even if its constituting elements are corrupted by decoherence. In this context, real-time decoding is a necessity for implementing arbitrary quantum computations on the logical level. In this work, we present a new decoder for Quantum Low Density Parity Check (QLDPC) codes, named the closed-branch decoder, with a worst-case complexity loosely upper bounded by O(nmaxgrmaxbr)\mathcal{O}(n\text{max}_{\text{gr}}\text{max}_{\text{br}})O(nmaxgr​maxbr​), where maxgr\text{max}_{\text{gr}}maxgr​ and maxbr\text{max}_{\text{br}}maxbr​ are tunable parameters that pose the accuracy versus speed trade-off of decoding algorithms. For the best precision, the maxgrmaxbr\text{max}_{\text{gr}}\text{max}_{\text{br}}maxgr​maxbr​ product increases exponentially as ∝djd\propto dj^d∝djd, where ddd indicates the distance of the code and jjj indicates the average row weight of its parity check matrix. Nevertheless, we numerically show that considering small values that are polynomials of the code distance are enough for good error correction performance. The decoder is described to great extent and compared with the Belief Propagation Ordered Statistics Decoder (BPOSD) operating over data qubit, phenomenological and circuit-level noise models for the class of Bivariate Bicycle (BB) codes. The results showcase a promising performance of the decoder, obtaining similar results with much lower complexity than BPOSD when considering the smallest distance codes, but experiencing some logical error probability degradation for the larger ones. Ultimately, the performance and complexity of the decoder depends on the product maxgrmaxbr\text{max}_{\text{gr}}\text{max}_{\text{br}}maxgr​maxbr​, which can be considered taking into account benefiting one of the two aspects at the expense of the other.
Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random qqq-ary LDPC codes over symmetric qqq-ary pure-state channels, where qqq is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength NNN tends to infinity. For regular ensembles with dv≥3d_v\geq3dv​≥3, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-ℓ\ellℓ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable ℓ=Θ(log⁡log⁡N)\ell=Θ(\log\log N)ℓ=Θ(loglogN), a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.
We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.
Due to code degeneracy and the graph structure of quantum low-density parity-check (QLDPC) codes, the performance of conventional belief propagation (BP) decoding can be poor. Recently, belief propagation guided decimation (BPGD) has shown promise to combat these challenges. In this paper, we investigate various decimation approaches to improve the error correcting performance and convergence speed of BPGD. We first consider soft decimation, where the BP equations are modified via several tuneable parameters. This approach exhibits linear complexity relative to the length of the block code and is shown to outperform hard decimation approaches for careful selection of the algorithm parameters. We then combine the approaches in a "soft-hard" BPGD variant, where hard decisions are periodically made and those symbols are permanently fixed throughout the remainder of the decoding process. Simulation results show that further performance improvement can be observed in this case at the cost of increasing the algorithmic complexity.