Scegliere il numero di iterazioni

Abbiamo stabilito che il vettore di stato del registro $\mathsf{Q}$ nell'algoritmo di Grover rimane nel sottospazio bidimensionale generato da $\vert A_0\rangle$ e $\vert A_1\rangle$ una volta eseguito il passo di inizializzazione.

L'obiettivo è trovare un elemento $x\in A_1,$ e questo obiettivo sarà raggiunto se riusciamo a ottenere lo stato $\vert A_1\rangle$ — poiché, misurando questo stato, siamo certi di ottenere un risultato di misura $x\in A_1.$ Dato che lo stato di $\mathsf{Q}$ dopo $t$ iterazioni al passo 2 è

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

dovremmo scegliere $t$ in modo che

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

sia il più vicino possibile a $1$ in valore assoluto, per massimizzare la probabilità di ottenere $x\in A_1$ dalla misura. Per qualsiasi angolo $\theta \in (0,2\pi),$ il valore $\sin((2t + 1)\theta)$ oscilla all'aumentare di $t$, anche se non è necessariamente periodico — non c'è garanzia che si ottenga mai due volte lo stesso valore.

Naturalmente, oltre a massimizzare la probabilità di ottenere un elemento $x\in A_1$ dalla misura, vorremmo anche scegliere $t$ il più piccolo possibile, perché $t$ applicazioni dell'operazione $G$ richiedono $t$ query alla funzione $f.$ Poiché vogliamo che $\sin( (2t + 1) \theta)$ sia vicino a $1$ in valore assoluto, un modo naturale per farlo è scegliere $t$ in modo che

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

Risolvendo per $t$ si ottiene

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Ovviamente, $t$ deve essere un intero, quindi non sarà necessariamente possibile raggiungere esattamente questo valore — ma quello che possiamo fare è prendere l'intero più vicino a questo valore, che è

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

Questo è il numero di iterazioni consigliato per l'algoritmo di Grover. Proseguendo con l'analisi, vedremo che la vicinanza di questo intero al valore target influenza naturalmente le prestazioni dell'algoritmo.

