Algorytm faktoryzacji Shora

Kwantowy algorytm Shora

Algorytm kwantowy Shora jest zdolny do rozkładu liczby naturalnej N na czynniki pierwsze w czasie

O((log N)³)

oraz wykorzystuje pamięć

O(log N),

operując na komputerze kwantowym. Stanowi on teoretyczne zagrożenie dla powszechnie stosowanego w internecie systemu kryptograficznego RSA. Klucz publiczny w tym systemie jest iloczynem dwóch dużych liczb pierwszych. Efektywne odtworzenie tych liczb na podstawie klucza publicznego umożliwiałoby poznanie klucza prywatnego i złamanie szyfru.

Jak wiele algorytmów kwantowych, algorytm Shora jest algorytmem probabilistycznym, co oznacza, że zwraca poprawną odpowiedź jedynie z określonym prawdopodobieństwem. Niemniej jednak, ponieważ odpowiedź może być szybko weryfikowana, powtarzanie algorytmu pozwala na uzyskanie poprawnej odpowiedzi z dowolnie dużym prawdopodobieństwem.

Algorytm ten został opublikowany przez Petera Shora w 1994 roku. W 2001 roku zespół informatyków z firmy IBM oraz Uniwersytetu Stanford zademonstrował jego działanie na 7-kubitowym komputerze kwantowym opartym na jądrowym rezonansie magnetycznym, dokonując rozkładu liczby

15 = 3 ⋅ 5. Faktoryzacja liczby

21 miała miejsce w 2011 roku.

Procedura realizacji

Na początku algorytmu wprowadzamy liczbę naturalną N. Naszym celem jest znalezienie liczby p w zakresie od 1 do N, która dzieli N bez reszty.

Algorytm Shora składa się z dwóch głównych etapów:

Sprowadzenia problemu faktoryzacji do problemu znajdowania rzędu elementu w grupie, co realizowane jest na komputerze klasycznym.
Wyznaczenia rzędu elementu przy użyciu algorytmu kwantowego.

Część klasyczna

Na początku losujemy liczbę a, gdzie a < N. Następnie obliczamy NWD(a, N) – na przykład za pomocą algorytmu Euklidesa.

Jeżeli NWD(a, N) ≠ 1, to znaleziono nietrywialny dzielnik N i część klasyczna może zostać zakończona.

W przeciwnym razie, trzeba skorzystać z podprocedury, aby znaleźć r, czyli okres funkcji:

f(x) = a^x (mod N),

czyli musimy znaleźć najmniejsze naturalne r, takie że f(x + r) = f(x).

Jeśli r jest nieparzyste, wracamy do punktu 1.

Jeżeli a^r/2 ≡ -1 (mod N), wracamy do punktu 1.

Dzielnikiem N jest NWD(a^r/2 ± 1, N).

Koniec algorytmu.

Część kwantowa: Znajdowanie okresu funkcji

Przygotowujemy dwa rejestry kwantowe: wejściowy i wyjściowy, każdy z log₂N kubitów, i inicjujemy je w stanie:

N^-1/2∑x|x⟩ |0⟩

dla x od 0 do N – 1.

Następnie konstruujemy układ realizujący funkcję f(x) w postaci kwantowej i stosujemy go do powyższego stanu, uzyskując:

N^-1/2∑x|x⟩ |f(x)⟩

Teraz stosujemy odwrotną kwantową transformatę Fouriera do rejestru wejściowego, co jest zdefiniowane wzorem:

U_QFT|x⟩ = N^-1/2∑ye^-2πixy/N|y⟩

Efektem tej operacji będzie stan:

N^-1∑x∑ye^-2πixy/N|y⟩ |f(x)⟩

Dokonujemy pomiaru, otrzymując y w rejestrze wejściowym oraz f(x₀) w rejestrze wyjściowym.

Ponieważ f jest okresowa, prawdopodobieństwo uzyskania pary y, f(x₀) wynosi:

N^-1∑x : f(x) = f(x₀) e^-2πixy/N

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

Przekształcamy y/N w nieskracalny ułamek i bierzemy jego mianownik r’ jako kandydata na r.

Sprawdzamy, czy f(x) = f(x + r’)

Jeśli tak, algorytm kończy się. Jeśli nie, sprawdzamy innych kandydatów na r z wartości bliskich y, lub wielokrotności r’.

Jeśli któryś z kandydatów działa, algorytm kończy się. W przeciwnym razie, jeśli nie udało się znaleźć dobrego r, wracamy do punktu 1.

Analiza algorytmu

Część klasyczna

Liczby naturalne mniejsze od N i względnie pierwsze z N tworzą grupę skończoną. Każdy element a w tej grupie ma skończony rząd r – najmniejszą dodatnią liczbę, dla której:

a^r ≡ 1 (mod N).

W związku z tym, N dzieli (a^r – 1).

Jeżeli potrafimy obliczyć r i jest ono parzyste, to:

a^r – 1 = (a^r/2 – 1)(a^r/2 + 1) ≡ 0 (mod N).

Skoro r jest najmniejszą liczbą, dla której a^r ≡ 1, to N nie 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 tymi liczbami: (a^r/2 – 1) oraz (a^r/2 + 1).

W ten sposób uzyskujemy jakąś faktoryzację N. Jeśli 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 x, uzyskując superpozycję wszystkich wartości.

Jednak fizyka kwantowa nie pozwala na bezpośredni odczyt tych informacji. Każdy pomiar niszczy superpozycję, umożliwiając odczyt tylko jednej wartości. Zamiast tego 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ą jakiegoś okresu funkcji.

Aby wykonać kwantowy algorytm, niezbędne są trzy operacje:

Stworzenie superpozycji stanów, co można osiągnąć za pomocą bramek Hadamarda do wszystkich kubitów w rejestrze.
Wykonanie funkcji f jako funkcji kwantowej, używając algorytmu szybkiego potęgowania w wersji modulo N. To jest najtrudniejszy krok w implementacji, wymagający dodatkowych kubitów i największej liczby bramek logicznych.
Odwrotna kwantowa transformacja Fouriera, z użyciem kontrolowanych bramek obrotu i bramek Hadamarda.

Shor zaprojektował układ, który realizuje odwrotną kwantową transformację Fouriera przy użyciu O((log N)²) bramek.

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

Zakładając, że istnieje takie y, że yr/N jest całkowite, prawdopodobieństwo uzyskania dobrego y wynosi 1. Suma czynników dających wartość y będzie równa N/r, ponieważ istnieje N/r różnych wartości b dających ten sam wykładnik. Prawdopodobieństwo każdego takiego y wynosi zatem 1/r².

W sumie, prawdopodobieństwo uzyskania dobrego r wynosi 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.