ALGORITMO DI GROVER

Dobbiamo risolvere il seguente problema: cercare in un database di N nomi in ordine sparso il numero di un amico. Classicamente necessitiamo di una media di N/2 passi per ottenere il risultato, quindi un numero di passi della stessa cardinalità N, O(N).

Grover, dei Bell Laboratories, nel 1996 riuscì a trovare la soluzione in O(√N) passi tramite computazione quantistica.

Dato un sistema con N = 2^L stati, ciascuno sia etichettabile con stringhe ad L bit S₁, S₂, …Lo stato che ci interessa è S_m.

L’algoritmo è il seguente:

a) Partiamo con un registro ad L qubit nello stato | 0 > = | 00...0 >.

b) Applichiamo la trasformata di Hadamard per generare una sovrapposizione di tutti i possibili stati:

c) DO i = 1, √N.

d) Applichiamo l’operatore U_m definito da:

U_m | i > = - | i > per  i = m,

U_m | i > = | i > altrimenti.

e) Applichiamo l’operatore "diffusione" di Grover, che corrisponde ad una riflessione di tutte le ampiezze intorno alla loro media. Poiché il segno dell’ampiezza  è stato invertito, l’operazione amplifica quest’ampiezza rispetto alle altre:

U_DG = U_HU₀U_H

f) ENDDO

g) A questo punto la misura fornisce con alta probabilità lo stato S_m.

Inizio della simulazione

Settaggio

Selezione stato qubit

Avanzamento della simulazione (spin lungo l'asse z)

Ricerca dello stato prescelto

Risultato finale