Résumé IA · arXiv: 2611.14087v1 · cs.IT

Classical Tensor Codes and Quantum Tanner Codes Achieve Capacity on Erasure Channels

Henry D. Pfister, Oscar Sprumont, Gilles Zémor
Article original Soumis à arXiv le 10 Nov. 2026 Licence : CC BY 4.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

L’essentiel

L’article établit que certains produits tensoriels de codes classiques atteignent la capacité d’effacement et construit des codes de Tanner quantiques à décodage linéaire en temps, proches de la capacité.

Question

Le travail étudie si les produits tensoriels de familles de codes classiques capables d’atteindre la capacité conservent cette propriété, notamment après dualisation. Il cherche ensuite à construire des codes de Tanner quantiques décodant près de la capacité du canal d’effacement avec une complexité linéaire.

Méthode

Les auteurs analysent les effacements indépendants et corrélés afin de borner la dimension du sous-code couvert par le motif d’effacement, puis appliquent ces bornes à des codes tensoriels et à leurs duaux. Pour la construction quantique, ils combinent des codes locaux aléatoires de longueur Δ, un complexe de Cayley de degré fixe et un décodage local suivi d’un décodeur correcteur d’erreurs adverses.

Résultats

  • Résultat Sous une condition de décroissance des probabilités d’échec, le produit tensoriel de deux familles atteignant la capacité atteint lui aussi la capacité sur le canal d’effacement.
    Voir le passage dans l’article
    If the families achieve capacity on the erasure channel and have minimum distance $\omega(\log n)$, where $n$ denotes the blocklength, then the tensor family $\mathcal{F}_{0}\otimes\mathcal{F}_{1}$ also achieves capacity on the erasure channel.
  • Résultat Les duaux de produits tensoriels de codes binaires linéaires uniformément aléatoires atteignent la capacité d’effacement.
    Voir le passage dans l’article
    Thus, the duals of random tensor codes achieve vanishing error probability arbitrarily close to capacity (see Theorem 15).
  • Résultat Pour tout ρ entre 0 et 1/2 et tout ε positif, la construction fournit des codes de Tanner quantiques de taux au moins 1−2ρ−ε, avec une probabilité de succès d’au moins 1−2⁻ᵃᴺ et un temps de décodage linéaire.
    Voir le passage dans l’article
    Then there exists positive constants $a,\Delta,N_{0}$ (i.e. depending only on $\rho$ and $\varepsilon$) such that for all $N>N_{0}$, the quantum Tanner code $C_{\rho,\varepsilon,\Delta,N}$ has rate at least $1-2\rho-\varepsilon$ and can decode random quantum erasures of rate $\rho$ with probability
  • Résultat À ρ et ε fixés, les codes construits ont un poids de stabilisateur borné et une distance minimale linéaire en la longueur.
    Voir le passage dans l’article
    For fixed $\rho$ and $\varepsilon$, the degree and the local codes are fixed independently of $N$. The resulting codes have constant stabilizer weights and qubit degrees with minimum distance growing linearly with $N$.
  • Interprétation des auteurs Les auteurs interprètent l’analyse des effacements corrélés comme un outil général pour prouver la capacité des produits tensoriels.
    Voir le passage dans l’article
    We believe such a method to be of independent interest.

Limites

  • Les garanties de taux, de poids borné, de distance et de décodage linéaire reposent sur des paramètres et des codes locaux fixés après le choix de ρ et ε, plutôt que sur une construction uniforme indépendante de ces cibles.
    Voir le passage dans l’article
    For the bounded-check-weight and linear-time claims, the degree $\Delta$, the local codes, and the distance are chosen after the target rate and gap.
  • La construction décrite ne couvre que les probabilités d’effacement strictement inférieures à 1/2.
    Voir le passage dans l’article
    Consider any $\rho\in(0,\frac{1}{2})$ and any $\varepsilon\in(0,1-2\rho)$.

Portée

