Codici di ripetizione

Inizieremo la lezione con una discussione sui codici di ripetizione. I codici di ripetizione non proteggono le informazioni quantistiche da ogni tipo di errore che può verificarsi sui qubit, ma costituiscono la base per il codice di Shor a 9 qubit, che vedremo nella prossima lezione, e sono anche utili per spiegare i fondamenti della correzione degli errori.

Codifica e decodifica classica

I codici di ripetizione sono esempi estremamente elementari di codici per la correzione degli errori. L'idea è che possiamo proteggere i bit dagli errori semplicemente ripetendo ogni bit un numero fisso di volte.

In particolare, consideriamo prima il codice di ripetizione a 3 bit, nel contesto dell'informazione classica per cominciare. Questo codice codifica un bit in tre ripetendo il bit tre volte, quindi $0$ viene codificato come $000$ e $1$ viene codificato come $111.$

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

Se non va nulla storto, possiamo ovviamente distinguere le due possibilità per il bit originale dalle loro codifiche. Il punto è che se si è verificato un errore e uno dei tre bit si è invertito — cioè uno 0 è diventato 1 o un 1 è diventato 0 — possiamo comunque risalire al bit originale determinando quale dei due valori binari compare due volte. In modo equivalente, possiamo decodificare calcolando il valore di maggioranza (cioè il valore binario che compare più di frequente).

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

Naturalmente, se 2 o 3 bit della codifica si invertono, la decodifica non funzionerà correttamente e verrà recuperato il bit sbagliato, ma se al massimo 1 dei 3 bit si inverte, la decodifica sarà corretta. Questa è una proprietà tipica dei codici per la correzione degli errori in generale: possono consentire la correzione degli errori, ma solo se non sono troppo numerosi.

Riduzione del rumore per il canale binario simmetrico

Per un esempio di situazione in cui la probabilità di commettere un errore può essere ridotta usando un codice di ripetizione, supponiamo che il nostro obiettivo sia trasmettere un singolo bit a un ricevitore ipotetico, e che possiamo trasmettere bit attraverso un cosiddetto canale binario simmetrico, che inverte ogni bit inviato attraverso di esso in modo indipendente con una certa probabilità $p.$ Cioè, con probabilità $1-p,$ il ricevitore ottiene qualsiasi bit sia stato inviato attraverso il canale, ma con probabilità $p,$ il bit si inverte e il ricevitore ottiene il valore di bit opposto.

Quindi, se scegliamo di non usare il codice di ripetizione a 3 bit e inviamo semplicemente il bit che abbiamo in mente attraverso il canale, il ricevitore riceve il bit sbagliato con probabilità $p.$ D'altra parte, se prima codifichiamo il bit che vogliamo inviare usando il codice di ripetizione a 3 bit, e poi inviamo ciascuno dei tre bit della codifica attraverso il canale, ognuno di essi si inverte in modo indipendente con probabilità $p.$ La probabilità di un'inversione di bit è ora maggiore perché ci sono tre bit che potrebbero invertirsi anziché uno, ma se al massimo un bit si inverte, il ricevitore decodificherà correttamente. Un errore persiste quindi dopo la decodifica solo se due o più bit si invertono durante la trasmissione.

La probabilità che due bit si invertano durante la trasmissione è $3p^2(1-p),$ che è $p^2(1-p)$ per ciascuna delle tre scelte per il bit che non si inverte, mentre la probabilità che tutti e tre i bit si invertano è $p^3.$ La probabilità totale di due o tre inversioni di bit è quindi

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

Per valori di $p$ minori di un mezzo, questo comporta una diminuzione della probabilità che il ricevitore si ritrovi con il bit sbagliato. Ci sarà ancora una possibilità di errore in questo caso, ma il codice diminuisce la probabilità. (Per valori di $p$ maggiori di un mezzo, invece, il codice in realtà aumenta la probabilità che il ricevitore ottenga il bit sbagliato.)

Codifica di qubit

Il codice di ripetizione a 3 bit è un codice di correzione degli errori classico, ma possiamo considerare cosa succede se proviamo a usarlo per proteggere i qubit dagli errori. Come vedremo, non è un codice di correzione degli errori quantistici molto impressionante, perché in realtà rende alcuni errori più probabili. È tuttavia il primo passo verso il codice di Shor, e sarà molto utile da un punto di vista pedagogico.

Per essere chiari, quando parliamo del codice di ripetizione a 3 bit applicato ai qubit, abbiamo in mente una codifica di un qubit in cui gli stati della base standard vengono ripetuti tre volte, in modo che un vettore di stato a singolo qubit venga codificato come segue.

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

Questa codifica è facilmente implementata dal seguente circuito quantistico, che fa uso di due qubit di lavoro inizializzati e di due gate controlled-NOT.

