Co to jest?
Jak to działa?
Algorytm faktoryzacji Shora
W 1994 roku Peter Shor, pracujący wówczas w Bell Labs w New Jersey, pokazał, jak przy użyciu hipotetycznego komputera kwantowego rozłożyć w czasie wielomianowym dowolną liczbę naturalną na czynniki pierwsze. W tamtym czasie algorytmy kwantowe dopiero raczkowały. To właśnie odkrycie Shora spowodowało wielki rozwój tej dziedziny. Społeczność informatyków zrozumiała, że gdyby udało się zbudować komputer kwantowy rozsądnej wielkości, to świat stałby się istotnie inny. Nie jest bowiem znany żaden algorytm dla problemu faktoryzacji, czyli rozkładu na dzielniki pierwsze, który działa w czasie wielomianowym na komputerze klasycznym. Co więcej, nawet nie znaleziono algorytmu losowego, który z dużym prawdopodobieństwem w zazwyczaj niedługim czasie faktoryzuje liczbę: nie jest po prostu znana zupełnie żadna rozsądna heurystyka...

W 1994, ale też i teraz, w 2017 roku, po prostu nie umiemy rozkładać szybko liczb na czynniki pierwsze. A na trudności faktoryzacji opiera się m.in. kryptologia, najbardziej znany kryptosystem RSA dałby się łatwo łamać, gdybyśmy umieli szybko rozkładać liczby na czynniki pierwsze. Drugim najbardziej popularnym problemem, na którego trudności opiera się wiele w kryptologii, jest problem logarytmu dyskretnego (dla danych i liczby pierwszej
znajdź
takie, że
). Warto wiedzieć, że w tym samym artykule Shor udowodnił również, że komputer kwantowy umie rozwiązywać problem logarytmu dyskretnego w czasie wielomianowym. Algorytm Shora nie tylko zainspirował intensywne badania w tej dziedzinie, ale chyba do tej pory jest najbardziej znanym i celebrowanym algorytmem kwantowym.
W tym artykule postaramy się zrozumieć najistotniejsze idee w algorytmie Shora. Niektóre szczegóły techniczne pominiemy, gdyż tłumaczenie wszystkiego zajęłoby raczej kilkanaście stron niż kilka.
Sprecyzujmy problem. Dostajemy liczbę W naszych rozważaniach skupimy się na przypadku, gdy
jest iloczynem dwóch liczb pierwszych, tj.
Ten przypadek jest również trudny (nie ma dla niego żadnych szybko działających heurystyk), a algorytm Shora w ogólności działa prawie identycznie, jak dla tego przypadku. Nasz cel to znaleźć liczby
i
Po pierwsze powiedzmy sobie od razu, że algorytm Shora jest oparty na losowości. Uruchomiony wiele razy z pewnym dużym (bliskim
) prawdopodobieństwem znajdzie rozkład
Myślmy, że zarówno
jak i
mają po 100 cyfr, wtedy będziemy mieli odpowiednie wyobrażenie o tym, co się da, a czego nie da się szybko zrobić.
Pierwszy krok, niemający jeszcze żadnego związku z kwantami, to redukcja faktoryzacji do problemu rzędu elementu modulo Problem ten, dla danych
pyta o najmniejsze naturalne
takie, że
(takie
nazywamy rzędem
modulo
). Przy założeniu, że umiemy w czasie wielomianowym znajdować rząd elementu (wszędzie tu używana jest losowość, więc przestaniemy się na niej skupiać, a czasem nawet o niej wspominać), pokażemy, jak rozłożyć
na czynniki w czasie wielomianowym. Rozważmy
i wylosujmy liczbę
ze zbioru
Jeśli
(co możemy szybko sprawdzić algorytmem Euklidesa), to świetnie, bo wtedy
albo
i znaleźliśmy rozkład. Ale to się zdarza rzadko. Załóżmy więc, że
Można wykazać (nie bardzo trudno, szczegóły pominiemy), że dla co najmniej jednej czwartej wylosowanych
zachodzą następujące dwa warunki: 1)
czyli rząd
jest parzysty, 2)
Dla takiego
mamy
Jednak skoro
nie dzieli żadnego z dwóch nawiasów, to musi być tak, że
dzieli jeden z nich, a
drugi. Zatem
jest równe albo
albo
Łatwo je obliczyć algorytmem Euklidesa, a tym samym znaleźć rozkład
A więc wystarczy skupić się na znajdowaniu rzędu liczby
modulo
co zrobimy przy użyciu algorytmu kwantowego.
Ustalmy pewne które należy do przedziału
oraz jest potęgą dwójki, niech
Nasz algorytm na wejściu będzie miał
drutów, czyli będzie operował na
kubitach (albo jeszcze inaczej: stan pamięci może być opisany przez wektor długości 1 z
). Te
drutów podzielimy na dwa segmenty po
drutów. Zaczynamy od stanu pamięci równego 0 na wszystkich kubitach. Czyli, formalnie rzecz biorąc, jest to stan
gdzie ciąg zer ma długość
My jednak na potrzeby naszego algorytmu będziemy o nim myśleli jako o
co będziemy zapisywać w skrócie jako

