Code torique

Nous allons maintenant étudier un code CSS spécifique connu sous le nom de code torique, découvert par Alexei Kitaev en 1997. En réalité, le code torique n'est pas un seul code, mais plutôt une famille de codes, un pour chaque entier positif à partir de 2. Ces codes possèdent quelques propriétés clés :

• Les générateurs de stabilisateurs ont un faible poids, et en particulier ils ont tous le poids 4. Dans le jargon de la théorie des codes, le code torique est un exemple de code de contrôle de parité à faible densité quantique, ou code LDPC quantique (où faible signifie 4 dans ce cas). C'est intéressant car chaque mesure de générateur de stabilisateur ne doit pas impliquer trop de qubits.

• Le code torique possède une localité géométrique. Cela signifie que non seulement les générateurs de stabilisateurs ont un faible poids, mais il est aussi possible d'arranger les qubits dans l'espace de sorte que chaque mesure de générateur de stabilisateur n'implique que des qubits proches les uns des autres. En principe, cela rend ces mesures plus faciles à mettre en œuvre que si elles impliquaient des qubits spatialement éloignés.

• Les membres de la famille du code torique ont une grande distance croissante et peuvent tolérer un taux d'erreur relativement élevé.

Description du code torique

Soit $L\geq 2$ un entier positif, et considérons un réseau $L\times L$ avec ce qu'on appelle des frontières périodiques. Par exemple, la figure suivante représente un réseau $L\times L$ pour $L=9.$

Remarque : les lignes à droite et en bas sont des lignes en pointillés. Cela indique que la ligne en pointillés à droite est la même ligne que celle tout à gauche, et de même, la ligne en pointillés en bas est la même ligne que celle tout en haut.

Réaliser physiquement ce type de configuration nécessite trois dimensions. En particulier, on pourrait former le réseau en cylindre en faisant d'abord correspondre les côtés gauche et droit, puis plier le cylindre de façon à ce que les cercles aux extrémités — qui étaient autrefois les bords supérieur et inférieur du réseau — se rejoignent. On pourrait aussi faire correspondre d'abord le haut et le bas, puis les côtés ; les deux fonctionnent et cela n'a pas d'importance pour notre discussion.

Ce qu'on obtient est un tore — autrement dit, un beignet (bien que l'image d'une chambre à air de pneu soit peut-être plus appropriée, car ce n'est pas un solide : le réseau est devenu uniquement la surface d'un tore). C'est de là que vient le nom « code torique ».

La façon dont on peut « se déplacer » sur un tel tore, entre des points adjacents du réseau, sera probablement familière à ceux qui ont joué à des jeux vidéo à l'ancienne, où sortir par le haut de l'écran fait réapparaître le personnage en bas, et de même pour les bords gauche et droit de l'écran. C'est ainsi que nous concevrons ce réseau à frontières périodiques, plutôt que de parler spécifiquement d'un tore dans l'espace à 3 dimensions.

Ensuite, les qubits sont disposés sur les arêtes de ce réseau, comme illustré dans la figure suivante, où les qubits sont indiqués par des cercles bleus pleins.

Les qubits placés sur les lignes en pointillés ne sont pas pleins car ils sont déjà représentés sur les lignes les plus hautes et les plus à gauche du réseau. Au total, il y a $2L^2$ qubits : $L^2$ qubits sur les lignes horizontales et $L^2$ qubits sur les lignes verticales.

Pour décrire le code torique lui-même, il reste à décrire les générateurs de stabilisateurs :

• Pour chaque case formée par les lignes du réseau, il y a un générateur de stabilisateur $Z$, obtenu en tensorialisant les matrices $Z$ sur les quatre qubits touchant cette case avec des matrices identité sur tous les autres qubits.

• Pour chaque sommet formé par les lignes du réseau, il y a un générateur de stabilisateur $X$, obtenu en tensorialisant les matrices $X$ sur les quatre qubits adjacents à ce sommet avec des matrices identité sur tous les autres qubits.

