Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui...

42

Transcript of Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui...

Page 1: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer
Page 2: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Introduzione al Quantum Computing

Autore:Marco Ivaldi

Copyright c© 2002 – Apogeo Srl, Marco IvaldiVia Natale Battaglia 12 – 20127 Milano (Italy)Telefono: 02-28970277 (5 linee r.a.)Telefax: 02-26116334Email [email protected]. http://www.apogeonline.com

Responsabile editoria digitale: Alberto MariCopertina: Enrico Marcandalli

Tutti i diritti sono riservati a norma di legge e a normadelle convenzioni internazionali. È consentita lariproduzione integrale del testo senza alcuna modificapurché a fini non di lucro, inserendo chiara citazionedegli Autori e dell’Editore. Nomi e marchi citati nel testosono generalmente depositati o registrati dalle rispettivecase produttrici.

Page 3: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Indice

1 Introduzione: un nuovo modo di sfrutta-re la natura 1

2 Un po’ di storia 3

3 Dal bit al qubit 5

4 Algoritmi quantistici 9

5 Che cosa ci riserva il futuro? 15

6 Riferimenti 21

Page 4: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer
Page 5: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Introduzione: unnuovo modo disfruttare la natura

Molte tappe nella storia della tecnologia hannocomportato la scoperta di nuovi modi per sfruttarela natura: l’utilizzo di varie risorse fisiche comemateriali, forze e sorgenti di energia ha fatto sì chel’uomo compisse progressi tecnologici sempre piùgrandi. Nel corso del Ventesimo Secolol’informazione è entrata a far parte della tecnologia,a partire dal momento in cui l’invenzione deicomputer ha permesso di processare informazionicomplesse all’esterno dei cervelli umani. La stessastoria dei calcolatori è intessuta di una sequenza dicambiamenti da un tipo di implementazione fisicaad un altro, dalle prime valvole ai circuiti integratidi oggi. Fino alle odierne tecniche più avanzate checi consentono di costruire componenti di dimensioniinferiori al micron; e presto avremo chip ancora più

Page 6: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

2 Introduzione: un nuovo modo di sfruttare la natura

ridotti, sino a raggiungere il punto in cui le portelogiche necessarie al funzionamento dei computersaranno costituite di pochi atomi ciascuna.Sul piano degli atomi, la materia obbedisce alleregole della meccanica quantistica, molto differentida quelle della fisica classica, che invecedeterminano le proprietà delle porte logicheconvenzionali. Per questo motivo, se i computerdovranno diventare di dimensioni così ridotte nelprossimo futuro, una tecnologia completamentenuova dovrà sostituire ciò che utilizziamo ora. Latecnologia quantistica, però, può offrire molto di piùdella diminuzione delle dimensioni e dell’aumentodella velocità di clock dei calcolatori: essa puòaprire la strada a calcoli di un generecompletamente nuovo, con algoritmi basati suprincipi quantistici diversi da quelli a cui siamoabituati. Questa nuova tecnologia prende il nome di“Quantum Computing”.Il Quantum Computing nasce dall’unione tra Teoriadell’Informazione classica, Informatica e FisicaQuantistica. Questo breve e-book vuole essereun’introduzione al Quantum Computing eall’argomento molto vasto della nuova Teoriadell’Informazione Quantistica. La cosa che stupiscemaggiormente è che la Teoria dell’Informazione e laMeccanica Quantistica si sposano in effetti moltobene, dando vita ad interessanti implicazioni.

Page 7: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Un po’ di storia

I fondamenti dell’Informatica sono stati formulatipiù o meno contemporaneamente alla Teoriadell’Informazione di Shannon, fatto che non deveessere considerato come una mera coincidenza. Ilpadre dell’Informatica è probabilmente Alan Turing(1912-1954), ed il suo profeta è Charles Babbage(1791-1871). Babbage, infatti, ha concepito glielementi essenziali di un calcolatore moderno,nonostante ai suoi tempi non esistesse latecnologia necessaria a realizzare praticamente lesue idee. È dovuto passare un intero secolo primache l’Analytical Engine di Babbage fosse miglioratain quello che Turing ha descritto come la UniversalTuring Machine, verso la metà degli anni Trenta. Ipiù grandi meriti di Turing sono stati il chiarire conestrema precisione di che cosa debba essere capaceuna macchina per il calcolo e l’enfatizzare il ruolodel software e della programmazione, più ancora diquanto non avesse fatto il suo predecessore.I moderni calcolatori elettronici non sono né