Cały obwód kwantowy realizujący algorytm Shora przedstawiony jest na rysunku. Wchodzi do niego drutów po lewej, do których po kolei aplikowane są bramki kwantowe i na końcu wykonywany jest pomiar. Fakt, że algorytm jest wielomianowy, oznacza, że w obwodzie jest wielomianowo wiele podstawowych bramek (czyli bramek Hadamarda
obrotu
i kontrolowanej negacji CNOT, z których składamy wszystkie macierze unitarne, potrzebne do obliczeń). Teraz szczegółowo opiszemy, co dzieje się po kolei (od lewej).
Najpierw robimy to, co często robią na początek algorytmy kwantowe, czyli zamieniamy stan "same zera" na superpozycję wszystkich możliwych stanów bazowych, każdy z równym prawdopodobieństwem. Tyle, że my teraz zrobimy to tylko na pierwszych kubitach, tj. w pierwszym segmencie. Aby to zrobić, używamy, jak zawsze w takim przypadku, bramek Hadamarda
![H = √1--[1 1]. 2 1 −1](/math/temat/informatyka/algorytmy/2017/11/25/Algorytm_faktoryzacji_Shora/2x-ea8f712bf148fcbba45c594d6f8ec99f59801623-dm-33,33,33-FF,FF,FF.gif)
Bramka przekształca
na
czyli na superpozycję
i
z równym prawdopodobieństwem. Jeśli zastosujemy bramkę
do każdego z pierwszych
kubitów, to stan
zostanie przekształcony na stan
gdzie przez
rozumiemy stan określony przez binarną reprezentację
np. dla
przez
Formalnie rzecz biorąc, powyżej przyłożyliśmy do aktualnego stanu przekształcenie będące produktem
macierzy Hadamarda H i
macierzy identycznościowych I. Jednak warto patrzeć na to intuicyjnie, jako na przyłożenie bramki Hadamarda do każdego kubitu oddzielnie, bo takie jest właśnie znaczenie produktu tensorowego.

Następnie w algorytmie przykładamy do wszystkich drutów bramkę, która liczy funkcję (czyli z
kubitów w
kubitów) taką, że

Przypomnijmy, że to nasza wylosowana liczba ze zbioru
Na rysunku obwód obliczający funkcję
oznaczamy przez
Sprawdzenie, że obliczenie funkcji
jest unitarne oraz że da się je zrealizować obwodem o wielomianowej liczbie małych bramek, nie jest specjalnie trudne. Tutaj jednak pominiemy szczegóły. A więc po przejściu przez bramkę
stan jest następującą superpozycją:

Teraz wykonujemy pomiar na drugim segmencie, czyli na drugich kubitach. W wyniku pomiaru zmierzona zostaje jakaś (nie wiemy z góry jaka!) wartość
Przy czym nie wiadomo wcale, czy na pierwszych
kubitach jest wartość
Może być również tak, że jest tam wartość
gdyż
Podobnie może być tam wartość
Tak jak po każdym pomiarze, teraz stan układu jest superpozycją tych stanów bazowych sprzed pomiaru, które są zgodne z pomiarem.
W dalszej części rozważa się dwa przypadki. Pierwszy, gdy jest łatwiejszy, a drugi, gdy
trudniejszy. My przyjrzyjmy się pierwszemu, bo idea jest w obu przypadkach podobna, tylko w drugim jest więcej szczegółów technicznych. W tym przypadku z pomiarem
(dla
) zgodne są wartości
na pierwszych
kubitach. Zatem po pomiarze stan układu na pierwszych
kubitach jest postaci

Widać teraz, że jest jakoś związane ze stanem układu. Pytanie tylko, jak je z niego wydobyć. Jeśli zmierzymy po prostu wartość tych kubitów, to otrzymamy pewną liczbę
która będzie jakąś liczbą ze zbioru
wiele nam nie powie. Nie znamy przecież
żeby móc obliczyć
a tym bardziej nie znamy
żeby obliczyć z
wartość
Musimy więc postępować inaczej.
Tu w sukurs przychodzi nam dziedzina, która wielu Czytelnikom zapewne wcale nie kojarzy się z faktoryzacją liczb pierwszych. Przyjrzyjmy się jeszcze raz naszemu pytaniu, z nieco innej strony. Możemy pomyśleć o naszej superpozycji jako o ciągu wartości dla których przy większości jest współczynnik 0, ale dla niektórych niezerowy współczynnik
Te wartości o niezerowych współczynnikach powtarzają się co
i chcemy odkryć, z jakim okresem to robią. Wróćmy na chwilę do świata niekwantowego i zastanówmy się, co należy robić w takich sytuacjach, jak znaleźć okres pewnego okresowego zjawiska. Zauważmy, że nasze ucho robi to przez cały czas. Dźwięk, który słyszymy, rozkłada się bowiem na wiele składowych o różnych częstotliwościach. Ucho właśnie rozkłada dźwięk na składowe, które wyglądają jak sinusy i kosinusy. To, co robi, nazywa się w matematyce transformatą Fouriera. Okazuje się, że każdą funkcję okresową da się rozłożyć na nieskończoną sumę sinusów i kosinusów. Podobnie robi się, gdy mamy sygnał, który nie jest ciągły, lecz dyskretny. Tylko, że wtedy rozkładamy na skończoną sumę próbkowań kosinusów. Czytelnik Zapoznany Z Algebrą Liniową może sobie wyobrażać oba przekształcenia jako wyrażanie funkcji okresowej (bądź jej próbkowania) po prostu w innej bazie, złożonej z sinusów i kosinusów (bądź ich próbkowań). Ciekawostką może być, że ta sama transformata jest wykorzystywana w innych miejscach informatyki, np. w formatach jpeg lub mpeg.
A więc w świecie kwantowym, jeśli chcemy odnaleźć coś w stylu okresu w naszym stanie, też powinniśmy zastosować transformatę Fouriera, tylko że kwantową. Szczęśliwie rzeczywiście istnieje kwantowa transformata Fouriera (QFT - quantum Fourier transform), która okazuje się unitarna i daje się zaimplementować za pomocą wielomianowej liczby podstawowych bramek kwantowych. Przyłożenie jej do naszej konfiguracji na wyjściu daje współczynniki przy odpowiednich okresach. Dostajemy pewną superpozycję
Okazuje się, że dla przypadku gdy
współczynniki
są niezerowe jedynie dla
będących wielokrotnościami
A więc możemy teraz wykonać pomiar i jesteśmy pewni, że otrzymaliśmy jakąś wielokrotność
Gdy wykonamy wiele (ale wielomianowo wiele) takich pomiarów i weźmiemy minimum albo
to obliczymy z dużym prawdopodobieństwem
A zatem poznamy również i rząd
co kończy naszą opowieść.
Czytelnikom Zainteresowanym Szczegółami polecamy oryginalny artykuł Petera Shora dostępny pod adresem: arxiv.org/abs/quant-ph/9508027.