mateusz.czaplinski.pl - Notatki: Algorytm Shora

Spis treści: (ukryj)

1. Założenie
2. Redukcja problemu do zagadnienia szukania rzędu.
1. 2.1 Dlaczego szukać rzędu?
2. 2.2 Jak szukać rzędu?
3. Część kwantowa algorytmu Shora - szukanie okresu funkcji f.
4. Bibliografia
5. Brudnopis

1. Założenie

Mamy daną liczbę N, o której wiemy, że jest iloczynem dwóch liczb pierwszych N = pq.

Szukamy tych liczb pierwszych.

2. Redukcja problemu do zagadnienia szukania rzędu.

Df. Rzędem rz_n(a) liczby a modulo n nazywamy najmniejszą liczbę całkowitą r taką, że

$a^r \equiv 1 \; (\text{mod } n)$

(i jest dowód, że taka liczba istnieje).

2.1 Dlaczego szukać rzędu?

$a^r \equiv 1 \; (\text{mod } n) \Leftrightarrow \hspace{30}(1)\\ a^r -1 \equiv 0 \; (\text{mod } n) \Leftrightarrow$

$n \ | \ a^r -1$ (tzn. n dzieli a^r−1)

Jeżeli teraz znajdziemy r i będzie ono parzyste, to możemy rozbić

$a^r -1 = ( a^{\frac r2} -1 ) ( a^{\frac r2} +1 )$

(Nota: jeżeli r nieparzyste - startujemy od nowa.)

Ponieważ

$n \ | \ a^r -1 \Rightarrow\\ n \ | \ ( a^{\frac r2} -1 ) ( a^{\frac r2} +1 ) \Leftrightarrow\\ pq \ | \ ( a^{\frac r2} -1 ) ( a^{\frac r2} +1 ) \Leftrightarrow\\ kpq \ = \ ( a^{\frac r2} -1 ) ( a^{\frac r2} +1 ), \qquad k \in\mathbb{N}.$

Chcielibyśmy teraz mieć pewność, że jedno z wyrażeń w nawiasach jest równe p lub q. Pojawia się więc pytanie - czy liczby nie rozłożą się tak, że to n=pq będzie dzielić jedno z wyrażeń w nawiasach - i nic nie zyskamy?

Okazuje się, że dla pierwszego czynnika na pewno jest $n \not | ( a^{\frac r2} -1 )$ , gdyż w przeciwnym razie byłaby sprzeczność z (1). [rozwinąć w wolnym czasie]
Z kolei istnieje dowód, że z ponad 50%-owym prawdopodobieństwem również $n \not | ( a^{\frac r2} +1 )$ .

W takiej sytuacji mamy pewność (o ile akurat trafiliśmy), że jedna z szukanych liczb pierwszych (tzn. p lub q) jest NWD liczby n i jednego z nawiasów. (Jeżeli jednak wyjdzie nam, że wspomniane ok. 50% przyniosło nam pecha, będzie trzeba wystartować algorytm od nowa, z innym a.)

Wspomnieć trzeba przy okazji jaką wartość ma a. Otóż a bierzemy losowo ze zbioru liczb względnie pierwszych z rozgryzaną liczbą n:

$a \in \{ l\ :\ \text{NWD}(l,n) = 1 \}.$

Takich a zazwyczaj będzie dużo więcej niż jedno, więc jest z czego wybierać. Będziemy to (niestety) musieli często wykorzystywać, gdyż w algorytmie Shora jest wiele miejsc, gdzie szczęście może nam nie dopisać.

(Na marginesie: NWD jest bardzo łatwo znaleźć - stosuje się do tego algorytm Euklidesa).

2.2 Jak szukać rzędu?

Zagadnienie szukania rzędu z kolei przekształcimy do jeszcze innego problemu - szukania okresu funkcji

$f(x) = a^x\;(\text{mod }n), \quad x \in \mathbb{Z}$ .

Czemu możemy tak zrobić? Otóż z definicji rzędu możemy wysnuć taką równość:

$a^{x+kr} \;(\text{mod }n),\qquad k\in\mathbb{Z}\\ =a^x \underbrace{a^r}{}{}^k \;(\text{mod }n)\\ \overset{df}{=}a^x \cdot \overbrace{1}{}^k \;(\text{mod }n)\\ =a^x \;(\text{mod }n).$

Tak więc jeśli znajdziemy okres r funkcji f, to będziemy wiedzieć, że jest to jednocześnie szukany rząd:

$f(x+kr) = f(x) \Leftrightarrow$

$a^{x+kr} = a^x \;(\text{mod }n)$ - co analizujemy powyżej.

3. Część kwantowa algorytmu Shora - szukanie okresu funkcji f.

Pokazaliśmy wcześniej, że jeśli dla wybranej losowo liczby a znajdziemy okres r funkcji f=a^x (mod n), będziemy mogli (jeśli szczęście dopisze) rozwiązać nasz problem faktoryzacji. Jak więc znaleźć r? Tutaj wreszcie wykorzystamy właściwy komputer kwantowy.

3.1 Przygotowanie rejestru kwantowego

Do naszych obliczeń będziemy stosować rejestr kwantowy. Rejestr ten będzie zbudowany z 2m kubitów. Liczbę m wyznaczamy następująco:

Szukamy dowolnej liczby M, która jest potęgą dwójki, a jednocześnie spełnia warunek
$N^2 \leq M^2 < 2N^2.$ sprawdzić; czemu ma być mniejsza od 2N^2 ?
Liczba M jest potęgą dwójki - jej wykładnik bierzemy jako m - tzn. korzystamy z M=2^m.

Na początku ustawiamy rejestr w stan bazowy, w którym wszystkie kubity są wyzerowane:

$|\psi\rangle = |\underbrace{00...0}_m\rangle = |0\rangle^m.$

3.2 Rozszczepienie rejestru na M stanów.

Teraz korzystamy z q-kubitowej bramki Hadamarda, by w rejestrze kwantowym wygenerować superpozycję M stanów bazowych, odpowiadających kolejnym liczbom całkowitym od 0 do M−1

$U_M^H\ \otimes\ U_M^{\mathbb{1}}\ |0\rangle^m |0\rangle^m = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |0\rangle^m.$

3.3 Obliczenie wartości funkcji f dla liczb od 1 do M−1.

W tym kroku korzystamy z istotnej cechy komputera kwantowego, zgodnie z którą może on wykonywać obliczenia równolegle na wszystkich stanach bazowych. W naszym przypadku działaniem wykonywanym równolegle będzie obliczanie wartości funkcji f.

Aby wykonać wspomniane obliczenie, konieczne jest zbudowanie odpowiedniego obwodu kwantowego realizującego funkcję f. Okazuje się, że zadanie to wcale nie jest proste. Ponieważ jednak jest to temat "na osobną bajkę", w niniejszym rozważaniu pominiemy go; powiemy tylko, że da się to zrobić, a czytelnika odeślemy do opisu podanego przez Shora w jego pracy.

Obwód kwantowy realizujący funkcję f na potrzeby algorytmu Shora powinien być zbudowany tak, by wartość funkcji dla argumentu zakodowanego w pierwszej połowie rejestru kwantowego (kubity od 1 do m) znalazła się w drugiej połowie rejestru kwantowego (kubity od m+1 do 2m)

$U_{M^2}^f |x\rangle |0\rangle^m = |x\rangle |f(x)\rangle.$

Jeśli więc wykonamy tę operację na naszym rejestrze, dostaniemy

$U_{M^2}^f \; \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |0^m\rangle = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |f(x)\rangle.$

3.4 Kwantowa transformata Fouriera.

Po dokładniejszy, bardziej obrazowy opis kwantowej transformaty Fouriera (ang. QFT - quantum Fourier transform) odsyłam do osobnego artykułu. Mówiąc w skrócie, kw. t. F. jest operacją niemal identyczną do zwyczajnej dyskretnej transformaty Fouriera, tylko działającą na liczbach zakodowanych "binarnie" w rejestrze kwantowym. Tak więc

$U_{M}^{\text{QFT}} |x\rangle = \frac{1}{\sqrt{M}} \sum_{y=0}^{M-1} e^{xy\cdot 2\pi i/M} |y\rangle,$

gdzie i jest jednostką urojoną, $i^2 = -1$ . Dla ułatwienia interpretacji powyższego wzoru, możemy go przepisać do postaci

