Algorytm Simona

Algorytm Simona to kwantowy algorytm zapytań rozwiązujący problem znany jako problem Simona. Jest to problem z obietnicą o podobnym charakterze do problemów Deutscha-Jozsy i Bernsteina-Vaziranego, jednak różniący się szczegółami.

Algorytm Simona jest istotny, ponieważ zapewnia wykładniczą przewagę algorytmów kwantowych nad klasycznymi (w tym probabilistycznymi), a zastosowana w nim technika zainspirowała Petera Shora do odkrycia wydajnego algorytmu kwantowego dla rozkładu liczb na czynniki pierwsze.

Simon's problem

Funkcja wejściowa dla problemu Simona ma postać

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

dla dodatnich liczb całkowitych $n$ i $m.$ Moglibyśmy dla prostoty ograniczyć się do przypadku $m = n,$ ale niewiele zyskujemy na tym założeniu — algorytm Simona i jego analiza są zasadniczo takie same w obu przypadkach.

Problem Simona

Wejście: funkcja $f:\Sigma^n \rightarrow \Sigma^m$
Obietnica: istnieje ciąg $s\in\Sigma^n$ taki, że $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ dla wszystkich $x,y\in\Sigma^n$
Wyjście: ciąg $s$

Za chwilę dokładniej przeanalizujemy obietnicę, żeby lepiej zrozumieć, co mówi — najpierw jednak zaznaczmy wyraźnie, że wymaga ona od $f$ bardzo szczególnej struktury, więc większość funkcji tej obietnicy nie spełni. Warto też przyznać, że ten problem nie ma na celu praktycznego zastosowania. Jest to raczej nieco sztuczny problem, skrojony na miarę tak, by był łatwy dla komputerów kwantowych i trudny dla klasycznych.

Istnieją dwa główne przypadki: pierwszy to taki, w którym $s$ jest ciągiem samych zer $0^n,$ a drugi — gdy $s$ nie jest ciągiem samych zer.

• Przypadek 1: $s=0^n.$ Jeśli $s$ jest ciągiem samych zer, możemy uprościć warunek „wtedy i tylko wtedy" w obietnicy do postaci $[f(x) = f(y)] \Leftrightarrow [x = y].$ Jest to równoważne temu, że $f$ jest funkcją różnowartościową.

• Przypadek 2: $s\neq 0^n.$ Jeśli $s$ nie jest ciągiem samych zer, to spełnienie obietnicy dla tego ciągu oznacza, że $f$ jest dwa-do-jednego (ang. two-to-one), tzn. dla każdego możliwego ciągu wyjściowego $f$ istnieją dokładnie dwa ciągi wejściowe, które powodują, że $f$ zwraca ten ciąg. Co więcej, te dwa ciągi wejściowe muszą mieć postać $w$ i $w \oplus s$ dla pewnego ciągu $w.$

Ważne jest, by zauważyć, że jeśli obietnica jest spełniona, to może istnieć tylko jeden ciąg $s,$ który działa — zatem dla funkcji spełniających obietnicę zawsze istnieje dokładnie jedna poprawna odpowiedź.

Oto przykład funkcji postaci $f:\Sigma^3 \rightarrow \Sigma^5$ spełniającej obietnicę dla ciągu $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}$$

Istnieje $8$ różnych ciągów wejściowych i $4$ różne ciągi wyjściowe, z których każdy pojawia się dwukrotnie — mamy więc funkcję dwa-do-jednego. Co więcej, dla dowolnych dwóch różnych ciągów wejściowych dających ten sam ciąg wyjściowy, bitowy XOR tych dwóch ciągów wejściowych jest równy $011,$ co jest równoważne temu, że każdy z nich jest równy drugiemu po XOR-owaniu z $s.$

Zauważmy, że jedyne, co ma znaczenie w przypadku faktycznych ciągów wyjściowych, to czy są one takie same, czy różne dla różnych wyborów ciągów wejściowych. Na przykład w powyższym przykładzie cztery ciągi $(10011,$ $00101,$ $00001$ i $11010)$ pojawiają się jako wyjścia $f.$ Moglibyśmy zastąpić te cztery ciągi innymi, o ile byłyby wszystkie różne, a poprawne rozwiązanie $s = 011$ nie uległoby zmianie.

