Il modello di calcolo a query

Quando modelliamo i calcoli in termini matematici, di solito abbiamo in mente il tipo di processo rappresentato dalla figura seguente, dove le informazioni vengono fornite come input, viene eseguito un calcolo e viene prodotto un output.

Sebbene sia vero che i computer che usiamo oggi ricevono continuamente input e producono output, interagendo essenzialmente sia con noi sia con altri computer in un modo che la figura non riflette, l'intenzione non è quella di rappresentare il funzionamento continuo dei computer. Piuttosto, si tratta di creare una semplice astrazione del calcolo, concentrandosi su attività computazionali isolate. Ad esempio, l'input potrebbe codificare un numero, un vettore, una matrice, un grafo, la descrizione di una molecola, o qualcosa di più complesso, mentre l'output codifica la soluzione al problema computazionale che abbiamo in mente.

Il punto chiave è che l'input viene fornito al calcolo, di solito sotto forma di stringa binaria, senza che nessuna sua parte sia nascosta.

Descrizione del modello

Nel modello a query di calcolo, l'intero input non viene fornito al calcolo come nel modello più standard suggerito sopra. Piuttosto, l'input è reso disponibile sotto forma di funzione, a cui il calcolo accede effettuando delle query. In alternativa, possiamo vedere i calcoli nel modello a query come aventi accesso casuale ai bit (o a segmenti di bit) dell'input.

Spesso ci riferiamo all'input come fornito da un oracolo o scatola nera nel contesto del modello a query. Entrambi i termini suggeriscono che una descrizione completa dell'input è nascosta al calcolo, e l'unico modo per accedervi è fare domande. È come se stessimo consultando l'Oracolo di Delfi riguardo all'input: lei non ci dirà tutto ciò che sa, risponde solo a domande specifiche. Il termine scatola nera ha senso soprattutto quando pensiamo all'input come rappresentato da una funzione; non possiamo guardare dentro la funzione e capire come funziona, possiamo solo valutarla sugli argomenti che scegliamo.

In questa lezione lavoreremo esclusivamente con stringhe binarie, al contrario di stringhe contenenti simboli diversi, quindi scriviamo $\Sigma = \{0,1\}$ d'ora in poi per riferirci comodamente all'alfabeto binario. Prenderemo in considerazione diversi problemi computazionali, con alcuni semplici esempi descritti a breve, ma per tutti loro l'input sarà rappresentato da una funzione della forma

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

per due interi positivi $n$ e $m.$ Naturalmente, potremmo scegliere un nome diverso al posto di $f,$ ma useremo $f$ per tutta la lezione.

Dire che un calcolo fa una query significa che viene selezionata una stringa $x \in \Sigma^n,$ e poi la stringa $f(x)\in\Sigma^m$ viene resa disponibile al calcolo dall'oracolo. Il modo preciso in cui questo funziona per gli algoritmi quantistici verrà discusso a breve — dobbiamo assicurarci che sia possibile farlo con un'operazione quantistica unitaria che permetta di effettuare query in sovrapposizione — ma per ora possiamo pensarci intuitivamente ad alto livello.

Infine, il modo in cui misureremo l'efficienza degli algoritmi a query è semplice: conteremo il numero di query che richiedono. Questo è correlato al tempo necessario per eseguire un calcolo, ma non è esattamente la stessa cosa perché stiamo ignorando il tempo per le operazioni diverse dalle query, e stiamo anche trattando le query come se ciascuna avesse costo unitario. Possiamo tenere conto delle operazioni diverse dalle query se vogliamo (e questo a volte viene fatto), ma limitare la nostra attenzione solo al numero di query aiuta a mantenere le cose semplici.

Esempi di problemi a query

Ecco alcuni semplici esempi di problemi a query.

• OR. La funzione di input ha la forma $f:\Sigma^n \rightarrow \Sigma$ (quindi $m=1$ per questo problema). Il compito è restituire $1$ se esiste una stringa $x\in\Sigma^n$ per cui $f(x) = 1,$ e restituire $0$ se non esiste tale stringa. Se pensiamo alla funzione $f$ come a una sequenza di $2^n$ bit a cui abbiamo accesso casuale, il problema è calcolare l'OR di questi bit.

• Parità. La funzione di input ha di nuovo la forma $f:\Sigma^n \rightarrow \Sigma.$ Il compito è determinare se il numero di stringhe $x\in\Sigma^n$ per cui $f(x) = 1$ è pari o dispari. Per essere precisi, l'output richiesto è $0$ se l'insieme $\{x\in\Sigma^n : f(x) = 1\}$ ha un numero pari di elementi e $1$ se ne ha un numero dispari. Se pensiamo alla funzione $f$ come a una sequenza di $2^n$ bit a cui abbiamo accesso casuale, il problema è calcolare la parità (o OR esclusivo) di questi bit.

• Minimo. La funzione di input ha la forma $f:\Sigma^n \rightarrow \Sigma^m$ per qualsiasi scelta di interi positivi $n$ e $m.$ L'output richiesto è la stringa $y \in \{f(x) : x\in\Sigma^n\}$ che viene prima nell'ordinamento lessicografico (cioè, dizionario) di $\Sigma^m.$ Se pensiamo alla funzione $f$ come a una sequenza di $2^n$ interi codificati come stringhe di lunghezza $m$ in notazione binaria a cui abbiamo accesso casuale, il problema è calcolare il minimo di questi interi.

