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 è opportuno). Questi due insiemi soddisfano le condizioni $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.

Per inciso, la notazione qui 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.$$

Abbiamo anche che $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$, quindi $\vert u\rangle$ rappresenta lo stato del registro $\mathsf{Q}$ dopo l'inizializzazione al passo 1 dell'algoritmo di Grover.

Ciò implica che, immediatamente prima che avvengano le iterazioni di $G$ nella fase 2, lo stato di $\mathsf{Q}$ sia contenuto nello spazio vettoriale bidimensionale generato da $\vert A_0\rangle$ e $\vert A_1\rangle$, e che inoltre i coefficienti di questi vettori siano numeri reali. Come vedremo, lo stato $\mathsf{Q}$ avrà sempre queste proprietà — il che significa che 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 passaggio 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 sostituire la funzione $f$ con la composizione di $f$ e della funzione NOT — ovvero, la funzione che si ottiene invertendo il bit di uscita di $f$. Chiameremo questa nuova funzione $g$ e potremo esprimerla utilizzando i simboli in diversi 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, poiché gli stati ottenuti dall'algoritmo nei due casi sono necessariamente equivalenti, a parte 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 quantistico $\vert A_0\rangle$ e $\vert A_1\rangle$.

Innanzitutto, notiamo che l'operazione $Z_f$ ha un effetto molto semplice su $\vert A_0\rangle$ e $\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}$$

ancora una volta per ogni stringa $x\in\Sigma^n$, e un modo alternativo e pratico 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 in precedenza per la sovrapposizione uniforme su tutte le stringhe di bit $n$.

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}$ immediatamente prima della fase 2 è contenuto nello spazio bidimensionale generato da $\vert A_0\rangle$ e $\vert A_1\rangle$, e abbiamo appena dimostrato che $G$ mappa qualsiasi vettore in questo spazio su un altro vettore nello 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 prima e seconda riga/colonna corrispondono rispettivamente a $\vert A_0\rangle$ e $\vert A_1\rangle$. Finora, in questa serie, abbiamo sempre associato le righe e le colonne delle matrici agli stati classici di un sistema, ma le matrici possono anche essere utilizzate per descrivere le azioni delle applicazioni lineari su basi diverse, come nel caso che ci occupa.

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 di due volte di un angolo pari a $\theta$ equivale a ruotare di un angolo pari a $2\theta$. Un altro modo per renderlo evidente è quello di ricorrere all'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 generato da $\vert A_0\rangle$ e $\vert A_1\rangle$. Quindi, ad 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 che abbiamo appena svolto 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 complessivo dell'esecuzione di due riflessioni è quello di eseguire una rotazione.

Cominciamo 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 generato da $\vert A_0\rangle$ e $\vert A_1\rangle$, si tratta di una riflessione rispetto alla 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 supponiamo sia una combinazione lineare reale di $\vert A_0\rangle$ e $\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 riguardante la retta $L_2$ parallela al vettore $\vert u\rangle$. Ecco una figura che illustra l'effetto 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’effetto dell’operazione di Grover consiste nel ruotare le combinazioni lineari di $\vert A_0\rangle$ e $\vert A_1\rangle$ di un angolo pari a $2\theta$.