Algorytm faktoryzacji Shora

Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie ${\displaystyle \mathrm {O} ((\log N)^{3})}$ i wykorzystując pamięć ${\displaystyle \mathrm {O} (\log N),}$ przy wykorzystaniu komputera kwantowego. Algorytm ten stanowi teoretyczne zagrożenie dla powszechnie używanego w internecie kryptosystemu RSA. Klucz publiczny w RSA jest iloczynem dwóch dużych liczb pierwszych. Możliwość efektywnego odtworzenia tych liczb na podstawie klucza publicznego pozwalałaby poznać klucz prywatny i tym samym złamać cały szyfr.

Jak większość algorytmów kwantowych, algorytm Shora jest algorytmem probabilistycznym: zwraca poprawną odpowiedź jedynie z pewnym prawdopodobieństwem. Ponieważ jednak odpowiedź może być szybko sprawdzona, powtarzanie algorytmu umożliwia uzyskanie poprawnej odpowiedzi w sposób efektywny z dowolnie dużym prawdopodobieństwem.

Algorytm ten opublikował Peter Shor w 1994 roku. W 2001 roku grupa informatyków z firmy IBM i Uniwersytetu Stanford zademonstrowała jego działanie na 7-kubitowym komputerze kwantowym opartym o jądrowy rezonans magnetyczny. Dokonano wtedy rozkładu liczby ${\displaystyle 15\ =\ 3\cdot 5}$^[1]. Faktoryzacji liczby ${\displaystyle 21}$ dokonano w 2011 roku^[2].

Procedura realizacji

Na wejściu algorytmu dostajemy liczbę naturalną ${\displaystyle N.}$ Naszym zadaniem jest znalezienie liczby ${\displaystyle p}$ między ${\displaystyle 1}$ a ${\displaystyle N,}$ która dzieli ${\displaystyle N}$ bez reszty.

Algorytm Shora składa się z dwóch części:

1. Sprowadzenia problemu faktoryzacji do problemu znajdowania rzędu elementu w grupie – realizowanego na klasycznym komputerze.
2. Znajdowania rzędu elementu za pomocą algorytmu kwantowego.

Część klasyczna

1. Wylosować liczbę ${\displaystyle a<N.}$
2. Obliczyć ${\displaystyle NWD(a,N)}$ – na przykład za pomocą algorytmu Euklidesa.
3. Jeśli ${\displaystyle NWD(a,N)\neq 1,}$ to został znaleziony nietrywialny dzielnik ${\displaystyle N}$ i można zakończyć część klasyczną.
4. W przeciwnym wypadku należy użyć podprocedury znajdującej ${\displaystyle r,}$ które jest okresem następującej funkcji:

   ${\displaystyle f(x)=a^{x}{\pmod {N}},}$

   czyli znaleźć najmniejsze naturalne ${\displaystyle r,}$ takie że ${\displaystyle f(x+r)=f(x).}$

5. Jeśli ${\displaystyle r}$ jest nieparzyste, wrócić do punktu 1.
6. Jeśli ${\displaystyle a^{r/2}\equiv -1{\pmod {N}},}$ wrócić do punktu 1.
7. Dzielnikiem ${\displaystyle N}$ jest ${\displaystyle NWD(a^{r/2}\pm 1,N).}$ Koniec algorytmu.

Część kwantowa: Znajdowanie okresu funkcji

1. Przygotować dwa rejestry kwantowe: wejściowy i wyjściowy, każdy z ${\displaystyle \log _{2}N}$ kubitów, i zainicjować je na stan:

   ${\displaystyle N^{-1/2}\sum _{x}|x\rangle \,|0\rangle }$

   dla ${\displaystyle x}$ od ${\displaystyle 0}$ do ${\displaystyle N-1.}$

2. Skonstruować układ realizujący funkcję ${\displaystyle f(x)}$ w postaci kwantowej i zaaplikować ją do powyższego stanu, otrzymując:

   ${\displaystyle N^{-1/2}\sum _{x}|x\rangle \,|f(x)\rangle }$

3. Zaaplikować odwróconą kwantową transformatę Fouriera do rejestru wejściowego. Transformata ta jest zdefiniowana wzorem:

   ${\displaystyle U_{QFT}\left|x\right\rangle =N^{-1/2}\sum _{y}e^{-2\pi ixy/N}\left|y\right\rangle }$

   Efektem tej operacji będzie zatem stan:

   ${\displaystyle N^{-1}\sum _{x}\sum _{y}e^{-2\pi ixy/N}\left|y\right\rangle \left|f(x)\right\rangle }$

4. Dokonać pomiaru, otrzymując ${\displaystyle y}$ w rejestrze wejściowym i ${\displaystyle f(x_{0})}$ w rejestrze wyjściowym.

   Ponieważ ${\displaystyle f}$ jest okresowa, prawdopodobieństwo uzyskania pary ${\displaystyle y,f(x_{0})}$ wynosi:

   ${\displaystyle \left|N^{-1}\sum _{x:\,f(x)=f(x_{0})}e^{-2\pi ixy/N}\right|^{2}=N^{-2}\left|\sum _{b}e^{-2\pi i(x_{0}+rb)y/N}\right|^{2}}$

   Można obliczyć, że to prawdopodobieństwo jest tym większe, im wartość ${\displaystyle yr/N}$ jest bliższa liczbie całkowitej.

