Codes CSS

Codes linéaires classiques

Les codes correcteurs d'erreurs classiques ont été étudiés pour la première fois dans les années 1940, et de nombreux codes différents sont aujourd'hui connus. Les codes les plus couramment étudiés et utilisés appartiennent à une catégorie appelée codes linéaires. On va voir exactement ce que le mot « linéaire » signifie dans ce contexte dans un instant, mais une façon très simple de décrire les codes linéaires pour l'instant est de dire que ce sont des codes stabilisateurs qui se trouvent être classiques. Les codes CSS sont essentiellement des paires de codes linéaires classiques que l'on combine pour créer un code correcteur d'erreurs quantiques. Donc, pour la discussion qui suit, on va avoir besoin de comprendre quelques notions de base sur les codes linéaires classiques.

Soit $\Sigma$ l'alphabet binaire pour toute cette discussion. Quand on parle d'un code linéaire classique, on entend un ensemble non vide $\mathcal{C}\subseteq\Sigma^n$ de chaînes binaires de longueur $n,$ pour un certain entier positif $n,$ qui doit satisfaire une seule propriété fondamentale : si $u$ et $v$ sont des chaînes binaires dans $\mathcal{C},$ alors la chaîne $u\oplus v$ est aussi dans $\mathcal{C}.$ Ici, $u\oplus v$ désigne le OU exclusif bit à bit de $u$ et $v,$ que l'on a rencontré plusieurs fois dans le cours « Fondamentaux des algorithmes quantiques ».

En essence, quand on qualifie un code correcteur d'erreurs classique de linéaire, on pense aux chaînes binaires de longueur $n$ comme étant des vecteurs à $n$ dimensions dont les entrées sont toutes égales à $0$ ou $1,$ et on exige que le code lui-même forme un sous-espace linéaire. Au lieu de l'addition vectorielle ordinaire sur les réels ou les complexes, on utilise l'addition modulo $2,$ qui est simplement le OU exclusif. Autrement dit, si on a deux mots de code $u$ et $v,$ c'est-à-dire que $u$ et $v$ sont des chaînes binaires dans $\mathcal{C},$ alors $u + v$ modulo 2, c'est-à-dire $u\oplus v,$ doit aussi être un mot de code dans $\mathcal{C}.$ On remarque en particulier que cette implication doit être vraie même si $u = v.$ Cela implique que $\mathcal{C}$ doit contenir la chaîne tout-zéro $0^n,$ car le OU exclusif bit à bit d'une chaîne avec elle-même donne toujours la chaîne tout-zéro.

Exemple : le code à répétition sur 3 bits

Le code à répétition sur 3 bits est un exemple de code linéaire classique. En particulier, on a $\mathcal{C} = \{000,111\},$ donc, par rapport à la condition de linéarité, il n'y a que deux choix possibles pour $u$ et deux choix possibles pour $v.$ C'est trivial de parcourir les quatre paires possibles pour vérifier qu'on obtient toujours un mot de code en prenant le OU exclusif bit à bit :

$$000 \oplus 000 = 000, \quad 000 \oplus 111 = 111, \quad 111 \oplus 000 = 111, \quad 111 \oplus 111 = 000.$$

Exemple : le code de Hamming $[7,4,3]$

Voici un autre exemple de code linéaire classique, appelé le code de Hamming $[7,4,3]$. C'est l'un des tout premiers codes correcteurs d'erreurs classiques jamais découverts, et il est constitué de ces 16 chaînes binaires de longueur 7. (Parfois, le code de Hamming $[7,4,3]$ est compris comme le code dont ces chaînes sont inversées, mais on va le définir comme étant le code contenant les chaînes montrées ici.)

$$\begin{array}{cccc} 0000000 & 1100001 & 1010010 & 0110011\\[1mm] 0110100 & 1010101 & 1100110 & 0000111\\[1mm] 1111000 & 0011001 & 0101010 & 1001011\\[1mm] 1001100 & 0101101 & 0011110 & 1111111 \end{array}$$

