Dalla quantum experience alla quantum information, informatica quantistica

Dalla quantum experience alla quantum information, informatica quantistica
Dalla quantum experience alla quantum information, informatica quantistica
Condividi l'Articolo
Facebook
Facebook
Google+
Google+
http://scienzamagia.eu/dalla-quantum-experience-alla-quantum-information-informatica-quantistica/

Dai Bit ai Qubit: la rivoluzione dell’informatica quantistica. La rivoluzione scientifica del ventunesimo secolo? A determinarla sarà l’informatica quantistica (Quantum Information). Ad affermarlo è una voce assolutamente autorevole, quella del Premio Nobel per la Fisica William Phillips. Tra le scoperte e le innovazioni lasciate in eredità dal secolo precedente due sono particolarmente importanti: la scoperta del comportamento quantistico del mondo microscopico e l’avvento della scienza dell’informazione. Entrambe hanno avuto un enorme impatto nella nostra vita quotidiana, grazie alle loro implicazioni tecnologiche, e hanno anche inciso profondamente nella nostra visione del mondo. Ora, all’inizio di questo nuovo secolo, assistiamo a una rapida convergenza tra la meccanica quantistica e la scienza dell’informazione; da questo connubio, noto con il nome di quantum information, è attesa una nuova rivoluzione.

Della quantistica si è già parlato tantissimo, molte volte male, poche volte bene:
molto spesso la quantistica è stata sfruttata da mistici dei giorni nostri che, gonfiandone i pochi concetti che sono riusciti a comprendere e decontestualizzandoli, hanno creato vere e proprie micro-religioni con cui guadagnare sfruttando l’ignoranza e la superstizione. La fisica quantistica non ha niente a che vedere con tutto ciò, anzi, proprio il nome “fisica” e “quantistica” dovrebbero farci comprendere che l’ignoranza e la superstizione vadano messe proprio da parte, e che sia il caso di prendere in mano i libri con cui studiarla. La difficoltà nel comprendere un computer quantistico e in generale la fisica quantistica sembra risiedere nelle poche e semplici, ma contro-intuitive, regole. La matematica implicata in un computer quantistico in realtà non è che di poco più complessa di quella studiata alle superiori o al primo anno di università. (in un computer quantistico, non nella fisica quantistica, dove risulta più complessa)

Queste contro-intuitive regole sono principalmente due:
1) Un sistema fisico in uno stato perfettamente definito può comunque comportarsi in modo casuale.
2) Due sistemi fisici che sono abbastanza lontani da non potersi influenzare possono comunque comportarsi casualmente se presi individualmente, ma essere correlati se considerati insieme.

Una volta assimilati questi concetti, il tutto diventa realmente semplice. Come spiega IBM la fisica quantistica alla base di un computer quantistico è pedagogicamente simile alla teoria della relatività: parte da semplici idee contro-intuitive che degenerano in una teoria che può sembrare complessa proprio perchè contro-intuitiva.

I qubit

Le proprietà di un qubit discendono dai postulati della meccanica quantistica.

Di seguito ne elenchiamo le principali. Per una trattazione più dettagliata si faccia riferimento alla bibliografia.

In accordo col primo postulato, un qubit è rappresentato da un vettore unitario di uno spazio di Hilbert.

Così come il bit classico ammette due stati, cioè lo stato   e lo stato  , altrettanto accade al qubit. Per analogia con il caso classico chiameremo questi due stati  e . Ma grazie al principio di sovrapposizione, che emerge dal primo postulato, è anche possibile combinare linearmente i due stati  e  per ottenere lo stato di sovrapposizione:

in cui a e b sono due numeri complessi tali per cui .

Detto in altri termini, lo stato di un qubit è un vettore unitario dello spazio degli stati hilbertiano di dimensione 2 in cui gli stati speciali  e   formano una base ortonormale detta base computazionale. Nel caso classico è sempre possibile esaminare un bit per determinare se esso sia nello stato o nello stato. Di converso, nel caso quantistico, non è possibile esaminare un qubit per determinarne il suo stato, cioè per determinare i due coefficienti   e .