5. Przekształcić ${\displaystyle y/N}$ w nieskracalny ułamek i wziąć jego mianownik ${\displaystyle r'}$ jako kandydata na ${\displaystyle r.}$
6. Sprawdzić czy ${\displaystyle f(x)=f(x+r').}$ Jeśli tak, algorytm jest zakończony.
7. Jeśli nie, sprawdź innych kandydatów na ${\displaystyle r,}$ przez użycie wartości blisko ${\displaystyle y,}$ albo wielokrotności ${\displaystyle r'.}$ Jeśli któryś z kandydatów działa, algorytm jest zakończony.
8. Jeśli nie udało się znaleźć dobrego ${\displaystyle r,}$ wróć do punktu 1.

Analiza algorytmu

Część klasyczna

Liczby naturalne mniejsze od ${\displaystyle N}$ i względnie pierwsze z ${\displaystyle N}$ z mnożeniem modulo ${\displaystyle N}$ tworzą grupę skończoną. Każdy element ${\displaystyle a}$ należący do tej grupy ma więc jakiś skończony rząd ${\displaystyle r}$ – najmniejszą liczbę dodatnią taką że:

${\displaystyle a^{r}\equiv 1{\pmod {N}}.}$

Zatem ${\displaystyle N|(a^{r}-1).}$ Jeśli potrafimy obliczyć ${\displaystyle r}$ i jest ono parzyste, to:

${\displaystyle a^{r}-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0{\pmod {N}}}$

${\displaystyle \Rightarrow N\ |(a^{r/2}-1)(a^{r/2}+1).}$

Skoro ${\displaystyle r}$ jest najmniejszą liczbą taką że ${\displaystyle a^{r}\equiv 1,}$ to ${\displaystyle N}$ nie może dzielić ${\displaystyle (a^{r/2}-1).}$ Jeśli ${\displaystyle N}$ nie dzieli również ${\displaystyle (a^{r/2}+1),}$ to ${\displaystyle N}$ musi mieć nietrywialny wspólny dzielnik z obiema liczbami: ${\displaystyle (a^{r/2}-1)}$ i ${\displaystyle (a^{r/2}+1).}$

Otrzymujemy w ten sposób jakąś faktoryzację ${\displaystyle N.}$ Jeśli ${\displaystyle N}$ jest iloczynem dwóch liczb pierwszych, jest to jego jedyna faktoryzacja.

Część kwantowa

Algorytm znajdowania okresu funkcji bazuje na zdolności komputera kwantowego do jednoczesnych obliczeń na wielu stanach. Obliczamy wartość funkcji jednocześnie dla wszystkich wartości ${\displaystyle x,}$ uzyskując superpozycję wszystkich wartości.

Fizyka kwantowa nie umożliwia nam jednak bezpośredniego odczytania tych informacji. Każdy pomiar niszczy superpozycję, pozwalając nam odczytać tylko jedną z wartości. Zamiast odczytywać te wartości, dokonujemy transformacji Fouriera – która zamienia wartości funkcji na wartości jej okresów. Późniejszy odczyt daje z dużym prawdopodobieństwem wartość bliską jakiemuś okresowi funkcji.

Do wykonania kwantowego algorytmu niezbędna jest kwantowa implementacja trzech operacji:

1. Stworzenia superpozycji stanów.

   Można tego łatwo dokonać aplikując bramki Hadamarda do wszystkich kubitów w rejestrze.

2. Funkcji ${\displaystyle f}$ jako funkcji kwantowej.

   Używany do tego jest algorytm szybkiego potęgowania, w wersji modulo ${\displaystyle N.}$ Należy zauważyć, że ten krok jest najtrudniejszy w implementacji, i wymaga dodatkowych kubitów i największej ilości kwantowych bramek logicznych.

3. Odwrotnej kwantowej transformacji Fouriera.

   Używając kontrolowanych bramek obrotu i bramek Hadamarda, Shor zaprojektował układ, który realizuje to przy użyciu ${\displaystyle \mathrm {O} ((\log N)^{2})}$ bramek.

Po zastosowaniu tych przekształceń, pomiar stanu rejestru da przybliżoną wartość okresu ${\displaystyle r.}$

Przykładowo załóżmy dla uproszczenia, że istnieje takie ${\displaystyle y,}$ że ${\displaystyle yr/N}$ jest całkowite. Wtedy prawdopodobieństwo uzyskania dobrego ${\displaystyle y}$ jest równe 1. Aby to pokazać, wystarczy zauważyć, że

${\displaystyle e^{-2\pi ibyr/N}=1}$

dla dowolnego całkowitego ${\displaystyle b.}$

Zatem suma czynników dających wartość ${\displaystyle y}$ będzie równa ${\displaystyle N/r,}$ bo istnieje ${\displaystyle N/r}$ różnych wartości ${\displaystyle b}$ dających ten sam wykładnik. Prawdopodobieństwo każdego takiego ${\displaystyle y}$ wynosi zatem ${\displaystyle 1/r^{2}.}$ Istnieje ${\displaystyle r}$ różnych ${\displaystyle y}$ takich, że ${\displaystyle yr/N}$ jest całkowite, oraz ${\displaystyle r}$ różnych możliwych wartości ${\displaystyle f(x_{0}).}$ W sumie prawdopodobieństwo uzyskania dobrego ${\displaystyle r}$ wynosi zatem 1.

Przypisy

Literatura

Oryginalna praca Shora:

Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. „SIAM J.Sci.Statist.Comput. 26”. 26 (5), s. 1484–1509, 30 Aug 1995 (arxiv) | 1997 (SIAM). DOI: 10.1137/S0097539795293172. arXiv:quant-ph/9508027. 

Podręcznik obliczeń kwantowych:

Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000

Linki zewnętrzne

• Scott Aaronson, "Shor, I’ll do it" (popularne objaśnienie algorytmu Shora) (ang.)