Algoritmo di Simon

L'algoritmo di Simon è un algoritmo di query quantistico per un problema noto come problema di Simon. Si tratta di un problema con promessa, dal sapore simile ai problemi di Deutsch-Jozsa e Bernstein-Vazirani, ma con caratteristiche diverse.

L'algoritmo di Simon è significativo perché fornisce un vantaggio esponenziale del quantum rispetto agli algoritmi classici (inclusi quelli probabilistici), e la tecnica che utilizza ha ispirato Peter Shor nella scoperta di un efficiente algoritmo quantistico per la fattorizzazione di interi.

Problema di Simon

La funzione di input per il problema di Simon ha la forma

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

per interi positivi $n$ e $m.$ Potremmo limitarci al caso $m = n$ per semplicità, ma c'è poco da guadagnare facendo questa assunzione — l'algoritmo di Simon e la sua analisi sono sostanzialmente gli stessi in entrambi i casi.

Problema di Simon

Input: una funzione $f:\Sigma^n \rightarrow \Sigma^m$
Promessa: esiste una stringa $s\in\Sigma^n$ tale che $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ per tutti $x,y\in\Sigma^n$
Output: la stringa $s$

Analizzeremo la promessa tra poco per capire meglio cosa afferma, ma prima è importante chiarire che essa richiede che $f$ abbia una struttura molto speciale — quindi la maggior parte delle funzioni non la soddisferà. È anche opportuno riconoscere che questo problema non è pensato per avere importanza pratica. Piuttosto, è un problema in qualche modo artificiale, costruito appositamente per essere facile per i computer quantistici e difficile per quelli classici.

Esistono due casi principali: il primo caso è che $s$ sia la stringa tutta-zero $0^n,$ e il secondo caso è che $s$ non sia la stringa tutta-zero.

• Caso 1: $s=0^n.$ Se $s$ è la stringa tutta-zero, possiamo semplificare l'affermazione di "se e solo se" nella promessa in modo che reciti $[f(x) = f(y)] \Leftrightarrow [x = y].$ Questo è equivalente a dire che $f$ è una funzione iniettiva.

• Caso 2: $s\neq 0^n.$ Se $s$ non è la stringa tutta-zero, allora il soddisfacimento della promessa per questa stringa implica che $f$ sia due-a-uno, cioè per ogni possibile stringa di output di $f,$ esistono esattamente due stringhe di input che portano $f$ a produrre quella stringa. Inoltre, queste due stringhe di input devono avere la forma $w$ e $w \oplus s$ per qualche stringa $w.$

È importante riconoscere che può esserci una sola stringa $s$ che funziona se la promessa è soddisfatta, quindi c'è sempre una risposta corretta univoca per le funzioni che soddisfano la promessa.

Ecco un esempio di funzione nella forma $f:\Sigma^3 \rightarrow \Sigma^5$ che soddisfa la promessa per la stringa $s = 011.$

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

Ci sono $8$ stringhe di input diverse e $4$ stringhe di output diverse, ognuna delle quali appare due volte — quindi questa è una funzione due-a-uno. Inoltre, per qualsiasi coppia di stringhe di input diverse che producono la stessa stringa di output, vediamo che lo XOR bit a bit di queste due stringhe di input è uguale a $011,$ il che equivale a dire che ognuna di esse è uguale all'altra messa in XOR con $s.$

Nota che l'unica cosa che conta delle stringhe di output effettive è se sono uguali o diverse per diverse scelte di stringhe di input. Ad esempio, nell'esempio precedente, ci sono quattro stringhe $(10011,$ $00101,$ $00001,$ e $11010)$ che appaiono come output di $f.$ Potremmo sostituire queste quattro stringhe con stringhe diverse, purché siano tutte distinte, e la soluzione corretta $s = 011$ non cambierebbe.

Descrizione dell'algoritmo

Ecco un diagramma di circuito quantistico che rappresenta l'algoritmo di Simon.

Per essere precisi, ci sono $n$ qubit in alto su cui agiscono i gate di Hadamard e $m$ qubit in basso che entrano direttamente nel gate di query. Somiglia molto agli algoritmi già discussi nella lezione, ma questa volta non c'è phase kickback; gli $m$ qubit in basso entrano tutti nel gate di query nello stato $\vert 0\rangle.$

Per risolvere il problema di Simon usando questo circuito saranno necessarie diverse esecuzioni indipendenti seguite da un passaggio di post-elaborazione classica, che verrà descritto in seguito dopo aver analizzato il comportamento del circuito.

Analisi

L'analisi dell'algoritmo di Simon inizia in modo simile all'algoritmo di Deutsch-Jozsa. Dopo che il primo strato di gate di Hadamard viene applicato agli $n$ qubit in alto, lo stato diventa

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

Quando viene applicato $U_f,$ l'output della funzione $f$ viene messo in XOR sullo stato tutta-zero degli $m$ qubit in basso, quindi lo stato diventa

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

Quando viene applicato il secondo strato di gate di Hadamard, si ottiene il seguente stato usando la stessa formula per l'azione di uno strato di gate di Hadamard vista in precedenza.

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

A questo punto, l'analisi diverge da quelle degli algoritmi precedenti di questa lezione.

Siamo interessati alla probabilità che le misurazioni producano ogni possibile stringa $y\in\Sigma^n.$ Attraverso le regole per l'analisi delle misurazioni descritte nella lezione Sistemi multipli del corso Nozioni di base dell'informazione quantistica, troviamo che la probabilità $p(y)$ di ottenere la stringa $y$ è uguale a

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

Per capire meglio queste probabilità, abbiamo bisogno di un po' più di notazione e terminologia. Prima di tutto, il range della funzione $f$ è l'insieme contenente tutte le sue stringhe di output.

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

Poi, per ogni stringa $z\in\operatorname{range}(f),$ possiamo esprimere l'insieme di tutte le stringhe di input che fanno valutare la funzione a questa stringa di output $z$ come $f^{-1}(\{z\}).$

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

L'insieme $f^{-1}(\{z\})$ è noto come la preimmagine di $\{z\}$ sotto $f.$ Possiamo definire la preimmagine sotto $f$ di qualsiasi insieme al posto di $\{z\}$ in modo analogo — è l'insieme di tutti gli elementi che $f$ mappa in quell'insieme. (Questa notazione non va confusa con l'inversa della funzione $f,$ che potrebbe non esistere. Il fatto che l'argomento sul lato sinistro sia l'insieme $\{z\}$ piuttosto che l'elemento $z$ è il segnale che ci permette di evitare questa confusione.)

Usando questa notazione, possiamo spezzare la somma nella nostra espressione per le probabilità precedenti per ottenere

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

Ogni stringa $x\in\Sigma^n$ è rappresentata esattamente una volta dalle due sommatorie — stiamo fondamentalmente mettendo queste stringhe in secchi separati a seconda della stringa di output $z = f(x)$ che producono quando valutiamo la funzione $f,$ e poi sommando separatamente su tutti i secchi.

Ora possiamo calcolare il quadrato della norma euclidea per ottenere

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

Per semplificare ulteriormente queste probabilità, diamo un'occhiata al valore

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

per una scelta arbitraria di $z\in\operatorname{range}(f).$

Se $s = 0^n,$ allora $f$ è una funzione iniettiva e c'è sempre un solo elemento $x\in f^{-1}(\{z\}),$ per ogni $z\in\operatorname{range}(f).$ Il valore dell'espressione $(1)$ è $1$ in questo caso.

Se invece $s\neq 0^n,$ allora ci sono esattamente due stringhe nell'insieme $f^{-1}(\{z\}).$ Per essere precisi, se scegliamo $w\in f^{-1}(\{z\})$ come una qualsiasi di queste due stringhe, allora l'altra stringa deve essere $w \oplus s$ per la promessa nel problema di Simon. Usando questa osservazione possiamo semplificare $(1)$ come segue.

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

Quindi, risulta che il valore $(1)$ è indipendente dalla scelta specifica di $z\in\operatorname{range}(f)$ in entrambi i casi.

Possiamo ora concludere l'analisi esaminando separatamente gli stessi due casi di prima.

• Caso 1: $s = 0^n.$ In questo caso la funzione $f$ è iniettiva, quindi ci sono $2^n$ stringhe $z\in\operatorname{range}(f),$ e otteniamo

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  In altre parole, le misurazioni producono una stringa $y\in\Sigma^n$ scelta uniformemente a caso.

• Caso 2: $s \neq 0^n.$ In questo caso $f$ è due-a-uno, quindi ci sono $2^{n-1}$ elementi in $\operatorname{range}(f).$ Usando la formula precedente concludiamo che la probabilità di misurare ogni $y\in\Sigma^n$ è

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  In altre parole, si ottiene una stringa scelta uniformemente a caso dall'insieme $\{y\in\Sigma^n : y \cdot s = 0\},$ che contiene $2^{n-1}$ stringhe. (Poiché $s\neq 0^n,$ esattamente la metà delle stringhe binarie di lunghezza $n$ ha prodotto scalare binario $1$ con $s$ e l'altra metà ha prodotto scalare binario $0$ con $s,$ come già osservato nell'analisi dell'algoritmo di Deutsch-Jozsa per il problema di Bernstein-Vazirani.)

Post-elaborazione classica

Ora sappiamo quali sono le probabilità per i possibili esiti delle misurazioni quando eseguiamo il circuito quantistico per l'algoritmo di Simon. È sufficiente questa informazione per determinare $s$?

La risposta è sì, a condizione che si sia disposti a ripetere il processo più volte e ad accettare che potrebbe fallire con qualche probabilità, che possiamo rendere molto piccola eseguendo il circuito abbastanza volte. L'idea essenziale è che ogni esecuzione del circuito ci fornisce prove statistiche riguardo a $s,$ e possiamo usare tali prove per trovare $s$ con probabilità molto alta se eseguiamo il circuito un numero sufficiente di volte.

Supponiamo di eseguire il circuito indipendentemente $k$ volte, per $k = n + 10.$ Non c'è nulla di speciale in questo particolare numero di iterazioni — potremmo scegliere $k$ più grande (o più piccolo) a seconda della probabilità di fallimento che siamo disposti a tollerare, come vedremo. Scegliere $k = n + 10$ garantirà una probabilità superiore al $99,9$% di recuperare $s.$

Eseguendo il circuito $k$ volte, otteniamo le stringhe $y^1,...,y^{k} \in \Sigma^n.$ Per essere chiari, gli apici qui sono parte dei nomi di queste stringhe, non esponenti o indici dei loro bit, quindi abbiamo

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

Ora formiamo una matrice $M$ con $k$ righe e $n$ colonne prendendo i bit di queste stringhe come elementi a valori binari.

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

A questo punto non sappiamo ancora cosa sia $s$ — il nostro obiettivo è trovare questa stringa. Ma immagina per un momento di conoscere la stringa $s,$ e formiamo un vettore colonna $v$ dai bit della stringa $s = s_{n-1} \cdots s_0$ come segue.

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

Se eseguiamo la moltiplicazione matrice-vettore $M v$ modulo $2$ — cioè eseguiamo la moltiplicazione normalmente e poi prendiamo il resto delle voci del risultato dopo la divisione per $2$ — otteniamo il vettore tutto-zero.

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

Cioè, trattata come vettore colonna $v$ come appena descritto, la stringa $s$ sarà sempre un elemento del nucleo (null space) della matrice $M,$ purché si faccia l'aritmetica modulo $2.$ Questo vale sia nel caso $s = 0^n$ che nel caso $s\neq 0^n.$ Per essere più precisi, il vettore tutto-zero è sempre nel nucleo di $M,$ e nel caso $s\neq 0^n$ si aggiunge il vettore le cui voci sono i bit di $s.$

La domanda rimanente è se ci saranno altri vettori nel nucleo di $M$ oltre a quelli corrispondenti a $0^n$ e $s.$ La risposta è che ciò diventa sempre meno probabile man mano che $k$ aumenta — e se scegliamo $k = n + 10,$ il nucleo di $M$ non conterrà altri vettori oltre a quelli corrispondenti a $0^n$ e $s$ con probabilità superiore al $99,9$%. Più in generale, se sostituiamo $k = n + 10$ con $k = n + r$ per una scelta arbitraria di un intero positivo $r,$ la probabilità che i vettori corrispondenti a $0^n$ e $s$ siano gli unici nel nucleo di $M$ è almeno $1 - 2^{-r}.$

Usando l'algebra lineare, è possibile calcolare efficientemente una descrizione del nucleo di $M$ modulo $2.$ Nello specifico, ciò può essere fatto usando l'eliminazione di Gauss, che funziona allo stesso modo quando l'aritmetica viene fatta modulo $2$ come con i numeri reali o complessi. Finché i vettori corrispondenti a $0^n$ e $s$ sono gli unici nel nucleo di $M,$ il che avviene con alta probabilità, possiamo dedurre $s$ dai risultati di questo calcolo.

Difficoltà classica

Quante query ha bisogno un algoritmo di query classico per risolvere il problema di Simon? La risposta è: molte, in generale.

Esistono diverse affermazioni precise che possono essere fatte sulla difficoltà classica di questo problema, ed ecco solo una di esse. Se abbiamo un qualsiasi algoritmo di query probabilistico, e quell'algoritmo fa meno di $2^{n/2 - 1} - 1$ query, che è un numero di query esponenziale in $n,$ allora quell'algoritmo fallirà nel risolvere il problema di Simon con probabilità almeno $1/2.$

A volte dimostrare risultati di impossibilità come questo può essere molto impegnativo, ma questo non è troppo difficile da dimostrare attraverso un'analisi probabilistica elementare. Qui, tuttavia, esamineremo solo brevemente l'intuizione di base che ci sta dietro.

Stiamo cercando di trovare la stringa nascosta $s,$ ma finché non interroghiamo la funzione su due stringhe che hanno lo stesso valore di output, otterremo informazioni molto limitate su $s.$ In modo intuitivo, tutto ciò che impareremo è che la stringa nascosta $s$ non è lo XOR esclusivo di nessuna coppia di stringhe distinte che abbiamo interrogato. E se interroghiamo meno di $2^{n/2 - 1} - 1$ stringhe, ci saranno ancora molte scelte per $s$ che non abbiamo escluso perché non ci sono abbastanza coppie di stringhe per farlo. Questa non è una dimostrazione formale, è solo l'idea di base.

Quindi, in sintesi, l'algoritmo di Simon ci fornisce un notevole vantaggio del quantum rispetto agli algoritmi classici nell'ambito del modello di query. In particolare, l'algoritmo di Simon risolve il problema di Simon con un numero di query lineare nel numero di bit di input $n$ della nostra funzione, mentre qualsiasi algoritmo classico, anche se probabilistico, ha bisogno di fare un numero di query esponenziale in $n$ per risolvere il problema di Simon con una ragionevole probabilità di successo.