Algorithm description

Oto diagram kwantowego Circuit reprezentującego algorytm Simona.

Dla jasności: na górze znajduje się $n$ qubitów, na które działają Gate'y Hadamarda, a na dole $m$ qubitów wchodzących bezpośrednio do bramki zapytania (query gate). Wygląda to bardzo podobnie do algorytmów omawianych już w tej lekcji, ale tym razem nie ma phase kickback; dolne $m$ qubitów wchodzi do bramki zapytania w stanie $\vert 0\rangle.$

Rozwiązanie problemu Simona przy użyciu tego Circuit wymaga w praktyce kilku niezależnych jego uruchomień, a następnie etapu klasycznego przetwarzania końcowego, który zostanie opisany później, po przeanalizowaniu zachowania Circuit.

Analiza

Analiza algorytmu Simona przebiega początkowo podobnie jak w przypadku algorytmu Deutscha-Jozsy. Po wykonaniu pierwszej warstwy Hadamard gates na górnych $n$ qubitach stan przyjmuje postać

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

Po wykonaniu $U_f$ wyjście funkcji $f$ jest XORowane na stan zerowy dolnych $m$ qubitów, więc stan staje się

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

Po wykonaniu drugiej warstwy Hadamard gates, korzystając z tego samego wzoru na działanie warstwy Hadamard gates co poprzednio, otrzymujemy następujący stan.

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

W tym momencie analiza rozchodzi się z analizami poprzednich algorytmów z tej lekcji.

Interesuje nas prawdopodobieństwo, że pomiary dadzą każdy możliwy ciąg $y\in\Sigma^n.$ Korzystając z reguł analizowania pomiarów opisanych w lekcji Układy złożone kursu Podstawy informacji kwantowej, stwierdzamy, że prawdopodobieństwo $p(y)$ uzyskania ciągu $y$ wynosi

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

Aby lepiej zrozumieć te prawdopodobieństwa, potrzebujemy odrobiny dodatkowej notacji i terminologii. Po pierwsze, dziedzina obrazu funkcji $f$ to zbiór zawierający wszystkie jej ciągi wyjściowe.

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

Po drugie, dla każdego ciągu $z\in\operatorname{range}(f)$ możemy wyrazić zbiór wszystkich ciągów wejściowych, dla których funkcja przyjmuje wartość $z$, jako $f^{-1}(\{z\}).$

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

Zbiór $f^{-1}(\{z\})$ jest nazywany przeciwobrazem $\{z\}$ pod $f.$ Analogicznie możemy zdefiniować przeciwobraz pod $f$ dowolnego zbioru zamiast $\{z\}$ — jest to zbiór wszystkich elementów, które $f$ odwzorowuje na ten zbiór. (Tej notacji nie należy mylić z odwrotnością funkcji $f,$ która może nie istnieć. Fakt, że argument po lewej stronie to zbiór $\{z\}$, a nie element $z$, pozwala uniknąć tej pomyłki.)

Korzystając z tej notacji, możemy rozdzielić sumę w powyższym wyrażeniu na prawdopodobieństwa i uzyskać

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

Każdy ciąg $x\in\Sigma^n$ jest reprezentowany dokładnie raz przez obie sumy — zasadniczo umieszczamy te ciągi w oddzielnych „koszyczkach" zależnie od tego, który ciąg wyjściowy $z = f(x)$ produkują po obliczeniu funkcji $f$, a następnie sumujemy osobno po wszystkich koszyczkach.

Możemy teraz obliczyć kwadrat normy euklidesowej i otrzymać

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

Aby jeszcze bardziej uprościć te prawdopodobieństwa, przyjrzyjmy się wartości

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

dla dowolnie wybranego $z\in\operatorname{range}(f).$

Jeśli $s = 0^n,$ to $f$ jest funkcją różnowartościową i dla każdego $z\in\operatorname{range}(f)$ istnieje dokładnie jeden element $x\in f^{-1}(\{z\}).$ Wartość wyrażenia $(1)$ wynosi wtedy $1$.

