Codes stabilisateurs

Nous allons maintenant définir les codes stabilisateurs de manière générale. Nous aborderons également certaines de leurs propriétés fondamentales et leur fonctionnement, notamment comment les états peuvent être encodés et comment les erreurs sont détectées et corrigées à l'aide de ces codes.

Définition des codes stabilisateurs

Un code stabilisateur à $n$ qubits est spécifié par une liste d'opérations de Pauli à $n$ qubits, $P_1,\ldots,P_r.$ Ces opérations sont appelées générateurs stabilisateurs dans ce contexte, et elles doivent satisfaire les trois propriétés suivantes.

1. Les générateurs stabilisateurs commutent tous entre eux.

   $$P_j P_k = P_k P_j \qquad \text{(for all $j,k\in\{1,\ldots,r\}$)}$$

2. Les générateurs stabilisateurs forment un ensemble générateur minimal.

   $$P_k \notin \langle P_1,\ldots,P_{k-1},P_{k+1},\ldots,P_r\rangle \qquad \text{(for all $k\in\{1,\ldots,r\}$)}$$

3. Au moins un vecteur d'état quantique est fixé par tous les générateurs stabilisateurs.

   $$-\mathbb{I}^{\otimes n} \notin \langle P_1,\ldots, P_r\rangle$$

   (Il n'est pas évident que l'existence d'un vecteur d'état quantique $\vert\psi\rangle$ fixé par tous les générateurs stabilisateurs, c'est-à-dire tel que $P_1 \vert\psi\rangle = \cdots = P_r \vert\psi\rangle = \vert\psi\rangle,$ soit équivalente à $-\mathbb{I}^{\otimes n} \notin \langle P_1,\ldots, P_r\rangle,$ mais c'est bien le cas, et nous verrons pourquoi un peu plus loin dans la leçon.)

En supposant que nous disposons d'une telle liste $P_1,\ldots,P_r,$ l'espace de code défini par ces générateurs stabilisateurs est le sous-espace $\mathcal{C}$ contenant tous les vecteurs d'état quantique à $n$ qubits fixés par les $r$ générateurs stabilisateurs.

$$\mathcal{C} = \bigl\{ \vert\psi\rangle \,:\, P_1 \vert\psi\rangle = \cdots = P_r \vert\psi\rangle = \vert\psi\rangle \bigr\}$$

Les vecteurs d'état quantique dans ce sous-espace sont précisément ceux qui peuvent être considérés comme des encodages valides d'états quantiques. Nous aborderons le processus d'encodage proprement dit plus tard.

Enfin, le stabilisateur du code défini par les générateurs stabilisateurs $P_1, \ldots, P_r$ est l'ensemble engendré par ces opérations :

$$\langle P_1,\ldots,P_r\rangle.$$

Une façon naturelle de concevoir un code stabilisateur est de voir les générateurs stabilisateurs comme des observables, et d'interpréter collectivement les résultats des mesures associées à ces observables comme un syndrome d'erreur. Les encodages valides sont des vecteurs d'état quantique à $n$ qubits pour lesquels les résultats de mesure, en tant que valeurs propres, sont tous garantis être $+1.$ Tout autre syndrome, où au moins un résultat de mesure $-1$ se produit, signale qu'une erreur a été détectée.

Nous allons examiner plusieurs exemples sous peu, mais voici d'abord quelques remarques sur les trois conditions imposées aux générateurs stabilisateurs.

La première condition est naturelle, à la lumière de l'interprétation des générateurs stabilisateurs comme des observables, car elle implique que l'ordre dans lequel les mesures sont effectuées n'a pas d'importance : les observables commutent, donc les mesures commutent. Cela impose naturellement certaines contraintes algébriques sur les codes stabilisateurs, qui sont importantes pour leur fonctionnement.

La deuxième condition exige que les générateurs stabilisateurs forment un ensemble générateur minimal, ce qui signifie que la suppression de l'un d'entre eux donnerait un stabilisateur plus petit. À strictement parler, cette condition n'est pas vraiment essentielle au fonctionnement des codes stabilisateurs dans un sens opérationnel — et, comme nous le verrons dans la prochaine leçon, il est parfois utile de considérer des ensembles de générateurs stabilisateurs pour des codes qui ne satisfont pas réellement cette condition. Pour analyser les codes stabilisateurs et expliquer leurs propriétés, cependant, nous supposerons que cette condition est en vigueur. En résumé, cette condition garantit que chaque observable que nous mesurons pour obtenir le syndrome d'erreur apporte des informations sur les erreurs possibles, plutôt que d'être redondante et de produire des résultats qui pourraient être déduits des autres mesures des générateurs stabilisateurs.

La troisième condition exige qu'au moins un vecteur non nul soit fixé par tous les générateurs stabilisateurs, ce qui est équivalent à $-\mathbb{I}^{\otimes n}$ n'étant pas contenu dans le stabilisateur. La nécessité de cette condition vient du fait qu'il est effectivement possible de choisir un ensemble générateur minimal d'opérations de Pauli à $n$ qubits qui commutent toutes entre elles, et pourtant aucun vecteur non nul n'est fixé par chacune de ces opérations. Nous ne nous intéressons pas aux « codes » pour lesquels il n'y a pas d'encodages valides, donc nous excluons cette possibilité en imposant cette condition dans la définition.