Les auteurs montrent que les produits tensoriels et leurs duaux peuvent fournir les codes locaux nécessaires à une construction de Tanner quantique proche de la capacité d’effacement. Leur résultat associe cette proximité à une distance linéaire, des poids de stabilisateur bornés et un décodage garanti en temps linéaire.

Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.

Mots clés générés par l'IA : codes correcteurs quantiques canal à effacements codes de Tanner produits tensoriels décodage en temps linéaire

Pour aller plus loin

  • Résumé Complet
  • Résumé vulgarisé
  • Article de blog
  • Abstract original
Cet article étudie la construction de codes correcteurs capables d’approcher la capacité des canaux à effacements. Pour un canal quantique à effacements de probabilité \(\rho\), cette capacité vaut \(1-2\rho\), tant que \(\rho<1/2\). Les auteurs cherchent à atteindre ce taux avec des codes de Tanner quantiques qui conservent des contrôles de poids borné et permettent un décodage en temps linéaire, contrairement aux méthodes qui approchent la capacité sans garantir un tel temps de décodage. Le travail établit d’abord un résultat classique sur les produits tensoriels de codes. Les auteurs montrent que si deux familles de codes atteignent la capacité du canal classique à effacements, leur famille de produits tensoriels l’atteint également, sous certaines hypothèses de décroissance de l’erreur et, dans le théorème général, de distances minimales supérieures à l’ordre de \(\log n\). L’idée consiste à représenter les effacements comme la combinaison de deux motifs indépendants, puis à comparer leurs effets à ceux de motifs corrélés le long des lignes ou des colonnes. Une inégalité portant sur la dimension des sous-codes couverts permet d’analyser un décodeur en deux étapes : le décodage s’effectue d’abord selon une dimension du tableau, puis selon l’autre. La borne obtenue pour la probabilité d’échec dépend des probabilités d’erreur des codes constitutifs. Pour des codes de longueur \(n\), elle est au plus égale à \(n^3\) fois l’erreur du premier code, plus \(n^2\) fois celle du second. Les auteurs démontrent également que les duaux de produits tensoriels de codes linéaires binaires aléatoires uniformes atteignent la capacité classique. Cette étape est plus délicate, car elle exige de contrôler les petits mots de code qui pourraient être entièrement effacés. La preuve combine l’expansion des produits tensoriels, les propriétés de robustesse des codes aléatoires et des bornes sur la dimension des sous-codes couverts. Pour les codes duaux considérés, dont les taux constitutifs sont déterminés par \(\rho_1\) et \(\rho_2\), la probabilité d’échec tend vers zéro lorsque la probabilité d’effacement se rapproche de la limite de capacité. L’écart à cette limite est de l’ordre de \(n^{-1/2+3\nu/2}\), et la probabilité d’échec est bornée par \(4n^{-\nu/2}\), pour \(0<\nu<1/3\). Ces résultats classiques fournissent les petits codes locaux nécessaires à la construction quantique. Les auteurs intègrent ces codes dans un complexe carré de Cayley quadripartite, où quatre types de contraintes locales sont agencés de façon à garantir la commutation des contrôles \(X\) et \(Z\). Les taux des codes locaux sont volontairement asymétriques : certaines contraintes sont concentrées sur les vues locales où le décodage initial est le plus utile, tandis que d’autres sont choisies avec un taux très faible ou très proche de un. Après ce décodage local, un décodeur existant, capable de corriger un nombre borné d’erreurs adversariales, traite les erreurs résiduelles.

Cette synthèse vous a-t-elle été utile ?

Note : 0

Pourquoi avons-nous besoin de votes ?

Les votes sont utilisés pour déterminer si nous devons réexécuter nos outils de synthèse. Si le compte atteint -10, nos outils peuvent être redémarrés.

Figures et graphiques

Posez une question sur une figure en indiquant son numéro ou en utilisant son bouton de question pour demander une analyse visuelle. Au maximum deux figures et quatre panneaux par question. Les valeurs lues sur les graphiques sont approximatives ; vérifiez les données originales.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 1 réécriture gratuite restante aujourd'hui
Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Continuer avec Google Créer un compte gratuit Se connecter

