INTRODUZIONE AL
QUANTUM COMPUTING
L. Martina, G. Soliani
Dipartimento di Fisica dell'Universita' e
Sezione INFN, Lecce
Sommario
• Quadro d’insieme
• La Storia
• Stati Quantici e qubit
• Quantum Entanglement
• Capacità del Quantum Computer
• Disuguaglianza di Bell
• Sistema binario
• Porte Logiche Quantistiche a
• 1-qubit
• Trappole Ioniche
• Porte Logiche Quantistiche a 2-qubit
• Teorema di No - Cloning
• Teletrasporto Quantistico
• Control-Control-Not
• Universalità delle porte 1-qubit e CNOT
• La Trasformata di Fourier Quantistica
• Il problema della Stima della Fase
• Algoritmo di fattorizzazione di un Intero
• Il problema della decoerenza
Bibliografia
M.A. Nielsen, I. L. Chuang: “Quantum Computation and Quantum Information”,
Cambridge Univ. Press (Cambridge,2000) G. P. Berman, G. D. Doolen, R. Manieri, V. I.
Tsifrinovich:” Introduction to quantum Computers”, World Scientific (Singapore, 1998)
D. Bouwmeester, A. Ekert, A. Zeilinger:” The Physics of Quantum Information”, Springer Verlag (Berlin, 2000)
Quadro
d’insieme
Concetti base
• Cos’è il
• Quantum Computing ?
• Quantum Information ?
• Come si sono sviluppati ?
• Quale il loro uso ?
• Storia del QC e QI
• Qubits
• QuComputer qugate qucircuiti qualgoritmi
• Procedure sperimentali dell’informazione quantistica
• Informatica Quantistica e Comunicazione Quantistica
La Storia
• 1926 –’27 La Meccanica Quantistica (Schrödinger, Heisenberg, Born, Dirac,...)
• > 1970 controllo di sistemi atomici singoli, (trappole ioniche, microscopio a effetto tunnel, ....) Quantum criptography
• 1936 La Macchina di Turing Universale, Tesi di Church – Turing
• J. von Neumann
• 1947 Transistor (Bardeen, Brattain, Shockley)
• 1965 Legge di Moore
La Macchina di Turing
Tre parti:
a) nastro
b) Testina di lettura/scrittura c) Unità di controllo
Il nastro è infinito e suddiviso in celle, nelle quali può essere scritto un simbolo di un alfabeto predefinito (tipicamente {0,1, _ }
La testina legge i simboli scritti in una cella, può scrivervi un nuovo simbolo, si muove in entrambi i versi di una singola cella
L’ unità di controllo è definita ad ogni passo da una quintupla di elementi:
s: lo stato della macchina al passo presente;
i: il simbolo letto al passo presente;
S(s, i): lo stato della macchina al passo successivo, funzione dei primi due parametri.
I(s, i): il simbolo scritto sul nastro al passo successivo, funzione dei primi due parametri.
D(s, i): il verso (movimento) della testina (destra/sinistra), funzione dei primi due parametri
Tesi di Church – Turing
– Esiste una Macchina di Turing Universale che simula ogni altra Macchina di Turing
– Se un calcolo può essere eseguito
algoritmicamente su un qualunque apparato fisico (PC,...), allora esiste un equivalente algoritmo per una Macchina di Turing
(Universale), che esegue esattamente lo
stesso calcolo.
Oltre la Legge di Moore
Metodi litografici in UV (193 nm)
Computers “Classici”
Per immagazzinare dati
•La microelettronica si basa sugli stati di corrente elettrica nei dispositivi ma si sono usati
•Fori nei nastri di carta, Momenti di dipolo magnetici, Momenti di dipolo elettrico o si possono usare
•Campi fotonici
• Stati quantici :
Uso della MQ invece della MC Le previsioni di Intel per la tecnologia
CMOS si estendono fino al 2016
Algoritmo efficiente T ≈ N
pTempo di calcolo
“lunghezza”
dei dati
Complessità Computazionale
Esempio: Fattorizzazione di un intero n -> L = log2 n bits
# di passi per trovare un fattore in :
[ ]
1, n( )
L n eL2S ≈ =
Ogni algoritmo può essere simulato efficientemente
usando una macchina di Turing
T. di C – T forte
?
?
P NP
PSPACE BQP
Classi di Complessità
P - efficientemente risolvibili
NP - soluzioni efficientemente verificabili PSPACE – problemi localizzati spazialmente BQP – efficientemente risolvibili con il QC
• Computer analogici – Effetto del Rumore
– Un computer analogico realistico (con rumore) non può risolvere un problema più efficientemente di una Macchina di Turing
• (1976) Algoritmi probabilistici , Test di primalità Solovay- Strassen
• (1989) D. Deutsch, Proc. R. Soc. London, Ser A 425,73 Universal Quantum Computer
E’ lo strumento computazionale che può simulare un arbitrario sistema fisico
• Un computer “classico” può simulare un computer quantistico, MA può farlo in maniera EFFICIENTE?
• Correlazioni di Bell-EPR.
• E’ possibile per un QC risolvere efficientemente un problema computazionale, che non può esserlo per una macchina di Turing?
T. di C – T forte modificata
Oltre l’efficienza della Macchina di Turing
• 1994 P. Shor, Proc. 35th Symp. IEEE, :
efficiente risolubilità del problema della
“fattorizzazione di un intero” e del “logaritmo discreto
• 1995 L. Grover : algotitmo di ricerca in un database non strutturato
• 1995 Barenco et al., Phys. Rev. A 52, 3457
CONTROL – NOT gate
• J.I. Cirac, P. Zoller Phys. Rev. Lett. 74, 4091
manipolazione laser di trappole ioniche
• C. Monroe et al. Phys. Rev. Lett. 75, 4714 2 qubit quantum logic gate
• 1996 N. Gershenfeld et al., D.G. Cory et al. Phys. Comp. 96, QC a temperatura ambiente
Decoerenza quantistica
N 2
TQC ≈ TCl ≈ exp