Il terzo postulato ci dice che è possibile acquisire una quantità più limitata di informazioni relative allo stato quantistico. Quando misuriamo lo stato di un qubit possiamo ottenere il risultato  con una probabilità  o il risultato  con probabilità .

Proviamo ad applicare le regole dettate dal terzo postulato in questo semplice ma significativo caso. Abbiamo già visto che la misurazione può avere soltanto due esiti definiti dai due operatori di misurazione  .

Notiamo che ogni operatore di misurazione è hermitiano  e che  e ciò ci garantisce che la condizione di completezza è soddisfatta.

Supponiamo che lo stato oggetto di misurazione sia. Allora la probabilità di ottenere come risultato della misurazione è data da

.

Analogamente la probabilità di ottenere  è data da

.

Lo stato del sistema dopo la misurazione sarà, nel primo caso

mentre nel secondo avremo

dove i coefficienti  e  sono fattori di fase che non incidono sullo stato del sistema e che possono essere, quindi, trascurati consentendoci di arrivare ai risultati attesi.

Per vedere meglio quanto affermato facciamo uso di vettori e matrici per rappresentare in maniera tradizionale gli stati e gli operatori in gioco. Se definiamo

 e , allora .

In questo modo i due operatori di proiezione diventano:

e

.

La probabilità di ottenere  sarà dunque

che è quanto ci aspettavamo. Infine, lo stato del qubit dopo la misurazione sarà proprio

 

Come si elabora un Qubit? I pauli operators e operazioni base

Per ora abbiamo spiegato quindi qual è il qubit base e alla domanda “come si elabora un qubit?” Rispondiamo: Con dei gates. Vediamo ora i Pauli Operators, cioè i gates basilari per elaborare un qubit.

Il gate X:

Pauli Operators: X Gate

Possiamo notare subito come X sia un classico “NOT” in algebra booleana, e trasformerà un  |0|0⟩ in |1|1⟩ e viceversa.

Abbiamo poi un phase-flips Z, cioè una matrice che cambia la fase al qubit che moltiplica, ruotandolo però lungo l’asse Z. Per vederne gli effetti, è quindi necessario che il qubit non sia sullo stesso asse. Per fare ciò, viene prima applicata la matrice H, che vedremo a breve.

Pauli Operators: Z Gate

Per finire, abbiamo la combinazione di X e Z in Y, che negherà il nostro qubit e lo cambierà di fase.

Possiamo notare subito come il secondo qubit base |1|1⟩ si ottenga dal primo:

|1=X|0|1⟩=X|0⟩

Rappresentiamo un qubit

Risulta impossibile capire realmente il qubit senza rappresentarlo.
Per farlo ricorriamo alla sfera di Bloch. Per ora vi risulterà arcano il suo funzionamento, ma ci aiuterà a distinguere i vari qubit che creeremo. Successivamente spiegheremo come funziona la rappresentazione. Per ora, basti questo:

Bloch Sphere

Possiamo quindi ridefinire il nostro qubit come:

|ψ=cos(θ/2)|0+eiϕsin(θ/2)|1|ψ⟩=cos⁡(θ/2)|0⟩+eiϕsin⁡(θ/2)|1⟩

Dove θθ e ϕϕ sono segnati in figura.
Chiariremo meglio successivamente.

Ecco i qubit che conosciamo:

Qubits

qubit 0: |0|0⟩
qubit 1: |1=X|0|1⟩=X|0⟩
qubit 2: Z|0Z|0⟩
qubit 3: Y|0Y|0⟩

Come possiamo vedere i qubit |0|0⟩ e |1|1⟩ stanno solo nell’asse Z, rispettivamente a +1 e -1.

Quelle che per ora ci sembrano operazioni inutili (Z e Y) acquisiranno significato fra poco, introducendo i Clifford Gates.