Outils avancés Premium

Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium

Zotero Guide Zotero
Alertes de citation Guide des alertes de citations
Qui travaille dessus ?

Parmi les 23 articles autour de celui-ci, le nom qui revient le plus : Anthony Leverrier (5 articles)

6 autres personnes en signent plusieurs. La carte complète ajoute leurs institutions et leurs approches, d’après les articles des dernières années.

Continuer avec Google Créez un compte gratuit : votre première carte est offerte
Lettre hebdomadaire Présenté dans « Informatique hors IA cette semaine » du 16 novembre 2026. Informatique hors IA cette semaine : les coûts cachés des réseaux et les limites repoussées des algorithmes · En recevoir une par email gratuitement

Les articles autour de celui-ci

Les voir sur une carte

Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.

Les articles les plus proches

  1. Très proche Autre approche du problème Cité par cet article
    Efficient Decoding up to a Constant Fraction of the Code Length for Asymptotically Good Quantum Codes
    Anthony Leverrier, Gilles Z'emor · 2022 · Electron. Colloquium Comput. Complex. · cité 51 fois · Pas encore résumé

    Efficient Decoding up to a Constant Fraction of the Code Length for Asymptotically Good Quantum Codes décode les codes de Tanner quantiques contre des erreurs adverses, tandis que cet article vise les effacements proches de la capacité.

    Résumé scientifique

    We introduce and analyse an efficient decoder for quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight \(O(\sqrt{n\log n})\) . We also work on the link between quantum Tanner codes and the lifted product codes of Panteleev and Kalachev and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.

  2. Très proche Autre approche du problème Cité par cet article Utilisé en profondeur par cet article
    Decoding Quantum Tanner Codes
    Anthony Leverrier, Gilles Zémor · 2022 · IEEE Transactions on Information Theory · cité 49 fois · Pas encore résumé

    Decoding Quantum Tanner Codes corrige des erreurs adverses linéaires sur des codes de Tanner quantiques, alors que cet article construit un décodeur linéaire pour le canal d’effacement.

    Résumé scientifique

    We introduce sequential and parallel decoders for quantum Tanner codes. When the Tanner code construction is applied to a sufficiently expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. In this case, our decoders provably correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. The same decoders are easily adapted to the expander lifted product codes of Panteleev and Kalachev. Along the way, we exploit recently established bounds on the robustness of random tensor codes to give a tighter bound on the minimum distance of quantum Tanner codes.

  3. Très proche Même question Cité par cet article
    Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel
    S. Lloyd, P. Shor, Kevin Thompson · 2017 · IEEE Transactions on Information Theory · cité 4 fois · Pas encore résumé

    Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel construit des codes quantiques clairsemés proches de la capacité d’effacement, comme cet article, mais avec des contraintes de poids polylogarithmiques.

    Résumé scientifique

    We provide polylog sparse quantum codes for correcting the Erasure channel arbitrarily close to the capacity. Specifically, we provide the <inline-formula> <tex-math notation="LaTeX">$[[n, k, d]]$ </tex-math></inline-formula> quantum stabilizer codes that correct for the erasure channel arbitrarily close to the capacity if the erasure probability is at least 0.33 and with a generating set <inline-formula> <tex-math notation="LaTeX">$\langle S_{1}, S_{2}, \cdots {} S_{n-k} \rangle $ </tex-math></inline-formula> such that <inline-formula> <tex-math notation="LaTeX">$|S_{i}|\leq {\mathrm{ log}} ^{2+\zeta }(n)$ </tex-math></inline-formula> for all <inline-formula> <tex-math notation="LaTeX">$i$ …

  4. Proche Contexte plus large
    Optimal Interleavers for Classical and Quantum Tensor Product Codes
    P. Nadkarni, S. Garani · 2021 · IEEE Communications Letters · cité 1 fois · Pas encore résumé

    Optimal Interleavers for Classical and Quantum Tensor Product Codes étudie les rafales d’effacements et les entrelaceurs de codes produits tensoriels, plutôt que leur capacité asymptotique.

    Résumé scientifique

    By exploiting the subblock structure of a tensor product code, we provide an upper bound on the maximum correctable burst length of tensor product codes used with interleavers designed based on only the minimum distance and the maximum correctable burst length of its component codes, without taking the specific code geometry and soft decoding into consideration. We provide necessary and sufficient conditions for an interleaver to achieve this upper bound. Further, for two cases of the tensor product codes, we design optimal intracodeword interleavers that satisfy the proposed conditions.

  5. Proche Base de cet article Cité par cet article
    Capacities of Quantum Erasure Channels
    Charles H. Bennett, D. Divincenzo, J. Smolin · 1997 · Physical Review Letters · cité 362 fois · Pas encore résumé

    Capacities of Quantum Erasure Channels établit les capacités du canal d’effacement quantique, référence théorique pour la construction de codes visant le débit 1−2ρ.

    Résumé scientifique

    The quantum analog of the classical erasure channel provides a simple example of a channel whose asymptotic capacity for faithful transmission of intact quantum states, with and without the assistance of a two-way classical side channel, can be computed exactly. We derive the quantum and classical capacities for the quantum erasure channel and related channels, and compare them to the depolarizing channel, for which only upper and lower bounds on the capacities are known.

  6. Proche Base de cet article Cité par cet article
    Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel
    Nicolas Delfosse, G. Zémor · 2012 · Quantum information & computation · cité 41 fois · Pas encore résumé

    Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel borne le débit des codes stabilisateurs clairsemés sur le canal d’effacement, fournissant un repère aux constructions proches de la capacité.

    Résumé scientifique

    Using combinatorial arguments, we determine an upper bound on achievable rates of stabilizer codes used over the quantum erasure channel. This allows us to recover the no-cloning bound on the capacity of the quantum erasure channel, R is below 1-2p, for stabilizer codes: we also derive an improved upper bound of the form : R is below 1-2p-D(p) with a function D(p) that stays positive for 0 < p < 1/2 and for any family of stabilizer codes whose generators have weights bounded from above by a constant - low density stabilizer codes. We obtain an application to percolation theory for a family of self-dual tilings of the hyperbolic plane. We associate a family of low density stabilizer codes wit…

  7. Proche* Base de cet article
    Degenerate quantum codes and the quantum channel capacity problem
    Graeme Smith, J. Smolin · 2008 · 2008 IEEE Information Theory Workshop · Pas encore résumé

    Degenerate quantum codes and the quantum channel capacity problem traite de la capacité des canaux quantiques et des codes dégénérés, mais son résumé n’indique pas de méthode précise.

  8. Proche Même question
    Fidelity of Finite Length Quantum Codes in Qubit Erasure Channel
    A. Ashikhmin · 2020 · International Symposium on Information Theory · cité 5 fois · Pas encore résumé

    Fidelity of Finite Length Quantum Codes in Qubit Erasure Channel analyse les erreurs de décodage de codes quantiques sous effacements, avec des bornes à longueur finie plutôt qu’une construction asymptotique.

    Résumé scientifique

    We consider the probability of decoding error, equivalently the fidelity, of finite length quantum codes assuming quantum information transmission via qubit erasure channel. First, we obtain an analytical expression on this probability via combinatorial invariants of quantum codes. Next, we derive a generalization of the MacWilliams identities for those invariants and use them to formulate a linear programming optimization problem, which allows us to obtain lower bounds on the number of unrecoverable sets of i erasures and the probability of decoding error. Our example shows that the obtain bounds can be very tight. Next, we derive upper (achievability) bounds on the probability of decoding …

