Codes répétitifs

Nous allons commencer cette leçon par une présentation des codes répétitifs. Les codes répétitifs ne protègent pas l'information quantique contre tous les types d'erreurs pouvant survenir sur des qubits, mais ils constituent la base du code de Shor à 9 qubits, que nous verrons dans la prochaine leçon, et ils sont également utiles pour expliquer les bases de la correction d'erreurs.

Encodage et décodage classiques

Les codes répétitifs sont des exemples extrêmement basiques de codes correcteurs d'erreurs. L'idée est que l'on peut protéger des bits contre les erreurs en répétant simplement chaque bit un nombre fixe de fois.

En particulier, considérons d'abord le code répétitif à 3 bits, dans le contexte de l'information classique pour commencer. Ce code encode un bit en trois en répétant le bit trois fois, donc $0$ est encodé en $000$ et $1$ est encodé en $111.$

$$\begin{aligned} 0 & \mapsto 000\\ 1 & \mapsto 111 \end{aligned}$$

Si rien ne se passe mal, on peut évidemment distinguer les deux possibilités pour le bit original à partir de leurs encodages. L'idée est que s'il y a eu une erreur et qu'un des trois bits a basculé — c'est-à-dire qu'un 0 devient 1 ou qu'un 1 devient 0 — on peut quand même déterminer quel était le bit original en cherchant laquelle des deux valeurs binaires apparaît deux fois. De façon équivalente, on peut décoder en calculant la valeur majoritaire (c'est-à-dire la valeur binaire qui apparaît le plus souvent).

$$a b c \mapsto \operatorname{majority}(a,b,c)$$

Bien sûr, si 2 ou 3 bits de l'encodage basculent, le décodage ne fonctionnera pas correctement et le mauvais bit sera récupéré, mais si au plus 1 des 3 bits bascule, le décodage sera correct. C'est une propriété typique des codes correcteurs d'erreurs en général : ils peuvent permettre la correction d'erreurs, mais seulement s'il n'y en a pas trop.

Réduction du bruit pour le canal binaire symétrique

Pour illustrer une situation dans laquelle les chances de faire une erreur peuvent être réduites grâce à un code répétitif, supposons que notre objectif soit de communiquer un seul bit à un destinataire hypothétique, et que nous pouvons transmettre des bits via un canal binaire symétrique, qui fait basculer chaque bit qui le traverse indépendamment avec une probabilité $p.$ C'est-à-dire qu'avec une probabilité $1-p,$ le destinataire reçoit le bit envoyé à travers le canal, mais avec une probabilité $p,$ le bit bascule et le destinataire reçoit la valeur binaire opposée.

Donc, si on choisit de ne pas utiliser le code répétitif à 3 bits et d'envoyer simplement le bit voulu à travers le canal, le destinataire reçoit alors le mauvais bit avec une probabilité $p.$ En revanche, si on encode d'abord le bit à envoyer avec le code répétitif à 3 bits, puis qu'on envoie chacun des trois bits de l'encodage à travers le canal, alors chacun d'eux bascule indépendamment avec une probabilité $p.$ Les chances d'un basculement de bit sont désormais plus grandes car il y a maintenant trois bits susceptibles de basculer plutôt qu'un, mais si au plus un des bits bascule, le destinataire décodera correctement. Une erreur persiste donc après décodage uniquement si deux bits ou plus basculent pendant la transmission.

La probabilité que deux bits basculent pendant la transmission est $3p^2(1-p),$ soit $p^2(1-p)$ pour chacun des trois choix du bit qui ne bascule pas, tandis que la probabilité que les trois bits basculent est $p^3.$ La probabilité totale de deux ou trois basculements de bits est donc

$$3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.$$

Pour des valeurs de $p$ inférieures à un demi, cela se traduit par une diminution de la probabilité que le destinataire finisse avec le mauvais bit. Il y aura toujours une chance d'erreur dans ce cas, mais le code diminue cette probabilité. (Pour des valeurs de $p$ supérieures à un demi, en revanche, le code augmente en réalité la probabilité que le destinataire reçoive le mauvais bit.)

Encodage de qubits

Le code répétitif à 3 bits est un code correcteur d'erreurs classique, mais on peut se demander ce qui se passe si on essaie de l'utiliser pour protéger des qubits contre des erreurs. Comme nous le verrons, ce n'est pas un code correcteur d'erreurs quantiques très impressionnant, car il rend en réalité certaines erreurs plus probables. C'est cependant la première étape vers le code de Shor, et il nous sera utile d'un point de vue pédagogique.

Pour être clair, lorsque nous parlons du code répétitif à 3 bits utilisé pour des qubits, nous pensons à un encodage d'un qubit où les états de la base standard sont répétés trois fois, de sorte qu'un vecteur d'état à un qubit est encodé comme suit.

$$\alpha \vert 0\rangle + \beta \vert 1\rangle \mapsto \alpha \vert 000\rangle + \beta \vert 111\rangle$$

Cet encodage est facilement implémenté par le circuit quantique suivant, qui utilise deux qubits de travail initialisés et deux portes CNOT.

Remarque en particulier que cet encodage n'est pas identique à la répétition de l'état quantique trois fois, comme dans le cas d'un vecteur d'état de qubit encodé en $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Un tel encodage ne peut pas être implémenté pour un état quantique inconnu $\vert\psi\rangle$ en raison du théorème de non-clonage.

Erreurs de basculement de bit

Supposons maintenant qu'une erreur se produise après que l'encodage a été effectué. Plus précisément, supposons qu'une porte $X$, c'est-à-dire un basculement de bit, se produise sur l'un des qubits. Par exemple, si le qubit du milieu subit un basculement de bit, l'état des trois qubits est transformé en cet état :

$$\alpha \vert 010\rangle + \beta \vert 101\rangle.$$

Bien sûr, ce n'est pas le seul type d'erreur qui pourrait se produire — et il est également raisonnable de remettre en question l'hypothèse selon laquelle une erreur prend la forme d'une opération parfaitement unitaire. Nous reviendrons sur ces questions dans la dernière section de la leçon, et pour l'instant nous pouvons considérer une erreur de cette forme comme étant simplement un type possible d'erreur (bien que fondamentalement important).

On peut voir clairement à partir de l'expression mathématique de l'état ci-dessus que le bit du milieu est celui qui diffère à l'intérieur de chaque ket. Mais supposons que nous ayons les trois qubits en notre possession et que nous ne connaissions pas leur état. Si nous soupçonnions qu'un basculement de bit a pu se produire, une option pour vérifier qu'un bit a basculé serait d'effectuer une mesure dans la base standard, ce qui, dans le cas présent, nous ferait voir $010$ ou $101$ avec des probabilités $\vert\alpha\vert^2$ et $\vert\beta\vert^2,$ respectivement. Dans les deux cas, notre conclusion serait que le bit du milieu a basculé — mais, malheureusement, nous perdrions l'état quantique original $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ C'est l'état que nous cherchons à protéger, donc mesurer dans la base standard est une option insatisfaisante.

Ce que nous pouvons faire à la place, c'est utiliser le circuit quantique suivant, en introduisant l'état encodé dans les trois qubits supérieurs. Ce circuit mesure de façon non destructive la parité des états de la base standard des deux qubits supérieurs ainsi que des deux qubits inférieurs des trois qubits de l'encodage.

Sous l'hypothèse qu'au plus un bit a basculé, on peut facilement déduire des résultats de mesure l'emplacement du basculement de bit (ou son absence). En particulier, comme l'illustrent les quatre schémas de circuit suivants, le résultat de mesure $00$ indique qu'aucun basculement de bit ne s'est produit, tandis que les trois autres possibilités indiquent quel qubit a subi un basculement de bit.

Fait crucial, l'état des trois qubits supérieurs ne s'effondre dans aucun des cas, ce qui nous permet de corriger une erreur de basculement de bit si elle s'est produite — en appliquant simplement à nouveau le même basculement de bit avec une porte $X.$ Le tableau suivant résume les états obtenus après au plus un basculement de bit, les résultats de mesure (appelés syndrome dans le contexte de la correction d'erreurs), et la correction nécessaire pour revenir à l'encodage original.

