Vai al contenuto principale

Descrizione dell'algoritmo di Grover

In questa sezione descriveremo l'algoritmo di Grover. Inizieremo parlando dei gate di query di fase e di come costruirli, per poi passare alla descrizione dell'algoritmo di Grover vero e proprio. Infine, discuteremo brevemente come questo algoritmo si applichi naturalmente al problema della ricerca.

gate di query di fase​

L'algoritmo di Grover si avvale di operazioni note come gate di query di fase. A differenza di un gate di query ordinario Uf,U_f, definito per una data funzione ff nel modo consueto descritto in precedenza, un gate di query di fase per la funzione ff è definito come

Zf∣x⟩=(−1)f(x)∣x⟩Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle

per ogni stringa x∈Σn.x\in\Sigma^n.

L'operazione ZfZ_f può essere implementata usando un solo gate di query UfU_f, come suggerisce questo diagramma:

A quantum circuit implementing a Z_f gate using one query gate together with the phase kickback phenomenon

Questa implementazione sfrutta il fenomeno del phase kickback e richiede la disponibilità di un qubit di workspace aggiuntivo, inizializzato nello stato ∣−⟩.\vert -\rangle. Questo qubit rimane nello stato ∣−⟩\vert - \rangle al termine dell'implementazione e può essere riutilizzato (ad esempio per implementare successivi gate ZfZ_f) oppure semplicemente scartato.

Oltre all'operazione Zf,Z_f, faremo uso anche di un gate di query di fase per la funzione OR a nn bit, definita come segue per ogni stringa x∈Σn.x\in\Sigma^n.

OR(x)={0x=0n1x≠0n\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}

In modo esplicito, il gate di query di fase per la funzione OR a nn bit si comporta così:

ZOR∣x⟩={∣x⟩x=0n−∣x⟩x≠0n.Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}

Per essere chiari, questo è il comportamento di ZORZ_{\mathrm{OR}} sugli stati della base standard; il suo comportamento su stati arbitrari si ricava da questa espressione per linearità.

L'operazione ZORZ_{\mathrm{OR}} può essere implementata come circuito quantistico partendo da un circuito booleano per la funzione OR, costruendo poi un'operazione UORU_{\mathrm{OR}} (ossia un gate di query standard per la funzione OR a nn bit) seguendo la procedura descritta nella lezione Fondamenti di algoritmica quantistica, e infine ottenendo un'operazione ZORZ_{\mathrm{OR}} tramite il fenomeno del phase kickback come descritto sopra. Da notare che l'operazione ZORZ_{\mathrm{OR}} non dipende dalla funzione ff e può quindi essere implementata da un circuito quantistico privo di gate di query.

Descrizione dell'algoritmo​

Ora che disponiamo delle due operazioni ZfZ_f e ZOR,Z_{\mathrm{OR}}, possiamo descrivere l'algoritmo di Grover.

L'algoritmo fa riferimento a un numero t,t, che rappresenta il numero di iterazioni eseguite (e quindi il numero di query alla funzione ff richieste). Questo numero tt non è specificato dall'algoritmo di Grover così come lo stiamo descrivendo, e discuteremo più avanti nella lezione come sceglierlo.

Algoritmo di Grover
  1. Inizializza un registro di nn qubit Q\mathsf{Q} nello stato tutti-zero ∣0n⟩\vert 0^n \rangle e applica un'operazione di Hadamard a ciascun qubit di Q.\mathsf{Q}.
  2. Applica tt volte l'operazione unitaria G=H⊗nZORH⊗nZfG = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f al registro Q\mathsf{Q}
  3. Misura i qubit di Q\mathsf{Q} rispetto alle misurazioni della base standard e restituisce la stringa risultante.

L'operazione G=H⊗nZORH⊗nZfG = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f iterata nel passo 2 sarà chiamata operazione di Grover nel resto di questa lezione. Ecco una rappresentazione come circuito quantistico dell'operazione di Grover per n=7 ⁣:n=7\!:

A quantum circuit representation of the Grover operation

In questo diagramma, l'operazione ZfZ_f è raffigurata più grande di ZORZ_{\mathrm{OR}} come indicazione visiva informale per suggerire che è probabilmente l'operazione più costosa. In particolare, quando lavoriamo all'interno del modello delle query, ZfZ_f richiede una query mentre ZORZ_{\mathrm{OR}} non ne richiede nessuna. Se invece disponiamo di un circuito booleano per la funzione ff e lo convertiamo in un circuito quantistico per Zf,Z_f, ci si può ragionevolmente aspettare che il circuito quantistico risultante sia più grande e complesso di quello per ZOR.Z_{\mathrm{OR}}.

Ecco il diagramma di un circuito quantistico per l'intero algoritmo con n=7n=7 e t=3.t=3. Per valori più grandi di tt è sufficiente inserire ulteriori istanze dell'operazione di Grover immediatamente prima delle misurazioni.

A quantum circuit for Grover's algorithm when t=3

L'algoritmo di Grover può essere applicato al problema della Ricerca nel modo seguente:

  • Scegli il numero tt nel passo 2. (Questo aspetto viene discusso più avanti nella lezione.)
  • Esegui l'algoritmo di Grover sulla funzione f,f, usando la scelta effettuata per t,t, per ottenere una stringa x∈Σn.x\in\Sigma^n.
  • Interroga la funzione ff sulla stringa xx per verificare se è una soluzione valida:
    • Se f(x)=1,f(x) = 1, allora abbiamo trovato una soluzione, quindi possiamo fermarci e restituire x.x.
    • Altrimenti, se f(x)=0,f(x) = 0, possiamo eseguire nuovamente la procedura, eventualmente con una scelta diversa per t,t, oppure decidere di rinunciare e restituire "nessuna soluzione."

Una volta analizzato il funzionamento dell'algoritmo di Grover, vedremo che scegliendo t=O(N),t = O(\sqrt{N}), si ottiene una soluzione al problema di ricerca (se esiste) con alta probabilità.