La logique très simple qui sous-tend le choix de ces chaînes est secondaire par rapport à la leçon et ne sera pas expliquée ici. Pour l'instant, il suffit d'observer que c'est bien un code linéaire classique : faire un XOR de deux quelconques de ces chaînes donnera toujours une autre chaîne appartenant au code.

La notation $[7,4,3]$ (entre crochets simples) signifie quelque chose d'analogue à la notation entre double crochets pour les codes stabilisateurs mentionnée dans la leçon précédente, mais ici c'est pour les codes linéaires classiques. En particulier, les mots de code ont $7$ bits, on peut encoder $4$ bits avec le code (car il y a $16 = 2^4$ mots de code), et il s'agit d'un code de distance $3,$ ce qui signifie que deux mots de code distincts quelconques diffèrent en au moins $3$ positions — il faut donc retourner au moins $3$ bits pour passer d'un mot de code à un autre. Le fait que ce soit un code de distance $3$ implique qu'il peut corriger jusqu'à une erreur de retournement de bit.

Description des codes linéaires classiques

Les exemples mentionnés à l'instant sont des exemples très simples de codes linéaires classiques, mais même le code de Hamming $[7,4,3]$ paraît un peu mystérieux quand on se contente de lister les mots de code. Il existe de meilleures façons, plus efficaces, de décrire les codes linéaires classiques, notamment les deux suivantes.

1. Générateurs. Une façon de décrire un code linéaire classique est avec une liste minimale de mots de code qui génèrent le code, c'est-à-dire qu'en prenant tous les sous-ensembles possibles de ces mots de code et en faisant leur XOR, on obtient l'intégralité du code.

   Plus précisément, les chaînes $u_1,\ldots,u_m\in\Sigma^n$ génèrent le code linéaire classique $\mathcal{C}$ si

   $$\mathcal{C} = \bigl\{\alpha_1 u_1 \oplus \cdots \oplus \alpha_m u_m\,:\,\alpha_1,\ldots,\alpha_m\in\{0,1\}\bigr\},$$

   avec la convention que $\alpha u = u$ quand $\alpha = 1$ et $\alpha u = 0^n$ quand $\alpha = 0,$ et on dit que cette liste est minimale si en retirant l'une des chaînes on génère un code plus petit. Une façon naturelle de penser à une telle description est que la collection $\{u_1,\ldots,u_m\}$ forme une base pour $\mathcal{C}$ en tant que sous-espace, où l'on considère les chaînes comme des vecteurs à entrées binaires, en gardant à l'esprit qu'on travaille dans un espace vectoriel où l'arithmétique est faite modulo $2.$

2. Vérifications de parité. Une autre façon naturelle de décrire un code linéaire classique est par des vérifications de parité — c'est-à-dire une liste minimale de chaînes binaires telles que les chaînes du code sont précisément celles dont le produit scalaire binaire avec chacune de ces chaînes de vérification de parité est zéro. (Comme le OU exclusif bit à bit, le produit scalaire binaire est apparu plusieurs fois dans « Fondamentaux des algorithmes quantiques ».)

   Autrement dit, les chaînes $v_1,\ldots,v_r\in\Sigma^n$ sont des chaînes de vérification de parité pour le code linéaire classique $\mathcal{C}$ si

   $$\mathcal{C} = \bigl\{ u\in \Sigma^n\,:\, u\cdot v_1 = \cdots = u \cdot v_r = 0 \bigr\},$$

   et cet ensemble de chaînes est minimal si en en retirant une on obtient un code plus grand. On les appelle chaînes de vérification de parité parce que $u$ a un produit scalaire binaire égal à zéro avec $v$ si et seulement si les bits de $u$ aux positions où $v$ vaut 1 ont une parité paire. Donc, pour déterminer si une chaîne $u$ appartient au code $\mathcal{C},$ il suffit de vérifier la parité de certains sous-ensembles des bits de $u.$

   Une chose importante à noter ici est que le produit scalaire binaire n'est pas un produit intérieur au sens formel. En particulier, quand deux chaînes ont un produit scalaire binaire égal à zéro, cela ne signifie pas qu'elles sont orthogonales au sens habituel. Par exemple, le produit scalaire binaire de la chaîne $11$ avec elle-même est zéro — il est donc possible qu'une chaîne de vérification de parité pour un code linéaire classique soit elle-même dans le code.

