Analisi

Ora analizzeremo l'algoritmo di Grover per capire come funziona. Inizieremo con quella che potremmo definire un'analisi simbolica, in cui calcoliamo come l'operazione di Grover $G$ agisce su determinati stati, e poi legheremo questa analisi simbolica a un'immagine geometrica utile per visualizzare il funzionamento dell'algoritmo.

---

Soluzioni e non soluzioni

Iniziamo definendo due serie di stringhe.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

L'insieme $A_1$ contiene tutte le soluzioni al nostro problema di ricerca, mentre $A_0$ contiene le stringhe che non sono soluzioni (che possiamo chiamare non soluzioni quando è conveniente). Questi due insiemi soddisfano $A_0 \cap A_1 = \varnothing$ e $A_0 \cup A_1 = \Sigma^n,$, il che significa che si tratta di una bipartizione di $\Sigma^n.$

Successivamente definiremo due vettori unitari che rappresentano le sovrapposizioni uniformi sugli insiemi di soluzioni e non soluzioni.

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

Dal punto di vista formale, ognuno di questi vettori è definito solo quando l'insieme corrispondente è non vuoto, ma di seguito ci concentreremo sul caso in cui né $A_0$ né $A_1$ siano vuoti. I casi di $A_0 = \varnothing$ e $A_1 = \varnothing$ possono essere trattati separatamente e lo faremo più avanti.

A parte questo, la notazione utilizzata è comune: ogni volta che abbiamo un insieme finito e non vuoto $S,$ possiamo scrivere $\vert S\rangle$ per indicare il vettore di stato quantistico che è uniforme sugli elementi di $S.$

Definiamo inoltre che $\vert u \rangle$ è uno stato quantistico uniforme su tutte le stringhe di $n$ bit:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Si noti che

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

Si ha inoltre che $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ e $\vert u\rangle$ rappresentano lo stato del registro $\mathsf{Q}$ dopo l'inizializzazione al passo 1 dell'algoritmo di Grover.

Ciò implica che, appena prima che avvengano le iterazioni di $G$ nel passo 2, lo stato di $\mathsf{Q}$ è contenuto nello spazio vettoriale bidimensionale spaziato da $\vert A_0\rangle$ e $\vert A_1\rangle,$ e inoltre i coefficienti di questi vettori sono numeri reali. Come vedremo, lo stato di $\mathsf{Q}$ avrà sempre queste proprietà - cioè lo stato è una combinazione lineare reale di $\vert A_0\rangle$ e $\vert A_1\rangle$ - dopo un numero qualsiasi di iterazioni dell'operazione $G$ nel passo 2.

---

Un'osservazione sull'operazione Grover

Passiamo ora all'operazione di Grover

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

iniziando con un'interessante osservazione al riguardo.

Immaginiamo per un momento di aver sostituito la funzione $f$ con la composizione di $f$ con la funzione NOT, ovvero la funzione che si ottiene capovolgendo il bit di uscita di $f.$ Chiameremo questa nuova funzione $g,$ e possiamo esprimerla con i simboli in alcuni modi alternativi.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Si noti che

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

per ogni stringa $x\in\Sigma^n,$ e quindi

$$Z_g = - Z_f.$$

Ciò significa che se sostituissimo la funzione $f$ con la funzione $g,$ l'algoritmo di Grover non funzionerebbe in modo diverso, perché gli stati ottenuti dall'algoritmo nei due casi sono necessariamente equivalenti fino a una fase globale.

Non è un problema! Intuitivamente, l'algoritmo non si preoccupa di quali stringhe siano soluzioni e quali non soluzioni: deve solo essere in grado di distinguere le soluzioni e le non soluzioni per funzionare correttamente.

---

Azione dell'operazione Grover

Consideriamo ora l'azione di $G$ sui vettori di stato quantistici $\vert A_0\rangle$ e $\vert A_1\rangle.$

Per prima cosa, osserviamo che l'operazione $Z_f$ ha un'azione molto semplice su $\vert A_0\rangle$ e su $\vert A_1\rangle.$

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

In secondo luogo, abbiamo l'operazione $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ L'operazione $Z_{\mathrm{OR}}$ è definita come

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

per ogni stringa $x\in\Sigma^n,$ e un modo alternativo per esprimere questa operazione è il seguente:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

Un modo semplice per verificare che questa espressione sia in accordo con la definizione di $Z_{\mathrm{OR}}$ è quello di valutare la sua azione sugli stati base standard.

L'operazione $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ può quindi essere scritta in questo modo:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

utilizzando la stessa notazione, $\vert u \rangle,$, che abbiamo usato sopra per la sovrapposizione uniforme di tutte le stringhe di $n$ bit.

E ora abbiamo ciò che ci serve per calcolare l'azione di $G$ su $\vert A_0\rangle$ e $\vert A_1\rangle.$ Per prima cosa calcoliamo l'azione di $G$ su $\vert A_0\rangle.$

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

In secondo luogo, calcoliamo l'azione di $G$ su $\vert A_1\rangle.$

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

In entrambi i casi si utilizza l'equazione

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

insieme alle espressioni

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

che seguono.

In sintesi, abbiamo

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Come abbiamo già osservato, lo stato di $\mathsf{Q}$ appena prima del passo 2 è contenuto nello spazio bidimensionale compreso tra $\vert A_0\rangle$ e $\vert A_1\rangle,$ e abbiamo appena stabilito che $G$ mappa qualsiasi vettore di questo spazio in un altro vettore dello stesso spazio. Ciò significa che, ai fini dell'analisi, possiamo concentrare la nostra attenzione esclusivamente su questo sottospazio.

Per comprendere meglio ciò che accade in questo spazio bidimensionale, esprimiamo l'azione di $G$ su questo spazio come una matrice,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

le cui prime e seconde righe/colonne corrispondono rispettivamente a $\vert A_0\rangle$ e $\vert A_1\rangle,$. Finora in questa serie abbiamo sempre collegato le righe e le colonne delle matrici con gli stati classici di un sistema, ma le matrici possono essere utilizzate anche per descrivere le azioni di mappature lineari su basi diverse, come in questo caso.

Anche se non è affatto ovvio a prima vista, la matrice $M$ è ciò che si ottiene squadrando una matrice di aspetto più semplice.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

La matrice

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

è una matrice di rotazione, che possiamo esprimere alternativamente come

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

per

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr).$$

Questo angolo $\theta$ avrà un ruolo molto importante nell'analisi che segue, quindi vale la pena di sottolinearne l'importanza in questa sede, visto che lo vediamo per la prima volta.

Alla luce di questa espressione della matrice, osserviamo che

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

Questo perché ruotare due volte dell'angolo $\theta$ equivale a ruotare dell'angolo $2\theta.$ Un altro modo di vedere questo aspetto è quello di utilizzare l'espressione alternativa

$$\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),$$

insieme alle formule degli angoli doppi della trigonometria:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

In sintesi, lo stato del registro $\mathsf{Q}$ all'inizio del passo 2 è

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

e l'effetto dell'applicazione di $G$ a questo stato è quello di ruotarlo di un angolo $2\theta$ all'interno dello spazio compreso tra $\vert A_0\rangle$ e $\vert A_1\rangle.$ Quindi, per esempio, abbiamo

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

e in generale

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle.$$

---

Immagine geometrica

Ora colleghiamo l'analisi appena svolta a un'immagine geometrica. L'idea è che l'operazione $G$ sia il prodotto di due riflessioni, $Z_f$ e $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ E l'effetto netto dell'esecuzione di due riflessioni è quello di eseguire una rotazione.

Iniziamo con $Z_f.$ Come abbiamo già osservato in precedenza, abbiamo

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

All'interno dello spazio vettoriale bidimensionale compreso tra $\vert A_0\rangle$ e $\vert A_1\rangle,$ si tratta di una riflessione sulla retta parallela a $\vert A_0\rangle,$ che chiameremo $L_1.$ Ecco una figura che illustra l'azione di questa riflessione su un ipotetico vettore unitario $\vert\psi\rangle,$ che assumiamo essere una combinazione lineare reale di $\vert A_0\rangle$ e di $\vert A_1\rangle.$

In secondo luogo abbiamo l'operazione $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ che, come abbiamo già visto, può essere scritta come

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Anche questa è una riflessione, questa volta sulla retta $L_2$ parallela al vettore $\vert u\rangle.$ Ecco una figura che illustra l'azione di questa riflessione su un vettore unitario $\vert\psi\rangle.$

Quando componiamo queste due riflessioni, otteniamo una rotazione - di due volte l'angolo tra le linee di riflessione - come illustra questa figura.

Questo spiega, in termini geometrici, perché l'operazione di Grover ha l'effetto di far ruotare le combinazioni lineari di $\vert A_0\rangle$ e $\vert A_1\rangle$ di un angolo pari a $2\theta.$