Introduzione
II
Il processo tecnologico, grazie anche all’introduzione dei transistor, fece sì che negli
anni successivi la costruzione e la produzione di elaboratori numerici subissero uno
sviluppo senza precedenti.
Tale crescita portò Gordon Moore, cofondatore assieme a Robert Noyce della Intel
Corporation, a pubblicare, nel 1965, la famosa previsione che negli anni successivi
ha poi assunto valore di profezia: il raddoppiamento delle prestazioni dei microchip
e del numero di transistor in esso contenuti approssimativamente ogni due anni
2
.
Fig.1: Grafico della legge di Moore
2
Nel 1965 Moore suppose che le prestazioni dei microprocessori sarebbero raddoppiate ogni 12 mesi. Nel 1975 questa previsione
si rivelò corretta e prima della fine del decennio i tempi si allungarono a 2 anni, periodo che rimarrà valido per tutti gli anni
Ottanta. La legge, che verrà estesa per tutti gli anni Novanta e resterà valida fino ai nostri giorni, viene riformulata alla fine degli
anni Ottanta ed elaborata nella sua forma definitiva, ovvero le prestazione dei processori raddoppiano ogni 18 mesi.Questa legge è
diventata il metro di misura e l’obiettivo di tutte le aziende che operano nel settore, e non solo Intel.
Introduzione
III
L’estensione di questo trend nel futuro porta a domandarci cosa sarà in grado di
realizzare l’industria del settore nei prossimi 50 anni.
La miniaturizzazione dei componenti ha favorito il raggiungimento di dimensioni
dei transistor dell’ordine di grandezza delle molecole e le ricerche più avanzate non
escludono la realizzazione di dispositivi elettronici, che utilizzino componenti di
grandezza analoga a quella di un atomo. La ricerca scientifica si trova quindi a due
possibilità, entrambe molto promettenti.
La prima tenta, attraverso l’utilizzo delle nanotecnologie, di applicare il modello di
calcolo dei nostri attuali computer a sistemi di dimensioni sub-microscopiche,
scontrandosi tuttavia con notevoli difficoltà realizzative. I problemi legati a questo
approccio sono rappresentati dalla difficoltà di operare con oggetti in dimensioni
dell'ordine di grandezza di un atomo e trattare quindi con le reazioni energetiche,
che avvengono tra gli atomi dei materiali.
L’altra possibilità da sfruttare, quella che ha attirato l’attenzione di molti scienziati
in tutto il mondo a partire dagli anni ottanta, cerca di esplorare le molte potenzialità
offerte dalla fisica quantistica. Quando infatti cominciamo a trattare con dispositivi a
dimensione comparabile con quella atomica, le interazioni energetiche non
rispondono più alle leggi della fisica classica, ma subiscono degli effetti che sono
esplorati dalla branca della fisica, detta meccanica quantistica. Questo non vuol dire
tuttavia che non ci sia alcun legame tra la fisica dei sistemi macroscopici, la
cosiddetta fisica classica, e quella dei sistemi microscopici chiamata fisica
quantistica. In realtà tale legame esiste ed è noto come Principio di corrispondenza.
Tutto il novecento è stato appunto dominato dal desiderio dei più grandi nomi della
scienza di trovare interpretazioni classiche ai fenomeni, che avvengono nei sistemi
quantistici:ciò ha dato luogo a interminabili dibattiti e a questioni ancora aperte.
A partire dalla fine degli anni settanta tuttavia, la fisica quantistica non è stata più
considerata materia teorica e settore di ricerca senza prospettive applicative. Sulla
scia di alcuni fisici, pionieri di una nuova idea, quella cioè di sfruttare le peculiarità
delle leggi quantistiche per costruire un nuovo tipo di calcolatore, nacque un settore
di studio chiamato quantum computing. Ben presto cominciarono a occuparsi della
materia ricercatori e fisici di elevato livello, primo fra tutti Richard Feynman,
premio nobel per la fisica e grande sostenitore di questa idea.
I principali risultati scientifici che stimolarono i ricercatori furono quelli riguardanti
la “reversible computation” ossia, calcolatori che sono in grado effettuare calcoli
Introduzione
IV
0
reversibili, calcoli cioè che permettono di risalire dal risultato agli ingressi che lo
hanno generato. Ad esempio l’operazione di negazione 01 è un’
operazione reversibile, mentre non lo è uno XOR o un AND. Questo tipo di calcoli
aveva attratto l’interesse dei fisici perché, per un noto principio
,1→→
3
, permette di non
dissipare calore e quindi energia nell’operazione. L’idea iniziale di calcolo
reversibile trovò un equivalente quantistico nel calcolo unitario che è alla base del
quantum computing. I calcolatori che avrebbero dovuto obbedire a queste leggi
furono chiamati Quantum computers.
Tuttavia, nonostante il grande entusiasmo iniziale, passarono dieci anni senza
risultati anche se furono messe le fondamenta di uno di quei settori che sarebbero
emersi in maniera inaspettata, negli anni successivi. Uno dei principali risultati
ottenuti da Feynman fu quello riguardante la simulazione di un sistema quantistico
con un computer tradizionale: egli dimostrò che questa era un problema difficile
4
.
Questa affermazione, se da un lato era scoraggiante, dall’ altro significava che un
calcolatore costruito sfruttando le proprietà di un sistema quantistico avrebbe potuto
fornire una maggior potenza di calcolo. Purtroppo Richard Feynman morì prima che
potesse veder nascere quello che fu il suo ultimo campo di interesse di ricerca.
David Deutsch, suo collaboratore, non lasciò che gli sforzi del premio nobel
andassero perduti e cominciò seriamente a pensare cosa fosse in grado di calcolare
un quantum computer e al modo in cui lo potesse fare.
Nel 1985, insieme a Richard Josza, Deutsch arrivò ad un risultato importante
dimostrando l’esistenza di una reale incremento della potenza di calcolo
nell’ambito delle funzioni logiche. La pubblicazione mostrava che,
quantisticamente, era possibile risolvere con un solo tentativo un problema che,
classicamente, ne richiedeva una quantità esponenziale nell’input. Altri ricercatori
tra cui prima Ethan Bernstein e Umesh Vazirani e in seguito Dan Simon,
presentarono la soluzione, attraverso l'uso di algoritmi polinomiali, di alcuni
problemi classicamente esponenziali. Nello stesso periodo fu inoltre portata a
compimento la dimostrazione, con argomenti simili a quelli utilizzati da Alan
Turing nella sua famosa pubblicazione, dell’universalità di un insieme di porte
quantistiche.
3
Principio di Landauer.
4
Tale problema fu classificato NP-Hard.
Introduzione
V
Sono questi gli anni in cui si apre anche il nuovo campo della crittografia
quantistica: Wiesner, Bennett e Brassard nella prima metà degli anni ottanta
pubblicano articoli che lasciano intravedere una rivoluzione nei metodi di
trasmissione cifrata dell’informazione.
Nonostante il notevole clamore che suscitarono queste pubblicazioni, la ricerca ebbe
un periodo di arresto in quanto il mondo scientifico non riusciva a intravedere in
questo settore alcuna applicazione utile e convenientemente realizzabile che potesse
attirare i fondi necessari.
Bisogna aspettare quindi il 1994, anno in cui Peter Shor, ricercatore presso i famosi
Bell Laboratories, annunciò una delle più grandi scoperte degli ultimi anni in questo
settore.
Shor presentò al mondo scientifico un algoritmo in grado di fattorizzare un numero
intero con complessità polinomiale e risolvere quindi efficientemente il problema
del logaritmo discreto.
La notevole complessità di questi due problemi aveva infatti spinto le
organizzazioni mondiali per gli Standard a utilizzare, negli ultimi anni, istanze di
essi in tutti i sistemi di sicurezza telematici: dalle transazioni bancarie all’e-
commerce, dalle telecomunicazioni ai sistemi militari.
La diffusione della notizia fece piombare sulla ricerca più di un miliardo di dollari di
finanziamenti pubblici da parte di enti governativi come CIA, NASA e NSA
(National Security Agency) che dettero luogo a uno dei maggiori investimenti in
ricerca della storia. Inoltre, colossi dell’informatica come IBM, Toshiba, NEC,
Microsoft e compagnie come VISA, American Express e MasterCard hanno
finanziato e investito in ricerca cifre impressionanti nella corsa per aggiudicarsi un
posto nella creazione di sistemi che potrebbero cambiare il mondo.
Nonostante, il grande entusiasmo iniziale, ben presto i fisici e gli ingegneri si
trovarono a dover fare i conti con numerosi problemi realizzativi causati
dall’instabilità dei sistemi quantistici.
Sono così trascorsi alcuni anni e agli inizi del nuovo millennio, alcuni ricercatori,
ancora poco conosciuti, come A.Kitaev,E.Knill,D.Gottesman e M.Chuang solo per
citarne alcuni, dimostrarono che era possibile superare i problemi di instabilità con
l’introduzione della nuova teoria della Fault Tolerant Quantum Computation. Nuovi
formalismi matematici e molta ricerca algebrica hanno permesso, negli ultimi anni,
di elaborare strategie atte a contrastare il rumore nei sistemi quantistici, principale
Introduzione
VI
causa di perdita di preziosa informazione contenuta nella particolare
sovrapposizione di stati che si crea in questi sistemi.
Da allora sono apparse numerose pubblicazioni riguardanti metodi di
implementazione fault tolerant capaci di far si che questo ambito di ricerca
diventasse uno dei principali temi di interesse scientifico internazionale.
Il lavoro presentato si apre con una parte introduttiva in cui vengono definiti i
concetti di base della materia, alla quale fa seguito una sezione in cui vengono
esplorate alcune delle applicazioni di questo settore, per poi concludersi con
l’illustrazione di temi inerenti i meccanismi di correzione degli errori.
Il lavoro è composto di due sezioni: la prima descrive temi riguardanti i sistemi
fisici utilizzati, i modelli circuitali e il modello di calcolo utilizzato e si conclude
con una descrizione delle più interessanti applicazioni di questo nuovo settore
scientifico, la seconda, invece, lascia spazio ad argomenti che si inseriscono
nell’area di ricerca del settore inerente i meccanismi di protezione dal rumore e
approfondisce le metodologie di concatenazione dei codici correttori.
Ampio spazio è inoltre dedicato alla trattazione della Fault Tolerant Quantum
Computation mentre conclusivo riferimento è stato dedicato alla ricerca di una
nuova forma di concatenazione bidimensionale elaborata con il contributo del
Computer Science&Engineering Department della University of Washington
(Seattle – USA) e la collaborazione del Professor Dave Bacon, Principal Researcher
presso quel dipartimento e autore di numerose pubblicazioni in proposito.
Lo studio riguarda in particolare l’applicabilità di tale metodo ai codici correttori
sviluppati in questi anni e ne analizza le proprietà col fine di sviluppare prestazioni
sempre migliori.
Nello specifico, vengono trattati alcuni temi di teoria dei gruppi, necessari alla
migliore comprensione dei progressi teorici in tema di codici correttori e affidabilità
dei sistemi di calcolo basati sulle leggi quantistiche.
Lo studio si espande quindi ad analizzare lo sviluppo di metodi “Fault Tolerant”
nella creazione dei circuiti logici quantistici mediante la descrizione di un
particolare gruppo algebrico matriciale, il cosiddetto “Gruppo di Paoli”, che
costituisce uno dei più importanti e recenti formalismi matematici adottati per lo
studio dei codici correttori.
Introduzione
VII
Attraverso questo gruppo algebrico si possono infatti dimostrare proprietà di
universalità di alcune porte logiche e viene trattato il calcolo fault tolerant sugli stati
codificati.
Infine, il “Threshold Theorem” introduce negli ultimi capitoli uno dei temi più
studiati attualmente in questo ambito di ricerca: la concatenazione di codici. Questo
teorema stabilisce inoltre, la crescita polinomiale di un circuito Fault Tolerant nel
numero delle concatenazioni.
Queste proprietà giustificano perciò l’interesse verso sempre nuove forme di
concatenazione che abbiano proprietà in grado di rallentare tale crescita e
rappresentino un accettabile punto di compromesso tra l’affidabilità del sistema e
le dimensioni dei circuiti.
La richiamata forma di concatenazione, oggetto di esperimento in questa tesi, che si
discosta da quella classica per l’utilizzo dimensionale dello stesso codice,
rappresenta quindi una metodologia fino ad ora mai sviluppata in nessuna
pubblicazione apparsa in materia e viene dimostrata l’applicabilità a tutti i codici
lineari e vengono le proprietà nell’ambito di un settore di studi futuri volti ad
abbassare la soglia probabilistica di funzionamento dei codici correttori.
Sommario
Prima Sezione
Quantum computing
Capitolo 1:In questo capitolo introduttivo saranno richiamati alcuni concetti di fisica classica per
affrontare in seguito gli esperimenti fondamentali, che portarono all’elaborazione di un nuovo
impianto teorico in grado di spiegare quello che la teoria classica non riusciva a giustificare.
Questi richiami serviranno a introdurre la notazione di Dirac utilizzata in meccanica quantistica e
in questa tesi.
Capitolo 2:In questo capitolo introdurremo i concetti base della computazione quantistica
(Quantum Computing) a partire dall’unità di informazione quantistica elementare: il Q-bit
(Quantum bit). Saranno esplorate inoltre le proprietà intrinseche di un elaboratore che sfrutti
tale nuova unitari dell’informazione.
Capitolo 3:In questo capitolo verrà trattato il modello circuitale quantistico. In particolare
saranno presentati tutti gli elementi circuitali necessari ad elaborare l’informazione contenuta
nei sistemi quantistici. La dimostrazione di universalità di un set di porte logiche permetterà di
comprendere la possibilità di utilizzare elaboratori quantistici per il calcolo di tutte le funzioni
classiche implementate nei nostri attuali calcolatori.
Capitolo 4:In questo capitolo consideriamo come l’utilizzo meccanica quantistica possa essere
utilizzata per compiere calcoli e come questi siano qualitativamente differenti da quelli svolti su
un calcolatore tradizionale. Termineremo il capitolo con il famoso algoritmo di Deutsch-Josza.
Capitolo 5:Numerose applicazioni della teoria alla base del quantum computing sono state
pensate e ingegnerizzate. In questo capitolo introdurremo quattro esempi derivati dai principali
campi di sviluppo del quantum computing. Con questo capitolo si conclude la prima sezione.
Seconda Sezione
Quantum Error Correction
Capitolo 6: Questo capitolo apre la seconda sezione e affronta i problemi inerenti il rumore: questi
affliggono i sistemi quantistici, per questo saranno presentati gli strumenti matematici utilizzati per
trattarlo e le principali tipologie di rumore che colpiscono i sistemi quantistici.
Capitolo 7: Questo capitolo introdurrà il concetto di codice correttore partendo dalla teoria
classica di correzione degli errori. Verrà quindi presentata la teoria quantistica per la correzione e
il ripristino dell’informazione negli stati corrotti dal rumore.
Capitolo 8: Questo capitolo introdurrà, partendo da uno dei codici quantistici più famosi, il
Calderbank-Shor-Steane code, lo Stabilizer Formalism che rappresenta uno dei più potenti
strumenti matematici utilizzati in meccanica quantistica e nell’ambito dei codici correttori per
descrivere gli stati quantistici.
Capitolo 9:In questo capitolo saranno ripresi i concetti esposti nei precedenti capitoli per
introdurre gli strumenti matematici e algebrici della moderna teoria dei codici correttori
quantistici. Sarà inoltre presentato il teorema di Gottesman-Knill che rappresenta uno dei
maggiori risultati nell’ambito dell’elaborazione quantistica. Una panoramica sul calcolo
quantistico fault tolerant introdurrà i più recenti sviluppi nell’ambito della progettazione di
architettura quantistiche resistenti al rumore.
Capitolo 10 :Questo capitolo finale presenta il lavoro di ricerca svolto presso il Dipartimento di
Computer Science della University of Washington,( Seattle, USA) sotto la guida di del Professor
Dave Bacon. Verrà presentata una nuova forma di codifica, detta Subsystem coding e ne
verranno illustrate le proprietà algebriche. La parte conclusiva è dedicata all’estensione di
questa tecnica a tutti i codici lineari quantistici.
Prima Sezione
“Quantum Computing”
Capitolo 1
1
Capitolo 1
Meccanica quantistica: dal modello fisico a
quello matematico
“Non mi piace, e mi spiace di averci avuto a che fare”
Erwin Schrödinger
In questo capitolo introduttivo saranno richiamati alcuni concetti di fisica classica per
affrontare in seguito gli esperimenti fondamentali, che portarono all’elaborazione di
un nuovo impianto teorico in grado di spiegare quello che la teoria classica non
riusciva a giustificare. Questi richiami serviranno a introdurre la notazione di Dirac
utilizzata in meccanica quantistica e in questa tesi.
Introduzione
La meccanica quantistica o fisica quantistica è una teoria formulata nella prima metà
del ventesimo secolo che descrive il comportamento della materia a livello sub-
microscopico. In sistemi dell'ordine di grandezza dell'atomo e con energie tipiche delle
interazioni nucleari cadono le ipotesi, che stanno alla base della meccanica classica.
La meccanica quantistica spiega e descrive fenomeni che, nell'opinione della maggior
parte dei fisici del ‘900, non possono essere giustificati tramite la meccanica classica.
La peculiarità della meccanica quantistica è il fatto che la particelle vengono descritte
tramite onde di probabilità.
Una conseguenza importante di questo approccio è il cosiddetto principio di
indeterminazione di Heisenberg
1
, secondo il quale esistono coppie di variabili(dette
anche coniugate), come la posizione e l’impulso di una particella, il cui valore non può
essere conosciuto simultaneamente con precisione arbitraria, indipendentemente
dall'accuratezza delle misure.
1
Il principio di indeterminazione di Heisenberg è descritto nell’appendice A relativa alla
meccanica quantistica.
Capitolo 1
2
In meccanica classica la conoscenza ad un dato istante del valore delle variabili
coniugate permette, attraverso le equazioni del moto, di predirne l'evoluzione con un
livello di precisione arbitraria. L'indeterminazione quantistica, invece, permette di
prevedere solo la probabilità di misurare determinati valori all'atto dell'esperimento;
questo conferisce un carattere prettamente probabilistico alla meccanica quantistica.
Tale teoria elimina anche la distinzione tra particelle e onde che aveva caratterizzato la
fisica del XIX secolo. L'evoluzione temporale di un sistema quantistico, infatti,
presenta le caratteristiche tipiche delle onde (fenomeni di interferenza e diffrazione),
mentre all'atto della misura viene osservato un comportamento corpuscolare, vale a dire
la materia non viene rilevata come un flusso continuo, ma divisa in elementi minimi
detti quanti (dal latino quantum, da cui il nome della teoria). In questo modo, non si è
costretti a dire che la materia si comporta contemporaneamente come onde e particelle,
che sarebbe una contraddizione, ma che l'evoluzione della distribuzione delle
probabilità ha caratteristiche ondulatorie, mentre all'atto della misura si riscontrano
proprietà corpuscolari.
Questa doppia natura prende il nome di dualità onda-corpuscolo ed è spesso
considerata come una caratteristica fondamentale della meccanica quantistica.
1.1 Storia della meccanica quantistica
Nel 1900 Max Planck introdusse l'idea che l'energia fosse quantizzata per ottenere una
formula per la dipendenza dalla frequenza dell'energia emessa da un corpo nero.
Cinque anni dopo Einstein spiegò l'effetto fotoelettrico proponendo che l'energia
luminosa viaggiasse in quanti, chiamati fotoni.
Nel 1913 Bohr spiegò le linee spettrali dell'atomo di idrogeno, sempre introducendo
una quantizzazione.
Dieci anni più tardi Louis de Broglie introdusse la sua teoria delle onde materiali.
Tutte queste teorie, che descrivono con successo gli esperimenti effettuati dai fisici del
tempo, erano basate su osservazioni empiriche: non c'era infatti alcuna giustificazione
alla quantizzazione, esse sono note collettivamente come la vecchia teoria quantistica.
Occorre aspettare il 1925, data di nascita della meccanica quantistica moderna, per
poter parlare di sviluppo della meccanica matriciale da parte di Heisenberg e della
Capitolo 1
3
meccanica ondulatoria da parte di Schrödinger. E’ stato quest' ultimo a mostrare in
seguito che i due approcci sono equivalenti.
Due anni dopo Heisenberg formula il suo principio di indeterminazione e circa nello
stesso periodo nasce l'interpretazione di Copenaghen.
Pochi anni dopo Dirac unisce la meccanica quantistica con la relatività ristretta ed usa
pesantemente la teoria degli operatori, compresa l'importante notazione “bra-ket”.
Negli anni trenta John von Neumann pone basi matematiche rigorose alla formulazione
della teoria degli operatori quantistici.
Sono gli anni successivi a determinare la nascita di diversi campi di applicazione della
meccanica quantistica.
Agli inizi degli anni quaranta Feynman, Dyson, Schwinger e Tomonaga introducono
l'elettrodinamica quantistica (QED), che servirà anche come modello per le successive
teorie di campo.
Negli anni sessanta comincia la lunga storia della cromodinamica quantistica (QCD)
legata allo studio di particelle subatomiche quali i quark e i gluoni.
Nel 1975, Polizter, Gross and Wilzcek formulano la QCD nella forma attualmente
accettata.
Negli anni ottanta, partendo da un lavoro di Schwinger; Higgs, Goldstone, Glashow,
Weinberg e Salam mostrarono in modo indipendente che la forza debole e la QED
possono essere fuse in un'unica teoria, la teoria elettrodebole.
Infine nel 1982 un'equipe dell'Istituto Ottico di Orsay, diretta da Alain Aspect, porta a
buon esito una lunga serie di esperimenti che mostrano una violazione della
disuguaglianza di Bell[2].
1.2 Lo stato di un sistema classico e di un sistema quantistico
Mentre in meccanica classica lo stato di un sistema viene definito attraverso il valore
esatto delle sue variabili di posizione e quantità di moto, in meccanica quantistica lo
stato del sistema è descritto da una funzione d'onda il cui modulo al quadrato fornisce
le distribuzioni di probabilità di tutte le proprietà misurabili.
Essa fornisce quindi informazioni sulle probabilità di misurare un dato valore per una
“osservabile”, ossia per un operatore che permette di determinare una proprietà del
sistema.
Capitolo 1
4
Il significato di questa probabilità può essere così interpretato: se abbiamo a
disposizione infiniti sistemi identici, effettuando la stessa misura su tutti i sistemi, la
distribuzione dei valori ottenuti è proprio il quadrato del modulo della funzione d'onda.
La funzione d'onda che descrive lo stato del sistema può cambiare al passare del tempo.
Ad esempio, una particella che si muove in uno spazio vuoto è descritta da una
funzione d'onda costituita da un pacchetto d'onda centrato in una posizione media per
la posizione della particella considerata; al passare del tempo, quando il centro del
pacchetto d'onda cambia, la particella può essere localizzata in una posizione
differente.
L'evoluzione temporale della funzione d'onda è descritta dall'Equazione di Schrödinger
dipendente dal tempo
2
),
2
),)(
4
2
2
tx
t
h
itxxV
xm
h
(
∂
∂
=(
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
∂
∂
− ψ
π
ψ
π
(1.1)
dove:
h = costante di Planck
3
;
V(x)= energia potenziale nella posizione x;
La funzione ψ è chiamata anche ampiezza di probabilità e si postula che rappresenti
tutto quello che è possibile misurare di una particella, in altre parole il suo vettore di
stato .
La quantità ψ è funzione del tempo e delle coordinate, mentre non porta informazione
sull’impulso e moltiplicata per una variabile complessa la sua descrizione dello stato
rimane immutata: questo permette di normalizzarla ponendo 1
2
=
∫
dqψ dove dq è
l’elemento infinitesimale di volume.
2
Esiste anche una versione più semplice dell’equazione che è quella in cui la funzione ψ non dipende
dal tempo.
3
Il valore assegnato alla costante di Planck è
16
6.62 10heV
−
=× .
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.