Exemples

Voici quelques exemples de codes stabilisateurs pour de petites valeurs de $n.$ Nous verrons d'autres exemples, y compris des cas où $n$ peut être beaucoup plus grand, dans la prochaine leçon.

Code à répétition 3 bits

Le code à répétition 3 bits est un exemple de code stabilisateur, dont les générateurs stabilisateurs sont $Z \otimes Z \otimes \mathbb{I}$ et $\mathbb{I} \otimes Z \otimes Z.$

On peut vérifier facilement que ces deux générateurs stabilisateurs satisfont les conditions requises. Premièrement, les deux générateurs stabilisateurs $Z \otimes Z \otimes \mathbb{I}$ et $\mathbb{I} \otimes Z \otimes Z$ commutent entre eux.

$$(Z \otimes Z \otimes \mathbb{I})(\mathbb{I} \otimes Z \otimes Z) = Z \otimes \mathbb{I} \otimes Z = (\mathbb{I} \otimes Z \otimes Z)(Z \otimes Z \otimes \mathbb{I})$$

Deuxièmement, nous avons un ensemble générateur minimal (de façon assez triviale dans ce cas).

$$\begin{aligned} Z \otimes Z \otimes \mathbb{I} \notin \langle\mathbb{I} \otimes Z \otimes Z\rangle & = \{\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, \mathbb{I} \otimes Z \otimes Z\}\\[1mm] \mathbb{I} \otimes Z \otimes Z \notin \langle Z \otimes Z \otimes \mathbb{I}\rangle & = \{\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, Z \otimes Z \otimes \mathbb{I}\} \end{aligned}$$

Et troisièmement, nous savons déjà que $\vert 000\rangle$ et $\vert 111\rangle,$ ainsi que toute combinaison linéaire de ces vecteurs, sont fixés par $Z \otimes Z \otimes \mathbb{I}$ et $\mathbb{I} \otimes Z \otimes Z.$ On peut aussi en conclure en utilisant la condition équivalente de la définition.

$$-\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\notin \langle Z \otimes Z \otimes \mathbb{I}, \mathbb{I} \otimes Z \otimes Z\rangle = \{ \mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, Z\otimes Z\otimes\mathbb{I}, Z\otimes\mathbb{I}\otimes Z, \mathbb{I}\otimes Z\otimes Z \}$$

Ces conditions peuvent être beaucoup plus difficiles à vérifier pour des codes stabilisateurs plus complexes.

Code à répétition 3 bits modifié

Dans la leçon précédente, nous avons vu qu'il est possible de modifier le code à répétition 3 bits pour le rendre capable de protéger contre les erreurs de déphasage plutôt que contre les erreurs de retournement de bit. En tant que code stabilisateur, ce nouveau code est facile à décrire : ses générateurs stabilisateurs sont $X \otimes X \otimes \mathbb{I}$ et $\mathbb{I} \otimes X \otimes X.$

Cette fois, les générateurs stabilisateurs représentent des observables $X\otimes X$ plutôt que $Z\otimes Z$, il s'agit donc essentiellement de contrôles de parité dans la base plus/moins plutôt que dans la base standard. Les trois conditions requises sur les générateurs stabilisateurs sont facilement vérifiées, de façon similaire au code à répétition 3 bits ordinaire.

Code de Shor à 9 qubits

Voici le code de Shor à 9 qubits, qui est également un code stabilisateur, exprimé par ses générateurs stabilisateurs.

$$\begin{gathered} Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z\\[1mm] X \otimes X \otimes X \otimes X \otimes X \otimes X \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\otimes X \otimes X \otimes X \otimes X \otimes X \otimes X \end{gathered}$$

Dans ce cas, nous avons essentiellement trois copies du code à répétition 3 bits, une pour chacun des trois blocs de trois qubits, ainsi que les deux derniers générateurs stabilisateurs, qui prennent une forme rappelant le circuit de détection des déphasages pour ce code.

Une autre façon de concevoir les deux derniers générateurs stabilisateurs est qu'ils prennent la même forme que pour le code à répétition 3 bits contre les déphasages, sauf que $X\otimes X\otimes X$ est substitué à $X,$ ce qui est cohérent avec le fait que $X\otimes X\otimes X$ correspond à une opération $X$ sur des qubits logiques encodés à l'aide du code à répétition 3 bits.

Avant de passer à d'autres exemples, il convient de noter que les symboles de produit tensoriel sont souvent omis lors de la description des codes stabilisateurs par des listes de générateurs stabilisateurs, car cela les rend généralement plus faciles à lire et à comprendre leurs structures. Par exemple, les mêmes générateurs stabilisateurs que ci-dessus pour le code de Shor à 9 qubits ressemblent à ceci sans les symboles de produit tensoriel écrits explicitement.

$$\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}$$

Code de Steane à 7 qubits

Voici un autre exemple de code stabilisateur, connu sous le nom de code de Steane à 7 qubits. Il présente des caractéristiques remarquables, et nous reviendrons sur ce code à plusieurs reprises dans les leçons restantes du cours.

$$\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}$$