$U_{M}^{\text{QFT}} |x\rangle = \frac{1}{\sqrt{M}} \sum_{y=0}^{M-1} \omega^{xy} |y\rangle,\quad\quad\text{gdzie }\omega=e^{\frac{2\pi i}{M}}.$

$\opaque \picture(200,200){ %%osie%% (0,0){\longr[190]} (170,20){Re} (0,0){\longu[190]} (20,180){Im} %%rys.kata%% (8,9){\line(135,55){132}} (139,62){\line(-8,3)} (139,62){\line(-4,-7)} (8,9){\circle(160;0,20)} (83,36){\line(-3,-7)} (83,37){\line(7,-5)} %%opis kata%% (92,13){\theta=\frac{2\pi}{M}} %%jednostki%% (8,9){\circle(290;5,85)} (152,3){\line(0,12)} (157,13){1} (3,153){\line(12,0)} (13,157){i} }$
Rys.1. Liczba zespolona e^iθ, gdzie $\theta=\frac{2\pi}{M}$ , jako wektor na płaszczyźnie zespolonej. Zwróćmy uwagę, że ω jest liczbą zespoloną zapisaną w postaci wykładniczej. Liczbę zespoloną zapisaną tak właśnie (jako e^iθ) można bardzo łatwo zinterpretować geometrycznie, jako wektor na płaszczyźnie zespolonej, leżący pod kątem $\theta = \frac{2\pi}{M}$ do osi odciętych (na płaszczyźnie zespolonej nazywa się ją osią rzeczywistą). Dodatkowo, przy takim dokładnie zapisie jak powyżej, długość takiego wektora będzie równa 1 (zob. rys. 1). Zauważmy wreszcie, że skoro 2π jest kątem pełnym, to $\frac{2\pi}{M}$ jest wycinkiem powstałym z podziału koła na M równych części. Te wszystkie spostrzeżenia pomogą nam później zrozumieć cel zastosowania QFT w tym punkcie algorytmu.

Stosując kwantową transformatę Fouriera na pierwszej połowie naszego rejestru, przeprowadzamy go w stan

$U_M^{QFT}\ \otimes\ U_M^{\mathbb 1}\ |\psi\rangle = \frac{1}{M} \sum_{x=0}^{M-1} \sum_{y=0}^{M-1} \omega^{xy} |y\rangle |f(x)\rangle.$

3.5 Znaczenie QFT w algorytmie Shora

W komputerze kwantowym jedynym sposobem, w jaki możemy odczytać jakąkolwiek informację z rejestru kwantowego, jest jego obserwacja. A jedyną informacją, jaką odczytujemy podczas takiej obserwacji, jest amplituda $\alpha_x$ , czyli liczba stojąca przed jednym, wybranym przez nas wcześniej, stanem bazowym |x› rejestru. Po takiej obserwacji zawartość całego rejestru kwantowego niszczy się i staje bezużyteczna. Co więcej, obserwacja daje nam w rzeczywistości przybliżoną wartość $\alpha_x$ , tym lepszą, im więcej razy wykonamy obserwację (jest to bowiem tak na prawdę obserwacja prawdopodobieństwa). Dlatego większość algorytmów kwantowych, w tym także algorytm Shora, opiera się na takim ustawieniu amplitud, by już minimalna ilość obserwacji dała nam bardzo wartościową informację, pozwalającą kontynuować algorytm w jego części klasycznej.

4. Bibliografia

arxiv.org:quant-ph/9508027v2 Peter W. Shor (1996), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Mika Hirvensalo, Algorytmy kwantowe, WSiP 2004
Shor's algorithm w angielskojęzycznej Wikipedii
Wykład J.Preskilla z obliczeń kwantowych.
Stanisław Bednarek, skrypt Wstęp do informatyki kwantowej, AGH Kraków (niepublik.)

5. Brudnopis

The numbers a < N coprime to N (having no common factor with N) form a finite group under multiplication mod N. [Why? We need to establish that each element a has an inverse. But for given a < N coprime to N, each ab (mod N) is distinct, as b ranges over all b < N coprime to N ((If N divides ab - ab' , it must divide b - b' ). Therefore, for some b, we must have ab == 1 (mod N); hence the inverse of a exists.] Each element a of this finite group has a finite order r, the smallest positive integer such that

$a^r == 1\quad (\text{mod }N).$