Jeśli natomiast $s\neq 0^n,$ to w zbiorze $f^{-1}(\{z\})$ są dokładnie dwa ciągi. Dokładniej: jeśli wybierzemy $w\in f^{-1}(\{z\})$ jako jeden z tych dwóch ciągów, to drugim ciągiem musi być $w \oplus s$ zgodnie z założeniem problemu Simona. Korzystając z tej obserwacji, możemy uprościć $(1)$ w następujący sposób.

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

Okazuje się zatem, że wartość $(1)$ jest niezależna od konkretnego wyboru $z\in\operatorname{range}(f)$ w obu przypadkach.

Możemy teraz dokończyć analizę, rozpatrując osobno te same dwa przypadki co poprzednio.

• Przypadek 1: $s = 0^n.$ W tym przypadku funkcja $f$ jest różnowartościowa, więc istnieje $2^n$ ciągów $z\in\operatorname{range}(f)$ i otrzymujemy

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

  Innymi słowy, pomiary dają ciąg $y\in\Sigma^n$ wybrany jednostajnie losowo.

• Przypadek 2: $s \neq 0^n.$ W tym przypadku $f$ jest funkcją dwu-do-jednego, więc $\operatorname{range}(f)$ zawiera $2^{n-1}$ elementów. Korzystając z powyższego wzoru, wnioskujemy, że prawdopodobieństwo zmierzenia każdego $y\in\Sigma^n$ wynosi

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

  Innymi słowy, otrzymujemy ciąg wybrany jednostajnie losowo ze zbioru $\{y\in\Sigma^n : y \cdot s = 0\},$ który zawiera $2^{n-1}$ ciągów. (Ponieważ $s\neq 0^n,$ dokładnie połowa ciągów binarnych długości $n$ ma binarny iloczyn skalarny $1$ z $s$, a pozostałe mają binarny iloczyn skalarny $0$ z $s$, co już zaobserwowaliśmy w analizie algorytmu Deutscha-Jozsy dla problemu Bernsteina-Vaziraniego.)

Klasyczne przetwarzanie końcowe

Wiemy już, jakie są prawdopodobieństwa możliwych wyników pomiarów podczas uruchamiania układu kwantowego dla algorytmu Simona. Czy to wystarczy, aby wyznaczyć $s$?

Odpowiedź brzmi: tak, pod warunkiem że jesteśmy gotowi kilkukrotnie powtórzyć proces i zaakceptować, że może on zakończyć się niepowodzeniem z pewnym prawdopodobieństwem, które możemy uczynić bardzo małym, uruchamiając układ wystarczająco wiele razy. Podstawowy pomysł polega na tym, że każde wykonanie układu dostarcza nam statystycznych dowodów dotyczących $s,$ a na ich podstawie możemy znaleźć $s$ z bardzo dużym prawdopodobieństwem, jeśli uruchomimy układ odpowiednio wiele razy.

Załóżmy, że uruchamiamy układ niezależnie $k$ razy, gdzie $k = n + 10.$ Ta konkretna liczba iteracji nie ma nic szczególnego — możemy wybrać większe (lub mniejsze) $k$ w zależności od tego, jakie prawdopodobieństwo błędu jesteśmy w stanie zaakceptować, co zobaczymy dalej. Wybór $k = n + 10$ zapewni nam ponad $99{,}9$% szansę na odzyskanie $s.$

Uruchamiając układ $k$ razy, otrzymujemy ciągi $y^1,...,y^{k} \in \Sigma^n.$ Dla jasności: indeksy górne są tutaj częścią nazw tych ciągów, a nie wykładnikami ani indeksami bitów, więc mamy

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

Tworzymy teraz macierz $M$ o $k$ wierszach i $n$ kolumnach, przyjmując bity tych ciągów jako wartości binarne wpisów.

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

W tym momencie nie znamy jeszcze $s$ — naszym celem jest właśnie znalezienie tego ciągu. Wyobraź sobie jednak na chwilę, że znamy ciąg $s$ i tworzymy wektor kolumnowy $v$ z bitów ciągu $s = s_{n-1} \cdots s_0$ w następujący sposób.

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