Pour l'instant, observons simplement qu'il s'agit d'un code stabilisateur valide. Les trois premiers générateurs stabilisateurs commutent clairement entre eux, car $Z$ commute avec lui-même et l'identité commute avec tout, et la situation est similaire pour les trois derniers générateurs stabilisateurs. Il reste à vérifier que si l'on prend un générateur stabilisateur de type $Z$ (c'est-à-dire l'un des trois premiers) et un générateur stabilisateur de type $X$ (c'est-à-dire l'un des trois derniers), ces deux générateurs commutent, et on peut passer en revue les 9 pairages possibles pour le vérifier. Dans tous ces cas, une matrice de Pauli $X$ et une matrice de Pauli $Z$ se retrouvent toujours au même emplacement un nombre pair de fois, de sorte que les deux générateurs commutent, tout comme $X\otimes X$ et $Z\otimes Z$ commutent. Il s'agit également d'un ensemble générateur minimal, et il définit un espace de code non trivial, ce sont des faits que nous te laissons méditer.

Le code de Steane à 7 qubits est similaire au code de Shor à 9 qubits en ce sens qu'il encode un seul qubit et permet la correction d'une erreur arbitraire sur un qubit, mais il ne nécessite que 7 qubits au lieu de 9.

Code à 5 qubits

Sept n'est pas le nombre minimal de qubits nécessaires pour encoder un qubit et le protéger contre une erreur arbitraire sur un qubit — voici un code stabilisateur qui y parvient en utilisant seulement 5 qubits.

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

Ce code est généralement appelé le code à 5 qubits. C'est le nombre minimal de qubits dans un code correcteur d'erreurs quantiques capable de corriger une erreur arbitraire sur un seul qubit.

Codes stabilisateurs unidimensionnels

Voici un autre exemple de code stabilisateur, bien qu'il n'encode en réalité aucun qubit : l'espace de code est unidimensionnel. Il s'agit cependant toujours d'un code stabilisateur valide selon la définition.

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

Plus précisément, l'espace de code est l'espace unidimensionnel engendré par un e-bit $\vert\phi^+\rangle.$

Voici un exemple connexe d'un code stabilisateur dont l'espace de code est l'espace unidimensionnel engendré par un état GHZ $(\vert 000\rangle + \vert 111\rangle)/\sqrt{2}.$

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

Dimension de l'espace de code

Supposons que nous ayons un code stabilisateur, décrit par des générateurs stabilisateurs à $n$ qubits $P_1,\ldots,P_r.$ La toute première question qui vient à l'esprit à propos de ce code est peut-être : « Combien de qubits encode-t-il ? »

Cette question a une réponse simple. En supposant que les générateurs stabilisateurs à $n$ qubits $P_1, \ldots, P_r$ satisfassent les trois exigences de la définition (à savoir que les générateurs stabilisateurs commutent tous entre eux, que c'est un ensemble générateur minimal, et que l'espace de code est non vide), il doit alors s'ensuivre que l'espace de code pour ce code stabilisateur a la dimension $2^{n-r},$ de sorte que $n-r$ qubits peuvent être encodés à l'aide de ce code.

Intuitivement, nous disposons de $n$ qubits pour cet encodage, et chaque générateur stabilisateur « retire effectivement un qubit » en termes de nombre de qubits que nous pouvons encoder. Note que cela ne concerne pas quelles erreurs ni combien d'erreurs peuvent être détectées ou corrigées, c'est uniquement une affirmation sur la dimension de l'espace de code.

Par exemple, pour le code à répétition 3 bits et sa version modifiée pour les erreurs de déphasage, nous avons $n=3$ qubits et $r=2$ générateurs stabilisateurs, et donc ces codes peuvent chacun encoder 1 qubit. Pour un autre exemple, considère le code à 5 qubits : nous avons 5 qubits et 4 générateurs stabilisateurs, donc une fois de plus l'espace de code a la dimension 2, ce qui signifie qu'un qubit peut être encodé à l'aide de ce code. Pour un dernier exemple, le code dont les générateurs stabilisateurs sont $X\otimes X$ et $Z\otimes Z$ a un espace de code unidimensionnel, engendré par l'état $\vert\phi^+\rangle,$ ce qui est cohérent avec $n=2$ qubits et $r=2$ générateurs stabilisateurs.

Voyons maintenant comment ce résultat peut être prouvé. La première étape consiste à observer que, puisque les générateurs stabilisateurs commutent, et puisque chaque opération de Pauli est son propre inverse, tout élément du stabilisateur peut s'exprimer comme un produit

$$P_1^{a_1} \cdots P_r^{a_r},$$

où $a_1,\ldots,a_r\in\{0,1\}.$ De manière équivalente, chaque élément du stabilisateur s'obtient en multipliant ensemble un sous-ensemble des générateurs stabilisateurs. En effet, chaque élément du stabilisateur peut s'exprimer de manière unique de cette façon, grâce à la condition que $\{P_1,\ldots,P_r\}$ est un ensemble générateur minimal.

Ensuite, définissons $\Pi_k$ comme la projection sur l'espace des vecteurs propres de valeur propre $+1$ de $P_k,$ pour chaque $k\in\{1,\ldots,r\}.$ Ces projections peuvent être obtenues en faisant la moyenne des opérations de Pauli correspondantes avec l'opération identité comme suit.

$$\Pi_k = \frac{\mathbb{I}^{\otimes n} + P_k}{2}$$