Page 8: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

4 Un po’ di storia

Macchine di Turing né Motori di Babbage;ciononostante sono basati su principi molto simili epossiedono un potere computazionale equivalente.Senza scendere troppo nel dettaglio, vogliamoporre l’accento sul fatto che durante la storia dellosviluppo dei computer non vi è stato mai alcunsostanziale cambiamento dell’idea essenziale dicalcolatore o di come esso operi. Tutti imiglioramenti sono quantificabili in termini divelocità e dimensioni. Ed ecco che cosa differenziail Quantum Computing dall’Informatica classica: laMeccanica Quantistica per la prima volta faintravedere la possibilità di un cambiamentosostanziale dei computer e del loro modo dioperare.Cerchiamo di capire semplicemente in che terminied in che modo.

Page 9: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Dal bit al qubit

La caratteristica fondamentale dell’informazione èla possibilità di essere codificata in un numero dimodi virtualmente infinito. Ad esempio la fraseitaliana “Alice è a casa mia” ed il corrispettivofrancese “Alice est chez-moi” contengono la stessainformazione, espressa in codici differenti.Comunque sia, ciò che accomuna tutti i modi diesprimere informazione è la necessità di strumentifisici. Le parole parlate, infatti, sono costituite dafluttuazioni nella pressione dell’aria, quelle scritteda molecole di inchiostro su carta, persino gli stessipensieri dipendono dai neuroni. Il motto deiricercatori è pertanto: “nessuna informazionesenza la sua rappresentazione fisica!”.I computer classici che tutti conosciamo utilizzanocome unità di informazione di base il cosiddetto bit.Da un punto di vista prettamente fisico il bit è unsistema a 2 stati: può infatti essere indotto in unodei due stati distinti rappresentanti 2 valori logici -no o sì , falso o vero, o semplicemente 0 o 1. In

Page 10: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

6 Dal bit al qubit

termini pratici, senza scendere nei dettagliimplementatitivi, il bit viene realizzato utilizzando leproprietà dell’energia elettrica (assenza di carica opresenza di carica). Un bit di informazione puòovviamente venire rappresentato anche attraversoaltri mezzi: ad esempio con 2 differentipolarizzazioni di luce o 2 differenti stati elettronicidi un atomo. Ed è proprio quando arriviamoall’infinitamente piccolo che la MeccanicaQuantistica entra in gioco, informandoci che se unbit può esistere in 2 stati distinti può anche esisterein una loro sovrapposizione coerente. Si tratta diun terzo stato, che non ha un analogo classico ingenerale, in cui l’atomo rappresenta entrambi ivalori 0 e 1 contemporaneamente. Per aiutare acomprendere come una quantità fisica possaassumere 2 valori in contemporanea viene ingenere illustrato un semplice esperimento diriflessione dei fotoni, che noi non tratteremo,limitandoci a segnalarlo tra i Riferimenti.Occupiamoci invece di ampliare ulteriormente ilconcetto di sovrapposizione di numeri.Consideriamo un registro composto da 3 bit fisici.Un registro a 3-bit classico può contenereesattamente uno degli 8 diversi numeri possibili: inaltre parole esso può trovarsi in una delle ottopossibili configurazioni 000, 001, 010, ..., 111,rappresentazioni binarie dei numeri da 0 a 7. Adifferenza di ciò, un registro quantistico composto

Page 11: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

7

da 3-qubit (come vengono chiamate le unità diinformazione di base nel Quantum Computing,corrispettive del bit classico) è in grado di contenerefino a tutti e 8 i numeri contemporaneamente inuna sovrapposizione quantistica.Il fatto che 8 numeri differenti possano esserefisicamente presenti in contemporanea nello stessoregistro è una diretta conseguenza delle proprietàdei qubit, e ha delle grandi implicazioni dal punto divista della Teoria dell’Informazione. Seaggiungessimo più qubit al registro la sua capacitàdi memorizzare informazioni crescerebbe inmaniera esponenziale: 4 qubit possonoimmagazzinare fino a 16 numeri allo stesso tempo,ed in generale L qubit sono in grado di conservare2L numeri contemporaneamente. Un registro di250-qubit, per capirci, composto essenzialmente di250 atomi, sarebbe capace di memorizzare piùnumeri contemporaneamente di quanti siano gliatomi presenti nell’universo conosciuto. Un datosenza dubbio scioccante.In termini pratici, però, quando misuriamo ilcontenuto di un registro siamo in grado di vederesolamente uno dei numeri della sovrapposizione:ciò rappresenta sicuramente un problema nel casodi quantistica applicata a problemi tradizionalimolto semplici. Ma nel caso in cui dovessimoeffettuare un calcolo quantistico più complesso, checonsista di più passaggi e pertanto più operazioni

Page 12: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

8 Dal bit al qubit

sui registri, il vero vantaggio del QuantumComputing inizierebbe a manifestarsi: quando unregistro contiene una sovrapposizione di moltinumeri differenti, infatti, un calcolatore quantisticoè in grado di effettuare operazioni matematiche sututti loro contemporaneamente, allo stesso costo intermini computazionali dell’operazione eseguita suuno solo dei numeri. Ed il risultato sarà a sua voltauna sovrapposizione coerente di più numeri. Inaltre parole: è possibile eseguire un massicciocalcolo parallelo ad un costo computazionaleirrisorio rispetto a quello richiesto dai computertradizionali, che avrebbero bisogno per compiere lastessa operazione di ripetere il calcolo 2L volte o dipoter contare su 2L processori paralleli.In breve, ecco riassunto quello che ci offre uncalcolatore quantistico: un enorme guadagno dirisorse computazionali come tempo e memoria,anche se solamente per certi tipi di operazione.

Page 13: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Algoritmi quantistici

Cerchiamo ora di fare luce sulle possibiliapplicazioni dei calcolatori quantistici. Comeabbiamo accennato le leggi della fisica cipermettono di leggere un solo risultato da unregistro, anche se esso contiene 2L numeridifferenti: per questo motivo il QuantumComputing non ci porta un vantaggio immediato intermini di conservazione dell’informazione.Sapendo però che grazie ad una proprietà deiquanti molto importante nota con il nome di“quantum interference” siamo in grado di ottenereun risultato finale singolo che dipende logicamenteda tutti i 2L risultati intermedi, possiamocomprendere gli algoritmi che sono stati introdottidai ricercatori.Consideriamo ad esempio l’algoritmo scoperto daLov Grover dei Bell Labs della AT&T, che realizzauna ricerca in una lista non ordinata di N elementiin radice di N passi. È lampante per chi non ètotalmente digiuno di informatica che un algoritmo

Page 14: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

10 Algoritmi quantistici

del genere è impossibile da realizzare con letecniche classiche. Pensiamo, ad esempio, di doverricercare un numero di telefono specifico all’internodi un elenco contenente 1 milione di elementi,ordinati alfabeticamente: è ovvio che nessunalgoritmo classico più migliorare il metodo diricerca a forza bruta che consiste nella semplicescansione degli elementi fino a quando non si trovaquello che ci interessa. Gli accessi alla memoriarichiesti nel caso medio saranno pertanto 500.000,che è dello stesso di grandezza di N (O(N), comeviene espresso in notazione matematica).Un computer quantistico è invece in grado diesaminare tutti gli elementi simultaneamente, neltempo di un singolo accesso alla memoria: se fosseprogrammato per stampare semplicemente ilrisultato a questo punto, però, non costituirebbe unmiglioramento rispetto all’algoritmo classico,perché solamente uno sul milione dei percorsi dicalcolo effettuati conterrà l’elemento a cui siamointeressati, e per conoscerlo dovremo per forza dicose ispezionarli tutti.Se però lasciamo l’informazione quantistica ricavataall’interno del calcolatore senza misurarla,possiamo applicarvi direttamente un’altraoperazione che automaticamente andrà ad influiresu altri percorsi (che comunemente vengonochiamati “universi”). In questo modo l’informazioneriguardante l’elemento ricercato è diffusa,