Les codes linéaires classiques sur l'alphabet binaire contiennent toujours un nombre de chaînes qui est une puissance de $2$ — et pour un seul code linéaire classique décrit des deux façons qui viennent d'être présentées, on aura toujours $n = m + r.$ En particulier, si on a un ensemble minimal de $m$ générateurs, le code encode $m$ bits et on aura nécessairement $2^m$ mots de code ; et si on a un ensemble minimal de $r$ chaînes de vérification de parité, on aura $2^{n-r}$ mots de code. Donc, chaque générateur double la taille de l'espace du code tandis que chaque chaîne de vérification de parité réduit cet espace de moitié.

Par exemple, le code à répétition sur 3 bits est un code linéaire, donc il peut être décrit des deux façons. En particulier, il n'y a qu'un seul choix de générateur qui fonctionne : $111.$ On peut également décrire le code avec deux chaînes de vérification de parité, comme $110$ et $011$ — ce qui devrait sembler familier d'après nos discussions précédentes sur ce code — ou on pourrait prendre les chaînes de vérification de parité comme étant $110$ et $101,$ ou $101$ et $011.$ (Les générateurs et les chaînes de vérification de parité ne sont généralement pas uniques pour un code linéaire classique donné.)

Pour un deuxième exemple, considérons le code de Hamming $[7,4,3]$. Voici un choix de liste de générateurs qui fonctionne.

$$\begin{array}{c} 1111000\\[1mm] 0110100\\[1mm] 1010010\\[1mm] 1100001 \end{array}$$

Et voici un choix de liste de vérifications de parité pour ce code.

$$\begin{array}{c} 1111000\\[1mm] 1100110\\[1mm] 1010101 \end{array}$$

Ici, on voit d'ailleurs que toutes nos chaînes de vérification de parité sont elles-mêmes dans le code.

Une dernière remarque sur les codes linéaires classiques, qui les relie au formalisme stabilisateur : les chaînes de vérification de parité sont équivalentes à des générateurs stabilisateurs qui ne sont constitués que de matrices de Pauli $Z$ et identité. Par exemple, les chaînes de vérification de parité $110$ et $011$ pour le code à répétition sur 3 bits correspondent précisément aux générateurs stabilisateurs $Z\otimes Z\otimes \mathbb{I}$ et $\mathbb{I}\otimes Z\otimes Z,$ ce qui est cohérent avec les discussions sur les observables de Pauli de la leçon précédente.

Définition des codes CSS

Les codes CSS sont des codes stabilisateurs obtenus en combinant certaines paires de codes linéaires classiques. Cela ne fonctionne pas pour deux codes linéaires classiques quelconques — les deux codes doivent avoir une certaine relation. Néanmoins, cette construction ouvre de nombreuses possibilités pour les codes correcteurs d'erreurs quantiques, basées en partie sur plus de 75 ans de théorie du codage classique.

Dans le formalisme stabilisateur, les générateurs stabilisateurs contenant uniquement des matrices de Pauli $Z$ et identité sont équivalents aux vérifications de parité, comme on vient de l'observer pour le code à répétition sur 3 bits. Pour un autre exemple, considérons les chaînes de vérification de parité suivantes pour le code de Hamming $[7,4,3]$.

$$\begin{array}{c} 1111000\\[1mm] 1100110\\[1mm] 1010101 \end{array}$$

Ces chaînes de vérification de parité correspondent aux générateurs stabilisateurs suivants (écrits sans les symboles de produit tensoriel), qu'on obtient en remplaçant chaque $1$ par un $Z$ et chaque $0$ par un $\mathbb{I}.$ Ce sont trois des six générateurs stabilisateurs du code de Steane à 7 qubits.

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \end{array}$$

Donnons le nom de générateurs $Z$ stabilisateurs à des générateurs stabilisateurs comme ceux-ci, c'est-à-dire qu'ils n'ont que des facteurs tensoriels de Pauli $Z$ et identité — donc les matrices de Pauli $X$ et $Y$ n'apparaissent jamais dans les générateurs $Z$ stabilisateurs.