État	Syndrome	Correction
$\alpha\vert 000\rangle + \beta \vert 111\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert 001\rangle + \beta \vert 110\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes X$
$\alpha\vert 010\rangle + \beta \vert 101\rangle$	$11$	$\mathbb{I}\otimes X\otimes\mathbb{I}$
$\alpha\vert 100\rangle + \beta \vert 011\rangle$	$10$	$X\otimes\mathbb{I}\otimes\mathbb{I}$

Encore une fois, nous ne considérons que la possibilité qu'au plus un basculement de bit se soit produit. Cela ne fonctionnerait pas correctement si deux ou trois basculements de bits se produisaient, et nous n'avons pas non plus considéré d'autres erreurs possibles en dehors des basculements de bits.

Erreurs de basculement de phase

Dans le cadre quantique, les erreurs de basculement de bit ne sont pas les seules erreurs dont nous devons nous préoccuper. Par exemple, nous devons également nous préoccuper des erreurs de basculement de phase, qui sont décrites par des portes $Z.$ Dans le même ordre d'idées que les erreurs de basculement de bit, on peut considérer les erreurs de basculement de phase comme représentant simplement une autre possibilité d'erreur pouvant affecter un qubit.

Cependant, comme nous le verrons dans la dernière section de la leçon, qui porte sur ce qu'on appelle la discrétisation des erreurs pour les codes correcteurs d'erreurs quantiques, se concentrer sur les erreurs de basculement de bit et de basculement de phase s'avère bien justifié. Plus précisément, la capacité à corriger une erreur de basculement de bit, une erreur de basculement de phase, ou les deux simultanément implique automatiquement la capacité à corriger une erreur quantique arbitraire sur un seul qubit.