Nota in particolare che questa codifica non è la stessa cosa di ripetere lo stato quantistico tre volte, come nel caso di un dato vettore di stato qubit codificato come $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Tale codifica non può essere implementata per uno stato quantistico sconosciuto $\vert\psi\rangle$ a causa del teorema di no-cloning.

Errori di inversione di bit

Supponiamo ora che si verifichi un errore dopo che la codifica è stata eseguita. In particolare, supponiamo che si verifichi un gate $X$, ovvero un'inversione di bit, su uno dei qubit. Ad esempio, se il qubit centrale subisce un'inversione di bit, lo stato dei tre qubit viene trasformato in questo stato:

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

Naturalmente, questo non è l'unico tipo di errore che potrebbe verificarsi — ed è anche ragionevole mettere in discussione il presupposto che un errore assuma la forma di un'operazione unitaria perfetta. Torneremo su questi problemi nell'ultima sezione della lezione, e per ora possiamo considerare un errore di questa forma come uno dei possibili tipi di errore (sebbene di fondamentale importanza).

Possiamo vedere chiaramente dall'espressione matematica dello stato sopra che il bit centrale è quello diverso all'interno di ogni ket. Ma supponiamo di avere i tre qubit in nostro possesso e di non conoscerne lo stato. Se sospettassimo che si sia verificata un'inversione di bit, un'opzione per verificarlo sarebbe eseguire una misurazione nella base standard, che, nel caso in esame, ci farebbe osservare $010$ o $101$ con probabilità $\vert\alpha\vert^2$ e $\vert\beta\vert^2,$ rispettivamente. In entrambi i casi, la nostra conclusione sarebbe che il bit centrale si è invertito — ma, purtroppo, perderemmo lo stato quantistico originale $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ Questo è lo stato che stiamo cercando di proteggere, quindi misurare nella base standard è un'opzione insoddisfacente.

Quello che possiamo fare invece è usare il seguente circuito quantistico, alimentando lo stato codificato nei primi tre qubit. Questo circuito misura in modo non distruttivo la parità degli stati della base standard dei primi due qubit e degli ultimi due qubit della codifica a tre qubit.

Nell'ipotesi che al massimo un bit si sia invertito, si può facilmente dedurre dai risultati della misurazione la posizione dell'inversione di bit (o la sua assenza). In particolare, come illustrano i seguenti quattro diagrammi di circuito, il risultato di misurazione $00$ indica che non si è verificata alcuna inversione di bit, mentre le altre tre possibilità indicano quale qubit ha subito l'inversione.

Aspetto cruciale: lo stato dei primi tre qubit non collassa in nessuno dei casi, il che ci permette di correggere un errore di inversione di bit se si è verificato — applicando semplicemente di nuovo la stessa inversione di bit con un gate $X$. La tabella seguente riassume gli stati che otteniamo da al massimo un'inversione di bit, i risultati della misurazione (chiamati sindrome nel contesto della correzione degli errori) e la correzione necessaria per tornare alla codifica originale.

Stato	Sindrome	Correzione
$\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}$

Ancora una volta, stiamo considerando solo la possibilità che si sia verificata al massimo un'inversione di bit. Questo non funzionerebbe correttamente se si verificassero due o tre inversioni di bit, e non abbiamo ancora considerato altri possibili errori oltre alle inversioni di bit.

Errori di inversione di fase

In ambito quantistico, le inversioni di bit non sono gli unici errori di cui dobbiamo preoccuparci. Ad esempio, dobbiamo anche preoccuparci degli errori di inversione di fase, descritti dai gate $Z$. In modo analogo alle inversioni di bit, possiamo considerare gli errori di inversione di fase come un'altra possibile tipologia di errore che può colpire un qubit.

Tuttavia, come vedremo nell'ultima sezione della lezione, dedicata alla cosiddetta discretizzazione degli errori per i codici di correzione degli errori quantistici, concentrarsi sugli errori di inversione di bit e di fase si rivela ampiamente giustificato. In particolare, la capacità di correggere un errore di inversione di bit, un errore di inversione di fase, o entrambi contemporaneamente, implica automaticamente la capacità di correggere un errore quantistico arbitrario su un singolo qubit.

Purtroppo, il codice di ripetizione a 3 bit non protegge affatto dalle inversioni di fase. Ad esempio, supponiamo che uno stato qubit $\alpha\vert 0\rangle + \beta\vert 1\rangle$ sia stato codificato usando il codice di ripetizione a 3 bit, e che si verifichi un errore di inversione di fase sul qubit centrale. Questo produce lo stato

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

che è esattamente lo stato che avremmo ottenuto codificando lo stato qubit $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ In effetti, un errore di inversione di fase su uno qualsiasi dei tre qubit della codifica produce questo stesso effetto, equivalente a un errore di inversione di fase che si verifica sul qubit originale prima della codifica. Nell'ipotesi che lo stato quantistico originale sia uno stato sconosciuto, non è quindi possibile rilevare che si è verificato un errore, perché lo stato risultante è una codifica perfettamente valida di un diverso stato qubit. In particolare, eseguire il circuito di rilevamento degli errori di prima sullo stato $\alpha \vert 000\rangle - \beta \vert 111\rangle$ darà certamente la sindrome $00$, che suggerisce erroneamente che non si sono verificati errori.

Nel frattempo, ci sono ora tre qubit invece di uno che potrebbero potenzialmente subire errori di inversione di fase. Quindi, in una situazione in cui si assume che gli errori di inversione di fase si verifichino in modo indipendente su ciascun qubit con una certa probabilità non nulla $p$ (simile a un canale binario simmetrico ma per inversioni di fase anziché di bit), questo codice aumenta effettivamente la probabilità di un errore di inversione di fase dopo la decodifica per valori piccoli di $p$. Per essere più precisi, otterremo un errore di inversione di fase sul qubit originale dopo la decodifica ogni volta che si verifica un numero dispari di errori di inversione di fase sui tre qubit della codifica, il che accade con probabilità

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

Questo valore è maggiore di $p$ quando $0<p<1/2,$ quindi il codice aumenta la probabilità di un errore di inversione di fase per valori di $p$ in questo intervallo.

Codice di ripetizione modificato per errori di inversione di fase

Abbiamo osservato che il codice di ripetizione a 3 bit è completamente insensibile agli errori di inversione di fase, quindi non sembra essere molto utile per gestire questo tipo di errore. Possiamo però modificare il codice di ripetizione a 3 bit in modo semplice affinché rilevi gli errori di inversione di fase. Questa modifica renderà il codice insensibile agli errori di inversione di bit — ma, come vedremo nella sezione successiva, possiamo combinare il codice di ripetizione a 3 bit con questa versione modificata per ottenere il codice di Shor, che può correggere sia gli errori di inversione di bit che quelli di inversione di fase.

Ecco la versione modificata del circuito di codifica di prima, che sarà ora in grado di rilevare gli errori di inversione di fase. La modifica è molto semplice: applichiamo semplicemente un gate di Hadamard a ciascun qubit dopo aver eseguito i due gate controlled-NOT.

Un gate di Hadamard trasforma uno stato $\vert 0\rangle$ in uno stato $\vert + \rangle$ e uno stato $\vert 1\rangle$ in uno stato $\vert - \rangle$, quindi l'effetto netto è che lo stato a singolo qubit $\alpha\vert 0\rangle + \beta \vert 1\rangle$ viene codificato come

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

dove $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ e $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

Un errore di inversione di fase, ovvero un gate $Z$, scambia tra gli stati $\vert + \rangle$ e $\vert - \rangle$, quindi questa codifica sarà utile per rilevare (e correggere) gli errori di inversione di fase. In particolare, il circuito di rilevamento degli errori di prima può essere modificato come segue.

In parole povere, prendiamo il circuito di prima e aggiungiamo semplicemente gate di Hadamard sui primi tre qubit sia all'inizio che alla fine. L'idea è che i primi tre gate di Hadamard trasformano gli stati $\vert + \rangle$ e $\vert - \rangle$ negli stati $\vert 0\rangle$ e $\vert 1\rangle$, vengono eseguiti gli stessi controlli di parità di prima, e poi il secondo strato di gate di Hadamard trasforma lo stato di nuovo in stati $\vert + \rangle$ e $\vert - \rangle$ in modo da recuperare la nostra codifica. Per riferimento futuro, notiamo che questo circuito di rilevamento delle inversioni di fase può essere semplificato come segue.

I seguenti quattro diagrammi di circuito descrivono come funziona la nostra versione modificata del codice di ripetizione a 3 bit, compreso il passo di codifica e il passo di rilevamento degli errori, quando si verifica al massimo un errore di inversione di fase. Il comportamento è simile al codice di ripetizione a 3 bit ordinario per le inversioni di bit.

Ecco una tabella analoga a quella di prima, questa volta considerando la possibilità di al massimo un errore di inversione di fase.

Stato	Sindrome	Correzione
$\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}$

Purtroppo, questa versione modificata del codice di ripetizione a 3 bit non è più in grado di correggere gli errori di inversione di bit. Non tutto è perduto, però. Come suggerito in precedenza, saremo in grado di combinare i due codici che abbiamo appena visto in un unico codice — il codice di Shor a 9 qubit — che può correggere sia gli errori di inversione di bit che quelli di inversione di fase, e in effetti qualsiasi errore su un singolo qubit.