Jeśli wykonamy mnożenie macierzy przez wektor $M v$ modulo $2$ — tzn. wykonamy mnożenie w zwykły sposób, a następnie weźmiemy reszty z dzielenia przez $2$ dla każdego wpisu wyniku — otrzymamy wektor zerowy.

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

Innymi słowy, potraktowany jako wektor kolumnowy $v$ w sposób opisany powyżej, ciąg $s$ zawsze będzie elementem jądra macierzy $M,$ pod warunkiem że wykonujemy arytmetykę modulo $2.$ Jest to prawdziwe zarówno w przypadku $s = 0^n,$ jak i $s\neq 0^n.$ Mówiąc precyzyjniej, wektor zerowy zawsze należy do jądra $M,$ a w przypadku $s\neq 0^n$ dołącza do niego wektor, którego wpisy są bitami $s.$

Pozostaje pytanie, czy w jądrze $M$ pojawią się jakieś inne wektory oprócz tych odpowiadających $0^n$ i $s.$ Odpowiedź jest taka, że staje się to coraz mniej prawdopodobne wraz ze wzrostem $k$ — a jeśli wybierzemy $k = n + 10,$ jądro macierzy $M$ nie będzie zawierać żadnych innych wektorów poza tymi odpowiadającymi $0^n$ i $s$ z prawdopodobieństwem większym niż $99{,}9$%. Mówiąc ogólniej, jeśli zastąpimy $k = n + 10$ przez $k = n + r$ dla dowolnie wybranej dodatniej liczby całkowitej $r,$ prawdopodobieństwo, że wektory odpowiadające $0^n$ i $s$ są jedynymi elementami jądra $M,$ wynosi co najmniej $1 - 2^{-r}.$

Używając algebry liniowej, można efektywnie obliczyć opis jądra macierzy $M$ modulo $2.$ Konkretnie, można to zrobić za pomocą eliminacji Gaussa, która działa tak samo, gdy arytmetyka jest wykonywana modulo $2,$ jak w przypadku liczb rzeczywistych lub zespolonych. Dopóki wektory odpowiadające $0^n$ i $s$ są jedynymi elementami jądra $M$ — co zachodzi z dużym prawdopodobieństwem — możemy na podstawie wyników tego obliczenia wyznaczyć $s.$

Klasyczna trudność

Ile zapytań potrzebuje klasyczny algorytm z wyroczną, aby rozwiązać problem Simona? Odpowiedź brzmi: generalnie bardzo dużo.

Istnieje kilka precyzyjnych sformułowań dotyczących klasycznej trudności tego problemu — oto jedno z nich. Jeśli mamy dowolny probabilistyczny algorytm z wyroczną, który wykonuje mniej niż $2^{n/2 - 1} - 1$ zapytań — czyli liczbę zapytań wykładniczą względem $n$ — to algorytm ten nie rozwiąże problemu Simona z prawdopodobieństwem co najmniej $1/2.$

Udowodnienie takich twierdzeń o niemożności bywa niekiedy bardzo trudne, ale to konkretne można wykazać stosunkowo prosto za pomocą elementarnej analizy probabilistycznej. Tutaj jednak tylko pokrótce zarysujemy podstawową intuicję stojącą za tym wynikiem.

Staramy się znaleźć ukryty ciąg $s,$ ale dopóki nie zapytamy wyroczni o dwa ciągi dające tę samą wartość funkcji, będziemy mieć bardzo ograniczone informacje na temat $s.$ Intuicyjnie mówiąc, dowiemy się jedynie, że ukryty ciąg $s$ nie jest XOR-em żadnej pary różnych ciągów, o które zapytaliśmy. A jeśli zapytamy o mniej niż $2^{n/2 - 1} - 1$ ciągów, nadal pozostanie wiele możliwych wartości $s,$ których nie wykluczyliśmy, bo nie ma wystarczająco wielu par ciągów, by to zrobić. To nie jest formalny dowód — to tylko podstawowy pomysł.

Podsumowując, algorytm Simona daje nam uderzającą przewagę algorytmów kwantowych nad klasycznymi w modelu z wyroczną.