Algoritmi Quantistici – Proviamo il computer quantistico di IBM Parte 6
IBM ha lanciato il suo programma IBM Quantum Experience!
Noi di Close-up Engineering ci siamo subito iscritti e IBM ci ha gentilmente accettati!
In questo articolo-tutorial composto da 6 parti, vedremo:
[button color=”” size=”large” type=”” target=”_blank” link=”http://systems.closeupengineering.it/proviamo-computer-quantistico-ibm-parte-1-by-close-engineering/8963/”]Parte 1: Come funziona un computer quantistico[/button]
[button color=”” size=”large” type=”” target=”_blank” link=”http://systems.closeupengineering.it/come-si-elabora-qubit-proviamo-computer-quantistico-ibm-parte-2-2/8984/”]Parte 2: L’algebra del qubit e le operazioni base[/button]
[button color=”” size=”large” type=”” target=”_blank” link=”http://systems.closeupengineering.it/elaborazione-nel-computer-quantistico-ibm-proviamo-computer-quantistico-ibm-parte-3/9016/”]Parte 3: Proviamo il computer quantistico di IBM[/button]
[button color=”” size=”large” type=”” target=”_blank” link=”http://systems.closeupengineering.it/sistemi-qubit-t-gates-bell-states-ghz-states-proviamo-computer-quantistico-ibm-parte-4/9014/”]Parte 4: Sistemi di qubit, gates ed entangled state[/button]
[button color=”” size=”large” type=”” target=”_blank” link=”http://systems.closeupengineering.it/potenziamo-computer-quantistico-ideale-reale-proviamo-computer-quantistico-ibm-parte-5/9110/”]Parte 5: Potenziamo il computer quantistico di IBM! [/button]
[button color=”” size=”large” type=”” target=”_blank” link=”http://systems.closeupengineering.it/algoritmi-quantistici-proviamo-computer-quantistico-ibm-parte-6/9123/”]Parte 6: Algoritmi Quantistici [/button]
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.
È 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 \(f\) 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 \(2^{n-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 \(N\) elementi e in questa lista, avere un elemento che vogliamo trovare, che chiameremo \(w\) di “winner”.
Con un computer classico, bisognerebbe scorrere la lista dal primo elemento all’elemento w: questo in media richiede \(N/2\) operazioni, e nel peggior caso \(N\). Grazie all’algoritmo di Grover, questo procedimento si può eseguire in \(\sqrt{N}\) operazioni!
Inanzi tutto, dobbiamo codificare la lista in qubit, scegliamo una codifica per ogni elemento \(x, w \in \{0,1\}^n\) con \( N = 2^n\).
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 \(U_f\):
$$U_f | x \rangle = (-1)^{f(x)} | x \rangle$$
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/2^n\).
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/2^n\):
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 \(U_s\) 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? \(\sqrt{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 \(U_s\) per portare la probabilità del sistema di collassare nello stato corretto al 100%.
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!