Resume : Ce memoire porte sur l’etude de la complexite
du probleme du decodage des codes stabilisateurs quantiques. Les
trois premiers chapitres introduisent les notions necessaires pour
comprendre notre resultat principal. D’abord, nous rappelons les
bases de la theorie de la complexite et illustrons les concepts qui
s’y rattachent a l’aide d’exemples tires de la physique. Ensuite,
nous expliquons le probleme du decodage des codes correcteurs
classiques. Nous considerons les codes lineaires sur le canal
binaire symetrique et nous discutons du celebre resultat de
McEliece et al. [1].
Dans le troisieme chapitre, nous etudions le
probleme de la communication quantique
sur des canaux de Pauli.
Dans ce chapitre, nous introduisons le formalisme des codes
stabilisateurs pour etudier la correction d’erreur quantique et
mettons en evidence le concept de degenerescence. Le probleme de
decodage des codes stabilisateurs quantiques negligeant la
degenerescence est appele «quantum maximum likelihood
decoding»(QMLD). Il a ete demontre que ce probleme est NP-complet
par Min Hseiu Heish et al., dans [2]. Nous nous concentrons sur la
strategie optimale de decodage, appelee «degenerate quantum maximum
likelihood decoding »(DQMLD), qui prend en compte la presence de la
degenerescence et nous mettons en evidence quelques instances pour
lesquelles les performances de ces deux methodes
different
drastiquement. La contribution principale de ce memoire est de
prouver que DQMLD est considerablement plus difficile que ce que
les resultats precedents indiquaient. Dans le dernier chapitre,
nous presentons notre resultat principal (Thm. 5.1.1), etablissant
que DQMLD estP-complet. Pour le prouver, nous demontrons que le
probleme de l’evaluation de l’enumerateur de poids d’un code
lineaire, qui est #P-complet, se reduit au probleme DQMLD. Le
resultat principal de ce memoire est presente sous forme d’article
dans [3] et est presentement considere pour publication dans IEEE
Transactions on Information Theory. Nous montrons egalement que,
sous certaines conditions, les resultats de QMLD et DQMLD
coincident. Il s’agit d’une amelioration par rapport aux resultats
obtenus dans [4, 5]. // Abstract : This thesis deals with the study
of computational complexity of decoding stabilizer codes. The first
three chapters contain all the necessary background to understand
the main result of this thesis. First, we explain the necessary
notions in computational complexity, introducing P, NP, #P classes
of problems, along with some examples intended for physicists.
Then, we explain the decoding problem in classical error
correction, for linear codes on the binary symmetric channel and
discuss the celebrated result of Mcleicee et al., in [1]. In the
third chapter, we study the problem of quantum communication, over
Pauli channels. Here, using the stabilizer formalism, we discuss
the concept of degenerate errors. The decoding problem for
stabilizer codes, which simply neglects the presence of degenerate
errors, is called quantum maximum likelihood decoding (QMLD)…
Resume : Ce memoire porte sur l’etude de la complexite
du probleme du decodage des codes stabilisateurs quantiques. Les
trois premiers chapitres introduisent les notions necessaires pour
comprendre notre resultat principal. D’abord, nous rappelons les
bases de la theorie de la complexite et illustrons les concepts qui
s’y rattachent a l’aide d’exemples tires de la physique. Ensuite,
nous expliquons le probleme du decodage des codes correcteurs
classiques. Nous considerons les codes lineaires sur le canal
binaire symetrique et nous discutons du celebre resultat de
McEliece et al. [1].
Dans le troisieme chapitre, nous etudions le
probleme de la communication quantique
sur des canaux de Pauli.
Dans ce chapitre, nous introduisons le formalisme des codes
stabilisateurs pour etudier la correction d’erreur quantique et
mettons en evidence le concept de degenerescence. Le probleme de
decodage des codes stabilisateurs quantiques negligeant la
degenerescence est appele «quantum maximum likelihood
decoding»(QMLD). Il a ete demontre que ce probleme est NP-complet
par Min Hseiu Heish et al., dans [2]. Nous nous concentrons sur la
strategie optimale de decodage, appelee «degenerate quantum maximum
likelihood decoding »(DQMLD), qui prend en compte la presence de la
degenerescence et nous mettons en evidence quelques instances pour
lesquelles les performances de ces deux methodes
different
drastiquement. La contribution principale de ce memoire est de
prouver que DQMLD est considerablement plus difficile que ce que
les resultats precedents indiquaient. Dans le dernier chapitre,
nous presentons notre resultat principal (Thm. 5.1.1), etablissant
que DQMLD estP-complet. Pour le prouver, nous demontrons que le
probleme de l’evaluation de l’enumerateur de poids d’un code
lineaire, qui est #P-complet, se reduit au probleme DQMLD. Le
resultat principal de ce memoire est presente sous forme d’article
dans [3] et est presentement considere pour publication dans IEEE
Transactions on Information Theory. Nous montrons egalement que,
sous certaines conditions, les resultats de QMLD et DQMLD
coincident. Il s’agit d’une amelioration par rapport aux resultats
obtenus dans [4, 5]. // Abstract : This thesis deals with the study
of computational complexity of decoding stabilizer codes. The first
three chapters contain all the necessary background to understand
the main result of this thesis. First, we explain the necessary
notions in computational complexity, introducing P, NP, #P classes
of problems, along with some examples intended for physicists.
Then, we explain the decoding problem in classical error
correction, for linear codes on the binary symmetric channel and
discuss the celebrated result of Mcleicee et al., in [1]. In the
third chapter, we study the problem of quantum communication, over
Pauli channels. Here, using the stabilizer formalism, we discuss
the concept of degenerate errors. The decoding problem for
stabilizer codes, which simply neglects the presence of degenerate
errors, is called quantum maximum likelihood decoding (QMLD)…
La correction d'erreur fera partie intégrante de toute technologie d'information quantique. Diverses méthodes de correction d'erreurs quantiques ont par conséquent été élaborées pour pallier les erreurs inévitables qui proviennent de la manipulation des qubits ainsi que de leur interaction inévitable avec l'environnement. Parmi les familles de codes de correction d'erreurs se trouvent les codes convolutifs, dont l'utilité envisagée est surtout pour protéger l'information quantique envoyée à travers un canal de communication bruyant. La méthode de décodage des codes convolutifs utilise des algorithmes d'estimation d'erreur basés sur un principe de maximum de vraisemblance. L'algorithme de Viterbi permet de déterminer ce maximum de vraisemblance de façon efficace. Cette méthode permet de trouver le mot code le plus probable et ce en utilisant des outils telle décodage par trellis. De plus, cet algorithme a une complexité linéaire avec le nombre de qubits encodés. Ce mémoire porte sur l'effet de la dégénérescence sur le décodage Viterbi. La dégénérescence est une propriété de lamécanique quantique ne possédant aucun analogue classique par laquelle des corrections distinctes peuvent corriger une erreur donnée. Les versions précédentes de décodage quantique suivant l'algorithme de Viterbi étaient sous-optimales parce qu'elles ne tenaient pas compte de la dégénérescence. La réalisation principale de ce mémoire est la conception d'un algorithme de décodage de Viterbi qui tient compte des erreurs dégénérées et nous les testons par des simulations numériques. Ces simulations démontrent qu'il y a effectivement un avantage à utiliser le décodeur Viterbi qui tient compte de la dégénérescence.
Le problème de décodage quantique : bornes d'atteignabilité et applications à la recherche de mots de code courts Cette thèse repose sur le concept de cryptographie post-quantique, qui a pour objectif de concevoir des cryptosystèmes résistants aux attaques classiques et quantiques. Nous nous concentrons ici sur le problème de décodage (DP) et le problème du court mot de code (SCP) en cryptographie à base de codes. Nous allons étudier comment des algorithmes quantiques peuvent exploiter la structure de ces problèmes. Dans une première partie, nous avons généralisé la borne informationnelle d'atteignabilité du problème de décodage quantique à toutes les distributions de bruit sans mémoire. En combinant ce résultat avec la réduction quantique de Regev, on obtient un algorithme quantique qui échantillonne des mots du code dual dont le poids approche le minimum à la limite d'atteignabilité. Dans un second temps, nous formulons un cadre général pour adapter à la théorie des codes la réduction du problème Learning With Errors (LWE) au problème Extrapolated Dihedral Coset Problem (EDCP). Nous étudions ce cadre dans le cas de la métrique de Hamming binaire et montrons que le régime de paramètres obtenu peut déjà être décodé classiquement en temps polynomial.
Étude de codes LDPC quantiques et de leur décodage Les codes quantiques de type LDPC (Low-Density Parity-Check, à matrice de parité creuse) offrent une solution prometteuse pour protéger l’information quantique contre les erreurs et sont donc considérés comme une étape importante dans la réalisation à grande échelle d’un ordinateur quantique tolérant aux fautes. Dans cette thèse, nous étudions les codes LDPC quantiques selon trois approches différentes, en analysant le décodage par renormalisation du code torique de Kitaev, en établissant des limites sur la distance minimale des codes géométriquement locaux et en construisant de petits exemples de codes de Tanner quantiques. Le code torique de Kitaev est un code LDPC quantique remarquable et est actuellement le plus largement considéré pour une mise en œuvre expérimentale. Nous examinons les décodeurs par renormalisation probabiliste introduits par Duclos-Cianci et Poulin, une famille de décodeurs qui offrent l’un des meilleurs compromis entre précision et rapidité. Nous étudions la manière dont ils gèrent les erreurs adverses en introduisant un décodeur par renormalisation déterministe, n’utilisant pas les probabilités a priori du modèle d’erreur. Nous constatons que ce décodeur par renormalisation admet des motifs d’erreurs incorrigibles de type fractal et nous obtenons une borne inférieure sur le poids de ces erreurs. En raison de contraintes physiques, une grande attention a été accordée aux codes LDPC quantiques dont les stabilisateurs n’agissent que sur un nombre limité de qubits voisins. Nous étendons la fameuse borne de Bravyi-Terhal aux codes quantiques définis par des contraintes locales sur un quotient de réseau, fournissant ainsi un aperçu essentiel des limites des codes stabilisateurs géométriquement locaux. En guise d’application, nous fournissons des bornes supérieures sur la distance minimale de codes à deux blocs construits à l’aide d’une algèbre d’un groupe abélien, une famille de codes LDPC quantiques pour laquelle la distance minimale est actuellement inconnue. Ces dernières années, des codes LDPC quantiques asymptotiquement bons ont été construits, mais les résultats démontrables concernant leurs distances minimales ne s’appliquent qu’à des codes trop longs pour être utilisables. Dans le cadre des efforts visant à concevoir des codes pouvant être mis en œuvre à court terme, nous construisons des instances courtes de codes quantiques de Tanner à l’aide de complexes carrés obtenus à partir de produits liftés de graphes réguliers. Plusieurs instances explicites de ces codes présentent des distances minimales dépassant la racine carrée de la longueur du code.
Codes Polaires Quantiques Dans la théorie de l'information classique, les codes polaires sont la première construction explicite d'une famille de codes correcteurs d’erreurs qui atteignent la capacité de n'importe quel canal classique, discret sans mémoire. Dans cette thèse, nous nous intéressons aux généralisations des codes polaires au cas des canaux quantiques. Nous commençons par passer en revue une construction de type Calderbank-Shor-Steane (CSS) des codes polaires pour les canaux quantiques opérant sur des systèmes de dimension 2 (qubits). Cette construction exploite le phénomène de polarisation classique à la fois en base de phase et en base d’amplitude. Nous proposons ensuite une approche différente, qui s’intéresse à un phénomène de polarisation quantique. Ainsi, le premier théorème important de cette thèse prouve une « polarisation purement quantique » des canaux quantiques opérant sur des systèmes de dimension supérieure ou égale à 2 (qudits). Ce phénomène de polarisation permet de synthétiser des canaux dits « virtuels », qui ont tendance à être soit complètement débruités, soit complètement bruités, en tant que canaux quantiques, et pas seulement en une base. Il utilise une opération dite de « combinaison » de deux canaux quantiques, définie par une opération à deux qudits, opérant sur les entrées des deux canaux, et choisie de manière aléatoire dans un ensemble fini d’opérations. Profitant de ce phénomène de polarisation, nous construisons un code quantique efficace assisté par enchevêtrement, où les canaux complètement bruités sont figés en prenant en entrée la moitié d'une paire EPR pré-partagée entre l'encodeur et le décodeur. Nous montrons que la construction proposée permet d’atteindre un taux de communication d’information quantique égal à la capacité symétrique du canal quantique pour communication assistée par enchevêtrement. De plus, en enchaînant plusieurs codes polaires quantiques, nous proposons un schéma de codage qui utilise les paires EPR pré-partagées comme catalyseur, de sorte que le taux d'enchevêtrement pré-partagé s'annule asymptotiquement.Par la suite, nous nous concentrons sur une importante famille de canaux quantiques appelés canaux de Pauli, opérant sur des qubits. Etant donné un canal Pauli, nous lui associons un canal classique à alphabet quaternaire, et nous montrons que le premier se polarise quantiquement si et seulement si ce dernier se polarise classiquement. Sur la base du canal classique associé, nous fournissons une preuve alternative de la polarisation quantique pour les canaux de Pauli. De manière plus importante, nous fournissons également un moyen efficace de décoder les canaux de Pauli, en décodant le code polaire sur le canal classique associé. Nous considérons également une polarisation multiniveau des canaux de Pauli, où la polarisation se produit à plusieurs niveaux, de sorte que les canaux virtuels synthétisés peuvent également être « semi-bruités », au lieu d'être complètement débruités ou complètement bruités. Cette construction n'utilise pas la randomisation de l'opération de combinaison de canaux. Nous montrons ensuite que les canaux semi-bruités peuvent être figés soit en base de phase, soit en base d’amplitude. Par conséquent, la polarisation à plusieurs niveaux peut être utilisée efficacement pour construire un schéma de codage quantique.Enfin, nous exposons nos travaux en cours sur les codes polaires quantiques CSS, dans le contexte du calcul quantique tolérant aux fautes. Nous fournissons des procédures tolérantes aux fautes pour la préparation d’états quantiques logiques et pour l'extraction du syndrome d'erreur. Ainsi, nous pouvons protéger un état logique pendant un temps arbitrairement long, dans la limite d’un bruit suffisamment faible. De plus, pour le traitement de l'information quantique, nous fournissons des procédures tolérantes aux fautes pour mettre en œuvre les portes logiques de Pauli, Hadamard et CNOT.
Le thème unificateur des contenus sera l’examen des codes correcteurs d’erreurs à travers le prisme du calcul ZX. Plus précisément, nous aborderons les codes de stabilisateur ainsi que les codes polaires classique et quantique. L’objectif d’utiliser le prisme du ZX-calculus est de bénéficier d’un niveau d’abstraction plus élevé. Le premier avantage de cette approche est de voir si nous pouvons offrir une interprétation plus naturelle des preuves existantes, ce qui faciliterait leur enseignement et leur apprentissage. L’autre avantage est que la simplification conceptuelle apportée par l’abstraction permettrait de mieux comprendre les effets et les implications de la mécanique quantique, favorisant ainsi des avancées plus significatives dans le développement des algorithmes quantiques de tous types. En utilisant le ZX-calculus, nous commencerons par examiner les codes stabilisateurs qui sont les plus utilisés parmi les codes correcteurs d’erreurs quantiques. Ensuite, nous entrerons également dans les détails des codes polaires classiques et quantiques et montrerons comment nous pouvons reformuler la méthode de décodage classique en une méthode qui prend en compte les contraintes de l’information quantique, telles que l’impossibilité de connaître l’état d’un qubit à moins de le mesurer et donc de le perturber. Cette nouvelle méthode est applicable dans les cas quantiques ainsi que classiques pour certains types de canaux d’erreur. Tout cela conduit à la formulation d’une nouvelle méthode de décodage visant à fonctionner pour tous les types de canaux d’erreur en catégorisant tous les scénarios d’erreur possibles nécessitant des actions pour corriger les données, puis en utilisant un ensemble de mesures pour réduire les possibilités à un point qui nous donne une certitude presque totale.
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.