Dans les deux cas, on obtient une opération de Pauli de poids 4. Individuellement, ces générateurs de stabilisateurs peuvent être illustrés comme suit.

Voici une illustration montrant quelques exemples de générateurs de stabilisateurs dans le contexte du réseau lui-même. On remarque que les générateurs de stabilisateurs qui s'enroulent autour des frontières périodiques sont inclus. Ces générateurs qui s'enroulent autour des frontières périodiques ne sont pas spéciaux et ne se distinguent en aucune façon de ceux qui ne le font pas.

Les générateurs de stabilisateurs doivent commuter pour que ce soit un code stabilisateur valide. Comme d'habitude, les générateurs de stabilisateurs $Z$ commutent tous les uns avec les autres, car $Z$ commute avec lui-même et l'identité commute avec tout, et de même pour les générateurs de stabilisateurs $X$. Les générateurs de stabilisateurs $Z$ et $X$ commutent clairement lorsqu'ils agissent de manière non triviale sur des ensembles disjoints de qubits, comme dans les exemples montrés dans la figure précédente. La possibilité restante est qu'un générateur de stabilisateur $Z$ et un générateur de stabilisateur $X$ se chevauchent sur les qubits sur lesquels ils agissent de manière non triviale, et chaque fois que cela se produit, les générateurs se chevauchent toujours sur deux qubits, comme dans la figure suivante.

Par conséquent, deux générateurs de stabilisateurs comme ceux-ci commutent, tout comme $Z\otimes Z$ et $X\otimes X$ commutent. Les générateurs de stabilisateurs commutent donc tous les uns avec les autres.

La deuxième condition requise sur les générateurs de stabilisateurs pour un code stabilisateur est qu'ils forment un ensemble générateur minimal. Cette condition n'est en réalité pas satisfaite par cette collection : si on multiplie tous les générateurs de stabilisateurs $Z$ ensemble, on obtient l'opération identité, et de même pour les générateurs de stabilisateurs $X$. Ainsi, n'importe lequel des générateurs de stabilisateurs $Z$ peut être exprimé comme le produit de tous les autres, et de même, n'importe lequel des générateurs de stabilisateurs $X$ peut être exprimé comme le produit des générateurs de stabilisateurs $X$ restants. Si on retire n'importe quel générateur de stabilisateur $Z$ et n'importe quel générateur de stabilisateur $X$, on obtient cependant un ensemble générateur minimal.

Pour être clair à ce sujet, nous nous intéressons en fait de manière égale à tous les générateurs de stabilisateurs, et dans un sens strictement opérationnel, il n'est pas nécessaire de sélectionner un générateur de stabilisateur de chaque type à retirer. Mais, pour analyser le code — et compter les générateurs en particulier — on peut imaginer qu'un générateur de stabilisateur de chaque type a été retiré, de façon à obtenir un ensemble générateur minimal, en gardant à l'esprit qu'on pourrait toujours déduire les résultats de ces générateurs retirés (en les considérant comme des observables) à partir des résultats de tous les autres observables de générateurs de stabilisateurs du même type.

Cela laisse $L^2 - 1$ générateurs de stabilisateurs de chaque type, soit $2L^2 - 2$ au total, dans un ensemble générateur minimal (hypothétique). Étant donné qu'il y a $2L^2$ qubits au total, cela signifie que le code torique encode $2L^2 - 2 (L^2 - 1) = 2$ qubits.

La dernière condition requise des générateurs de stabilisateurs est qu'au moins un vecteur d'état quantique soit fixé par tous les générateurs de stabilisateurs. Nous verrons que c'est bien le cas en poursuivant l'analyse du code, mais il est aussi possible de raisonner qu'il n'est pas possible de générer $-1$ fois l'identité sur tous les $2L^2$ qubits à partir des générateurs de stabilisateurs.

Détection des erreurs

Le code torique possède une description simple et élégante, mais ses propriétés de correction d'erreurs quantiques peuvent ne pas être du tout évidentes au premier coup d'œil. En réalité, c'est un code remarquable ! Pour comprendre pourquoi et comment il fonctionne, commençons par examiner différentes erreurs et les syndromes qu'elles génèrent.

Le code torique est un code CSS, car tous nos générateurs de stabilisateurs sont soit des générateurs de stabilisateurs $Z$ soit des générateurs de stabilisateurs $X$. Cela signifie que les erreurs $X$ et les erreurs $Z$ peuvent être détectées (et éventuellement corrigées) séparément. En fait, il existe une symétrie simple entre les générateurs de stabilisateurs $Z$ et $X$ qui nous permet d'analyser les erreurs $X$ et les erreurs $Z$ essentiellement de la même façon. Nous allons donc nous concentrer sur les erreurs $X$, qui sont éventuellement détectées par les générateurs de stabilisateurs $Z$ — mais toute la discussion qui suit peut être transposée des erreurs $X$ aux erreurs $Z$, qui sont détectées de manière analogue par les générateurs de stabilisateurs $X$.

Le diagramme suivant représente l'effet d'une erreur $X$ sur un seul qubit. L'hypothèse ici est que nos $2L^2$ qubits étaient précédemment dans un état contenu dans l'espace de code du code torique, faisant que toutes les mesures de générateurs de stabilisateurs donnent $+1.$ Les générateurs de stabilisateurs $Z$ détectent les erreurs $X$, et il y a un tel générateur de stabilisateur pour chaque case de la figure, donc nous pouvons indiquer le résultat de la mesure du générateur de stabilisateur correspondant par la couleur de cette case : les résultats $+1$ sont indiqués par des cases blanches et les résultats $-1$ sont indiqués par des cases grises. Si une erreur de retournement de bit se produit sur l'un des qubits, l'effet est que les mesures de générateurs de stabilisateurs correspondant aux deux cases touchant le qubit affecté donnent maintenant $-1.$

C'est intuitif lorsqu'on considère les générateurs de stabilisateurs $Z$ et leur comportement. En essence, chaque générateur de stabilisateur $Z$ mesure la parité des quatre qubits touchant la case correspondante (par rapport à la base standard). Ainsi, un résultat $+1$ n'indique pas qu'aucune erreur $X$ ne s'est produite sur ces quatre qubits, mais plutôt qu'un nombre pair d'erreurs $X$ se sont produites sur ces qubits, tandis qu'un résultat $-1$ indique qu'un nombre impair d'erreurs $X$ se sont produites. Une seule erreur $X$ retourne donc la parité des quatre bits sur les deux cases qu'elle touche, ce qui fait que les mesures de générateurs de stabilisateurs donnent $-1.$

Introduisons maintenant plusieurs erreurs $X$ pour voir ce qui se passe. En particulier, nous allons considérer une chaîne d'erreurs $X$ adjacentes, où deux erreurs $X$ sont adjacentes si elles affectent des qubits touchant la même case.

Les deux générateurs de stabilisateurs $Z$ aux extrémités de la chaîne donnent tous les deux le résultat $-1$ dans ce cas, car un nombre impair d'erreurs $X$ se sont produites sur ces deux cases correspondantes. Tous les autres générateurs de stabilisateurs $Z$, en revanche, donnent le résultat $+1,$ y compris ceux qui touchent la chaîne mais ne se trouvent pas aux extrémités, car un nombre pair d'erreurs $X$ se sont produites sur les qubits touchant les cases correspondantes.

Ainsi, tant qu'on a une chaîne d'erreurs $X$ qui a des extrémités, le code torique détectera que des erreurs se sont produites, donnant des résultats de mesure $-1$ pour les générateurs de stabilisateurs $Z$ correspondant aux extrémités de la chaîne. Notez que la chaîne d'erreurs réelle n'est pas révélée, seulement les extrémités ! C'est acceptable — dans la sous-section suivante, nous verrons qu'il n'est pas nécessaire de savoir exactement quels qubits ont été affectés par des erreurs $X$ pour les corriger. (Le code torique est un exemple de code hautement dégénéré, dans le sens où il n'identifie généralement pas de manière unique les erreurs qu'il corrige.)

Il est cependant possible qu'une chaîne d'erreurs $X$ adjacentes n'ait pas d'extrémités, c'est-à-dire qu'une chaîne d'erreurs puisse former une boucle fermée, comme dans la figure suivante.

Dans un tel cas, un nombre pair d'erreurs $X$ se sont produites sur chaque case, donc chaque mesure de générateur de stabilisateur donne un résultat $+1$. Les boucles fermées d'erreurs $X$ adjacentes ne sont donc pas détectées par le code.

Cela peut sembler décevant, car il ne faut que quatre erreurs $X$ pour former une boucle fermée (et on espère quelque chose de bien meilleur qu'un code de distance 4). Cependant, une boucle fermée d'erreurs $X$ de la forme représentée dans la figure précédente n'est pas réellement une erreur — car elle est dans le stabilisateur ! Rappelons qu'en plus des générateurs de stabilisateurs $Z$, nous avons également un générateur de stabilisateur $X$ pour chaque sommet du réseau. Et si on multiplie des générateurs de stabilisateurs $X$ adjacents ensemble, le résultat est qu'on obtient des boucles fermées d'opérations $X$. Par exemple, la boucle fermée dans la figure précédente peut être obtenue en multipliant les générateurs de stabilisateurs $X$ indiqués dans la figure suivante.

Ce n'est cependant pas le seul type de boucle fermée d'erreurs $X$ qu'on peut avoir — et il n'est pas vrai que chaque boucle fermée d'erreurs $X$ soit incluse dans le stabilisateur. En particulier, les différents types de boucles peuvent être caractérisés comme suit.

1. Les boucles fermées d'erreurs $X$ avec un nombre pair d'erreurs $X$ sur chaque ligne horizontale et chaque ligne verticale de qubits. (L'exemple montré ci-dessus appartient à cette catégorie.) Les boucles de cette forme sont toujours contenues dans le stabilisateur, car elles peuvent être effectivement réduites à rien en les multipliant par des générateurs de stabilisateurs $X$.

2. Les boucles fermées d'erreurs $X$ avec un nombre impair d'erreurs $X$ sur au moins une ligne horizontale ou au moins une ligne verticale de qubits. Les boucles de cette forme ne sont jamais contenues dans le stabilisateur et représentent donc des erreurs non triviales qui passent inaperçues pour le code.

Un exemple de boucle fermée d'erreurs $X$ dans la deuxième catégorie est montré dans le diagramme suivant.

Une telle chaîne d'erreurs n'est pas contenue dans le stabilisateur car chaque générateur de stabilisateur $X$ place un nombre pair d'opérations $X$ sur chaque ligne horizontale et chaque ligne verticale de qubits. C'est donc un exemple concret d'erreur non triviale que le code ne parvient pas à détecter.

L'élément clé est que la seule façon de former une boucle du deuxième type est de faire le tour du tore, c'est-à-dire soit autour du trou au milieu du tore, soit à travers, soit les deux. Intuitivement, une chaîne d'erreurs $X$ comme celle-ci ne peut pas être réduite à rien en la multipliant par des générateurs de stabilisateurs $X$ car la topologie d'un tore l'en empêche. Le code torique est parfois classé comme un code de correction d'erreurs quantiques topologique pour cette raison. La longueur minimale d'une telle boucle est $L,$ et c'est donc la distance du code torique : toute boucle fermée d'erreurs $X$ de longueur inférieure à $L$ doit appartenir à la première catégorie, et est donc contenue dans le stabilisateur ; et toute chaîne d'erreurs $X$ avec des extrémités est détectée par le code.

Étant donné que le code torique utilise $2L^2$ qubits pour encoder $2$ qubits et a une distance $L,$ il s'ensuit que c'est un code stabilisateur $[[2L^2,2,L]]$.

Correction des erreurs

Nous avons discuté de la détection des erreurs pour le code torique, et nous allons maintenant aborder brièvement comment corriger les erreurs. Le code torique est un code CSS, donc les erreurs $X$ et les erreurs $Z$ peuvent être détectées et corrigées indépendamment. En nous concentrant toujours sur les générateurs de stabilisateurs $Z$, qui détectent les erreurs $X$, examinons comment une chaîne d'erreurs $X$ peut être corrigée. (Les erreurs $Z$ sont corrigées de manière symétrique.)

Si un syndrome différent du syndrome $(+1,\ldots,+1)$ apparaît lorsque les générateurs de stabilisateurs $Z$ sont mesurés, les résultats $-1$ révèlent les extrémités d'une ou plusieurs chaînes d'erreurs $X$. On peut tenter de corriger ces erreurs en associant les résultats $-1$ par paires et en formant une chaîne de corrections $X$ entre eux. En faisant cela, il est judicieux de choisir les chemins les plus courts le long desquels les corrections sont appliquées.

Par exemple, considérons le diagramme suivant, qui représente un syndrome avec deux résultats $-1$, indiqués par des cases grises, causés par une chaîne d'erreurs $X$ illustrée par la ligne et les cercles magenta. Comme nous l'avons déjà remarqué, la chaîne elle-même n'est pas révélée par le syndrome ; seules les extrémités sont visibles.

Pour tenter de corriger cette chaîne d'erreurs, un chemin le plus court entre les résultats de mesure $-1$ est sélectionné et des portes $X$ sont appliquées comme corrections aux qubits le long de ce chemin (indiqué en jaune dans la figure). Bien que les corrections ne correspondent pas nécessairement à la chaîne d'erreurs réelle, les erreurs et les corrections ensemble forment une boucle fermée d'opérations $X$ qui est contenue dans le stabilisateur du code. La correction réussit donc dans cette situation, car l'effet combiné des erreurs et des corrections ne fait rien à un état encodé.

Cette stratégie ne sera pas toujours couronnée de succès. Par exemple, une explication différente pour le même syndrome que dans la figure précédente est montrée dans la figure suivante.

Cette fois, la même chaîne de corrections qu'auparavant ne parvient pas à corriger cette chaîne d'erreurs, car l'effet combiné des erreurs et des corrections est qu'on obtient une boucle fermée d'opérations $X$ qui s'enroule autour du tore, et a donc un effet non trivial sur l'espace de code. Donc, il n'y a aucune garantie que la stratégie décrite précédemment, consistant à choisir un chemin le plus court de corrections $X$ entre deux résultats de mesure de syndrome $-1$, corrigera correctement l'erreur qui a causé ce syndrome.

Peut-être plus probable, selon le modèle de bruit, est qu'un syndrome avec plus de deux entrées $-1$ est mesuré, comme la figure suivante le suggère.

Dans ce cas, différentes stratégies de correction sont connues. Une stratégie naturelle est de tenter de regrouper les résultats de mesure $-1$ par paires et d'effectuer des corrections le long de chemins les plus courts reliant les paires, comme indiqué en jaune dans la figure. En particulier, un couplage parfait de poids minimum entre les résultats de mesure $-1$ peut être calculé, puis les paires sont reliées par des chemins les plus courts de corrections $X$. Le calcul d'un couplage parfait de poids minimum peut être effectué efficacement avec un algorithme classique connu sous le nom d'algorithme du blossom, découvert par Edmonds dans les années 1960.

Cette approche n'est généralement pas optimale pour les modèles de bruit les plus couramment étudiés, mais d'après des simulations numériques, elle fonctionne très bien en pratique en dessous d'un taux de bruit d'environ 10%, en supposant des erreurs de Pauli indépendantes où $X,$ $Y,$ et $Z,$ sont également probables. Augmenter $L$ n'a pas d'effet significatif sur le point d'équilibre auquel le code commence à être utile, mais conduit à une diminution plus rapide de la probabilité d'une erreur logique à mesure que le taux d'erreur descend en dessous du point d'équilibre.