Vai al contenuto principale

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:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m

per interi positivi nn e m.m. Potremmo limitarci al caso m=nm = 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:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m
Promessa: esiste una stringa s∈Σns\in\Sigma^n tale che [f(x)=f(y)]⇔[(x=y)∨(x⊕s=y)][f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)] per tutti x,y∈Σnx,y\in\Sigma^n
Output: la stringa ss

Analizzeremo la promessa tra poco per capire meglio cosa afferma, ma prima è importante chiarire che essa richiede che ff 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 ss sia la stringa tutta-zero 0n,0^n, e il secondo caso è che ss non sia la stringa tutta-zero.

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

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

È importante riconoscere che può esserci una sola stringa ss 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:Σ3→Σ5f:\Sigma^3 \rightarrow \Sigma^5 che soddisfa la promessa per la stringa s=011.s = 011.

f(000)=10011f(001)=00101f(010)=00101f(011)=10011f(100)=11010f(101)=00001f(110)=00001f(111)=11010\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 88 stringhe di input diverse e 44 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,011, il che equivale a dire che ognuna di esse è uguale all'altra messa in XOR con s.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,(10011, 00101,00101, 00001,00001, e 11010)11010) che appaiono come output di f.f. Potremmo sostituire queste quattro stringhe con stringhe diverse, purché siano tutte distinte, e la soluzione corretta s=011s = 011 non cambierebbe.

Descrizione dell'algoritmo​

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

Algoritmo di Simon

Per essere precisi, ci sono nn qubit in alto su cui agiscono i gate di Hadamard e mm 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 mm qubit in basso entrano tutti nel gate di query nello stato ∣0⟩.\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 nn qubit in alto, lo stato diventa

12n∑x∈Σn∣0m⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.

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

12n∑x∈Σn∣f(x)⟩∣x⟩.\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.

12n∑x∈Σn∑y∈Σn(−1)x⋅y∣f(x)⟩∣y⟩\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∈Σn.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)p(y) di ottenere la stringa yy è uguale a

p(y)=∥12n∑x∈Σn(−1)x⋅y∣f(x)⟩∥2.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 ff è l'insieme contenente tutte le sue stringhe di output.

range⁡(f)={f(x):x∈Σn}\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}

Poi, per ogni stringa z∈range⁡(f),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 zz come f−1({z}).f^{-1}(\{z\}).

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

L'insieme f−1({z})f^{-1}(\{z\}) è noto come la preimmagine di {z}\{z\} sotto f.f. Possiamo definire la preimmagine sotto ff di qualsiasi insieme al posto di {z}\{z\} in modo analogo — è l'insieme di tutti gli elementi che ff mappa in quell'insieme. (Questa notazione non va confusa con l'inversa della funzione f,f, che potrebbe non esistere. Il fatto che l'argomento sul lato sinistro sia l'insieme {z}\{z\} piuttosto che l'elemento zz è 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)=∥12n∑z∈range⁡(f)(∑x∈f−1({z})(−1)x⋅y)∣z⟩∥2.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∈Σnx\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)z = f(x) che producono quando valutiamo la funzione f,f, e poi sommando separatamente su tutti i secchi.

Ora possiamo calcolare il quadrato della norma euclidea per ottenere

p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2.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

∣∑x∈f−1({z})(−1)x⋅y∣2(1)\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}

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

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

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

∣∑x∈f−1({z})(−1)x⋅y∣2=∣(−1)w⋅y+(−1)(w⊕s)⋅y∣2=∣(−1)w⋅y(1+(−1)s⋅y)∣2=∣1+(−1)y⋅s∣2={4y⋅s=00y⋅s=1\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)(1) è indipendente dalla scelta specifica di z∈range⁡(f)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=0n.s = 0^n. In questo caso la funzione ff è iniettiva, quindi ci sono 2n2^n stringhe z∈range⁡(f),z\in\operatorname{range}(f), e otteniamo

    p(y)=122n⋅2n=12n.p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.

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

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

    p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2={12n−1y⋅s=00y⋅s=1p(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∈Σn:y⋅s=0},\{y\in\Sigma^n : y \cdot s = 0\}, che contiene 2n−12^{n-1} stringhe. (Poiché s≠0n,s\neq 0^n, esattamente la metà delle stringhe binarie di lunghezza nn ha prodotto scalare binario 11 con ss e l'altra metà ha prodotto scalare binario 00 con s,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 ss?

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,s, e possiamo usare tali prove per trovare ss con probabilità molto alta se eseguiamo il circuito un numero sufficiente di volte.

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

Eseguendo il circuito kk volte, otteniamo le stringhe y1,...,yk∈Σn.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

y1=yn−11⋯y01y2=yn−12⋯y02    ⋮yk=yn−1k⋯y0k\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 MM con kk righe e nn colonne prendendo i bit di queste stringhe come elementi a valori binari.

M=(yn−11⋯y01yn−12⋯y02⋮⋱⋮yn−1k⋯y0k)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 ss — il nostro obiettivo è trovare questa stringa. Ma immagina per un momento di conoscere la stringa s,s, e formiamo un vettore colonna vv dai bit della stringa s=sn−1⋯s0s = s_{n-1} \cdots s_0 come segue.

v=(sn−1⋮s0)v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}

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

Mv=(y1⋅sy2⋅s⋮yk⋅s)=(00⋮0)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 vv come appena descritto, la stringa ss sarà sempre un elemento del nucleo (null space) della matrice M,M, purché si faccia l'aritmetica modulo 2.2. Questo vale sia nel caso s=0ns = 0^n che nel caso s≠0n.s\neq 0^n. Per essere più precisi, il vettore tutto-zero è sempre nel nucleo di M,M, e nel caso s≠0ns\neq 0^n si aggiunge il vettore le cui voci sono i bit di s.s.

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

Usando l'algebra lineare, è possibile calcolare efficientemente una descrizione del nucleo di MM modulo 2.2. Nello specifico, ciò può essere fatto usando l'eliminazione di Gauss, che funziona allo stesso modo quando l'aritmetica viene fatta modulo 22 come con i numeri reali o complessi. Finché i vettori corrispondenti a 0n0^n e ss sono gli unici nel nucleo di M,M, il che avviene con alta probabilità, possiamo dedurre ss 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 2n/2−1−12^{n/2 - 1} - 1 query, che è un numero di query esponenziale in n,n, allora quell'algoritmo fallirà nel risolvere il problema di Simon con probabilità almeno 1/2.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,s, ma finché non interroghiamo la funzione su due stringhe che hanno lo stesso valore di output, otterremo informazioni molto limitate su s.s. In modo intuitivo, tutto ciò che impareremo è che la stringa nascosta ss non è lo XOR esclusivo di nessuna coppia di stringhe distinte che abbiamo interrogato. E se interroghiamo meno di 2n/2−1−12^{n/2 - 1} - 1 stringhe, ci saranno ancora molte scelte per ss 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 nn della nostra funzione, mentre qualsiasi algoritmo classico, anche se probabilistico, ha bisogno di fare un numero di query esponenziale in nn per risolvere il problema di Simon con una ragionevole probabilità di successo.