Les travaux antérieurs sur lesquels il s’appuie

  1. Proche Base de cet article
    Good Quantum LDPC Codes with Linear Time Decoders
    Irit Dinur, Min-Hsiu Hsieh, Ting Lin et al. · 2022 · Symposium on the Theory of Computing · cité 231 fois · Pas encore résumé

    Good Quantum LDPC Codes with Linear Time Decoders construit des codes quantiques LDPC par un complexe de Cayley et des codes locaux aléatoires, ingrédients repris pour les codes de Tanner quantiques.

    Résumé scientifique

    We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain (2m× m)V →δ0 (2m)E →δ1 2F where V (X-checks) are the vertices, E (qubits) are the edges, and F (Z-checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes CA,CB:2m→2Δ where Δ is the regularity of the underlying Cayley graphs. One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

  2. Proche Contexte plus large
    Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
    Adar Avsian, F. G. Jeronimo, Abhi Shukul · 2026 · arXiv.org · preprint, non relu par les pairs · cité 1 fois · Pas encore résumé

    Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time vise le décodage en liste près de la capacité pour des codes quantiques LDPC, plutôt que le décodage d’effacements.

    Résumé scientifique

    In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achiev…

  3. Proche Base de cet article
    Two-sided Robustly Testable Codes
    G. Kalachev, P. Panteleev · 2022 · arXiv.org · preprint, non relu par les pairs · cité 17 fois · Pas encore résumé

    Two-sided Robustly Testable Codes établit la robustesse de produits tensoriels de codes aléatoires, propriété liée aux constructions de codes quantiques LDPC utilisées ici.

    Résumé scientifique

    We show that the tensor product of two random linear codes is robustly testable with high probability. This implies that one can obtain pairs of linear codes such that their product and the product of their dual codes are simultaneously robustly testable. Such two-sided robustly testable codes (with a much weaker form of robustness) were the key ingredient in the recent constructions of asymptotically good quantum LDPC codes, which ensured their linear minimum distance. We hope that the existence of such codes with a stronger form of robustness, shown here, can be used to simplify the proofs and provide better distance bounds in these constructions. We also give new very simple examples of n…

  4. Proche Autre approche du problème
    Stabilizer-Assisted Inactivation Decoding of Quantum Error-Correcting Codes with Erasures
    Giulio Pech, Mert Gökduman, Hanwen Yao et al. · 2026 · International Symposium on Information Theory · cité 5 fois · Pas encore résumé

    Stabilizer-Assisted Inactivation Decoding of Quantum Error-Correcting Codes with Erasures décode les effacements de codes QLDPC par inactivation et élimination duale, tandis que cet article propose un décodeur linéaire pour ses codes de Tanner.

    Résumé scientifique

    We present a maximum-likelihood (ML) decoder with reduced complexity for quantum low-density parity-check (QLDPC) codes on the quantum erasure channel. Our decoder combines classical inactivation decoding, which integrates peeling with symbolic guessing, with a new dual peeling procedure. In the dual peeling stage, we perform row operations on the stabilizer matrix to efficiently reveal stabilizer generators and their linear combinations whose support lies entirely on the erased set. Each such stabilizer identified allows us to freely fix a bit in its support without affecting the logical state of the decoded result. This removes a degree of freedom that would otherwise require a symbolic gu…

  5. Proche Contexte plus large
    Maximally Extendable Product Codes are Good Coboundary Expanders
    G. Kalachev, P. Panteleev · 2025 · IEEE Annual Symposium on Foundations of Computer Science · cité 16 fois · Pas encore résumé

    Maximally Extendable Product Codes are Good Coboundary Expanders étudie l’expansion des produits tensoriels de codes, propriété pertinente aux constructions de codes quantiques LDPC.

    Résumé scientifique

    We investigate the coboundary expansion property of tensor product codes, known as product expansion, which plays an important role in recent constructions of good quantum LDPC codes and classical locally testable codes. Prior research has shown that this property is equivalent to agreement testability and robust testability for products of two codes with linear distance. However, for products of more than two codes, product expansion is a strictly stronger property. In this paper, we prove that a collection of an arbitrary number of random codes over a sufficiently large field has good product expansion. We believe that, in the case of four codes, the same ideas can be used to construct goo…

Comment ces articles sont-ils trouvés ?

Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.

Mis à jour le 16 novembre 2026.

Le guide illustré des articles autour d’un article

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.