Algorytm faktoryzacji Shora

Z Wikipedii

Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie O((log N)³) i pamięci 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 . Do tej pory jest to największe znane obliczenie kwantowe.

Spis treści 1 Procedura 1.1 Część klasyczna 1.2 Część kwantowa: Znajdowanie okresu funkcji 2 Analiza algorytmu 2.1 Część klasyczna 2.2 Część kwantowa 3 Literatura

[edytuj] Procedura

Na wejściu algorytmu dostajemy liczbę naturalną N. Naszym zadaniem jest znalezienie liczby p między 1 a N która dzieli N.

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.

[edytuj] Część klasyczna

1. Wylosuj liczbę a < N
2. Oblicz NWD(a, N) – na przykład za pomocą algorytmu Euklidesa.
3. Jeśli NWD(a, N) ≠ 1, to znaleźliśmy nietrywialny dzielnik N i możemy zakończyć.
4. W przeciwnym wypadku używamy podprocedury znajdującej okres funkcji (poniżej) dla znalezienia r – okresu następującej funkcji:

   ,

   (czyli znajdujemy najmniejsze r takie że f(x + r) = f(x)).
5. Jeśli r jest nieparzyste, wróć do punktu 1.
6. Jeśli a ^{r /2} ≡ -1 (mod N), wróć do punktu 1.
7. Dzielnikiem N jest NWD(a^{r /2} ± 1, N). Koniec algorytmu.

[edytuj] Część kwantowa: Znajdowanie okresu funkcji

1. Przygotuj dwa rejestry kwantowe: wejściowy i wyjściowy, każdy z log₂N kubitów, i zainicjuj je na stan:

   

   dla x od 0 do N - 1.
2. Skonstruuj układ realizujący funkcję f(x) w postaci kwantowej i zaaplikuj ją do powyższego stanu, otrzymując

   

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

   

   Efektem tej operacji będzie zatem stan:

   

4. Dokonaj pomiaru, otrzymując y w rejestrze wejściowym i f(x₀) w rejestrze wyjściowym. Ponieważ f jest okresowa, prawdopodobieństwo uzyskania pary y, f(x₀) wynosi:

   

   Można policzyć że to prawdopodobieństwo jest tym większe, im wartość yr/N jest bliższa liczbie całkowitej.
5. Przekształć y/N w nieskracalny ułamek i weź jego mianownik r′ jako kandydata na r.
6. Sprawdź czy f(x) = f(x + r′). Jeśli tak, algorytm jest zakończony.
7. Jeśli nie, sprawdź innych kandydatów na r przez użycie wartości blisko y, albo wielokrotności r′. Jeśli któryś z kandydatów działa, algorytm jest zakończony.
8. Jeśli nie udało się znaleźć dobrego r, wróć do punktu 1.

[edytuj] Analiza algorytmu

[edytuj] Część klasyczna

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

Zatem N | (a ^r − 1). Jeśli potrafimy obliczyć r i jest ono parzyste, to:

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

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

[edytuj] 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 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 f jako funkcji kwantowej. Używany do tego jest algorytm szybkiego potęgowania, w wersji modulo 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 O((logN)²) bramek.

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

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

e ^{− 2πibyr / N} = 1

dla dowolnego całkowitego b.

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

[edytuj] Literatura

Oryginalna praca Shora:

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

Podręcznik obliczeń kwantowych:

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

Implementacja algorytmu Shor's do faktoryzacji liczby 15:

• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance