Come abbiamo già visto nei paragra precedenti, un codici correttori quantistico codica stati quantistici in qubit, in modo che gli errori o la decoerenza in un piccolo numero di singoli qubit avranno poco o nessun eetto sui dati codicati. Più precisamente, una codica di k qubit in n qubit viene considerata come un'applicazione lineare da C2k in un sottospazio 2k− dimensionale di C2n.
Osserviamo che la legge denita in 4.2, che associa ad ogni elemento di Gn un vettore di Z2n2 ,
ϕ : Gn−→ Z2n2
g 7−→ (a|b)
risulta un omomorsmo di gruppi, con nucleo ker ϕ =±I⊗n, ±iI⊗n .
Il ker ϕ è il centro di Gn, così ϕ (Gn) = Gn ∼= Gn
/
ker ϕ risultaessere un gruppo abeliano elementare di ordine 22n, che è uno spazio
vettoriale su Z2.
Deniamo su Gn il prodotto scalare
((a|b) , (a0|b0)) = a · b0+ a0· b.
Questo risulta essere un prodotto scalare simplettico, dato che ((a|b) , (a|b)) = 0.
E' facile vericare che g, g0 ∈ G
n commutano se e solo se
(ϕ (g) , ϕ (g0)) = 0.
Se S ⊂ Gn, indichiamo S = ϕ (S). Diremo che S ⊂ Gn è total-
mente isotropo se ∀ s1, s2 ∈ S,
(s1, s2) = 0.
Quindi un sottoinsieme S ⊂ Gn è commutativo se e solo se S è
totalmente isotropo. Deniamo
S⊥ =g ∈ Gn
g, S = 0 .
E' chiaro che ϕ−1S⊥ è il centralizzatore di S in G n.
Se vogliamo che S sia lo stabilizzatore di un codice C, allora S ⊂ Gn
deve essere commutativo, così S ⊂ Gn è isotropo
S ⊂ S⊥
. Dato che gli elementi di S possono essere diagonalizzati simultaneamente, questo induce ad una decomposizione di C2n in autospazi ortogonali.
Anchè S agisca banalmente sul codice è quindi necessario che il codice si trovi interamente in uno di questi autospazi. Inoltre, poichè vogliamo anche che S⊥ conservi il codice scegliamo il codice C in uno
degli autospazi.
Ad ogni autospazio di S corrisponde un omomorsmo χ : S −→ C
che associa ad ogni elemento di S il corrispondente autovalore. χ è una carattere di S e χ (iI) = i.
Lemma 4.8
Un codice correttore additivo C associato ad un insieme ¯Sè in grado di correggere errori Σ ⊆ Gn se ¯e−11 e¯2 ∈ ¯/S⊥\ ¯S per ogni e1, e2 ∈ Σ.
Dim.
Sia e ∈ Gn un errore da correggere; per farlo dobbiamo trovare
e1 ∈ Gn tale che e−11 e agisce banalmente su C, cioè e −1 1 e ∈ S.
In altre parole dobbiamo determinare la classe laterale eS.
L'ipotesi implica che ogni classe laterale di S⊥contiene al massimo
una classe laterale di S intersecato Σ. E' suciente quindi determi- nare la classe laterale eS⊥.
Ricordiamo che Gn/S⊥ permuta gli autospazi di S regolarmente.
Se misuriamo in quale autospazio ci troviamo possiamo immediata- mente leggere eS⊥. Questa misura non ha alcun eetto sullo stato,
poichè si trova all'interno di uno degli autospazi.
D'altra parte, supponiamo che e1, e2 sono due errori tali che e−11 e2 ∈
S⊥\S. Qualsiasi procedura di correzione deve prendere tutti gli stati e1(v) ∈ e1(C) di v.
Da e−1
1 e2 ∈ S⊥, e2(v) ∈ e1(C) , così e2(v) è corretto da e−11 e2(v) .
Tuttavia, poichè e−1
1 e2 ∈ S/ , c'è uno stato v ∈ C tale che e−11 e2(v)
non è proporzionale a v,e non siamo riusciti a correggere e2.
@
Dal lemma, risulta che se d è il peso minimo di S⊥\ S, il codice può correggere l'insieme di tutti gli errori di peso minore o uguale d−1
2 .
Ricordiamo che gli autospazi di S sono in corrispondenza uno a uno con i caratteri di S che soddisfano χ (iI) = i.
Per determinare quale autospazio contiene un dato stato basta cal- colare il carattere. Inoltre, poichè χ è un omomorsmo, è suciente calcolare il carattere su una base di S.
Ogni elemento della base fornisce un bit di informazione; la raccolta di questi bit non è altro che la sindrome dell'errore.
Concludendo se S ⊂ Gn isotropo, se ϕ−1 S = S è possibile co-
struire, a partire da S, un codice quantistico. Più precisamente vale:
Teorema 4.9
Se S ⊂ Gn è totalmente isotropo
S ⊂ S⊥ ed è tale che non esi- stono in S⊥\ S vettori di peso ≤ d − 1, esiste un codice correttore quantistico C ⊆ C2n
di distanza d e dimensione 2k, in grado di cor-
reggere d−1 2
errori che appartiene ad uno qualsiasi degli autospazi di ϕ−1 S .
Un codice correttore quantistico di parametri [[n, k, d]], ottenuto tramite il teorema 4.9 si dice codice additivo. Quasi tutti i codici correttori quantistici noti al momento sono additivi.
Teorema 4.10
Sia S⊥ l'(2n − k)- sottospazio ortogonale ad S rispetto al prodotto scalare
(¯s, ¯s0) = a · b0+ a0· b = 0. (4.5) Se per ogni due vettori d'errore e1, e2 ∈ Gn, e1e2 ∈ S oppure e1e2 ∈/
S⊥. Allora l'autospazio C corrispondente a qualsiasi carattere del gruppo S è un codice correttore, che corregge eventuali errori e ∈ Gn.
Dim.
Per prima cosa dimostriamo che se e ∈ Gn, allora e permuta i 2k
spazi Ci, che vengono generati dai 2k diversi caratteri lineari di S.
Consideriamo un elemento s ∈ S con autovalore λs. Scriviamo s
per la rappresentazione associata. Allora, per ogni |ci ∈ C abbiamo s |ci = λs|ci, e
se |ci = (−1)(s,e)es |ci = (−1)(s,e)λse |ci ,
dove (s, e) è il prodotto interno 4.5. Dal momento che (−1)(s,e)
λs è
indipendente da c, l'azione di e permuta gli autospazi generati dai caratteri di S.
Dividiamo da dimostrazione in due casi, a seconda che e1e2 ∈ S o
e1e2 ∈ S/ ⊥
.
Caso 1: Supponiamo che e1e2 ∈ S. Ne consegue che, per |c1i e
|c2i ∈ C, con hc1|c2i = 0,
hc1|e1e2| c2i = λe1e2hc1|c2i = 0,
e per ogni |ci ∈ C,
hc |e1e2| ci = λe1e2hc|ci = λe1e2,
che stabilisce le equazioni
hc1| e−11 e2|c2i = 0,
hc1| e−11 e2|c1i = hc2| e−11 e2|c2i .
Caso 2: Supponiamo e1e2 ∈ S/ ⊥
ne segue che per qualche s ∈ S, se1e2 = −e1e2s. Pertanto, per |ci ∈ C,
se1e2|ci = −e1e2s |ci = −λse1e2|ci ,
così e1e2|ci /∈ C. Allora e1e2|ciè un diverso autospazio, in modo che
hc1|e1e2| c2i = 0 per ogni c1, c2 ∈ C. Anche questo caso otteniamo
le equazioni
hc1| e−11 e2|c2i = 0,
hc1| e−11 e2|c1i = hc2| e−11 e2|c2i .
@ Per costruire il codice possiamo riassumere la discussione precedente nella seguente
Proposizione 4.11
Sia S come nel teorema 4.9 e sia V uno degli autospazi di ϕ−1 S =
S.Se {g1, . . . , gn−k}sono generatori linearmente indipendenti di S
e ai = χ (ϕ (gi)), allora a−11 g1, . . . , a−1n−kgn−k
generano un gruppo S0 che è lo stabilizzatore di V.
In questo modo V è un codice stabilizzatore di distanza d, di dimen- sione 2k, in grado di correggere d−1
2
errori. Esempio:
Descriviamo il codice che manda un qubit in cinque qubits, che contiene due parole di codice,
c0 = |00000i + |11000i + |01100i + |00110i + |00011i + |10001i
− |10100i − |01010i − |00101i − |10010i − |01001i − |11110i − |01111i − |10111i − |11011i − |11101i ,
c1 = |11111i + |00111i + |10011i + |11001i + |11100i + |01110i
− |01011i − |10101i − |11010i − |01101i − |10110i − |00001i − |10000i
− |01000i − |00100i − |00010i .
E' facile vericare che X (11000) Z (00101)ssa |c0ie |c1i .Così pos-
siamo prendere il vettore (11000|00101) ∈ Gn nel sottospazio S.
Utilizziamo il fatto che il codice è chiuso rispetto alle permutazioni cicliche, per scoprire che S è un sottospazio 4-dimensionale del tutto singolare generato dai vettori:
11000 01100 00110 00011 00101 10010 01001 10100 .
Il duale S⊥è generato da S e dai vettori (11111|00000) e (00000|11111) . E' semplice vericare che il peso minimo dei vettori in S⊥ ha peso tre e quindi il codice può correggere un errore.
@ Esempio:
Consideriamo il sottospazio S ottenuto modicando il codice classico di Hamming [8, 4, 4] come segue
0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 .
E' semplice vericare che questi vettori generano un sottospazio S di dimensione 5 che è invariante per permutazioni cicliche degli ultimi 7 bit, e che S⊥ ha peso ≤ 3.
Questo porta ad un codice correttore quantistico che mappa 3 qubit in 8 qubit e che è in grado di correggere un errore.
Lo stesso codice è stato scoperto da Gottesmann, anche mediante la teoria dei gruppi (per approfondimenti consultare [4]).
Capitolo 5
Codici quantistici e codici
lineari
Nel capitolo precedente abbiamo visto come associare ad un codice quantistico in Gn un sottospazio ortogonale di Z2n2 e viceversa. In
questo capitolo vedremo come costruire, a partire da ognuno di que- sti sottospazi di Z2n
2 , un particolare codice in GF (4)
n detto codice
additivo. Invertendo questi procedimenti otterremo un modo per costruire nuovi codici quantistici a partire da codici additivi.
5.1 Dagli spazi binari ai codici in GF (4)
Consideriamo il campo di Galois GF (4) costituito dagli elementi {0, 1, ω, ¯ω}, con ω2 = ω + 1, ω3 = 1, la coniugazione denita da
¯
x = x2 e l'applicazione traccia
T r : GF (4) −→ Z2
x 7−→ x + ¯x.
Ricordiamo che il peso di Hamming di un vettore u ∈ GF (4)n, che
indichiamo con wt (u), è il numero di componenti diversi da zero e la distanza di Hamming tra due vettori u, u0 ∈ GF (4)n è
dist (u, u0) = wt (u − u0) .
La distanza di un codice C ⊂ GF (4)n
, che indichiamo con d, è denita come la distanza minima degli elementi di C.
Ricordiamo, inoltre, che: Gn è denito come il prodotto tensoriale
n−esimo delle matrici di Pauli, considerando ovviamente i fattori moltiplicativi ±1 e ±i Gn =ikA1⊗ . . . ⊗ An| ∀ j ∈ [1, n] , Aj ∈ G1 ; ϕ (Gn) = Gn ∼= Gn
/
ker ϕdove ϕ : Gn−→Z 2n /2 è l'omomorsmo di gruppi denito il 4.2. Deniamo φ : Gn−→ GF (4)n g = (a|b) 7−→ ωa + ωb.Il peso di g è uguale al peso di Hamming di φ (g) e la distanza tra i vettori g = (a|b) e g0 = (a0|b0) ∈ G
n è uguale a dist (φ (g) , φ (g0)) .
Se g, g0 ∈ G
n il loro prodotto scalare simplettico risulta uguale a
T r φ (g) , φ (g0), infatti si ha: T rφ (g) , φ (g0)= T r ((ωa + ωb) · (ωa0+ ωb0)) = (a · a0) T r (1) + (a · b0) T r (ω) + (a0 · b) T r (ω) + (b · b0) T r (1) = a · b0+ a0 · b.
Inne osserviamo che se S è un sottospazio lineare di Gn,allora C =
φ S è un sottoinsieme di GF (4)nche è chiuso rispetto l'addizione. Diciamo che C è un codice additivo su GF (4) e che è un codice n, 2k se contiene 2k vettori. Se C è anche chiuso rispetto alla moltiplicazione per ω, diciamo che C è un codice lineare. Osserviamo che considerando φ ◦ ϕ : Gn−→ GF (4)
n abbiamo associato ad ogni
codice quantistico (e quindi in parte ad un codice stabilizzatore) un codice additivo.
Chiamiamo lineari i codici quantistici tali che il codice additivo associato è lineare.
Il prodotto scalare traccia fra due vettori u, v ∈ GF (4)n verrà
indicato con u ∗ v = T r (u · v) = n X j=1 (ujvj + ujvj) .
Se C è un codice additivo n, 2k , il suo duale è denito come
C⊥= {u ∈ GF (4)n: u ∗ v = 0 ∀v ∈ C} ed è un codice n, 22n−k
.
Se C ⊆ C⊥ diciamo che C è auto-ortogonale e se C = C⊥ allora C
è auto-duale. Teorema 5.1
Un codice lineare C è auto-ortogonale se e solo se il codice classico è ortogonale rispetto all'usuale prodotto scalare hermitiano.
Dim.
La condizione è chiaramente suciente.
Supponiamo che C sia auto-ortogonale. Per u, v ∈ C si ha u · v = α + βω,
con α, β ∈ Z2.
Allora T r (u · v) = 0 implica β = 0 e T r (u · ¯ω¯v) = 0 implica che α = 0, così u · ¯v = 0.
Possiamo riformulare, a questo punto, il teorema 4.9 nel seguente Teorema 5.2
Sia C ⊂ GF (4)n un codice additivo auto-ortogonale, contenente
2kvettori, tale che non ci siano vettori di peso ≤ d − 1 in C⊥\ C. Allora qualsiasi autospazio di (ϕ ◦ φ)−1
(C) è un codice correttore quantistico di parametri [[n, n − k, d]] .
Diciamo che C è puro se non ci sono vettori non nulli di peso minore di d in C⊥, altrimenti C è detto impuro.
Qualsiasi codice additivo n, 2k
è equivalente ad uno con una ma- trice generatrice della forma
Ik0 ωB1 A1 ωIk0 ωB2 A2 0 Ik1 B3 ,
dove Ir denota una matrice identità di ordine r, Aj è una matrice
arbitraria, Bj è una matrice binaria, e k = 2k0+ k1.
Un codice n, 2k
si dice pari se il peso di ogni parola è pari, altrimenti si dice dispari.
Teorema 5.3
Un codice pari additivo è auto-ortogonale. Un codice auto-ortogonale lineare è pari.
Dim.
La prima aermazione è vera in quanto
wt (u + v) ≡ wt (u) + wt (v) + u ∗ v (mod 2) per ogni u, v ∈ GF (4)n
;
u ∗ (ωu) ≡ wt (u) (mod 2) .
@
La distribuzione dei pesi di un codice additivo C n, 2k
è la se- quenza A0,. . . , An, dove Aj è il numero di vettori in C di peso
j.
E' facile vedere che la distribuzione dei pesi di u + C, con u ∈ C, è la stessa di C. Il polinomio W (x, y) = n X j=0 Ajxn−jyj
si chiama il polinomio enumeratore dei pesi di C. Teorema 5.4
Sia C un codice additivo n, 2k
con polinomio enumeratore dei pesi W (x, y) .Allora il polinomio enumeratore dei pesi del codice duale C⊥ è dato da
2−kW (x + 3y, x − y) . Per approfondimenti rimandiamo a [6].