On peut aussi considérer des générateurs stabilisateurs dans lesquels seuls $X$ et les matrices de Pauli identité apparaissent comme facteurs tensoriels. De tels générateurs stabilisateurs peuvent être vus comme étant analogues aux générateurs $Z$ stabilisateurs, sauf qu'ils décrivent des vérifications de parité dans la base $\{\vert+\rangle,\vert-\rangle\}$ plutôt que dans la base standard. Les générateurs stabilisateurs de cette forme sont appelés générateurs $X$ stabilisateurs — donc aucune matrice de Pauli $Y$ ou $Z$ n'est autorisée cette fois.

Par exemple, considérons les trois générateurs stabilisateurs restants du code de Steane à 7 qubits.

$$\begin{array}{ccccccc} X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

Ils suivent exactement le même schéma tiré du code de Hamming $[7,4,3]$ que les générateurs $Z$ stabilisateurs, sauf que cette fois on substitue $X$ à $1$ plutôt que $Z.$ Ce qu'on obtient à partir de ces seuls trois générateurs stabilisateurs est un code qui inclut les 16 états montrés ici, qu'on obtient en appliquant des opérations de Hadamard aux états de la base standard correspondant aux chaînes du code de Hamming $[7,4,3]$. (Bien sûr, l'espace de code pour ce code inclut également des combinaisons linéaires de ces états.)

$$\begin{array}{cccc} \vert {+++++++} \rangle \quad & \vert {--++++-} \rangle \quad & \vert {-+-++-+} \rangle \quad & \vert {+--++--} \rangle \\ \vert {+--+-++} \rangle \quad & \vert {-+-+-+-} \rangle \quad & \vert {--++--+} \rangle \quad & \vert {++++---} \rangle \\ \vert {----+++} \rangle \quad & \vert {++--++-} \rangle \quad & \vert {+-+-+-+} \rangle \quad & \vert {-++-+--} \rangle \\ \vert {-++--++} \rangle \quad & \vert {+-+--+-} \rangle \quad & \vert {++----+} \rangle \quad & \vert {-------} \rangle \end{array}$$

On peut maintenant définir les codes CSS en termes très simples.

Définition

Un code CSS est un code stabilisateur qui peut être exprimé en n'utilisant que des générateurs $X$ et $Z$ stabilisateurs.

Autrement dit, les codes CSS sont des codes stabilisateurs pour lesquels on dispose de générateurs stabilisateurs dans lesquels aucune matrice de Pauli $Y$ n'apparaît, et pour lesquels $X$ et $Z$ n'apparaissent jamais dans le même générateur stabilisateur.

Pour être clair, selon cette définition, un code CSS est un code pour lequel il est possible de choisir uniquement des générateurs $X$ et $Z$ stabilisateurs — mais on doit garder à l'esprit qu'il existe une liberté dans la façon de choisir les générateurs stabilisateurs pour les codes stabilisateurs. Ainsi, il y aura généralement différents choix de générateurs stabilisateurs pour un code CSS qui ne sont pas des générateurs $X$ ou $Z$ stabilisateurs (en plus d'au moins un choix pour lequel ils le sont).

Voici un exemple très simple de code CSS qui inclut à la fois un générateur $Z$ stabilisateur et un générateur $X$ stabilisateur :

$$\begin{array}{cc} Z & Z \\[1mm] X & X \end{array}$$

Il est clair que c'est un code CSS, car le premier générateur stabilisateur est un générateur $Z$ stabilisateur et le second est un générateur $X$ stabilisateur. Bien sûr, un code CSS doit également être un code stabilisateur valide — ce qui signifie que les générateurs stabilisateurs doivent commuter, former un ensemble générateur minimal, et fixer au moins un vecteur d'état quantique. Ces exigences sont faciles à vérifier pour ce code. Comme on l'a noté dans la leçon précédente, l'espace de code pour ce code est l'espace de dimension un engendré par l'état de Bell $\vert\phi^+\rangle$. Le fait que les deux générateurs stabilisateurs fixent cet état est apparent en considérant les deux expressions suivantes d'un e-bit, accompagnées d'une interprétation de ces générateurs stabilisateurs comme vérifications de parité dans les bases $\{\vert 0\rangle, \vert 1\rangle\}$ et $\{\vert +\rangle, \vert -\rangle\}$.

$$\vert\phi^+\rangle = \frac{\vert 0\rangle\vert 0\rangle + \vert 1\rangle\vert 1\rangle}{\sqrt{2}} = \frac{\vert +\rangle\vert +\rangle + \vert -\rangle\vert -\rangle}{\sqrt{2}}$$

Le code de Steane à 7 qubits est un autre exemple de code CSS.

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

On a ici trois générateurs $Z$ stabilisateurs et trois générateurs $X$ stabilisateurs, et on a déjà vérifié que c'est un code stabilisateur valide.

Et le code de Shor à 9 qubits en est un autre exemple.

$$\begin{array}{ccccccccc} Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z\\[1mm] X & X & X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I}& X & X & X & X & X & X \end{array}$$

Cette fois, on a six générateurs $Z$ stabilisateurs et seulement deux générateurs $X$ stabilisateurs. C'est tout à fait acceptable, il n'est pas nécessaire d'avoir un équilibre ou une symétrie entre les deux types de générateurs (même si c'est souvent le cas).

