Ricerca non strutturata

Riepilogo

Iniziamo con una descrizione del problema che l'algoritmo di Grover risolve. Come di consueto, indichiamo con $\Sigma = \{0,1\}$ l'alfabeto binario per tutta questa discussione.

Supponiamo che

$$f:\Sigma^n \rightarrow \Sigma$$

sia una funzione da stringhe binarie di lunghezza $n$ a bit. Assumeremo di poter calcolare questa funzione in modo efficiente, ma per il resto è arbitraria e non possiamo fare affidamento su una struttura particolare o un'implementazione specifica che faccia al caso nostro.

Quello che fa l'algoritmo di Grover è cercare una stringa $x\in\Sigma^n$ per cui $f(x) = 1.$ Chiameremo stringhe come questa soluzioni al problema di ricerca. Se esistono più soluzioni, ognuna di esse è considerata un output corretto; se invece non esistono soluzioni, la risposta corretta richiede che lo si dichiari esplicitamente.

Questo compito è descritto come un problema di ricerca non strutturata perché non possiamo fare affidamento sul fatto che $f$ abbia una struttura particolare che lo renda più semplice. Non stiamo cercando in una lista ordinata né all'interno di una struttura dati progettata specificamente per facilitare la ricerca: stiamo essenzialmente cercando un ago in un pagliaio.

In modo intuitivo, possiamo immaginare di avere un circuito booleano estremamente complesso che calcola $f,$ e di poter facilmente eseguire questo circuito su una stringa di input scelta. Ma poiché il circuito è così complicato, non abbiamo alcuna speranza di comprenderlo esaminandolo (al di là della capacità di valutarlo su stringhe di input selezionate).

Un modo per eseguire questo compito di ricerca in modo classico è semplicemente iterare su tutte le stringhe $x\in\Sigma^n,$ valutando $f$ su ciascuna per verificare se è o meno una soluzione. D'ora in poi, scriviamo

$$N = 2^n$$

per comodità. Ci sono $N$ stringhe in $\Sigma^n,$ quindi iterare su tutte richiede $N$ valutazioni di $f.$ Nell'ipotesi di essere limitati a valutare $f$ su input scelti, questo è il meglio che possiamo fare con un algoritmo deterministico se vogliamo garantire il successo. Con un algoritmo probabilistico, potremmo sperare di risparmiare tempo scegliendo casualmente le stringhe di input per $f,$ ma avremo comunque bisogno di $O(N)$ valutazioni di $f$ se vogliamo che questo metodo abbia successo con alta probabilità.

L'algoritmo di Grover risolve questo problema di ricerca con alta probabilità con sole $O(\sqrt{N})$ valutazioni di $f.$ Per essere chiari, queste valutazioni della funzione devono avvenire in sovrapposizione, in modo analogo agli algoritmi di query discussi nella lezione Algoritmi di query quantistici, tra cui l'algoritmo di Deutsch, l'algoritmo di Deutsch-Jozsa e l'algoritmo di Simon. A differenza di quegli algoritmi, l'algoritmo di Grover adotta un approccio iterativo: valuta $f$ su sovrapposizioni di stringhe di input e intervalla queste valutazioni con altre operazioni che hanno l'effetto di creare pattern di interferenza, portando a una soluzione con alta probabilità (se ne esiste una) dopo $O(\sqrt{N})$ iterazioni.

Enunciato formale del problema

Formalizzeremo il problema che l'algoritmo di Grover risolve usando il modello di calcolo basato su query. Cioè, assumeremo di avere accesso alla funzione $f:\Sigma^n\rightarrow\Sigma$ attraverso un gate di query definito nel modo usuale:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

per ogni $x\in\Sigma^n$ e $a\in\Sigma.$ Questa è l'azione di $U_f$ sugli stati della base standard, e la sua azione in generale è determinata dalla linearità.

Come discusso nella lezione Fondamenti algoritmici quantistici, se disponiamo di un circuito booleano per il calcolo di $f,$ possiamo trasformare la descrizione di quel circuito booleano in un circuito quantistico che implementa $U_f$ (usando un certo numero di qubit di lavoro che iniziano e terminano il calcolo nello stato $\vert 0\rangle$). Quindi, sebbene stiamo usando il modello di query per formalizzare il problema che l'algoritmo di Grover risolve, esso non è limitato a questo modello; possiamo eseguire l'algoritmo di Grover su qualsiasi funzione $f$ per cui disponiamo di un circuito booleano.

Ecco un enunciato preciso del problema, che si chiama Search perché stiamo cercando una soluzione, ovvero una stringa $x$ che fa sì che $f$ valuti $1.$

Search

Input: una funzione $f:\Sigma^n\rightarrow\Sigma$
Output: una stringa $x\in\Sigma^n$ che soddisfa $f(x) = 1,$ oppure "nessuna soluzione" se non esiste tale stringa $x$

Si noti che questo non è un problema promise — la funzione $f$ è arbitraria. Sarà tuttavia utile considerare la seguente variante promise del problema, in cui ci è garantito che esista esattamente una soluzione. Questo problema è apparso come esempio di problema promise nella lezione Algoritmi di query quantistici.

Unique search

Input: una funzione della forma $f:\Sigma^n \rightarrow \Sigma$
Promise: esiste esattamente una stringa $z\in\Sigma^n$ per cui $f(z) = 1,$ con $f(x) = 0$ per tutte le stringhe $x\neq z$
Output: la stringa $z$

Si noti inoltre che il problema Or menzionato nella stessa lezione è strettamente correlato a Search. Per quel problema, l'obiettivo è semplicemente determinare se esiste o meno una soluzione, anziché trovarne effettivamente una.