Algoritmul lui Simon

Algoritmul lui Simon este un algoritm cuantic de interogare pentru o problemă cunoscută sub numele de problema lui Simon. Aceasta este o problemă cu promisiune, cu o structură similară problemelor Deutsch-Jozsa și Bernstein-Vazirani, dar cu detalii diferite.

Algoritmul lui Simon este semnificativ deoarece oferă un avantaj exponențial al calculului cuantic față de cel clasic (inclusiv probabilistic), iar tehnica pe care o folosește l-a inspirat pe Peter Shor să descopere un algoritm cuantic eficient pentru factorizarea numerelor întregi.

Problema lui Simon

Funcția de intrare pentru problema lui Simon are forma

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

pentru numerele întregi pozitive $n$ și $m.$ Am putea restrânge atenția la cazul $m = n$ în interesul simplității, dar nu există mare câștig în a face această presupunere — algoritmul lui Simon și analiza sa sunt practic aceleași în ambele situații.

Problema lui Simon

Intrare: o funcție $f:\Sigma^n \rightarrow \Sigma^m$
Promisiune: există un șir $s\in\Sigma^n$ astfel încât $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ pentru orice $x,y\in\Sigma^n$
Ieșire: șirul $s$

Vom desface promisiunea pentru a înțelege mai bine ce spune imediat, dar mai întâi să fie clar că aceasta necesită ca $f$ să aibă o structură foarte specială — astfel, majoritatea funcțiilor nu vor satisface această promisiune. Este, de asemenea, potrivit să recunoaștem că această problemă nu este menită să aibă importanță practică. Mai degrabă, este o problemă oarecum artificială, concepută special pentru a fi ușoară pentru calculatoarele cuantice și dificilă pentru cele clasice.

Există două cazuri principale: primul caz este că $s$ este șirul de zerouri $0^n,$ iar al doilea caz este că $s$ nu este șirul de zerouri.

• Cazul 1: $s=0^n.$ Dacă $s$ este șirul de zerouri, putem simplifica enunțul de tip dacă și numai dacă din promisiune, astfel încât să citim $[f(x) = f(y)] \Leftrightarrow [x = y].$ Aceasta este echivalentă cu faptul că $f$ este o funcție injectivă.

• Cazul 2: $s\neq 0^n.$ Dacă $s$ nu este șirul de zerouri, atunci satisfacerea promisiunii pentru acest șir implică că $f$ este doi-la-unu, adică pentru fiecare șir de ieșire posibil al lui $f,$ există exact două șiruri de intrare care determină $f$ să producă acel șir. Mai mult, aceste două șiruri de intrare trebuie să aibă forma $w$ și $w \oplus s$ pentru un anume șir $w.$

Este important să recunoaștem că poate exista un singur șir $s$ care funcționează dacă promisiunea este îndeplinită, deci există întotdeauna un răspuns corect unic pentru funcțiile care satisfac promisiunea.

Iată un exemplu de funcție cu forma $f:\Sigma^3 \rightarrow \Sigma^5$ care satisface promisiunea pentru șirul $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}$$

Există $8$ șiruri de intrare diferite și $4$ șiruri de ieșire diferite, fiecare apărând de două ori — deci aceasta este o funcție doi-la-unu. Mai mult, pentru oricare două șiruri de intrare diferite care produc același șir de ieșire, observăm că XOR-ul bit cu bit al acestor două șiruri de intrare este egal cu $011,$ ceea ce este echivalent cu a spune că oricare dintre ele este egal cu celălalt XOR-at cu $s.$

Observă că singurul lucru care contează despre șirurile de ieșire efective este dacă sunt aceleași sau diferite pentru diferite alegeri de șiruri de intrare. De exemplu, în exemplul de mai sus, există patru șiruri $(10011,$ $00101,$ $00001,$ și $11010)$ care apar ca ieșiri ale lui $f.$ Am putea înlocui aceste patru șiruri cu șiruri diferite, atâta timp cât sunt toate distincte, iar soluția corectă $s = 011$ nu s-ar schimba.

Descrierea algoritmului

Iată o diagramă de Circuit cuantic care reprezintă algoritmul lui Simon.

Pentru a fi clar, există $n$ Qubiți în partea de sus care sunt acționați de Gate-uri Hadamard și $m$ Qubiți în partea de jos care intră direct în Gate-ul de interogare. Arată foarte similar cu algoritmii pe care i-am discutat deja în lecție, dar de data aceasta nu există kickback de fază; cei $m$ Qubiți din partea de jos intră în Gate-ul de interogare în starea $\vert 0\rangle.$

Rezolvarea problemei lui Simon folosind acest Circuit va necesita de fapt mai multe rulări independente ale acestuia, urmate de un pas de procesare clasică, care va fi descris ulterior după ce comportamentul Circuit-ului este analizat.

Analiză

Analiza algoritmului lui Simon începe în mod similar cu algoritmul Deutsch-Jozsa. După ce primul strat de porți Hadamard este aplicat pe cei $n$ qubiți superiori, starea devine

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

Când se aplică $U_f$, rezultatul funcției $f$ este aplicat prin XOR pe starea zero a celor $m$ qubiți inferiori, astfel că starea devine

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

Când se aplică al doilea strat de porți Hadamard, obținem starea de mai jos folosind aceeași formulă pentru acțiunea unui strat de porți Hadamard ca înainte.

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

În acest punct, analiza diverge față de cele ale algoritmilor precedenți din această lecție.

Suntem interesați de probabilitatea ca măsurătorile să producă fiecare șir posibil $y\in\Sigma^n.$ Prin regulile de analiză a măsurătorilor descrise în lecția Sisteme multiple din cursul Noțiuni de bază ale informației cuantice, găsim că probabilitatea $p(y)$ de a obține șirul $y$ este egală cu

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

Pentru a înțelege mai bine aceste probabilități, avem nevoie de puțină notație și terminologie suplimentară. Mai întâi, imaginea funcției $f$ este mulțimea care conține toate șirurile de ieșire ale acesteia.

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

În al doilea rând, pentru fiecare șir $z\in\operatorname{range}(f),$ putem exprima mulțimea tuturor șirurilor de intrare care determină funcția să evalueze la acest șir de ieșire $z$ ca $f^{-1}(\{z\}).$

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

Mulțimea $f^{-1}(\{z\})$ este cunoscută sub numele de preimaginea lui $\{z\}$ prin $f.$ Putem defini preimaginea prin $f$ a oricărei mulțimi în locul lui $\{z\}$ în mod analog — este mulțimea tuturor elementelor pe care $f$ le mapează în acea mulțime. (Această notație nu trebuie confundată cu inversa funcției $f,$ care s-ar putea să nu existe. Faptul că argumentul din stânga este mulțimea $\{z\}$ și nu elementul $z$ este indiciul care ne permite să evităm această confuzie.)

Folosind această notație, putem descompune suma din expresia noastră pentru probabilitățile de mai sus pentru a obține

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

Fiecare șir $x\in\Sigma^n$ este reprezentat exact o dată de cele două sume — practic grupăm aceste șiruri în compartimente separate în funcție de șirul de ieșire $z = f(x)$ pe care îl produc la evaluarea funcției $f,$ și apoi facem suma separat pentru fiecare compartiment.

Putem acum calcula norma euclidiană la pătrat pentru a obține

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

Pentru a simplifica și mai mult aceste probabilități, să analizăm valoarea

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

pentru o selecție arbitrară a lui $z\in\operatorname{range}(f).$

Dacă se întâmplă ca $s = 0^n,$ atunci $f$ este o funcție injectivă și există întotdeauna un singur element $x\in f^{-1}(\{z\}),$ pentru orice $z\in\operatorname{range}(f).$ Valoarea expresiei $(1)$ este $1$ în acest caz.

Dacă, pe de altă parte, $s\neq 0^n,$ atunci există exact două șiruri în mulțimea $f^{-1}(\{z\}).$ Mai precis, dacă alegem $w\in f^{-1}(\{z\})$ ca oricare dintre aceste două șiruri, atunci celălalt șir trebuie să fie $w \oplus s$ conform promisiunii din problema lui Simon. Folosind această observație, putem simplifica $(1)$ astfel.

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

Deci, se dovedește că valoarea $(1)$ este independentă de alegerea specifică a lui $z\in\operatorname{range}(f)$ în ambele cazuri.

Putem acum finaliza analiza examinând separat aceleași două cazuri ca înainte.

• Cazul 1: $s = 0^n.$ În acest caz funcția $f$ este injectivă, deci există $2^n$ șiruri $z\in\operatorname{range}(f),$ și obținem

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

  Cu alte cuvinte, măsurătorile produc un șir $y\in\Sigma^n$ ales uniform la întâmplare.

• Cazul 2: $s \neq 0^n.$ În acest caz $f$ este două-la-unu, deci există $2^{n-1}$ elemente în $\operatorname{range}(f).$ Folosind formula de mai sus, concluzionăm că probabilitatea de a măsura fiecare $y\in\Sigma^n$ este

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

  Cu alte cuvinte, obținem un șir ales uniform la întâmplare din mulțimea $\{y\in\Sigma^n : y \cdot s = 0\},$ care conține $2^{n-1}$ șiruri. (Deoarece $s\neq 0^n,$ exact jumătate dintre șirurile binare de lungime $n$ au produsul scalar binar $1$ cu $s$ iar celelalte au produsul scalar binar $0$ cu $s,$ după cum am observat deja în analiza algoritmului Deutsch-Jozsa pentru problema Bernstein-Vazirani.)

Postprocesare clasică

Știm acum care sunt probabilitățile pentru rezultatele posibile ale măsurătorii atunci când rulăm circuitul cuantic pentru algoritmul lui Simon. Este suficientă această informație pentru a determina $s$?

Răspunsul este da, cu condiția să fim dispuși să repetăm procesul de mai multe ori și să acceptăm că ar putea eșua cu o anumită probabilitate, pe care o putem face foarte mică rulând circuitul de suficient de multe ori. Ideea esențială este că fiecare execuție a circuitului ne oferă dovezi statistice cu privire la $s,$ iar putem folosi acele dovezi pentru a găsi $s$ cu o probabilitate foarte mare dacă rulăm circuitul de suficient de multe ori.

Să presupunem că rulăm circuitul independent de $k$ ori, pentru $k = n + 10.$ Nu există nimic special în legătură cu acest număr particular de iterații — am putea lua $k$ mai mare (sau mai mic) în funcție de probabilitatea de eșec pe care suntem dispuși să o tolerăm, după cum vom vedea. Alegând $k = n + 10$ ne vom asigura că avem o șansă mai mare de $99.9$% de a recupera $s.$

Rulând circuitul de $k$ ori, obținem șirurile $y^1,...,y^{k} \in \Sigma^n.$ Pentru a fi clari, supraindexurile de aici fac parte din numele acestor șiruri, nu sunt exponenți sau indici ai biților lor, deci avem

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

Formăm acum o matrice $M$ cu $k$ rânduri și $n$ coloane, luând biții acestor șiruri ca intrări cu valori binare.

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

Acum, nu știm ce este $s$ în acest moment — scopul nostru este să găsim acest șir. Dar imaginează-ți pentru o clipă că știm șirul $s,$ și formăm un vector coloană $v$ din biții șirului $s = s_{n-1} \cdots s_0$ după cum urmează.

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

Dacă efectuăm înmulțirea matrice-vector $M v$ modulo $2$ — adică efectuăm înmulțirea ca de obicei și apoi luăm restul intrărilor rezultatului după împărțirea la $2$ — obținem vectorul format din zerouri.

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

Adică, tratat ca vector coloană $v$ descris mai sus, șirul $s$ va fi întotdeauna un element al spațiului nul al matricei $M,$ cu condiția să facem aritmetica modulo $2.$ Acest lucru este adevărat atât în cazul în care $s = 0^n$, cât și în cazul în care $s\neq 0^n.$ Mai precis, vectorul format din zerouri se află întotdeauna în spațiul nul al lui $M,$ și i se alătură vectorul ale cărui intrări sunt biții lui $s$ în cazul în care $s\neq 0^n.$

Întrebarea rămasă este dacă vor exista alți vectori în spațiul nul al lui $M$ în afara celor corespunzători lui $0^n$ și $s.$ Răspunsul este că acest lucru devine din ce în ce mai puțin probabil pe măsură ce $k$ crește — și dacă alegem $k = n + 10,$ spațiul nul al lui $M$ nu va conține niciun alt vector în afara celor corespunzători lui $0^n$ și $s$ cu o șansă mai mare de $99.9$%. Mai general, dacă înlocuim $k = n + 10$ cu $k = n + r$ pentru o alegere arbitrară a unui număr întreg pozitiv $r,$ probabilitatea ca vectorii corespunzători lui $0^n$ și $s$ să fie singuri în spațiul nul al lui $M$ este de cel puțin $1 - 2^{-r}.$

Folosind algebra liniară, este posibil să calculăm eficient o descriere a spațiului nul al lui $M$ modulo $2.$ Mai precis, se poate face folosind eliminarea gaussiană, care funcționează la fel când aritmetica se face modulo $2$ ca și cu numere reale sau complexe. Atât timp cât vectorii corespunzători lui $0^n$ și $s$ sunt singuri în spațiul nul al lui $M,$ ceea ce se întâmplă cu probabilitate mare, putem deduce $s$ din rezultatele acestui calcul.

Dificultatea clasică

Câte interogări are nevoie un algoritm de interogare clasic pentru a rezolva problema lui Simon? Răspunsul este: multe, în general.

Există diferite afirmații precise care pot fi făcute despre dificultatea clasică a acestei probleme, și iată doar una dintre ele. Dacă avem orice algoritm de interogare probabilistic, iar acel algoritm face mai puțin de $2^{n/2 - 1} - 1$ interogări, ceea ce reprezintă un număr de interogări exponențial în $n,$ atunci acel algoritm va eșua în a rezolva problema lui Simon cu o probabilitate de cel puțin $1/2.$

Uneori, dovedirea unor rezultate de imposibilitate ca acesta poate fi foarte dificilă, dar acesta nu este prea greu de dovedit printr-o analiză probabilistică elementară. Totuși, aici vom examina doar pe scurt intuiția de bază din spatele lui.

Încercăm să găsim șirul ascuns $s,$ dar atât timp cât nu interogăm funcția pe două șiruri care au aceeași valoare de ieșire, vom obține informații foarte limitate despre $s.$ Intuitiv vorbind, tot ce vom afla este că șirul ascuns $s$ nu este SAU-ul exclusiv al niciunor două șiruri distincte pe care le-am interogat. Iar dacă interogăm mai puțin de $2^{n/2 - 1} - 1$ șiruri, vor exista în continuare multe alegeri pentru $s$ pe care nu le-am exclus deoarece nu există suficiente perechi de șiruri pentru a face asta. Acesta nu este un proof formal, este doar ideea de bază.

Deci, în rezumat, algoritmul lui Simon ne oferă un avantaj remarcabil al calculului cuantic față de algoritmii clasici în cadrul modelului de interogare. În particular, algoritmul lui Simon rezolvă problema lui Simon cu un număr de interogări liniar în numărul de biți de intrare $n$ ai funcției noastre, în timp ce orice algoritm clasic, chiar dacă este probabilistic, trebuie să facă un număr de interogări exponențial în $n$ pentru a rezolva problema lui Simon cu o probabilitate rezonabilă de succes.