Clifford gates

I Clifford Gates sono gli operatori secondari che servono a passare in uno stato di sovrapposizione.

Il primo gate, noto come Hadamard Gate serve a creare una nuova base detta diagonale, portando il nostro qubit |0|0⟩ in uno stato di sovrapposizione, con le due probabilità (di essere |0|0⟩ o |1|1⟩ ) a 1/21/2 se misurato con la base canonica.
Questo qubit rappresenta quello che nella Parte 1 abbiamo chiamato  |+|+⟩.

qubit H

Se lo andiamo a rappresentare, capiamo cosa succede:
Il qubit non sta più sull’asse Z. Abbiamo quindi un qubit che è sia |0|0⟩ che |1|1⟩ per metà del tempo.

Questo qubit è il risultato di questa operazione:
H|0H|0⟩

 

 

E cosa succede se neghiamo con Z il nostro nuovo qubit?
Come risultato, otteniamo ||−⟩ :

qubit XH
Abbiamo anche qui un qubit che è sia  |0|0⟩ che |1|1⟩per metà del tempo, ma differisce da quello precedente.

Questo qubit è dato da questa operazione:
ZH|0ZH|0⟩

E possiamo facilmente asserire che i due qubit appena creati siano ortogonali tra loro.

 

Abbiamo quindi una nuova base detta diagonale. Se misuriamo i vettori della base diagonale sulla base canonica otteniamo una misurazione al 50% |0|0⟩ e al 50% |1|1⟩, e viceversa se misuriamo i vettori della base canonica rispetto alla base diagonale.

Da notare, che lo stesso risultato si può ottenere con la combinazione XH, in quanto ruotando prima sull’asse X e poi su quello diagonale, si ottiene lo stesso risultato che ruotando sull’asse diagonale e poi sull’asse Z.

Hadamard Gate

Misurare in una base non canonica:

Nel modello di computer quantistico che ci fornisce IBM, non possiamo scegliere in che base misurare un qubit, ma basta reinvertire gli assi applicando ancora la matrice H per ottenere lo stesso risultato che misurare i qubit nella nuova base diagonale:
qubit HH

 

 

Questo qubit è dato da questa operazione:
HH|0HH|0⟩

 

 

 

qubit HXH

 

Questo qubit è dato da questa operazione:
HZH|0HZH|0⟩

Arriviamo ad una terza base, la base circolare:

|=12–√(|0+i|1)|↻⟩=12(|0⟩+i|1⟩)
|=12–√(|0i|1)|↺⟩=12(|0⟩−i|1⟩)

Questa base si ricava applicando la matrice S dopo aver applicato la matrice H:

|=SH|1|↻⟩=SH|1⟩
|=SZH|1|↺⟩=SZH|1⟩

I due qubit saranno rappresentati sull’asse Y, e questo vuol dire che, praticamente, la matrice S ruota di soli 90° intorno sull’asse Z. (a differenza di Z che crea una rotazione di 180°).
Ancora, se si misura un qubit di questo tipo su una base canonica, si ottiene un risultato incerto. Se si misura nella base circolare, si ottiene un risultato determinato. L’ultima matrice STST serve ad eseguire l’operazione inversa di S e quindi a passare dalla base circolare a quella canonica o diagonale.Vi è infine il Gate T, che non appartiene però ai Clifford Gate. Il gate T sembra ruotare di 45° sull’asse Z, ma in realtà compie un’operazione più complessa,

Ecco un riassunto di tutte le operazioni importanti con le matrici H, S, T e Z, partendo dallo stato |+|+⟩:

Sveliamo l’arcano sulla sfera di Bloch

E’ il momento di capire come si rappresentano i qubit in sovrapposizione nella sfera di Bloch .
Possiamo ricostruire un qualsiasi qubit (anche in sovrapposizione) calcolando il vettore di Bloch relativo, un vettore a tre dimensioni rappresentato in questo modo:

X=tr(|ψψ|X)⟨X⟩=tr(|ψ⟩⟨ψ|X)
Y=tr(|ψψ|Y)⟨Y⟩=tr(|ψ⟩⟨ψ|Y)
Z=tr(|ψψ|Z)⟨Z⟩=tr(|ψ⟩⟨ψ|Z)
Lo stato è dato da:
|ψψ|=(I+XX+YY+ZZ)/2|ψ⟩⟨ψ|=(I+⟨X⟩X+⟨Y⟩Y+⟨Z⟩Z)/2

E infine, ogni valore Q⟨Q⟩ è calcolato misurando il qubit nella base standard e calcolandone le due probabilità:

Q=P(0)P(1)⟨Q⟩=P(0)–P(1)

In questo modo, possiamo rappresentare un qualsiasi qubit a prescindere dalla base, in un unico grafico.
Questo è essenziale perchè i qubit ||↻⟩||↺⟩|+|+⟩ e ||−⟩ , quando misurati nella base canonica, si comporteranno esattamente allo stesso modo, cioè risultando per metà |0|0⟩ e per metà |1|1⟩. Ma quei qubit SONO DIVERSI, e per capirne la differenza, basta rappresentarli nella sfera di Bloch.

PROGRAMMIAMO IL COMPUTER QUANTISTICO!

Ora che sappiamo come si elabora un qubit, proviamo il computer quantistico di IBM ed elaboriamo qualche qubit con i nostri gates.

IBM ha iniziato ad accettare sempre più velocemente le richieste di iscrizione! Ecco il form per provare ad iscriversi al programma Quantum Experience e provare finalmente il Computer Quantistico di IBM: CLICCA QUI PER ISCRIVERTI 

IBM offre un’interfaccia grafica per programmare l’elaborazione di un qubit (o più qubit, come vedremo nella Parte 4).
Quest’interfaccia è molto semplice ed efficace:
Abbiamo alcuni qubit |0|0⟩ al quale possiamo applicare nel tempo i vari gates.  Questo ci consente di elaborarli.
Inoltre, possiamo misurare in un determinato istante il valore del qubit.
La misurazione avviene nella base canonica, e come abbiamo visto sempre nella Parte 2, misurare un qubit in sovrapposizione ci darà uno stato indeterminato. La misurazione infatti i dirà la probabilità con cui il qubit è stato misurato in ogni stato ( |0|0⟩ o |1|1⟩ ).
Infine, possiamo rappresentare in un dato istante il qubit nella sfera di Bloch. 
Semplice no?

Misuriamo il qubit  |0|0⟩:

0

 

X, H, SH – MISURIAMO LE OPERAZIONI BASE!

Facciamo qualche prova con i gate

Applichiamo il gate X al qubit  |0|0⟩ e vediamo cosa succede:

X0

I gate  Z e Y per ora non servono, in quanto Z non produce nessun cambiamento se misuriamo in base canonica, e Y produce lo stesso cambiamento di X.

Passiamo ad H ottenendo  |+|+⟩ :

H0

Possiamo notare che la percentuale è esattamente  1/21/2 per  |0|0⟩ e 1/21/2 per  |1|1⟩. Questo indica uno stato di sovrapposizione.

Proviamo applicando prima H e poi S  ottenendo ||↻⟩:

SH0

 

Come possiamo notare, si ottiene lo stesso risultato che con solo H… Ma i due qubit sono diversi, come sappiamo! Eccoli rappresentati nella sfera di Bloch:

H0 e SH0 - Bloch

 

PORTE LOGICHE: CNOT

Per rendere più interessante questa prima prova con il Computer Quantistico di IBM, introduciamo il Gate CNOT:
Prende un input di controllo in ingresso, e applica una NOT su un altro qubit SE l’input di controllo è un qubit |1|1⟩.

Programmiamo il computer quantistico e misuriamo.

In questo caso, il control è |0|0⟩ (qubit 1) e l’input rimane invariato a |0|0⟩ (qubit 2)

CNOT00

Proviamo invece con |0|0⟩ |1|1⟩

CNOT01x

Proviamo con |1|1⟩ |0|0⟩:

CNOT10x

Proviamo con |1|1⟩ |1|1⟩:

CNOT11x

Se invece, proviamo dopo aver applicato il gate H? 

CNOTH0

Ecco che l’indeterminatezza del qubit |+|+⟩: viene trasferita al qubit |0|0⟩, ma ecco cosa succede se proviamo a disegnarlo nella sfera di Bloch: 

CNOTH0 - Bloch

Questo vuol dire che l’input non si è tramutato in un |+|+⟩, ma è rimasto nella base canonica, solo con indeterminazione a 50 e 50 tra  |0|0⟩ e  |1|1⟩.
Abbiamo creato un nuovo qubit?!
Nella prossima parte risponderemo a questa domanda e vedremo come elaborare SISTEMI DI QUBIT!

DAL COMPUTER QUANTISTICO REALE AD UNO IDEALE

A questo punto della serie di articoli dovreste aver concepito quanto possa essere potente un computer quantistico ideale per risolvere molti dei problemi che invece non riusciamo a risolvere con un computer classico.
IBM mette a disposizione solo 5 qubit, ma già questi 5 qubit offrono la possibilità di provare algoritmi noti in ambito quantistico. Certo, non potremo programmare un decypher per rompere l’attuale sicurezza data dall’RSA, ma potremo comunque verificare la potenza del computer quantistico.

Il problema principale però è che il computer quantistico REALE di IBM ha alcuni limiti dovuti ai costi di produzione:
non tutti i qubit sono collegati agli altri, e la CNOT è applicabile solo al qubit centrale.

Per questo dobbiamo potenziare il computer quantistico reale di IBM, utilizzando alcuni costrutti base per ovviare a questi limiti fisici. Applicando dei costrutti nell’algoritmo potremo infatti simulare qualsiasi collegamento possibile in un computer quantistico ideale. Proprio per questo IBM non ha investito più del necessario nell’hardware, in quanto certe “funzioni hardware” si possono facilmente simulare, in modo da abbassare notevolmente i costi e renderne possibile la realizzazione.

CNOT INVERSA

La CNOT è applicabile solo al qubit centrale, ma possiamo facilmente invertirla in modo che possa essere applicata tra il qubit centrale e un altro qubit, ma al contrario:

Inverse CNOT

Questo non ci consente ancora di applicare la CNOT in tutte le possibili modalità che avremmo senza limitazioni. Infatti, in questo modo non è possibile applicare la CNOT a due qubit diversi da quello centrale.

INVERTIRE DUE QUBIT

Non possiamo applicare la CNOT a due qubit non centrali? Non importa. Basta che i valori siano giusti, non che effettivamente la si stia applicando al qubit corretto. Infatti, per risolvere il problema, basterà scambiare il valore del qubit che vogliamo utilizzare nella CNOT con il valore del qubit centrale, e poi applicare la CNOT al qubit centrale, ottenuto il risultato, scambiare ancora i due valori.
Ecco lo schema per scambiare i due qubit:

Swap Qubits

Con questi due costrutti possiamo quindi applicare la CNOT in qualsiasi modalità possibile in un computer quantistico ideale, ovviando alle limitazioni fisiche del computer quantistico reale di IBM.

CONTROLLED PAULI-OPERATORS

Nelle Parti precedenti, in realtà vi ho mentito (e IBM ha mentito a me): non esiste nessun CNOT Gate. E in effetti, se ci pensate, non esiste una matrice 4×4 che svolga la funzione di CNOT. In realtà, non è altro che un controlled-X gate, un X gate che agisce controllato da un altro qubit.

I controlled Pauli-Operators non sono semplici da creare e comprendere, ma ci proveremo.

Ricordiamo che:

HXH=ZHXH=Z
SXST=YSXST=Y
HH=IHH=I
SST=ISST=I