Il est encore une fois essentiel que les codes CSS soient des codes stabilisateurs valides, et en particulier chaque générateur $Z$ stabilisateur doit commuter avec chaque générateur $X$ stabilisateur. Donc, toute collection de générateurs $X$ et $Z$ stabilisateurs ne définit pas forcément un code CSS valide.

Détection et correction d'erreurs

En ce qui concerne la détection et la correction d'erreurs, les codes CSS ont en général une caractéristique similaire au code de Shor à 9 qubits, à savoir que les erreurs $X$ et $Z$ peuvent être détectées et corrigées de façon totalement indépendante ; les générateurs $Z$ stabilisateurs décrivent un code qui protège contre les retournements de bits, et les générateurs $X$ stabilisateurs décrivent un code qui protège indépendamment contre les retournements de phase. Cela fonctionne parce que les générateurs $Z$ stabilisateurs commutent nécessairement avec les erreurs $Z,$ ainsi qu'avec les opérations $Z$ appliquées comme corrections, donc ils en sont complètement indépendants, et de même pour les générateurs $X$ stabilisateurs, les erreurs et les corrections.

Prenons l'exemple du code de Steane à 7 qubits.

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

L'idée de base pour ce code est maintenant apparente : c'est un code de Hamming $[7,4,3]$ pour les erreurs de retournement de bits et un code de Hamming $[7,4,3]$ pour les erreurs de retournement de phase. Le fait que les générateurs $X$ et $Z$ stabilisateurs commutent est peut-être une heureuse coïncidence, car ce ne serait pas un code stabilisateur valide si ce n'était pas le cas. Mais il existe en fait de nombreux exemples connus de codes linéaires classiques qui donnent un code stabilisateur valide lorsqu'ils sont utilisés de façon similaire.

En général, supposons qu'on ait un code CSS pour lequel les générateurs $Z$ stabilisateurs permettent la correction jusqu'à $j$ erreurs de retournement de bits, et les générateurs $X$ stabilisateurs permettent la correction jusqu'à $k$ erreurs de retournement de phase. Par exemple, $j = 1$ et $k = 1$ pour le code de Steane, étant donné que le code de Hamming $[7,4,3]$ peut corriger un retournement de bit. Il s'ensuit alors, par la discrétisation des erreurs, que ce code CSS peut corriger toute erreur sur un nombre de qubits allant jusqu'au minimum de $j$ et $k.$ En effet, lors de la mesure du syndrome, une erreur arbitraire sur ce nombre de qubits se collapse probabilistiquement en une combinaison d'erreurs $X,$ d'erreurs $Z,$ ou des deux — puis les erreurs $X$ et les erreurs $Z$ sont détectées et corrigées indépendamment.

En résumé, à condition d'avoir deux codes linéaires classiques (ou deux copies d'un seul code linéaire classique) qui sont compatibles, en ce sens qu'ils définissent des générateurs $X$ et $Z$ stabilisateurs qui commutent, le code CSS qu'on obtient en les combinant hérite des propriétés de correction d'erreurs de ces deux codes, dans le sens qui vient d'être décrit.