Page 15: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

11

attraverso la quantum interference, ad altriuniversi. Si è verificato che se questa operazioneche genera interferenza viene ripetuta radice di Nvolte (nel nostro caso 1000), l’informazione che ciinteressa sarà accessibile attraverso il misuramentocon una probabilità di 0.5: in altre parole, si saràdiffusa in più della metà degli universi possibili.Pertanto ulteriori ripetizioni dell’algoritmo cipermetteranno di trovare il risultato che ciinteressa con una probabilità molto prossima ad 1.Nonostante l’algoritmo di Grover sia uno strumentoestremamente versatile e potente, in pratica laricerca in un database fisico sarà difficilmente unadelle sue applicazioni fondamentali, almeno fino aquando la memoria classica resterà molto piùeconomica di quella quantistica. Per queste ragioni,il campo in cui questo algoritmo da’ il meglio di sé èsicuramente quello della ricerca algoritmica, nellaquale i dati non sono conservati in memoria, masono generati al volo da un programma: pensiamoad esempio ad un calcolatore quantisticoprogrammato per giocare a scacchi, che utilizzil’algoritmo di Grover per investigare tutte lepossibili mosse a partire da una determinataconfigurazione della scacchiera.Come Gilles Brassard dell’Università di Montreal harecentemente fatto notare, inoltre, un’altraimportantissima applicazione dell’algoritmo diGrover è nel campo della crittanalisi, per attaccare

Page 16: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

12 Algoritmi quantistici

schemi crittografici classici come il Data EncryptionStandard (DES) con un approccio a forza bruta.Crackare il DES fondamentalmente richiede unaricerca tra tutte le 256 = 7 x 106 possibili chiavi. Uncomputer classico, potendo esaminarne ad esempio1 milione al secondo, impiegherebbe migliaia dianni a scoprire quella corretta; un computerquantistico che utilizzi l’algoritmo di Grover, invece,ci metterebbe meno di 4 minuti.Per qualche strana coincidenza, molte dellecaratteristiche superiori dei calcolatori quantisticihanno applicazioni nel campo della crittologia. Oltreall’algoritmo di ricerca di Grover che abbiamoappena visto, c’è quello scoperto nel 1994 da PeterShor (un altro ricercatore dei Bell Labs) per lafattorizzazione efficiente di numeri interi grandi. Inquesto caso la differenza di performance tra glialgoritmi quantistici e quelli classici è ancora piùspettacolare.I matematici sono convinti (anche se di fatto lacosa non è mai stata dimostrata in manierarigorosa) che la fattorizzazione di un numero interocon N cifre decimali sia particolarmente pesante intermini computazionali: per portare a terminel’operazione, qualsiasi computer classico ha bisognodi un numero di passi che cresce esponenzialmentecon N. Questo significa che aggiungendo unasemplice cifra al numero da fattorizzare il temponecessario a compiere l’operazione si moltiplica per

Page 17: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

13

un fattore fisso. Per rendere meglio l’idea, bastipensare che fino ad ora il numero più grande che èstato fattorizzato, nel corso di una “gara” tramatematici, aveva 129 cifre. Nessuno è in grado diconcepire la possibilità di fattorizzare numeri dimigliaia di cifre con i metodi classici: il calcolorichiederebbe più volte l’età stimata dell’universo.In contrasto, i calcolatori quantistici possonofattorizzare numeri di migliaia di cifre in unafrazione di secondo, ed il tempo di esecuzionecresce solamente secondo il cubo del numero dellecifre (e non esponenzialmente come nel casodell’algoritmo classico).La cosa più interessante è che sulla difficoltà dicalcolo dell’operazione di fattorizzazione si basa lasicurezza di quelli che sono al momento i metodi dicifratura più utilizzati ed universalmentericonosciuti come inattaccabili: stiamo parlando inparticolar modo del sistema RSA (Rivest, Shamir eAdleman). Tale algoritmo crittografico è almomento largamente impiegato per proteggere lecomunicazioni più riservate e le transazionibancarie, che si avvalgono di uno schemacrittografico a chiave asimmetrica (la crittografia achiave pubblica è stata scoperta originariamente daEllis e Cocks del GCHQ inglese). Quando dovesseessere costruita un’engine quantistica per lafattorizzazione, tutti i sistemi crittografici a chiaveasimmetrica diverranno completamente insicuri.

Page 18: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

14 Algoritmi quantistici

Probabilmente questo momento è ancora lontano,ma di fatto le recenti scoperte ci fanno capire che èora di pensare ad altri metodi crittografici, inprevisione di quello che ci può riservare il futuro.

Page 19: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Che cosa ci riserva ilfuturo?

In linea di principio siamo già in grado di costruireun calcolatore quantistico: cominciamo con dellesemplici porte logiche quantistiche, che come nelcaso delle porte classiche sono dei semplici devicesin grado di eseguire un’operazione elementare suuno o due qubit. Ovviamente esse differisconodalle loro controparti classiche, perché sono ingrado di operare su sovrapposizioni quantistiche.Tali porte dovranno poi essere collegate in reti, perpoter operare come un computer.Al crescere del numero delle porte quantistichenella rete, però, ci imbattiamo rapidamente inalcuni problemi pratici molto seri. Più qubit sonocoinvolti, più diventa complesso gestirel’interazione che genera la quantum interference. Aparte le difficoltà derivanti dal dover lavorare alivello di singolo atomo e singolo fotone, uno deiproblemi più importanti è quello di impedire che

Page 20: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

16 Che cosa ci riserva il futuro?

anche l’ambiente venga modificato dalle interazioniche generano le sovrapposizioni quantistiche. Piùcomponenti vi sono, più si fa probabile chel’informazione quantistica si diffonda all’esterno delcomputer per perdersi nell’ambiente,compromettendo i risultati del calcolo. Questoprocesso prende il nome di “decoerenza”, e perevitarlo gli ingegneri devono riuscire a produrresistemi sub-microscopici nei quali i qubit siinfluenzano l’un l’altro, ma sono completamenteseparati dall’ambiente esterno.Per lo stesso motivo, è immediato osservare che glieffetti della quantum interference che rendonorealizzabili algoritmi come quello di Shor sonoestremamente fragili: i computer quantistici sonomolto sensibili alle interferenze provenientidall’esterno.Ed è a questo punto che entra in gioco la nuovaTeoria dell’Informazione Quantistica, nata dalconnubio tra Teoria dell’Informazione classica eQuantum Computing: è infatti possibile,combinando elementi delle due discipline, realizzarecalcolatori quantistici molto meno sensibili alleinterferenze esterne, grazie a quella che vienechiamata “quantum error correction”. Solo nel 1996sono stati realizzati due documenti di Calderbank eShor, e indipendentemente Steane, che hannostabilito i principi generali con cui il quantuminformation processing può essere utilizzato per

Page 21: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

17

combattere una vasta gamma di interferenze in unsistema quantistico. Molti progressi sono stati fattisuccessivamente nell’opera di generalizzazione diqueste idee: in particolare, un importante sviluppoc’è stato con la dimostrazione effettuata da Shor eKitaev che la correzione degli errori può avereluogo anche quando le stesse operazioni correttivesono imperfette. Questi metodi conducono ad unconcetto di Quantum Computing “fault tolerant”. Sela correzione degli errori in sé non garantisce uncalcolo quantistico accurato, poiché non puòcombattere tutti i tipi di interferenza, il fatto che siapossibile rappresenta comunque uno svilupposignificativo che ci fa ben sperare per il futuro.Un’altra importante implicazione del connubio traMeccanica Quantistica e Teoria dell’Informazione,derivante direttamente dalle proprietà di base deisistemi quantistici applicate alla pratica, è la“quantum cryptography”. La crittografia quantisticacomprende numerose idee, tra le quali la piùinteressante (e la più seguita) è la “quantum keydistribution”. Si tratta di un metodo moltoingegnoso secondo il quale gli stati quantisticitrasmessi sono utilizzati per eseguire unacomunicazione molto particolare: creare in duelocazioni separate una coppia di sequenze di bitrandomiche identiche, impedendonel’intercettazione da terze parti. Si nota subito comequesto possa rivelarsi molto utile nel caso dello

Page 22: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

18 Che cosa ci riserva il futuro?

scambio di chiavi crittografiche per cifrarisimmetrici, operazione che necessita di un canaleassolutamente sicuro. La caratteristicafondamentale è che i principi della meccanicaquantistica garantiscono la conservazionedell’informazione, in modo che se essa arriva adestinazione si può essere sicuri che non è andatada nessun’altra parte (in altre parole, non è stataintercettata). Di conseguenza, l’intero problemadelle chiavi compromesse, che riempie da secoli gliannali della storia dello spionaggio, è evitatocompletamente avvalendosi della struttura delmondo naturale e delle sue leggi.Tra gli effetti del Quantum Computing che piùrischiano di influenzare il nostro futuro, uno dei piùinteressanti è sicuramente la rivoluzione delconcetto stesso di dimostrazione matematica.Quando abbiamo a che fare con computer classici,infatti, possiamo descrivere matematicamente confacilità le operazioni da essi compiute. In questomodo siamo in grado di fornire una prova dellacorrettezza del calcolo svolto che soddisfi ladefinizione classica: “una sequenza di proposizioniognuna delle quali è un assioma o deriva daproposizioni precedenti nella sequenza attraverso leregole standard di inferenza”. Con il QuantumComputing questa definizione non è più valida:d’ora in avanti una dimostrazione dovrà essereconsiderata come un processo (il calcolo stesso, e

Page 23: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

19

non una registrazione di tutti i suoi passaggi): infuturo è estremamente probabile che un calcolatorequantistico riesca a dimostrare teoremi attraversometodi che un cervello umano (o un calcolatoreclassico) non è in grado nella maniera più assolutadi controllare, perché se la “sequenza diproposizioni” corrispondente alla dimostrazioneintesa nel senso classico venisse stampata, la cartariempirebbe l’universo osservabile per molte volte.Riguardo alla realizzabilità di un calcolatorequantistico complesso, molti studiosi sono tutt’orascettici. Recentemente, però, l’IBM ha costruito unprimo esempio di computer quantistico, con laprima implementazione funzionante dell’algoritmodi fattorizzazione di Shor. Come si legge all’urlhttp://www.research.ibm.com/resources/news-/20011219_quantum.shtml, i ricercatori hannorealizzato un calcolatore a 7-qubit e fattorizzato ilnumero 15 nei suoi fattori primi 3 e 5. Nonostantel’apparente semplicità, si tratta del calcoloquantistico più complesso mai effettuato fino adora, e lascia ben sperare per gli sviluppi futuri diquesta affascinante materia di studio.

Page 24: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer
Page 25: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Riferimenti

• Centro di ricerca per il Quantum Computing,comprendente una grande quantità didocumentazione, compresa quellasull’esperimento della riflessione dei fotonicitato nel testo.

http://www.qubit.org

• QCL (Quantum Computation Language),linguaggio di programmazione architectureindependent ad alto livello per computerquantistici, con una sintassi derivata dailinguaggi procedurali classici come il C e ilPascal.

http://tph.tuwien.ac.at/ oemer/qcl.html

• “Heads” (1990), novella di Greg Bear.Pubblicata in Italia con il titolo di “Zeroassoluto”, nella raccolta “Cyberpunk” dellaEditrice Nord.

Page 26: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

22 Riferimenti

• Quantum Computation/Cryptography presso ilCentro di Ricerca di Los Alamos.

http://qso.lanl.gov/qc/

• Quantum Computing FAQ (Frequently AskedQuestions)

http://www.rdrop.com/ cary/html/quantum_c-_faq.html

Page 27: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Catalogo Apogeo – luglio 2002

Flash Xboxdi Viscardi RosarioPagine: 240Euro: 7,9

Xbox: oltre i videogiochi, verso il mondo delmultimedia, di Internet e del lavoro. Una guidapreziosa a tutti i segreti della console Microsoft.

XML Guida Completadi Devan ShepherdPagine: 496Euro: 34

Dalla sintassi di base fino allo sviluppo diapplicazione complete, un tutorial per apprendere isegreti del linguaggio XML in 21 giorni.

Page 28: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Red Hat Linux 7.3 Flashdi Georges PiriouPagine: 264Euro: 7,9

Un manuale tascabile sul sistema operativo liberoideato da Linus Torvalds nella distribuzione Red Hat7.3.

Object Oriented Programming GuidaCompletadi Anthony SintesPagine: 576Euro: 35,9

Dall’introduzione della programmazione orientataagli oggetti alla presentazione di case study dianalisi, progetti e implementazioni.

Page 29: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

AutoCAD LT 2002 Guida all’usodi Ralph GrabowskiPagine: 320Euro: 25

La guida all’ultima versione di AutoCAD a cura diRalph Grabowski, autore dei manuali più vendutinel mondo sul più famoso prodotto per il CAD.

Visual Basic .Net Flashdi Marisa PadovaniPagine: 216Euro: 7,9

Un piccolo manuale per avere in tasca tutte leinformazioni fondamentali su Visual Basic .Net,strutturate secondo brevi lezioni da 10 minuticiascuna.

Page 30: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Matlab Concetti e progettidi Naldi Giovanni, Pareschi LorenzoPagine: 360Euro: 22

Una introduzione all’uso del software MATLAB comeambiente particolarmente adatto per avvicinarsi almondo del calcolo scientifico e alle simulazioninumeriche di modelli matematici.

Flash MX Guida all’usodi M. MattioliPagine: 384Euro: 25

Come fare dell’animazione la chiave vincente deipropri siti Web. Dalle proprietà di base di Flash adalcuni elementi di programmazione conActionScript, il libro affronta tutti gli aspetti piùimportanti del software.

Page 31: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Catalogo Apogeo – giugno 2002

Visual Basic .Net Tutto & Oltredi Paul KimmelPagine: 600Euro: 39,9

Come costruire applicazioni distribuite e creareservizi con VB .NET: un manuale indispensabile peril programmatore.

Introduzione alla Macroeconomiadi Kennedy PeterPagine: 512Euro: 30

Un’introduzione, non tecnica ma rigorosa, allamacroeconomia per gli studenti di facoltàuniversitarie e di corsi post-laurea e per tutti gliinteressati a comprendere meglio il funzionamentodelle economie in cui viviamo.

Page 32: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Mobile Businessdi R. Kalakota, M. RobinsonPagine: 320Euro: 23

Diventa sempre più facile e relativamente pococostoso accedere a servizi diversi mediantedispositivi mobili di comunicazione, come cellulari epalmari. Quali sono le prospettive e le opportunitàdi business?

Strumenti quantitativi per lagestione aziendaledi Waner, CostenoblePagine: 360Euro: 23

La soluzione ideale per l’insegnamento dellamatematica nelle lauree triennali di Scienzedell’Economia e della Gestione Aziendale.

Page 33: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Fondamenti di telecomunicazionidi Leon W. CouchPagine: 768Euro: 44

Testo di riferimento per acquisire le competenzefondamentali riguardo ai sistemi ditelecomunicazione che ogni professionista delsettore dell’Ingegneria e delle Scienzedell’Informazione deve possedere.

Computer per tutti V edizionedi Enzo AmatoPagine: 224Euro: 16,9

Il computer incute ancora timore? Un manualedavvero per tutti per avvicinarsi al mondo dellatecnologia e imparare a usarla al meglio.

Page 34: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

JavaScript la guida II edizionedi David FlanaganPagine: 816Euro: 44,9

Dal nucleo del linguaggio fino alla creazione diesempi sofisticati, una guida di riferimentoessenziale per il programmatore Javascript.

Content Managementdi Lucchini (a cura di)Pagine: 420Euro: 23

Da un master dell’Ateneo Multimediale di Milano, unpercorso formativo per quanti devono assolvere allefunzioni di content management.

Page 35: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

C# Tutto & Oltredi Joseph MayoPagine: 672Euro: 44,9

Un testo fondamentale, in grado di mostrare comeC# possa essere usato per sviluppare del softwarecome servizio, concetto che sta alla base della suite.NET

Page 36: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Catalogo Apogeo – maggio 2002

ECDL Modulo 4: Foglio elettronicodi RubiniPagine: 144Euro: 9,8

Dal syllabus originale per la patente europea delcomputer, il modulo 4: Foglio elettronico.

PC For Dummiesdi Dan GookinPagine: 320Euro: 18,9

Un modo facile per avvicinarsi al mondo delcomputer, con gli ultimi aggiornamenti alla piùrecente versione di Windows, la XP, i virus, i DVD.

Page 37: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

ECDL Modulo 3: Elaborazione testidi RubiniPagine: 144Euro: 9,8

Dal syllabus originale per la patente europea delcomputer, il modulo 3: Elaborazione testi.

Thinking in Javadi Bruce EckelPagine: 768Euro: 45

Thinking in Java è considerato uno dei testi piùautorevoli e al tempo stesso più originali estimolanti sul linguaggio di programmazione Java.

Page 38: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

ECDL Modulo 5: Basi di datidi RubiniPagine: 144Euro: 9,8

Dal syllabus originale per la patente europea delcomputer, il modulo 5: Basi di dati.

ECDL Modulo 6: Strumenti dipresentazionedi RubiniPagine: 144Euro: 9,8

Dal syllabus originale per la patente europea delcomputer, il modulo 6: Strumenti di presentazione.

Page 39: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

AutoCAD 2002 Guida Completadi Ralph GrabowskiPagine: 840Euro: 44

La terza edizione per il mercato italiano di uno deipiù autorevoli testi su AutoCAD, curato da RalphGrabowski, uno degli autori più noti ed esperti delsettore.

Visual C++ .NET Guida Completadi Davis ChapmanPagine: 704Euro: 44,9

Progettare finestre d’applicazione, utilizzare icontrolli, visualizzare elementi grafici, creareapplicazioni SDI e MDI, lavorare con i database ecostruire applicazioni multitasking con Visual C++.NET.

Page 40: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

C# Guida Completadi Bradley L. JonesPagine: 672Euro: 35,9

Il modo migliore per acquisire le tecniche avanzatedella programmazione con C# come lo sviluppo diapplicazioni in ambiente Windows e la creazione diWeb form e Web service.

Internet Explorer 6 Flashdi R. ViscardiPagine: 240Euro: 7,9

Internet Explorer 6 in versione tascabile. Nelconsueto formato agile e veloce della collana Flash,tutte le informazioni che servono per scoprire ilnuovo browser targato Microsoft, incorporato nelsistema operativo Windows XP

Page 41: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer

Access 2002 Guida Completadi Paul Cassel, Craig Eddy, Jon PricePagine: 608Euro: 39,9

Strutturare un database, creare tabelle, report,maschere e query, interfacciarsi con il Webattraverso ASP, conoscere il linguaggio SQL,verificare la sicurezza dei dati.

Audio e multimediadi Lombardo, VallePagine: 408Euro: 26

Il mondo dell’audio nel contesto più ampio dellacomunicazione multimediale, dalla rielaborazionedel suono al protocollo MIDI. Un testo tecnico perchi studia o lavora nel campo multimediale.

Page 42: Introduzione al quantum computing - Apogeo Editore · principi quantistici diversi da quelli a cui siamo ... I moderni calcolatori elettronici non sono n ... sviluppo dei computer