Ora, concentriamoci su questa forma:

Dove P è un Controlled-Pauli-Operator e C è un Clifford Gate.

Risulta che (non lo dimostreremo) un qualsiasi controlled-V gate può essere costruito trovando tre costrutti A, B, C tali che:

ABC=IABC=I
eiαAZBZC=VeiαAZBZC=V

E’ complesso trovare queste tre matrici, ma vediamone il risultato per creare un controlled-H:

A=ei3π/8XSHTHSTA=ei3π/8XSHTHST
B=eiπ/8SHTTHSTHSHB=e−iπ/8SHTTHSTHSH
C=eiπ/4HSHC=e−iπ/4HSH
V=HV=H

Che combinate in questo schema forniscono una controlled-H:

Controlled-H

TOFFOLI GATE

Il Toffoli Gate è rappresentato da questa equazione:

TOF|a,b,c=|a,b,(a AND b) XOR cTOF|a,b,c⟩=|a,b,(a AND b) XOR c⟩

Come si può vedere la funzione svolta è elementare (è una semplice CNOT controllata da due input in AND), ma non è ovvio come si possa creare.

Ecco la soluzione:

Toffoli Gate

Questo circuito è quasi pronto per essere implementato, basta convertire lo scambio dei qubit nel costrutto che abbiamo visto precedentemente.

Eccone l’implementazione, tenendo conto che l’ultimo scambio di qubit non è implementato, quindi alla fine l’output sarà dato dal qubit1.

Toffoli GatePossiamo utilizzare il Toffoli gate per generare un nuovo sistema di 3 qubit in Entangled state:

SWAP1,2TOF|++00,1,2=12(|000+|001+|100+|111)SWAP1,2TOF|++0⟩0,1,2=12(|000⟩+|001⟩+|100⟩+|111⟩)

Per farlo basterà utilizzare l’algoritmo precedente, ponendo come input |++0|++0⟩ e applicando un gate H all’output (qubit1)prima di misurare i 3 qubit.

Ecco la misurazione del sistema di 3 qubit, come ci aspettiamo avremo una probabilità distribuita nei quattro stati |000,|001,|100,|111

ALGORITMI QUANTISTICI

 Il Computer Quantistico non è vantaggioso in tutti i problemi informatici, ma solo in alcuni.
Ha il privilegio però di poter essere usato anche come un computer classico, quindi di poter risolvere alla stessa velocità anche i problemi classici.
Un algoritmo quantistico è un algoritmo che sfrutta il potenziale della superposition o dell’entangled state, quindi funzioni che con un computer classico non si potrebbero svolgere.
E’ stato dimostrato che esistono algoritmi quantistici che possono aumentare la velocità di soluzione a problemi classici come ad esempio la ricerca in una lista, o la decrittazione di un messaggio crittografato in DES: vedremo in questo articolo l’algoritmo di Grover, che consente questa velocizzazione.
Un altro algoritmo molto importante e illuminante, è l’algoritmo di Deutsch-Jozsa:
Immaginiamo di avere una funzione ff che prende in input una stringa di n-bit e restituisce in output 1-bit. Ci viene detto che questa funzione può essere sia una funzione che restituisce o sempre 1 o sempre 0 per ogni input, oppure una funzione che restituisce per metà input 0 e per metà input 1.
Ponendosi l’obiettivo di capire cosa fa esattamente la funzione, con un computer classico, nel peggiore dei casi dovremo provare la funzione 2n1+12n−1+1 volte prima di avere una risposta.
Utilizzando l’algoritmo Deutsch-Jozsa basterà una sola computazione!

ALGORITMO DI GROVER

Uno dei più grandi vantaggi del computer quantistico, è la sua velocità nelle ricerche nei database. L’algoritmo di Grover può essere utilizzato per elevare al quadrato la velocità di ricerca in un database.
In realtà, può essere anche utilizzato per eseguire molte altre operazioni alla stessa velocità, ma appunto l’utilizzo più comune risulta essere quello della ricerca in un database.