On remarque cependant qu'il y a un prix à payer : on ne peut pas encoder autant de qubits qu'on pouvait encoder de bits avec les deux codes classiques. En effet, le nombre total de générateurs stabilisateurs pour le code CSS est la somme du nombre de vérifications de parité des deux codes linéaires classiques, et chaque générateur stabilisateur réduit la dimension de l'espace de code de moitié. Par exemple, le code de Hamming $[7,4,3]$ permet d'encoder quatre bits classiques, car on n'a que trois chaînes de vérification de parité pour ce code, tandis que le code de Steane à 7 qubits n'encode qu'un seul qubit, car il a six générateurs stabilisateurs.

Espaces de code des codes CSS

La dernière chose qu'on va faire dans cette discussion sur les codes CSS est de considérer les espaces de code de ces codes. Cela nous donnera l'occasion d'examiner plus en détail la relation qui doit exister entre deux codes linéaires classiques pour qu'ils soient compatibles, en ce sens qu'ils peuvent être combinés pour former un code CSS.

Considérons un code CSS quelconque sur $n$ qubits, et soient $z_1, \ldots, z_s \in \Sigma^n$ les chaînes de vérification de parité à $n$ bits qui correspondent aux générateurs $Z$ stabilisateurs de ce code. Cela signifie que le code linéaire classique décrit uniquement par les générateurs $Z$ stabilisateurs, que l'on va appeler $\mathcal{C}_Z,$ prend la forme suivante.

$$\mathcal{C}_Z = \bigl\{ u \in \Sigma^n \,:\, u \cdot z_1 = \cdots = u \cdot z_s = 0 \bigr\}$$

En d'autres termes, le code linéaire classique $\mathcal{C}_Z$ contient toutes les chaînes dont le produit scalaire binaire avec chacune des chaînes de vérification de parité $z_1, \ldots, z_s$ est zéro.

De la même façon, prenons $x_1,\ldots,x_t\in\Sigma^n$ comme étant les chaînes de vérification de parité à $n$ bits correspondant aux générateurs $X$ stabilisateurs de notre code. Ainsi, le code linéaire classique correspondant aux générateurs $X$ stabilisateurs prend cette forme.

$$\mathcal{C}_X = \bigl\{ u \in \Sigma^n \,:\, u \cdot x_1 = \cdots = u \cdot x_t = 0 \bigr\}$$

Les générateurs $X$ stabilisateurs seuls décrivent donc un code similaire à ce code, mais dans la base $\{\vert {+}\rangle,\vert {-}\rangle\}$ plutôt que dans la base standard.

On va maintenant introduire deux nouveaux codes linéaires classiques qui sont dérivés des mêmes choix de chaînes, $z_1,\ldots,z_s$ et $x_1,\ldots,x_t,$ mais où l'on prend ces chaînes comme générateurs plutôt que comme chaînes de vérification de parité. On obtient en particulier ces deux codes.

$$\begin{aligned} \mathcal{D}_Z & = \bigl\{ \alpha_1 z_1 \oplus \cdots \oplus \alpha_s z_s \,:\, \alpha_1,\ldots,\alpha_s \in \{0,1\} \bigr\}\\[1mm] \mathcal{D}_X & = \bigl\{ \alpha_1 x_1 \oplus \cdots \oplus \alpha_t x_t \,:\, \alpha_1,\ldots,\alpha_t \in \{0,1\} \bigr\} \end{aligned}$$

Ces codes sont connus sous le nom de codes duaux des codes définis précédemment : $\mathcal{D}_Z$ est le code dual de $\mathcal{C}_Z$ et $\mathcal{D}_X$ est le code dual de $\mathcal{C}_X.$ Il n'est peut-être pas évident pour l'instant pourquoi ces codes duaux sont pertinents, mais ils s'avèrent être très pertinents pour plusieurs raisons, notamment les deux raisons expliquées dans les paragraphes suivants.