Malheureusement, le code répétitif à 3 bits ne protège pas du tout contre les basculements de phase. Par exemple, supposons qu'un état de qubit $\alpha\vert 0\rangle + \beta\vert 1\rangle$ ait été encodé avec le code répétitif à 3 bits, et qu'une erreur de basculement de phase se produise sur le qubit du milieu. Cela donne l'état

$$(\mathbb{I} \otimes Z \otimes \mathbb{I}) ( \alpha \vert 000\rangle + \beta \vert 111\rangle) = \alpha \vert 000\rangle - \beta \vert 111\rangle,$$

qui est exactement l'état qu'on aurait obtenu en encodant l'état de qubit $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ En effet, une erreur de basculement de phase sur n'importe lequel des trois qubits de l'encodage produit le même effet, ce qui est équivalent à une erreur de basculement de phase se produisant sur le qubit original avant l'encodage. En supposant que l'état quantique original est un état inconnu, il n'y a donc aucun moyen de détecter qu'une erreur s'est produite, car l'état résultant est un encodage parfaitement valide d'un état de qubit différent. En particulier, exécuter le circuit de détection d'erreurs précédent sur l'état $\alpha \vert 000\rangle - \beta \vert 111\rangle$ donnera certainement le syndrome $00,$ ce qui suggère à tort qu'aucune erreur ne s'est produite.

De plus, il y a maintenant trois qubits plutôt qu'un seul susceptibles de subir des erreurs de basculement de phase. Ainsi, dans une situation où les erreurs de basculement de phase sont supposées se produire indépendamment sur chaque qubit avec une probabilité non nulle $p$ (similaire à un canal binaire symétrique mais pour les basculements de phase plutôt que de bits), ce code augmente en réalité la probabilité d'une erreur de basculement de phase après décodage pour de petites valeurs de $p.$ Pour être plus précis, une erreur de basculement de phase se produira sur le qubit original après décodage chaque fois qu'il y a un nombre impair d'erreurs de basculement de phase sur les trois qubits de l'encodage, ce qui se produit avec une probabilité