Supponiamo di avere una lunga lista di NN elementi e in questa lista, avere un elemento che vogliamo trovare, che chiameremo ww di “winner”.

Con un computer classico, bisognerebbe scorrere la lista dal primo elemento all’elemento w: questo in media richiede N/2N/2 operazioni, e nel peggior caso NN.
Grazie all’algoritmo di Grover, questo procedimento si può eseguire in N−−√N operazioni!

Inanzi tutto, dobbiamo codificare la lista in qubit, scegliamo una codifica per ogni elemento x,w{0,1}nx,w∈{0,1}n con N=2nN=2n.

Definita una funzione f() tale che f(e) = 1 se x è l’elemento cercato w, e f(e) = 0 se non lo è.

Definiamo poi una matrice unitaria chiamata Oracle come funzione UfUf:

Uf|x=(1)f(x)|xUf|x⟩=(−1)f(x)|x⟩

Questo significa appunto che la matrice non farà nulla se il qubit è diverso da w, mentre se è w lo trasformerà in -w.
Questa matrice può essere ricavata per ogni elemento senza saperne la posizione.

Ora, ricordiamoci che se abbiamo n qubits in superposition, la probabilità di ottenere il qubit corretto che cerchiamo misurando il sistema casualmente, è di 1/2n1/2n.

Qui entra in gioco l’Amplitude Amplification, che servirà ad aumentare la probabilità che il qubit misurato sia proprio quello cercato.

Partiamo da uno stato in cui tutti i qubit hanno la stessa Amplitude di 1/2n1/2n:

Applichiamo quindi la nostra matrice Oracle ottenendo:


Come possiamo notare, abbiamo abbassato l’amplitude media, in quanto ve n’è una negativa. Infine, applichiamo un’altra trasformazione nota UsUs che porta tutti i positivi alla amplitude media, mentre il negativo alla restante amplitude. Applicata nella situazione precedente, ci porta in questo stato:
Come possiamo vedere, la probabilità che il nostro sistema di qubit collassi proprio nel sistema che rappresenta il qubit cercato, è aumentata in quanto tutte le altre sono diminuite, e a lui è spettata la restante parte.

Questo processo, è un’iterazione di Grover. Applicata più volte, porterà il sistema a collassare, se misurato, proprio nel sistema che rappresenta il qubit cercato.
Quante volte esattamente? N−−√N.

Mettiamo di avere N = 1024, e quindi avere un sistema di 10 qubit che può rappresentare quattro elementi.
Mettiamo di cercare l’elemento w e che sia il 512esimo:
Ricaviamo la sua matrice Oracle.
Applicando l’iterazione di Grover 32 volte, il sistema di qubit collasserà proprio nel sistema che rappresenta il 512esimo qubit!
Questo vuol dire che al posto di 512 operazioni come dovremmo fare in un computer classico, ne faremo solo 32!

Proviamo, no?
Proviamo con N=4, quindi 2 qubit, e una sola iterazione. Supponiamo che il qubit cercato sia l’ultimo della lista, quindi il quarto.

Primo step: Portiamo i 2 qubit in superposition con il gate H.
Secondo step: Applichiamo l’Oracle dell’elemento cercato.
Terzo step: Applichiamo la matrice UsUs per portare la probabilità del sistema di collassare nello stato corretto al 100%.

Grover's Algorithm

Ed ecco che il nostro sistema di qubit, anche se inizialmente non conteneva nessuna informazione riguardo alla posizione dell’elemento cercato, ora ci indica esattamente l’ultima posizione, con una sola iterazione!

Condividi l'Articolo
Facebook
Facebook
Google+
Google+
http://scienzamagia.eu/dalla-quantum-experience-alla-quantum-information-informatica-quantistica/
Inviami gli Articoli in Email:

Be the first to comment

Leave a Reply

L'indirizzo email non sarà pubblicato.


*