Premièrement, les conditions qui doivent être satisfaites pour que deux codes linéaires classiques $\mathcal{C}_Z$ et $\mathcal{C}_X$ soient compatibles, en ce sens qu'ils peuvent être associés pour former un code CSS, peuvent être décrites simplement en faisant référence aux codes duaux. Plus précisément, il faut que $\mathcal{D}_Z\subseteq\mathcal{C}_X,$ ou de façon équivalente, que $\mathcal{D}_X\subseteq\mathcal{C}_Z.$ En d'autres termes, le code dual $\mathcal{D}_Z$ inclut les chaînes correspondant aux générateurs $Z$ stabilisateurs, et leur inclusion dans $\mathcal{C}_X$ est équivalente au fait que le produit scalaire binaire de chacune de ces chaînes avec celles correspondant aux générateurs $X$ stabilisateurs est zéro. Cela, à son tour, est équivalent au fait que chaque générateur $Z$ stabilisateur commute avec chaque générateur $X$ stabilisateur. Alternativement, en inversant les rôles des générateurs $X$ et $Z$ stabilisateurs et en partant de l'inclusion $\mathcal{D}_X\subseteq\mathcal{C}_Z,$ on arrive à la même conclusion.

Deuxièmement, en faisant référence aux codes duaux, on peut facilement décrire les espaces de code d'un code CSS donné. En particulier, l'espace de code est engendré par des vecteurs de la forme suivante.

$$\vert u \oplus \mathcal{D}_X\rangle = \frac{1}{\sqrt{2^t}} \sum_{v\in\mathcal{D}_X} \vert u \oplus v\rangle \qquad \text{(pour tout $u\in\mathcal{C}_Z$)}$$

En d'autres termes, ces vecteurs sont des superpositions uniformes sur les chaînes du code dual $\mathcal{D}_X$ du code correspondant aux générateurs $X$ stabilisateurs, décalées par (autrement dit, soumises à un OU exclusif bit à bit avec) des chaînes du code $\mathcal{C}_Z$ correspondant aux générateurs $Z$ stabilisateurs. Pour être clair, différents choix de décalage — représentés par la chaîne $u$ dans cette expression — peuvent donner le même vecteur. Donc, ces états ne sont pas tous distincts, mais collectivement ils engendrent l'intégralité de l'espace de code.

Voici une explication intuitive pour comprendre pourquoi de tels vecteurs sont à la fois dans l'espace de code et l'engendrent. Considérons l'état de la base standard à $n$ qubits $\vert u\rangle,$ pour une chaîne à $n$ bits $u$ quelconque, et supposons qu'on projette cet état sur l'espace de code. C'est-à-dire, en notant $\Pi$ la projection sur l'espace de code de notre code CSS, considérons le vecteur $\Pi\vert u\rangle.$ Il y a deux cas :