L'espace de code $\mathcal{C}$ est le sous-espace de tous les vecteurs fixés par les $r$ générateurs stabilisateurs $P_1,\ldots,P_r,$ ou de manière équivalente, par les $r$ projections $\Pi_1,\ldots,\Pi_r.$

Étant donné que les générateurs stabilisateurs commutent tous entre eux, les projections $\Pi_1,\ldots,\Pi_r$ doivent également commuter. Cela nous permet d'utiliser un résultat d'algèbre linéaire, à savoir que le produit de ces projections est la projection sur l'intersection des sous-espaces correspondant aux projections individuelles. Autrement dit, le produit $\Pi_1\cdots\Pi_r$ est la projection sur l'espace de code $\mathcal{C}.$

Nous pouvons maintenant développer le produit $\Pi_1\cdots\Pi_r$ à l'aide des formules de ces projections pour obtenir l'expression suivante.

$$\Pi_1\cdots\Pi_r = \biggl(\frac{\mathbb{I}^{\otimes n} + P_1}{2}\biggr)\cdots\biggl(\frac{\mathbb{I}^{\otimes n} + P_r}{2}\biggr) = \frac{1}{2^r}\sum_{a_1,\ldots,a_r \in \{0,1\}} P_1^{a_1}\cdots P_r^{a_r}$$

En d'autres termes, la projection sur l'espace de code d'un code stabilisateur est égale, en tant que matrice, à la moyenne sur tous les éléments du stabilisateur de ce code.

Enfin, nous pouvons calculer la dimension de l'espace de code en utilisant le fait que la dimension de tout sous-espace est égale à la trace de la projection sur ce sous-espace. Ainsi, la dimension de l'espace de code $\mathcal{C}$ est donnée par la formule suivante.

$$\operatorname{dim}(\mathcal{C}) = \operatorname{Tr}(\Pi_1\cdots\Pi_r) = \frac{1}{2^r} \sum_{a_1,\ldots,a_r \in \{0,1\}} \operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r})$$

Nous pouvons évaluer cette expression en utilisant quelques résultats élémentaires.

• Nous avons $P_1^0 \cdots P_r^0 = \mathbb{I}^{\otimes n}$ et donc

  $$\operatorname{Tr}(P_1^{0}\cdots P_r^{0}) = 2^n.$$

• Pour $(a_1,\ldots,a_r) \neq (0,\ldots,0),$ le produit $P_1^{a_1}\cdots P_r^{a_r}$ doit être $\pm 1$ fois une opération de Pauli — mais on ne peut pas obtenir $\mathbb{I}^{\otimes n}$ car cela contredirait la minimalité de l'ensemble $\{P_1,\ldots,P_r\},$ et on ne peut pas obtenir $-\mathbb{I}^{\otimes n}$ car la troisième condition sur les générateurs stabilisateurs l'interdit. Par conséquent, comme la trace de toute opération de Pauli non identité est nulle, on obtient

  $$\operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r}) = 0.$$

La dimension de l'espace de code est donc $2^{n-r}$ comme annoncé :

$$\begin{aligned} \operatorname{dim}(\mathcal{C}) & = \frac{1}{2^r} \sum_{a_1,\ldots,a_r \in \{0,1\}} \operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r}) \\ & = \frac{1}{2^r} \operatorname{Tr}(P_1^{0}\cdots P_r^{0}) \\ & = 2^{n-r}. \end{aligned}$$

Notons en passant que nous pouvons maintenant constater que l'hypothèse que $-\mathbb{I}^{\otimes n}$ n'est pas contenu dans le stabilisateur implique que l'espace de code doit contenir au moins un vecteur d'état quantique. En effet, comme nous venons de le vérifier, cette hypothèse implique que l'espace de code a la dimension $2^{n-r},$ qui ne peut pas être nulle. L'implication réciproque est d'ailleurs triviale : si $-\mathbb{I}^{\otimes n}$ est contenu dans le stabilisateur, alors l'espace de code ne peut contenir aucun vecteur d'état quantique, car aucun vecteur non nul n'est fixé par cette opération.

Opérations de Clifford et encodages

Nous allons maintenant aborder brièvement la façon dont les qubits peuvent être encodés à l'aide de codes stabilisateurs, mais pour cela nous devons d'abord introduire les opérations de Clifford.

Opérations de Clifford

Les opérations de Clifford sont des opérations unitaires, sur un nombre quelconque de qubits, qui peuvent être implémentées par des circuits quantiques avec un ensemble restreint de portes :

• Portes de Hadamard
• Portes $S$
• Portes CNOT

À noter que les portes $T$ ne font pas partie de cette liste, pas plus que les portes de Toffoli et de Fredkin. Non seulement ces portes ne figurent pas dans la liste, mais en fait il n'est pas possible de les implémenter avec celles qui y sont listées ; ce ne sont pas des opérations de Clifford. Les opérations de Pauli, en revanche, sont des opérations de Clifford car elles peuvent être implémentées avec des séquences de portes de Hadamard et $S$.

C'est une façon simple de définir les opérations de Clifford, mais cela n'explique pas pourquoi elles sont définies ainsi ni ce qui rend cet ensemble de portes particulier spécial. La vraie raison pour laquelle les opérations de Clifford sont définies de cette façon est que, à des facteurs de phase globale près, les opérations de Clifford sont précisément les opérations unitaires qui transforment toujours des opérations de Pauli en opérations de Pauli par conjugaison. Pour être plus précis, une opération unitaire $U$ sur $n$ qubits est équivalente à une opération de Clifford à un facteur de phase près si et seulement si, pour toute opération de Pauli $P$ sur $n$ qubits, on a