(Come nota a margine, se il valore target $\pi/(4\theta) - 1/2$ si trova esattamente a metà strada tra due interi, questa espressione di $t$ corrisponde all'arrotondamento per eccesso. In alternativa si potrebbe arrotondare per difetto, il che è ragionevole perché significa una query in meno — ma si tratta di un dettaglio secondario e non rilevante ai fini della lezione.)

Ricordando che il valore dell'angolo $\theta$ è dato dalla formula

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

vediamo che il numero di iterazioni consigliato $t$ dipende dal numero di stringhe in $A_1.$ Questo rappresenta una sfida se non sappiamo quante soluzioni abbiamo, come discuteremo più avanti.

Ricerca unica

Prima di tutto, concentriamoci sulla situazione in cui esiste un'unica stringa $x$ tale che $f(x)=1.$ Un altro modo per dirlo è che stiamo considerando un'istanza del problema di Ricerca unica. In questo caso abbiamo

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

che può essere convenientemente approssimato come

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

quando $N$ diventa grande. Se sostituiamo $\theta = 1/\sqrt{N}$ nell'espressione

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

otteniamo

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Ricordando che $t$ è non solo il numero di volte in cui l'operazione $G$ viene eseguita, ma anche il numero di query alla funzione $f$ richieste dall'algoritmo, vediamo che siamo sulla buona strada per ottenere un algoritmo che richiede $O(\sqrt{N})$ query.

Ora indagheremo quanto funziona bene la scelta consigliata di $t.$ La probabilità che la misura finale restituisca la soluzione unica può essere espressa esplicitamente come

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

Il primo argomento, $N,$ si riferisce al numero di elementi su cui effettuiamo la ricerca, e il secondo argomento, che in questo caso è $1,$ si riferisce al numero di soluzioni. Poco più avanti utilizzeremo la stessa notazione in modo più generale, quando ci sono più soluzioni.

Ecco una tabella delle probabilità di successo per valori crescenti di $N = 2^n.$

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Si noti che queste probabilità non sono strettamente crescenti. In particolare, si osserva un'anomalia interessante quando $N=4,$ dove si ottiene una soluzione con certezza. Tuttavia, è possibile dimostrare in generale che

$$p(N,1) \geq 1 - \frac{1}{N}$$

per ogni $N,$ quindi la probabilità di successo tende a $1$ nel limite in cui $N$ diventa grande, come sembrano suggerire i valori sopra riportati. Ottimo!

Si noti però che anche un limite debole come $p(N,1) \geq 1/2$ stabilisce l'utilità dell'algoritmo di Grover. Qualunque sia il risultato di misura $x$ ottenuto dall'esecuzione della procedura, possiamo sempre verificare se $f(x) = 1$ con una singola query a $f.$ E se non riusciamo a ottenere la stringa unica $x$ per cui $f(x) = 1$ con probabilità al massimo $1/2$ eseguendo la procedura una volta, dopo $m$ esecuzioni indipendenti della procedura non saremo riusciti a ottenere questa stringa unica $x$ con probabilità al massimo $2^{-m}.$ Cioè, usando $O(m \sqrt{N})$ query a $f,$ otterremo la soluzione unica $x$ con probabilità almeno $1 - 2^{-m}.$ Usando il limite migliore $p(N,1) \geq 1 - 1/N$ si rivela che la probabilità di trovare $x\in A_1$ con questo metodo è in realtà almeno $1 - N^{-m}.$

Soluzioni multiple

Al variare del numero di elementi in $A_1,$ varia anche l'angolo $\theta,$ il che può avere un effetto significativo sulla probabilità di successo dell'algoritmo. Per brevità, scriviamo $s = \vert A_1 \vert$ per indicare il numero di soluzioni, e come prima assumiamo $s\geq 1.$

Come esempio motivante, immaginiamo di avere $s = 4$ soluzioni invece di una sola, come considerato in precedenza. Questo significa che

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

che è approssimativamente il doppio dell'angolo che avevamo nel caso $\vert A_1 \vert = 1$ quando $N$ è grande. Supponiamo di non sapere nulla di meglio, e di selezionare lo stesso valore di $t$ del caso con soluzione unica:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

L'effetto sarà catastrofico, come rivela la seguente tabella di probabilità.

$$\begin{array}{ll} N & \text{Success probability}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Questa volta la probabilità di successo tende a $0$ al tendere di $N$ all'infinito. Ciò accade perché stiamo effettivamente ruotando a una velocità doppia rispetto al caso con soluzione unica, quindi finiamo per oltrepassare il target $\vert A_1\rangle$ e atterrare vicino a $-\vert A_0\rangle.$

Se invece utilizziamo la scelta consigliata di $t,$ che è

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

per

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

le prestazioni saranno migliori. Per essere più precisi, usando questa scelta di $t$ si ottiene successo con alta probabilità.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Generalizzando quanto affermato in precedenza, è possibile dimostrare che

$$p(N,s) \geq 1 - \frac{s}{N},$$

dove usiamo la notazione suggerita in precedenza: $p(N,s)$ indica la probabilità che l'algoritmo di Grover, eseguito per $t$ iterazioni, riveli una soluzione quando ci sono $s$ soluzioni in totale su $N$ possibilità.

Questo limite inferiore di $1 - s/N$ sulla probabilità di successo è leggermente peculiare, nel senso che più soluzioni ci sono, peggiore è il limite inferiore — ma sotto l'assunzione che $s$ sia significativamente più piccolo di $N,$ concludiamo comunque che la probabilità di successo è ragionevolmente alta. Come prima, il solo fatto che $p(N,s)$ sia ragionevolmente grande implica l'utilità dell'algoritmo.

Accade anche che

$$p(N,s) \geq \frac{s}{N}.$$

Questo limite inferiore descrive la probabilità che una stringa $x\in\Sigma^n$ selezionata uniformemente a caso sia una soluzione — quindi l'algoritmo di Grover fa sempre almeno quanto la scelta casuale. (In effetti, quando $t=0,$ l'algoritmo di Grover è una scelta casuale.)

