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.
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.
Przekształcić w nieskracalny ułamek i wziąć jego mianownik jako kandydata na
Sprawdzić czy Jeśli tak, algorytm jest zakończony.
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.
Jeśli nie udało się znaleźć dobrego wróć do punktu 1.
Analiza algorytmu
Część klasyczna
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.
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 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:
Stworzenia superpozycji stanów.
Można tego łatwo dokonać aplikując bramki Hadamarda do wszystkich kubitów w rejestrze.
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.
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.
↑Enrique Martín-López, Anthony Laing, Thomas Lawson. [1111.4147] Experimental realisation of Shor’s quantum factoring algorithm using qubit recycling. „Nature Photonics”. 6, s. 773–776, 2012. arxiv.org. DOI: 10.1038/nphoton.2012.259. arXiv:1111.4147. (ang.).
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.)