$$U P U^{\dagger} = \pm Q$$

pour une certaine opération de Pauli $Q$ sur $n$ qubits.

(Remarque : il n'est pas possible d'avoir $U P U^{\dagger} = \alpha Q$ avec $\alpha\notin\{+1,-1\}$ lorsque $U$ est unitaire et que $P$ et $Q$ sont des opérations de Pauli. Cela découle du fait que la matrice au membre gauche de l'équation est à la fois unitaire et hermitienne, et que $+1$ et $-1$ sont les seuls choix pour $\alpha$ permettant au membre droit d'être également unitaire et hermitien.)

Il est facile de vérifier la propriété de conjugaison décrite ci-dessus lorsque $U$ est une porte de Hadamard, $S$ ou CNOT. En particulier, c'est aisé pour les portes de Hadamard,

$$H X H^{\dagger} = Z, \qquad H Y H^{\dagger} = -Y, \qquad H Z H^{\dagger} = X,$$

et les portes $S$,

$$S X S^{\dagger} = Y, \qquad S Y S^{\dagger} = -X, \qquad S Z S^{\dagger} = Z.$$

Pour les portes CNOT, il y a 15 opérations de Pauli non-identité à deux qubits à vérifier. On peut bien sûr les vérifier individuellement — mais les relations entre les portes CNOT et les portes $X$ et $Z$ (présentées sous forme de circuits dans la leçon précédente), combinées aux règles de multiplication des matrices de Pauli, offrent un raccourci vers la même conclusion.

Une fois que l'on sait que cette propriété de conjugaison est vraie pour les portes de Hadamard, $S$ et CNOT, on peut immédiatement conclure qu'elle est vraie pour les circuits composés de ces portes — c'est-à-dire toutes les opérations de Clifford.

Il est plus difficile de prouver que la relation fonctionne dans l'autre sens, à savoir que si une opération unitaire $U$ donnée satisfait la propriété de conjugaison pour les opérations de Pauli, alors il doit être possible de l'implémenter (à une phase globale près) en utilisant uniquement des portes de Hadamard, $S$ et CNOT. Ce point ne sera pas expliqué dans cette leçon, mais c'est bien le cas.

Les opérations de Clifford ne sont pas universelles pour le calcul quantique ; contrairement aux ensembles de portes universels, il n'est pas possible d'approximer des opérations unitaires arbitraires avec n'importe quelle précision à l'aide d'opérations de Clifford. En effet, pour une valeur de $n$ donnée, il n'existe qu'un nombre fini d'opérations de Clifford sur $n$ qubits (à des facteurs de phase près). Effectuer des opérations de Clifford sur des états de base standard suivies de mesures dans la base standard ne permet pas non plus d'effectuer des calculs hors de portée des algorithmes classiques — car on peut simuler efficacement classiquement des calculs de cette forme. Ce fait est connu sous le nom de théorème de Gottesman-Knill.

Encodeurs pour les codes stabilisateurs

Un code stabilisateur définit un espace de code d'une certaine dimension, et nous avons la liberté d'utiliser cet espace de code comme bon nous semble — rien ne nous oblige à encoder des qubits dans cet espace de code d'une façon particulière. Il est toujours possible, cependant, d'utiliser une opération de Clifford comme encodeur, si on le souhaite. Pour être plus précis, pour tout code stabilisateur qui permet d'encoder $m$ qubits en $n$ qubits, il existe une opération de Clifford $U$ sur $n$ qubits telle que, pour tout vecteur d'état quantique $\vert\phi\rangle$ sur $m$ qubits, on a que

$$\vert\psi\rangle = U \bigl(\vert 0^{n-m} \rangle \otimes \vert \phi\rangle\bigr)$$

est un vecteur d'état quantique dans l'espace de code de notre code que l'on peut interpréter comme un encodage de $\vert\phi\rangle$.

C'est une bonne nouvelle, car les opérations de Clifford sont relativement simples comparées aux opérations unitaires arbitraires, et il existe des moyens d'optimiser leur implémentation à l'aide de techniques similaires à celles utilisées dans la preuve du théorème de Gottesman-Knill. En conséquence, les circuits permettant d'encoder des états à l'aide de codes stabilisateurs n'ont jamais besoin d'être trop grands. En particulier, il est toujours possible d'effectuer un encodage pour un code stabilisateur sur $n$ qubits à l'aide d'une opération de Clifford nécessitant $O(n^2/\log(n))$ portes. C'est parce que toute opération de Clifford sur $n$ qubits peut être implémentée par un circuit de cette taille.

Par exemple, voici un encodeur pour le code de Steane à 7 qubits. Il s'agit bien d'une opération de Clifford et, dans ce cas précis, il n'a même pas besoin de portes $S$.

Détection des erreurs

Pour un code stabilisateur sur $n$ qubits décrit par des générateurs stabilisateurs $P_1,\ldots, P_r,$ la détection d'erreurs fonctionne de la manière suivante.

Pour détecter les erreurs, tous les générateurs stabilisateurs sont mesurés comme des observables. Il y a $r$ générateurs stabilisateurs, et donc $r$ résultats de mesure, chacun valant $+1$ ou $-1$ (ou une valeur binaire si on choisit d'associer $0$ à $+1$ et $1$ à $-1$, respectivement). On interprète les $r$ résultats collectivement, comme un vecteur ou une chaîne, comme un syndrome. Le syndrome $(+1,\ldots,+1)$ indique qu'aucune erreur n'a été détectée, tandis qu'au moins un $-1$ quelque part dans le syndrome indique qu'une erreur a été détectée.

Supposons en particulier que $E$ est une opération de Pauli sur $n$ qubits, représentant une erreur hypothétique. (On ne considère que les opérations de Pauli comme erreurs, soit dit en passant, car la discrétisation des erreurs fonctionne de la même manière pour tous les codes stabilisateurs que pour le code de Shor à 9 qubits.) Il y a trois cas qui déterminent si $E$ est détectée comme une erreur ou non.

Cas de détection d'erreurs

1. L'opération $E$ est proportionnelle à un élément du stabilisateur.

   $$E = \pm Q \; \text{pour un certain}\; Q \in \langle P_1,\ldots,P_r\rangle$$

   Dans ce cas, $E$ doit commuter avec chaque générateur stabilisateur, donc on obtient le syndrome $(+1,\ldots,+1)$. Cela signifie que $E$ n'est pas détectée comme une erreur.

2. L'opération $E$ n'est pas proportionnelle à un élément du stabilisateur, mais elle commute néanmoins avec chaque générateur stabilisateur.

   $$E\neq \pm Q\; \text{pour} \; Q \in \langle P_1,\ldots,P_r\rangle, \;\text{mais}\; E P_k = P_k E \;\text{pour tout}\; k\in\{1,\ldots,r\}$$

   Il s'agit d'une erreur qui modifie les vecteurs dans l'espace de code d'une manière non triviale. Mais, comme $E$ commute avec chaque générateur stabilisateur, le syndrome est $(+1,\ldots,+1)$, donc $E$ passe inaperçue par le code.

3. L'opération $E$ anti-commute avec au moins l'un des générateurs stabilisateurs.

   $$P_k E = -E P_k \; \text{pour au moins un} \; k\in\{1,\ldots,r\}$$

   Le syndrome est différent de $(+1,\ldots,+1)$, donc l'erreur $E$ est détectée par le code.

Dans le premier cas, l'erreur $E$ n'est pas un problème car cette opération ne fait rien aux vecteurs dans l'espace de code, si ce n'est peut-être injecter une phase globale sans importance : $E \ket{\psi} = \pm\ket{\psi}$ pour tout état encodé $\ket{\psi}$. En substance, ce n'est pas réellement une erreur — quelle que soit l'action non triviale que $E$ peut avoir, elle se produit en dehors de l'espace de code — donc il est bien que $E$ ne soit pas détectée comme une erreur, car rien n'est à faire à son sujet.

Le deuxième cas est, intuitivement, le mauvais cas. C'est l'anti-commutation d'une erreur avec un générateur stabilisateur qui provoque l'apparition d'un $-1$ quelque part dans le syndrome, signalant une erreur, mais cela ne se produit pas dans ce cas. Ainsi, on a une erreur $E$ qui modifie bien les vecteurs dans l'espace de code d'une façon non triviale, mais elle passe inaperçue par le code. Par exemple, pour le code à répétition à 3 bits, l'opération $E = X\otimes X\otimes X$ appartient à cette catégorie.

Le fait qu'une telle erreur $E$ doive nécessairement modifier certains vecteurs de l'espace de code d'une façon non triviale peut être argumenté comme suit. Par l'hypothèse que $E$ commute avec $P_1,\ldots,P_r$ mais n'est pas proportionnelle à un élément stabilisateur, on peut conclure qu'on obtiendrait un nouveau code stabilisateur valide en incluant $E$ comme générateur stabilisateur en plus de $P_1,\ldots,P_r$. L'espace de code de ce nouveau code, cependant, n'a que la moitié de la dimension de l'espace de code original, ce qui nous permet de conclure que l'action de $E$ sur l'espace de code original ne peut pas être proportionnelle à l'opération identité.

Pour le dernier des trois cas, à savoir que l'erreur $E$ anti-commute avec au moins un générateur stabilisateur, le syndrome a au moins un $-1$ quelque part, ce qui indique qu'il y a un problème. Comme nous l'avons déjà évoqué, le syndrome n'identifiera pas $E$ de manière unique en général, il est donc toujours nécessaire de choisir une opération de correction pour chaque syndrome, qui peut corriger l'erreur $E$ ou non. Nous aborderons cette étape dans peu de temps, dans la dernière partie de la leçon.

Distance d'un code stabilisateur

En termes de terminologie, lorsqu'on parle de la distance d'un code stabilisateur, on entend le poids minimal d'une opération de Pauli $E$ qui tombe dans la deuxième catégorie ci-dessus — c'est-à-dire qu'elle modifie l'espace de code d'une façon non triviale, mais que le code ne la détecte pas. Lorsqu'on dit qu'un code stabilisateur est un code stabilisateur $[[n,m,d]]$, en utilisant des doubles crochets, cela signifie ce qui suit :

1. Les encodages font $n$ qubits de longueur,
2. le code permet d'encoder $m$ qubits, et
3. la distance du code est $d$.

À titre d'exemple, considérons le code de Steane à 7 qubits. Voici les générateurs stabilisateurs de ce code :

$$\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}$$

