EUVIMEDEUVIMED entdecken
Crossref

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

Agathe Blanvillain, André Chailloux, Jean-Pierre Tillich

IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 4980-4999

DOI: 10.1109/tit.2026.3689737 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Agathe Blanvillain und 2 weiteren Autor:innen. Gefördert von: French Programmes et Equipements Prioritaires de Recherche (PEPR) all part of plan France 2030 through the Project Etude de la Pile Quantique, Project Post-Quantum TLS : Un Cadenas Quantique Pour les Navigateurs Web, Project Hybrid Quantum Initiative.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 the $l_{\infty } $ 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.

Förderung

  • French Programmes et Equipements Prioritaires de Recherche (PEPR) all part of plan France 2030 through the Project Etude de la Pile Quantique
  • Project Post-Quantum TLS : Un Cadenas Quantique Pour les Navigateurs Web
  • Project Hybrid Quantum Initiative

Zitieren

APA

Blanvillain, A., Chailloux, A., & Tillich, J. (2026). The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction. IEEE Transactions on Information Theory, 72(7), 4980-4999. https://doi.org/10.1109/tit.2026.3689737

Vancouver

Blanvillain A, Chailloux A, Tillich J. The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction. IEEE Transactions on Information Theory. 2026;72(7):4980-4999. doi:10.1109/tit.2026.3689737

BibTeX
@article{Blanvillain2026,
  author = {Blanvillain, Agathe and Chailloux, André and Tillich, Jean-Pierre},
  title = {The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {7},
  pages = {4980--4999},
  doi = {10.1109/tit.2026.3689737}
}
Kostenlos starten →