Ora osserviamo il numero di iterazioni (e quindi il numero di query)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

per

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

Per ogni $\alpha \in [0,1],$ vale $\sin^{-1}(\alpha)\geq \alpha,$ e quindi

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Questo implica che

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Ciò si traduce in un risparmio nel numero di query al crescere di $s.$ In particolare, il numero di query necessarie è

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Numero di soluzioni sconosciuto

Se il numero di soluzioni $s = \vert A_1 \vert$ è sconosciuto, è necessario un approccio diverso, poiché in questa situazione non abbiamo alcuna conoscenza di $s$ per guidare la scelta di $t.$ Esistono, in realtà, diversi approcci.

Un approccio semplice è scegliere

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

uniformemente a caso. Selezionare $t$ in questo modo trova sempre una soluzione (supponendo che ne esista almeno una) con probabilità superiore al 40%, anche se questo non è ovvio e richiede un'analisi che non verrà inclusa qui. Ha però senso, soprattutto quando si pensa all'immagine geometrica: ruotare lo stato di $\mathsf{Q}$ un numero casuale di volte in questo modo non è dissimile dal scegliere un vettore unitario casuale nello spazio generato da $\vert A_0\rangle$ e $\vert A_1\rangle,$ per il quale è probabile che il coefficiente di $\vert A_1\rangle$ sia ragionevolmente grande. Ripetendo questa procedura e verificando il risultato nello stesso modo descritto in precedenza, la probabilità di trovare una soluzione può essere resa molto vicina a $1.$

Esiste un metodo raffinato che trova una soluzione quando ne esiste una usando $O(\sqrt{N/s})$ query, anche quando il numero di soluzioni $s$ non è noto, e richiede $O(\sqrt{N})$ query per determinare che non ci sono soluzioni quando $s=0.$

L'idea di base è scegliere $t$ uniformemente a caso dall'insieme $\{1,\ldots,T\}$ in modo iterativo, per valori crescenti di $T.$ In particolare, si può partire con $T = 1$ e aumentarlo in modo esponenziale, terminando sempre il processo non appena si trova una soluzione e limitando $T$ per non sprecare query quando non esiste una soluzione. Il processo sfrutta il fatto che sono necessarie meno query quando esistono più soluzioni. È tuttavia necessaria una certa attenzione per bilanciare il tasso di crescita di $T$ con la probabilità di successo per ogni iterazione. (Prendere $T \leftarrow \lceil \frac{5}{4}T\rceil$ funziona, ad esempio, come rivela un'analisi. Raddoppiare $T,$ invece, non funziona — risulta un aumento troppo rapido.)

I casi banali

In tutta l'analisi appena svolta, abbiamo assunto che il numero di soluzioni sia diverso da zero. Infatti, riferendoci ai vettori

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

abbiamo implicitamente assunto che $A_0$ e $A_1$ siano entrambi non vuoti. Qui considereremo brevemente cosa succede quando uno di questi insiemi è vuoto.

Prima di procedere con un'analisi, osserviamo l'ovvio: se ogni stringa $x\in\Sigma^n$ è una soluzione, vedremo una soluzione quando misuriamo; e quando non ci sono soluzioni, non ne vedremo nessuna. In un certo senso non c'è bisogno di andare oltre.

Possiamo però verificare rapidamente la matematica per questi casi banali. La situazione in cui uno tra $A_0$ e $A_1$ è vuoto si verifica quando $f$ è costante; $A_1$ è vuoto quando $f(x) = 0$ per ogni $x\in\Sigma^n,$ e $A_0$ è vuoto quando $f(x) = 1$ per ogni $x\in\Sigma^n.$ Questo significa che

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

e quindi

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Quindi, indipendentemente dal numero di iterazioni $t$ eseguite in questi casi, le misure riveleranno sempre una stringa casuale uniforme $x\in\Sigma^n.$