Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie i wykorzystując pamięć 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 ^[1]. Faktoryzacji liczby dokonano w 2011 roku^[2].

Na wejściu algorytmu dostajemy liczbę naturalną Naszym zadaniem jest znalezienie liczby między a która dzieli 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.

1. Wylosować liczbę
2. Obliczyć – na przykład za pomocą algorytmu Euklidesa.
3. Jeśli to został znaleziony nietrywialny dzielnik i można zakończyć część klasyczną.
4. W przeciwnym wypadku należy użyć podprocedury znajdującej które jest okresem następującej funkcji:

   

   czyli znaleźć najmniejsze naturalne takie że

5. Jeśli jest nieparzyste, wrócić do punktu 1.
6. Jeśli wrócić do punktu 1.
7. Dzielnikiem jest Koniec algorytmu.

1. Przygotować dwa rejestry kwantowe: wejściowy i wyjściowy, każdy z kubitów, i zainicjować je na stan:

   

   dla od do

2. Skonstruować układ realizujący funkcję w postaci kwantowej i zaaplikować ją do powyższego stanu, otrzymując:

   

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

   

   Efektem tej operacji będzie zatem stan:

   

4. Dokonać pomiaru, otrzymując w rejestrze wejściowym i w rejestrze wyjściowym.

   Ponieważ jest okresowa, prawdopodobieństwo uzyskania pary wynosi:

   

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

5. Przekształcić w nieskracalny ułamek i wziąć jego mianownik jako kandydata na
6. Sprawdzić czy Jeśli tak, algorytm jest zakończony.
7. Jeśli nie, sprawdź innych kandydatów na przez użycie wartości blisko albo wielokrotności Jeśli któryś z kandydatów działa, algorytm jest zakończony.
8. Jeśli nie udało się znaleźć dobrego wróć do punktu 1.

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

Zatem Jeśli potrafimy obliczyć i jest ono parzyste, to:

Skoro jest najmniejszą liczbą taką że to nie może dzielić Jeśli nie dzieli również to musi mieć nietrywialny wspólny dzielnik z obiema liczbami: i

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

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 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 jako funkcji kwantowej.

   Używany do tego jest algorytm szybkiego potęgowania, w wersji modulo 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 bramek.

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

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

dla dowolnego całkowitego

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

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

• Scott Aaronson, "Shor, I’ll do it" (popularne objaśnienie algorytmu Shora) (ang.)
• Hacking at Quantum Speed with Shor's Algorithm (ang.), kanał PBS Infinite Series na YouTube, 28 kwietnia 2017 [dostęp 2024-08-22].