• Cas 1 : $u\in\mathcal{C}_Z.$ Cela implique que chaque générateur $Z$ stabilisateur de notre code CSS agit trivialement sur $\vert u\rangle.$ Les générateurs $X$ stabilisateurs, en revanche, retournent simplement certains bits de $\vert u\rangle.$ En particulier, pour chaque générateur $v$ de $\mathcal{D}_X,$ le générateur $X$ stabilisateur correspondant à $v$ transforme $\vert u\rangle$ en $\vert u\oplus v\rangle.$ En caractérisant la projection $\Pi$ comme la moyenne sur les éléments du stabilisateur (comme on l'a vu dans la leçon précédente), on obtient cette formule :

  $$\Pi \vert u \rangle = \frac{1}{2^t} \sum_{v\in\mathcal{D}_{X}} \vert u \oplus v\rangle = \frac{1}{\sqrt{2^t}} \vert u \oplus \mathcal{D}_X\rangle.$$

• Cas 2 : $u\notin\mathcal{C}_Z.$ Cela implique qu'au moins une des vérifications de parité correspondant aux générateurs $Z$ stabilisateurs échoue, ce qui veut dire que $\vert u\rangle$ doit être un vecteur propre de valeur propre $-1$ d'au moins un des générateurs $Z$ stabilisateurs. L'espace de code du code CSS est l'intersection des espaces propres de valeur propre $+1$ des générateurs stabilisateurs. Donc, étant un vecteur propre de valeur propre $-1$ d'au moins un des générateurs $Z$ stabilisateurs, $\vert u\rangle$ est orthogonal à l'espace de code :

  $$\Pi\vert u\rangle = 0.$$

Et maintenant, en parcourant toutes les chaînes à $n$ bits $u,$ en écartant celles pour lesquelles $\Pi\vert u\rangle = 0,$ et en normalisant les restantes, on obtient les vecteurs décrits précédemment, ce qui démontre qu'ils engendrent l'espace de code.

On peut aussi utiliser la symétrie entre les générateurs $X$ et $Z$ stabilisateurs pour décrire l'espace de code d'une façon similaire mais différente. En particulier, c'est l'espace engendré par des vecteurs ayant la forme suivante.

$$H^{\otimes n} \vert u \oplus \mathcal{D}_Z\rangle = \frac{1}{\sqrt{2^s}} \sum_{v\in\mathcal{D}_Z} H^{\otimes n}\vert u \oplus v\rangle \qquad \text{(pour $u\in\mathcal{C}_X$)}$$

En substance, $X$ et $Z$ ont été échangés dans chaque instance où ils apparaissent — mais on doit aussi échanger la base standard contre la base $\{\vert+\rangle,\vert-\rangle\},$ c'est pourquoi les opérations de Hadamard sont incluses.

Comme exemple, considérons le code de Steane à 7 qubits. Les chaînes de vérification de parité pour les générateurs $X$ et $Z$ stabilisateurs sont les mêmes : $1111000,$ $1100110,$ et $1010101.$ Les codes $\mathcal{C}_X$ et $\mathcal{C}_Z$ sont donc identiques ; tous les deux sont égaux au code de Hamming $[7,4,3]$.

$$\mathcal{C}_X = \mathcal{C}_Z = \{0000000, 0000111, 0011001, 0011110, 0101010, 0101101, 0110011, 0110100, 1001011, 1001100, 1010010, 1010101, 1100001, 1100110, 1111000, 1111111\}$$

Les codes duaux $\mathcal{D}_X$ et $\mathcal{D}_Z$ sont donc aussi identiques. On a trois générateurs, donc on obtient huit chaînes.

$$\mathcal{D}_X = \mathcal{D}_Z = \{0000000, 0011110, 0101101, 0110011, 1001011, 1010101, 1100110, 1111000\}$$

Ces chaînes sont toutes contenues dans le code de Hamming $[7,4,3],$ et donc la condition CSS est satisfaite : $\mathcal{D}_Z \subseteq \mathcal{C}_X,$ ou de façon équivalente, $\mathcal{D}_X \subseteq \mathcal{C}_Z.$

Étant donné que $\mathcal{D}_X$ contient la moitié de toutes les chaînes de $\mathcal{C}_Z,$ il n'y a que deux vecteurs distincts $\vert u\oplus \mathcal{D}_X\rangle$ qu'on peut obtenir en choisissant $u\in\mathcal{C}_Z.$ C'est attendu, car le code de Steane à 7 qubits a un espace de code de dimension deux. On peut utiliser les deux états qu'on obtient de cette façon pour encoder les états logiques $\vert 0\rangle$ et $\vert 1\rangle$ comme suit.

$$\begin{aligned} \vert 0\rangle & \mapsto \frac{ \vert 0000000\rangle + \vert 0011110\rangle + \vert 0101101\rangle + \vert 0110011\rangle + \vert 1001011\rangle + \vert 1010101\rangle + \vert 1100110\rangle + \vert 1111000\rangle }{\sqrt{8}}\\[4mm] \vert 1\rangle & \mapsto \frac{ \vert 0000111\rangle + \vert 0011001\rangle + \vert 0101010\rangle + \vert 0110100\rangle + \vert 1001100\rangle + \vert 1010010\rangle + \vert 1100001\rangle + \vert 1111111\rangle }{\sqrt{8}} \end{aligned}$$

Comme toujours, ce choix ne s'impose pas à nous — on est libre d'utiliser l'espace de code pour encoder des qubits comme on le souhaite. Cet encodage est cependant cohérent avec l'exemple d'un circuit d'encodage pour le code de Steane à 7 qubits dans la leçon précédente.