Analisi

Ora analizzeremo l'algoritmo di Grover per capire come funziona. Partiremo da quella che potrebbe essere descritta come un'analisi simbolica, in cui calcoliamo come l'operazione di Grover $G$ agisce su certi stati, e poi collegheremo questa analisi simbolica a un'immagine geometrica che è utile per visualizzare il funzionamento dell'algoritmo.

Soluzioni e non-soluzioni

Iniziamo definendo due insiemi 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 questa è una bipartizione di $\Sigma^n.$

Definiamo ora due vettori unitari che rappresentano 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}$$

Formalmente, ciascuno di questi vettori è definito solo quando il corrispondente insieme è non vuoto, ma d'ora in poi ci concentreremo sul caso in cui né $A_0$ né $A_1$ sia vuoto. I casi in cui $A_0 = \varnothing$ e $A_1 = \varnothing$ si trattano facilmente separatamente, e lo faremo più avanti.

Come nota a margine, la notazione usata qui è 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 anche $\vert u \rangle$ come lo 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.$$

Nota 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 nel passo 1 dell'algoritmo di Grover.

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

Un'osservazione sull'operazione di Grover

Volgiamo ora la nostra attenzione all'operazione di Grover

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

partendo da un'interessante osservazione su di essa.

Immagina per un momento di sostituire la funzione $f$ con la composizione di $f$ con la funzione NOT — ovvero la funzione ottenuta invertendo il bit di output di $f.$ Chiameremo questa nuova funzione $g,$ e possiamo esprimerla simbolicamente 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}$$

Nota 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 a meno di una fase globale.

Questo non è un problema! Intuitivamente, l'algoritmo non si preoccupa di quali stringhe siano soluzioni e quali non lo siano — ha solo bisogno di essere in grado di distinguere soluzioni e non-soluzioni per funzionare correttamente.

Azione dell'operazione di Grover

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

Prima di tutto, osserviamo che l'operazione $Z_f$ ha un'azione 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}$$

sempre per ogni stringa $x\in\Sigma^n,$ e un modo alternativo comodo 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 corrisponda alla definizione di $Z_{\mathrm{OR}}$ è valutarne l'azione sugli stati della base standard.

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

$$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},$$

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

Ora abbiamo tutto il necessario per calcolare l'azione di $G$ su $\vert A_0\rangle$ e $\vert A_1\rangle.$ Calcoliamo prima 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}$$

E 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 utilizziamo 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{e}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

che ne derivano.

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 già osservato, lo stato di $\mathsf{Q}$ appena prima del passo 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 in un altro vettore nello stesso spazio. Ciò significa che, ai fini dell'analisi, possiamo concentrare la nostra attenzione esclusivamente su questo sottospazio.

Per capire meglio cosa 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 agli stati classici di un sistema, ma le matrici possono essere usate anche per descrivere le azioni di mappature lineari su basi diverse come nel nostro caso.

Sebbene non sia affatto ovvio a prima vista, la matrice $M$ è ciò che si ottiene elevando al quadrato una matrice dall'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 in alternativa esprimere 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 sottolinearne l'importanza la prima volta che lo incontriamo.

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 un angolo $\theta$ due volte equivale a ruotare di un angolo $2\theta.$ Un altro modo per vederlo è utilizzare l'espressione alternativa

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

insieme alle formule dell'angolo doppio 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.$ Così, 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

Colleghiamo ora l'analisi appena svolta a un'immagine geometrica. L'idea è che l'operazione $G$ è 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 generato da $\vert A_0\rangle$ e $\vert A_1\rangle,$ questa è 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 assumiamo essere 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 abbiamo già visto potersi scrivere 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 rispetto alla retta $L_2$ parallela al vettore $\vert u\rangle.$ Ecco una figura che mostra l'azione di questa riflessione su un vettore unitario $\vert\psi\rangle.$

Quando componiamo queste due riflessioni, otteniamo una rotazione — di un angolo doppio rispetto all'angolo tra le rette di riflessione — come illustra questa figura.

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