$$3 p (1 - p)^2 + p^3.$$

Cette valeur est supérieure à $p$ lorsque $0<p<1/2,$ donc le code augmente la probabilité d'une erreur de basculement de phase pour des valeurs de $p$ dans cette plage.

Code répétitif modifié pour les erreurs de basculement de phase

Nous avons observé que le code répétitif à 3 bits est complètement insensible aux erreurs de basculement de phase, il ne semble donc pas très utile pour traiter ce type d'erreur. Nous pouvons cependant modifier le code répétitif à 3 bits d'une façon simple afin qu'il détecte les erreurs de basculement de phase. Cette modification rendra le code insensible aux erreurs de basculement de bit — mais, comme nous le verrons dans la prochaine section, nous pouvons combiner le code répétitif à 3 bits avec cette version modifiée pour obtenir le code de Shor, qui peut corriger à la fois les erreurs de basculement de bit et de basculement de phase.

Voici la version modifiée du circuit d'encodage ci-dessus, qui sera désormais capable de détecter les erreurs de basculement de phase. La modification est très simple : on applique simplement une porte Hadamard à chaque qubit après avoir effectué les deux portes CNOT.

Une porte Hadamard transforme un état $\vert 0\rangle$ en un état $\vert + \rangle$, et un état $\vert 1\rangle$ en un état $\vert - \rangle$, de sorte que l'effet net est que l'état de qubit à un bit $\alpha\vert 0\rangle + \beta \vert 1\rangle$ est encodé en

$$\alpha \vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-} \rangle$$

où $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ et $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

Une erreur de basculement de phase, ou de façon équivalente une porte $Z$, fait basculer entre les états $\vert + \rangle$ et $\vert - \rangle$, donc cet encodage sera utile pour détecter (et corriger) les erreurs de basculement de phase. Plus précisément, le circuit de détection d'erreurs précédent peut être modifié comme suit.

En d'autres termes, on prend le circuit précédent et on place simplement des portes Hadamard sur les trois qubits supérieurs au début et à la fin. L'idée est que les trois premières portes Hadamard transforment les états $\vert + \rangle$ et $\vert - \rangle$ en états $\vert 0\rangle$ et $\vert 1\rangle$, les mêmes vérifications de parité qu'auparavant ont lieu, puis la deuxième couche de portes Hadamard transforme l'état de nouveau en états $\vert + \rangle$ et $\vert - \rangle$ afin que nous récupérions notre encodage. Pour référence future, observons que ce circuit de détection de basculement de phase peut être simplifié comme suit.

Les quatre schémas de circuit suivants décrivent comment notre version modifiée du code répétitif à 3 bits, incluant l'étape d'encodage et l'étape de détection d'erreurs, fonctionne lorsqu'au plus une erreur de basculement de phase se produit. Le comportement est similaire au code répétitif ordinaire à 3 bits pour les basculements de bit.

Voici un tableau analogue à celui ci-dessus, cette fois en considérant la possibilité d'au plus une erreur de basculement de phase.

État	Syndrome	Correction
$\alpha\vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-}\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert {+}\,{+}\,{-}\rangle + \beta \vert {-}\,{-}\,{+}\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes Z$
$\alpha\vert {+}\,{-}\,{+}\rangle + \beta \vert {-}\,{+}\,{-}\rangle$	$11$	$\mathbb{I}\otimes Z\otimes\mathbb{I}$
$\alpha\vert {-}\,{+}\,{+} \rangle + \beta \vert {+}\,{-}\,{-}\rangle$	$10$	$Z\otimes\mathbb{I}\otimes\mathbb{I}$

Malheureusement, cette version modifiée du code répétitif à 3 bits ne peut plus corriger les erreurs de basculement de bit. Tout n'est pas perdu, cependant. Comme suggéré précédemment, nous pourrons combiner les deux codes que nous venons de voir en un seul code — le code de Shor à 9 qubits — qui peut corriger à la fois les erreurs de basculement de bit et de basculement de phase, et en réalité toute erreur sur un seul qubit.