Ce code a une distance de 3, et on peut l'argumenter comme suit.

Considérons d'abord toute opération de Pauli $E$ de poids au plus 2, et supposons que cette opération commute avec les six générateurs stabilisateurs. Nous conclurons que $E$ doit être l'opération identité, qui (comme toujours) est un élément du stabilisateur. Cela montrera que la distance du code est strictement supérieure à 2. Supposons en particulier que $E$ prend la forme

$$E = P \otimes Q \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}$$

pour $P$ et $Q$ étant des matrices de Pauli potentiellement non-identité. Il ne s'agit que d'un cas, et il est nécessaire de répéter l'argument qui suit pour toutes les autres localisations possibles de matrices de Pauli non-identité parmi les facteurs tensoriels de $E$, mais l'argument est essentiellement le même pour toutes les localisations possibles.

L'opération $E$ commute avec les six générateurs stabilisateurs, donc elle commute en particulier avec ces deux-ci :

$$\begin{gathered} Z \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes Z\\[1mm] X \otimes \mathbb{I} \otimes X \otimes \mathbb{I} \otimes X \otimes \mathbb{I} \otimes X \end{gathered}$$

Le facteur tensoriel $Q$ dans notre erreur $E$ s'aligne avec la matrice identité dans ces deux générateurs stabilisateurs (c'est pourquoi ils ont été sélectionnés). Étant donné que nous avons des matrices identité dans les 5 positions les plus à droite de $E$, nous concluons que $P$ doit commuter avec $X$ et $Z$, car sinon $E$ anti-communterait avec l'un des deux générateurs. Cependant, la seule matrice de Pauli qui commute à la fois avec $X$ et $Z$ est la matrice identité, donc $P = \mathbb{I}$.

Maintenant que nous savons cela, nous pouvons choisir deux autres générateurs stabilisateurs qui ont un $X$ et un $Z$ en deuxième position à partir de la gauche, et nous tirons une conclusion similaire : $Q = \mathbb{I}$. C'est donc le cas que $E$ est l'opération identité.

Ainsi, il n'est pas possible qu'une erreur de poids au plus 2 passe inaperçue par ce code, à moins que l'erreur ne soit l'opération identité (qui est dans le stabilisateur et n'est donc pas réellement une erreur). D'autre part, il existe des opérations de Pauli de poids 3 qui commutent avec les six générateurs stabilisateurs, mais ne sont pas proportionnelles à des éléments du stabilisateur, comme $\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes X\otimes X\otimes X$ et $\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes Z\otimes Z\otimes Z$. Cela établit que ce code a bien une distance de 3, comme affirmé.

Correction des erreurs

Le dernier sujet de discussion de cette leçon est la correction des erreurs pour les codes stabilisateurs. Comme d'habitude, supposons que nous avons un code stabilisateur spécifié par des générateurs stabilisateurs sur $n$ qubits $P_1, \ldots, P_r$.

Les opérations de Pauli sur $n$ qubits, en tant qu'erreurs pouvant affecter des états encodés avec ce code, sont partitionnées en collections de même taille selon le syndrome qu'elles provoquent. Il y a $2^r$ syndromes distincts et $4^n$ opérations de Pauli, ce qui signifie qu'il y a $4^n/2^r$ opérations de Pauli provoquant chaque syndrome. N'importe laquelle de ces erreurs pourrait être responsable du syndrome correspondant.

Cependant, parmi les $4^n/2^r$ opérations de Pauli qui provoquent chaque syndrome, certaines doivent être considérées comme équivalentes. En particulier, si le produit de deux opérations de Pauli est proportionnel à un élément du stabilisateur, alors ces deux opérations sont effectivement équivalentes en tant qu'erreurs.

Une autre façon de dire cela est que si on applique une opération de correction $C$ pour tenter de corriger une erreur $E$, alors cette correction réussit tant que la composition $CE$ est proportionnelle à un élément du stabilisateur. Étant donné qu'il y a $2^r$ éléments dans le stabilisateur, il s'ensuit que chaque opération de correction $C$ corrige $2^r$ erreurs de Pauli différentes. Cela laisse $4^{n-r}$ classes inéquivalentes d'opérations de Pauli, considérées comme des erreurs, qui sont compatibles avec chaque syndrome possible.

Cela signifie que, sauf si $n=r$ (auquel cas nous avons un espace de code trivial unidimensionnel), il n'est pas possible de corriger chaque erreur détectée par un code stabilisateur. Ce qu'on doit faire à la place, c'est choisir une seule opération de correction pour chaque syndrome, dans l'espoir de corriger une seule classe d'erreurs équivalentes qui provoquent ce syndrome.

Une stratégie naturelle pour choisir quelle opération de correction effectuer pour chaque syndrome est de choisir l'opération de Pauli de poids minimal qui, en tant qu'erreur, provoque ce syndrome. Il peut en fait y avoir plusieurs opérations qui sont à égalité pour l'erreur de poids minimal compatible avec un syndrome donné, auquel cas on peut en sélectionner n'importe laquelle. L'idée est que les opérations de Pauli de poids plus faible représentent des explications plus probables pour le syndrome mesuré. Ce n'est peut-être pas le cas pour certains modèles de bruit, et une autre stratégie consiste à calculer l'erreur la plus probable qui cause le syndrome donné, en fonction du modèle de bruit choisi. Pour cette leçon, cependant, nous allons garder les choses simples et ne considérer que les corrections de poids minimal.

Pour un code stabilisateur de distance $d$, cette stratégie consistant à choisir l'opération de correction comme étant une opération de Pauli de poids minimal compatible avec le syndrome mesuré permet toujours de corriger les erreurs de poids strictement inférieur à la moitié de $d$, ou autrement dit, de poids au plus $(d-1)/2$. Cela montre, par exemple, que le code de Steane à 7 qubits peut corriger toute erreur de Pauli de poids un, et par la discrétisation des erreurs, cela signifie que le code de Steane peut corriger une erreur arbitraire sur un qubit.

Pour comprendre comment cela fonctionne, considère le diagramme ci-dessous. Le cercle de gauche représente toutes les opérations de Pauli qui donnent le syndrome $(+1,\ldots,+1)$, c'est-à-dire le syndrome qui suggère qu'aucune erreur n'a eu lieu et que tout va bien. Parmi ces opérations, on trouve des éléments du stabilisateur (ou des opérations qui sont proportionnelles à des éléments du stabilisateur, pour être plus précis), ainsi que des erreurs non triviales qui modifient l'espace de code d'une certaine façon mais ne sont pas détectées par le code. Par définition de la distance, toute opération de Pauli dans cette catégorie doit avoir un poids d'au moins $d$, car $d$ est défini comme le poids minimal de ces opérations.

Le cercle de droite représente les opérations de Pauli qui donnent un syndrome différent $s\neq(+1,\ldots,+1)$, y compris une erreur $E$ de poids strictement inférieur à $d/2$ que nous allons considérer.

L'opération de correction $C$ choisie pour le syndrome $s$ est l'opération de Pauli de poids minimal dans la collection représentée par le cercle de droite dans le diagramme (ou n'importe laquelle d'entre elles en cas d'égalité). Donc, il se pourrait que $C = E$, mais pas nécessairement. Ce que l'on peut dire avec certitude, cependant, c'est que $C$ ne peut pas avoir un poids plus grand que le poids de $E$, car $C$ a un poids minimal parmi les opérations de cette collection — et donc $C$ a un poids strictement inférieur à $d/2$.

Considérons maintenant ce qui se passe lorsque l'opération de correction $C$ est appliquée à l'état obtenu après que l'erreur $E$ se soit produite. En supposant que l'encodage original était $\vert\psi\rangle$, on se retrouve avec $CE\vert\psi\rangle$. Notre objectif sera de montrer que $CE$ est proportionnel à un élément du stabilisateur, ce qui implique que la correction réussit et (à une phase globale près) on se retrouve avec l'état encodé original $\vert\psi\rangle$.

Premièrement, comme $E$ et $C$ provoquent le même syndrome, la composition $CE$ doit commuter avec chaque générateur stabilisateur. En particulier, si $P_k$ est l'un des générateurs stabilisateurs, alors on doit avoir

$$P_k E = \alpha E P_k \quad\text{et}\quad P_k C = \alpha C P_k$$

pour la même valeur de $\alpha\in\{+1,-1\}$, car il s'agit de la $k$-ième entrée dans le syndrome $s$ que $C$ et $E$ génèrent tous les deux. On a donc

$$P_k (CE) = \alpha C P_k E = \alpha^2 (CE) P_k = (CE) P_k,$$

donc $P_k$ commute avec $CE$. On a donc montré que $CE$ appartient au cercle de gauche dans le diagramme, car il génère le syndrome $(+1,\ldots,+1)$.

Deuxièmement, la composition $CE$ doit avoir un poids au plus égal à la somme des poids de $C$ et $E$ — ce qui découle d'une réflexion rapide sur les produits d'opérations de Pauli — et donc le poids de $CE$ est strictement inférieur à $d$. Cela implique que $CE$ est proportionnel à un élément du stabilisateur de notre code, ce que nous voulions montrer. En choisissant nos opérations de correction comme représentants de poids minimal de l'ensemble des erreurs qui génèrent chaque syndrome, on est donc assuré de corriger toute erreur de Pauli de poids inférieur à la moitié de la distance du code.

Il y a cependant un problème. Pour les codes stabilisateurs en général, calculer l'opération de Pauli de poids minimal causant un syndrome donné est un problème difficile du point de vue computationnel. (En fait, c'est vrai même pour les codes classiques, que dans ce contexte on peut penser comme des codes stabilisateurs où seules les matrices $\mathbb{I}$ et $Z$ apparaissent comme facteurs tensoriels dans les générateurs stabilisateurs.) Donc, contrairement à l'étape d'encodage, les opérations de Clifford ne vont pas venir à notre secours cette fois-ci.

La solution consiste à choisir des codes spécifiques pour lesquels de bonnes corrections peuvent être calculées efficacement, pour lesquels il n'existe pas de recette simple. En somme, concevoir des codes stabilisateurs pour lesquels de bonnes opérations de correction peuvent être calculées efficacement fait partie de l'art de la conception de codes quantiques. Nous verrons cet art à l'œuvre dans la prochaine leçon.