Consideriamo anche problemi a query in cui abbiamo una promessa sull'input. Questo significa che ci viene data una qualche garanzia sull'input, e non siamo responsabili di ciò che accade quando questa garanzia non è rispettata. Un altro modo per descrivere questo tipo di problema è dire che alcune funzioni di input (quelle per cui la promessa non è soddisfatta) sono considerate input "don't care". Nessun requisito viene imposto agli algoritmi quando ricevono input "don't care".

Ecco un esempio di problema con una promessa:

• Ricerca unica. La funzione di input ha la forma $f:\Sigma^n \rightarrow \Sigma,$ ed è promesso che esiste esattamente una stringa $z\in\Sigma^n$ per cui $f(z) = 1,$ con $f(x) = 0$ per tutte le stringhe $x\neq z.$ Il compito è trovare questa stringa unica $z.$

Tutti e quattro gli esempi appena descritti sono naturali, nel senso che sono facili da descrivere e possiamo immaginare una varietà di situazioni o contesti in cui potrebbero presentarsi.

Al contrario, alcuni problemi a query non sono affatto "naturali" in questo modo. In effetti, nello studio del modello a query, a volte ci imbattiamo in problemi molto complessi e altamente artificiosi in cui è difficile immaginare che qualcuno voglia mai effettivamente risolverli in pratica. Questo non significa però che i problemi non siano interessanti! Cose che potrebbero sembrare artificiose o innaturali all'inizio possono fornire indizi inaspettati o ispirare nuove idee. L'algoritmo quantistico di Shor per la fattorizzazione, ispirato dall'algoritmo di Simon, ne è un ottimo esempio. È anche una parte importante dello studio del modello a query cercare gli estremi, che possono far luce sia sui potenziali vantaggi sia sui limiti del calcolo quantistico.

gate a query

Quando descriviamo i calcoli con circuiti, le query vengono effettuate tramite gate speciali chiamati gate a query.

Il modo più semplice per definire i gate a query per i circuiti booleani classici è semplicemente consentire loro di calcolare direttamente la funzione di input $f,$ come suggerisce la figura seguente.

Quando viene creato un circuito booleano per un problema a query, la funzione di input $f$ viene acceduta tramite questi gate, e il numero di query che il circuito effettua è semplicemente il numero di gate a query presenti nel circuito. I fili di input del circuito booleano stesso vengono inizializzati a valori fissi, che devono essere considerati parte dell'algoritmo (al contrario degli input del problema).

Ad esempio, ecco un circuito booleano con gate a query classici che risolve il problema della parità descritto sopra per una funzione della forma $f:\Sigma\rightarrow\Sigma$:

Questo algoritmo effettua due query perché ci sono due gate a query. Il modo in cui funziona è che la funzione $f$ viene interrogata sui due possibili input, $0$ e $1,$ e i risultati vengono inseriti in un circuito booleano che calcola lo XOR. (Questo particolare circuito è apparso come esempio di circuito booleano nella lezione Circuiti quantistici del corso Basi dell'informazione quantistica.)

Per i circuiti quantistici, questa definizione di gate a query non funziona, perché questi gate sarebbero non unitari per alcune scelte della funzione $f.$ Quindi, quello che facciamo invece è definire gate a query unitari che operano come suggerisce questa figura sugli stati della base standard:

Qui, assumiamo che $x\in\Sigma^n$ e $y\in\Sigma^m$ siano stringhe arbitrarie. La notazione $y\oplus f(x)$ si riferisce all'OR esclusivo bit a bit di due stringhe, che in questo caso hanno lunghezza $m.$ Ad esempio, $001 \oplus 101 = 100.$

Intuitivamente, ciò che fa il gate $U_f$ (per qualsiasi funzione $f$ scelta) è fare l'eco della stringa di input superiore $x$ e applicare tramite XOR il valore della funzione $f(x)$ sulla stringa di input inferiore $y,$ che è un'operazione unitaria per ogni scelta della funzione $f.$ In effetti, è un'operazione deterministica ed è il proprio inverso. Ciò implica che, come matrice, $U_f$ è sempre una matrice di permutazione, cioè una matrice con un singolo $1$ in ogni riga e in ogni colonna, con tutte le altre voci pari a $0.$ Applicare una matrice di permutazione a un vettore semplicemente mescola le voci del vettore (da cui il termine matrice di permutazione), e quindi non cambia la norma euclidea di quel vettore — il che rivela che le matrici di permutazione sono sempre unitarie.

Va sottolineato che, quando analizziamo gli algoritmi a query semplicemente contando il numero di query che un algoritmo effettua, stiamo completamente ignorando la difficoltà di costruire fisicamente i gate a query — sia per le versioni classiche che quantistiche appena descritte. Intuitivamente, la costruzione dei gate a query fa parte della preparazione dell'input, non della ricerca di una soluzione.

Questo potrebbe sembrare irragionevole, ma dobbiamo tenere a mente che non stiamo cercando di descrivere il calcolo pratico né di tenere pienamente conto delle risorse necessarie. Piuttosto, stiamo definendo un modello teorico che aiuta a far luce sui potenziali vantaggi del calcolo quantistico. Diremo di più su questo punto nella lezione successiva a questa, quando volgeremo la nostra attenzione a un modello di calcolo più standard in cui gli input vengono forniti esplicitamente ai circuiti come stringhe binarie.