Algorytm Shora


Algorytm faktoryzacji Shora w encyklopedii

Z Wikipedii, wolnej encyklopedii (Przekierowano z Algorytm Shora) Przejdź do nawigacji Przejdź do wyszukiwania

Kwantowy algorytm Shoraalgorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie O ( ( log N ) 3 ) {\displaystyle \mathrm {O} ((\log N)^{3})} i wykorzystując pamięć O ( log N ) , {\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 15   =   3 5 {\displaystyle 15\ =\ 3\cdot 5} [1]. Faktoryzacji liczby 21 {\displaystyle 21} dokonano w 2011 roku[2].

Spis treści

Procedura realizacji | edytuj kod

Na wejściu algorytmu dostajemy liczbę naturalną N . {\displaystyle N.} Naszym zadaniem jest znalezienie liczby p {\displaystyle p} między 1 {\displaystyle 1} a N , {\displaystyle N,} która dzieli N {\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 | edytuj kod

  1. Wylosować liczbę a < N . {\displaystyle a<N.}
  2. Obliczyć N W D ( a , N ) {\displaystyle NWD(a,N)} – na przykład za pomocą algorytmu Euklidesa.
  3. Jeśli N W D ( a , N ) 1 , {\displaystyle NWD(a,N)\neq 1,} to został znaleziony nietrywialny dzielnik N {\displaystyle N} i można zakończyć część klasyczną.
  4. W przeciwnym wypadku należy użyć podprocedury znajdującej r , {\displaystyle r,} które jest okresem następującej funkcji: f ( x ) = a x ( mod N ) , {\displaystyle f(x)=a^{x}{\pmod {N}},} czyli znaleźć najmniejsze naturalne r , {\displaystyle r,} takie że f ( x + r ) = f ( x ) . {\displaystyle f(x+r)=f(x).}
  5. Jeśli r {\displaystyle r} jest nieparzyste, wrócić do punktu 1.
  6. Jeśli a r / 2 1 ( mod N ) , {\displaystyle a^{r/2}\equiv -1{\pmod {N}},} wrócić do punktu 1.
  7. Dzielnikiem N {\displaystyle N} jest N W D ( a r / 2 ± 1 , N ) . {\displaystyle NWD(a^{r/2}\pm 1,N).} Koniec algorytmu.

Część kwantowa: Znajdowanie okresu funkcji | edytuj kod

Obwód kwantowy algorytmu faktoryzacji Shora
  1. Przygotować dwa rejestry kwantowe: wejściowy i wyjściowy, każdy z log 2 N {\displaystyle \log _{2}N} kubitów, i zainicjować je na stan: N 1 / 2 x | x | 0 {\displaystyle N^{-1/2}\sum _{x}|x\rangle \,|0\rangle } dla x {\displaystyle x} od 0 {\displaystyle 0} do N 1. {\displaystyle N-1.}
  2. Skonstruować układ realizujący funkcję f ( x ) {\displaystyle f(x)} w postaci kwantowej i zaaplikować ją do powyższego stanu, otrzymując: N 1 / 2 x | x | f ( x ) {\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: U Q F T | x = N 1 / 2 y e 2 π i x y / N | y {\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: N 1 x y e 2 π i x y / N | y | f ( x ) {\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 y {\displaystyle y} w rejestrze wejściowym i f ( x 0 ) {\displaystyle f(x_{0})} w rejestrze wyjściowym. Ponieważ f {\displaystyle f} jest okresowa, prawdopodobieństwo uzyskania pary y , f ( x 0 ) {\displaystyle y,f(x_{0})} wynosi: | N 1 x : f ( x ) = f ( x 0 ) e 2 π i x y / N | 2 = N 2 | b e 2 π i ( x 0 + r b ) y / N | 2 {\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 policzyć, że to prawdopodobieństwo jest tym większe, im wartość y r / N {\displaystyle yr/N} jest bliższa liczbie całkowitej.
  5. Przekształcić y / N {\displaystyle y/N} w nieskracalny ułamek i wziąć jego mianownik r {\displaystyle r'} jako kandydata na r . {\displaystyle r.}
  6. Sprawdzić czy f ( x ) = f ( x + r ) . {\displaystyle f(x)=f(x+r').} Jeśli tak, algorytm jest zakończony.
  7. Jeśli nie, sprawdź innych kandydatów na r , {\displaystyle r,} przez użycie wartości blisko y , {\displaystyle y,} albo wielokrotności r . {\displaystyle r'.} Jeśli któryś z kandydatów działa, algorytm jest zakończony.
  8. Jeśli nie udało się znaleźć dobrego r , {\displaystyle r,} wróć do punktu 1.

Analiza algorytmu | edytuj kod

Część klasyczna | edytuj kod

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

a r 1 ( mod N ) . {\displaystyle a^{r}\equiv 1{\pmod {N}}.}

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

a r 1 = ( a r / 2 1 ) ( a r / 2 + 1 ) 0 ( mod N ) {\displaystyle a^{r}-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0{\pmod {N}}} N   | ( a r / 2 1 ) ( a r / 2 + 1 ) . {\displaystyle \Rightarrow N\ |(a^{r/2}-1)(a^{r/2}+1).}

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

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

Część kwantowa | edytuj kod

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 , {\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 f {\displaystyle f} jako funkcji kwantowej. Używany do tego jest algorytm szybkiego potęgowania, w wersji modulo N . {\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 O ( ( log N ) 2 ) {\displaystyle \mathrm {O} ((\log N)^{2})} bramek.

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

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

e 2 π i b y r / N = 1 {\displaystyle e^{-2\pi ibyr/N}=1}

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

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

Przypisy | edytuj kod

  1. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance.
  2. 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 | edytuj kod

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
Na podstawie artykułu: "Algorytm Shora" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy