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• 10 citations• Revised Jul 2, 2026 (v2)
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 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•3 citations

Decoding of LDPC quantum codes

Lucien Grouès

Décodage de codes quantiques LDPC Afin de pouvoir réaliser des calculs utiles grâce à des ordinateurs quantiques nous devons rendre l’information quantique plus robuste contre le bruit. Une approche prometteuse repose sur l’utilisation de code quantiques LDPC, qui nécessitent d’être associés à un décodeur. Dans cette thèse nous étudions le décodage de codes quantiques LDPC, et en particulier de codes produits d’hypergraphes, par diverse décodeurs. Nous commençons par étudier un décodeur focalisé sur les performances et obtenus en combinant deux décodeurs existants, BP et SSF. Nous montrons par des simulations que ses performances sont meilleurs que celles de chacun des deux décodeurs seuls sur des codes produits d’hypergraphes aléatoires. Nous nous concentrons ensuite sur un décodeur plus simple à analyser et ayant des garanties théoriques intéressantes, en continuant l’importation du décodeur LP qu cas quantiques, travail entamé par Li et Vontobel. Nous réussissons à prouver des résultats négatifs limitant les performances asymptotiques du décodeur sur plusieurs codes quantiques LDPC, tout en obtenant de bons résultats sur des codes produits d’hypergraphes de tailles réalistes. Enfin nous étudions le décodage local de codes quantiques LDPC, et plus particulièrement nous analysons par des simulations les performances de l’implémentation la plus rapide et la plus locale de SSF.

•Dec 19, 2022•0 citations

Performance of ML decoding for ensembles of binary and nonbinary regular LDPC codes of finite lengths

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek

The Gallager ensembles of binary regular LDPC codes and binary images of nonbinary regular LDPC codes are studied. Recurrent procedure for computing average spectra for these two ensembles is presented. By using the existing bounding techniques, estimates on the error probability of the maximum-likelihood (ML) decoding over an AWGN channel with BPSK signaling for short codes from different ensembles of LDPC codes are obtained. The numerical results show performance of the ML decoding for different code ensembles. Conclusions drawn based on the average code spectra are then verified by near-ML decoding simulations for both randomly selected and the best known short codes. The asymptotic ML decoding thresholds for AWGN and BSC channels are calculated. As expected, codes with the ML decoding performance superior to that of the average code in the ensemble, are easy to find. However, comparison of the the presented results with simulation results for belief propagation (BP) decoding shows that the ML decoding performance should not be used as a target for searching for good iteratively decodable codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•9 citations

Decoding Quasi-Cyclic Quantum LDPC Codes

Louis Golowich, Venkatesan Guruswami

Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.

arXiv:2411.04464•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•3 citations

Efficient Message-Passing Decoding of Quantum LDPC Codes

Julien Du Crest

Décodage efficace de codes quantiques LDPC par passage de messages Pour construire un ordinateur quantique, il est nécessaire de corriger au fur et a mesure les erreurs qui se produisent au cours du calcul, qui, si elles s’accumulent, risquent de biaiser le résultat. Ces erreurs s’accumulent pour deux raisons, premièrement car les technologies utilisées aujourd’hui et dans un futur proche sont encore immatures, et deuxièmement, a cause d’un principe fondamental de la physique quantique, le principe d’incertitude de Hilbert. A cause des contraintes liées aux lois de la physique quantique, les méthodes utilisées pour protéger l’information quantique du bruit sont différentes en quantique comparé au classique. Par exemple, il n’est pas possible de faire des “sauvegardes” régulières sur un ordinateur quantique, a cause du Théorème de non-clonage qui stipule qu’il est impossible de copier parfaitement un état quantique.Par chance, il s’avère que la théorie de la correction d’erreur, utilisée de manière classique surtout dans les communications et le stockage d’information, trouve ici une application pour le calcul tolérant aux fautes.Parmi les nombreux problèmes liés a l’utilisation de cette belle et riche théorie pour le calcul tolérant aux fautes en quantique, dans la suite, nous nous intéresserons seulement à la question du décodage par passage de messages des codes LDPC. Dans la suite, je discuterai d’abord les limitations théoriques et pratique d’un certain type de décodeur par passage de message, le Min-Sum appliqué au code torique, un code pressenti pour être utilisé dans la première génération d’ordinateurs quantiques. Ensuite, je montrerai comment les performances pratiques des décodeurs par passage de message peuvent être grandement améliorées en utilisant des post-processings spécifiques aux codes quantiques.

•Nov 4, 2024•0 citations

Evaluation of LDPC decoder with standardized codes

Jun Zhao

Low density parity check (LDPC) codes are one of the most popular channel codes.Based on traditional sum-product and max-product algorithms, various modified algorithms are tried to improve the performance of LDPC codes in terms of error rate, complexity and latency.Uniformly rweighted belief propagation (URW-BP) algorithm can offer better performance than traditional algorithm especially for regular LDPC codes.linear programming (LP) decoder is also competitive to traditional message passing algorithm.We describe two traditional message passing decoders, four reweighted message passing decoders based on URW-BP and LP decoder in this paper.Reweighted decoders can outperform traditional decoders especially when iteration number is limited.Considering complexity and latency, reweighted max product decoder of version 2 (R-MPD-II) is the most promising decoder.CONTENTS 4.3 Short regular LDPC codes . . . . . . . .

•Jan 1, 2012•0 citations
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].
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.
Décodage de codes quantiques LDPC Afin de pouvoir réaliser des calculs utiles grâce à des ordinateurs quantiques nous devons rendre l’information quantique plus robuste contre le bruit. Une approche prometteuse repose sur l’utilisation de code quantiques LDPC, qui nécessitent d’être associés à un décodeur. Dans cette thèse nous étudions le décodage de codes quantiques LDPC, et en particulier de codes produits d’hypergraphes, par diverse décodeurs. Nous commençons par étudier un décodeur focalisé sur les performances et obtenus en combinant deux décodeurs existants, BP et SSF. Nous montrons par des simulations que ses performances sont meilleurs que celles de chacun des deux décodeurs seuls sur des codes produits d’hypergraphes aléatoires. Nous nous concentrons ensuite sur un décodeur plus simple à analyser et ayant des garanties théoriques intéressantes, en continuant l’importation du décodeur LP qu cas quantiques, travail entamé par Li et Vontobel. Nous réussissons à prouver des résultats négatifs limitant les performances asymptotiques du décodeur sur plusieurs codes quantiques LDPC, tout en obtenant de bons résultats sur des codes produits d’hypergraphes de tailles réalistes. Enfin nous étudions le décodage local de codes quantiques LDPC, et plus particulièrement nous analysons par des simulations les performances de l’implémentation la plus rapide et la plus locale de SSF.
The Gallager ensembles of binary regular LDPC codes and binary images of nonbinary regular LDPC codes are studied. Recurrent procedure for computing average spectra for these two ensembles is presented. By using the existing bounding techniques, estimates on the error probability of the maximum-likelihood (ML) decoding over an AWGN channel with BPSK signaling for short codes from different ensembles of LDPC codes are obtained. The numerical results show performance of the ML decoding for different code ensembles. Conclusions drawn based on the average code spectra are then verified by near-ML decoding simulations for both randomly selected and the best known short codes. The asymptotic ML decoding thresholds for AWGN and BSC channels are calculated. As expected, codes with the ML decoding performance superior to that of the average code in the ensemble, are easy to find. However, comparison of the the presented results with simulation results for belief propagation (BP) decoding shows that the ML decoding performance should not be used as a target for searching for good iteratively decodable codes.
Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.
Décodage efficace de codes quantiques LDPC par passage de messages Pour construire un ordinateur quantique, il est nécessaire de corriger au fur et a mesure les erreurs qui se produisent au cours du calcul, qui, si elles s’accumulent, risquent de biaiser le résultat. Ces erreurs s’accumulent pour deux raisons, premièrement car les technologies utilisées aujourd’hui et dans un futur proche sont encore immatures, et deuxièmement, a cause d’un principe fondamental de la physique quantique, le principe d’incertitude de Hilbert. A cause des contraintes liées aux lois de la physique quantique, les méthodes utilisées pour protéger l’information quantique du bruit sont différentes en quantique comparé au classique. Par exemple, il n’est pas possible de faire des “sauvegardes” régulières sur un ordinateur quantique, a cause du Théorème de non-clonage qui stipule qu’il est impossible de copier parfaitement un état quantique.Par chance, il s’avère que la théorie de la correction d’erreur, utilisée de manière classique surtout dans les communications et le stockage d’information, trouve ici une application pour le calcul tolérant aux fautes.Parmi les nombreux problèmes liés a l’utilisation de cette belle et riche théorie pour le calcul tolérant aux fautes en quantique, dans la suite, nous nous intéresserons seulement à la question du décodage par passage de messages des codes LDPC. Dans la suite, je discuterai d’abord les limitations théoriques et pratique d’un certain type de décodeur par passage de message, le Min-Sum appliqué au code torique, un code pressenti pour être utilisé dans la première génération d’ordinateurs quantiques. Ensuite, je montrerai comment les performances pratiques des décodeurs par passage de message peuvent être grandement améliorées en utilisant des post-processings spécifiques aux codes quantiques.
Low density parity check (LDPC) codes are one of the most popular channel codes.Based on traditional sum-product and max-product algorithms, various modified algorithms are tried to improve the performance of LDPC codes in terms of error rate, complexity and latency.Uniformly rweighted belief propagation (URW-BP) algorithm can offer better performance than traditional algorithm especially for regular LDPC codes.linear programming (LP) decoder is also competitive to traditional message passing algorithm.We describe two traditional message passing decoders, four reweighted message passing decoders based on URW-BP and LP decoder in this paper.Reweighted decoders can outperform traditional decoders especially when iteration number is limited.Considering complexity and latency, reweighted max product decoder of version 2 (R-MPD-II) is the most promising decoder.CONTENTS 4.3 Short regular LDPC codes . . . . . . . .