Trzydzieści lat później przyspieszenie faktoringu kwantowego | Magazyn Quanta

Piotr Szor nie zamierzał podbijać Internetu. Ale algorytm opracowany przez niego w połowie lat 1990. groził właśnie takim rozwiązaniem. W papier rozpoznawczyShor pokazał, jak hipotetyczny komputer wykorzystujący dziwactwa fizyki kwantowej może rozbić duże liczby na czynniki pierwsze znacznie szybciej niż jakakolwiek zwykła maszyna klasyczna.

Wynik miał konsekwencje daleko wykraczające poza matematykę. W tamtym czasie istotnym elementem bezpieczeństwa Internetu był tzw kryptografia z kluczem publicznym opierał się na założeniu, że rozkład na czynniki dużych liczb jest tak trudny obliczeniowo, że w rzeczywistości jest niemożliwy. Założenie to nadal leży u podstaw niektórych krytycznych protokołów. Algorytm Shora pokazał, że w świecie mającym władzę poniósłby spektakularną porażkę komputery kwantowe.

W ciągu ostatnich 30 lat informatycy udoskonalili algorytm Shora, przygotowując się na dzień, w którym technologia kwantowa będzie na tyle dojrzała, aby można było ją uruchomić. Ale nowy wariant, od informatyka z New York University Oded Regev, jest szybszy w całkowicie nowym sensie. Jest to pierwsza metoda, która poprawia związek między wielkością rozkładanej liczby a liczbą operacji kwantowych wymaganych do jej rozłożenia.

„To naprawdę niezwykłe, że komuś udało się poprawić złożoność tego wyniku wiele, wiele lat później” – powiedział Ashleya Montanaro, badacz obliczeń kwantowych na Uniwersytecie w Bristolu. „To naprawdę ekscytujące”.

Martina Ekerå, kryptolog w Szwedzkim Krajowym Urzędzie ds. Bezpieczeństwa Łączności, zgodził się, że artykuł Regeva jest interesujący, ale przestrzegł, że pokonanie najnowocześniejszego stanu wiedzy w praktyce będzie wymagało dalszej optymalizacji. „Oryginalne algorytmy Shora są już zaskakująco wydajne, więc wprowadzenie znaczących ulepszeń nie jest trywialne” – napisał w e-mailu.

Regev opracował swój nowy algorytm, rozszerzając algorytm Shora o techniki z gałęzi kryptografii zajmującej się geometrią wielowymiarową.

„Pomyślałem, że każdy algorytm działający w oparciu o ten podstawowy zarys będzie skazany na porażkę” – powiedział Shor, matematyk stosowany obecnie w Massachusetts Institute of Technology. "Ale byłem w błędzie."

Znajdowanie czynników

Komputery kwantowe czerpią swoją moc ze specyficznego sposobu przetwarzania informacji. Klasyczne komputery używają bitów, z których każdy musi zawsze znajdować się w jednym z dwóch stanów, oznaczonych jako 0 i 1. Bity kwantowe, czyli „kubity”, mogą dodatkowo występować w kombinacjach stanów 0 i 1 — jest to zjawisko zwane superpozycją. Możliwe jest również nakłonienie wielu kubitów do zbiorowego stanu superpozycji: superpozycja dwóch kubitów składa się z czterech komponentów, które mogą jednocześnie wykonywać różne obliczenia, a liczba takich komponentów rośnie wykładniczo wraz ze wzrostem liczby kubitów. Dzięki temu komputery kwantowe mogą skutecznie wykonywać wykładniczo wiele różnych obliczeń równolegle.

Ale jest haczyk: Odczytanie wyniku obliczeń wykonanych w superpozycji ujawnia jedynie odpowiedź na część obliczoną przez jeden losowy składnik. Aby czerpać korzyści z obliczeń w superpozycji, musisz w jakiś sposób odwzorować wynik końcowy na prostszy stan, w którym można bezpiecznie odczytać wynik. W większości przypadków nie jest to możliwe i na początku nikt nie wiedział, jak to rozwiązać w przypadku jakiegokolwiek problemu. „Bardzo niewielu ludzi miało odwagę pomyśleć o obliczeniach kwantowych” – powiedział Regev.

Następnie w 1994 r. Shor przeczytał papier przez informatyka Daniela Simona, który pokazał, jak wykorzystać superpozycję kwantową do rozwiązania wymyślonego problemu. Shor wymyślił, jak rozszerzyć wynik Simona na bardziej ogólny i praktyczny problem zwany znajdowaniem okresu. Mówi się, że funkcja matematyczna jest okresowa, gdy jej wartość wyjściowa cyklicznie przechodzi przez te same wartości w miarę wzrostu wartości wejściowej; długość pojedynczego cyklu nazywana jest okresem funkcji.

Aby znaleźć okres danej funkcji za pomocą komputera kwantowego, zacznij od skonfigurowania bardzo dużej superpozycji, w której każdy składnik oblicza wynik funkcji dla innego wejścia. Następnie użyj metody Shora, aby przekształcić tę dużą superpozycję w prostszy stan i odczytaj wynik. W tym momencie klasyczny komputer może przejąć kontrolę i szybko zakończyć obliczenia. Ogólnie rzecz biorąc, algorytm znajdowania okresu Shora działa wykładniczo szybciej niż jakakolwiek klasyczna alternatywa, ponieważ oblicza jednocześnie różne wyniki funkcji okresowej przy użyciu superpozycji.

Gdy Shor szukał zastosowań dla swojego algorytmu wyszukiwania okresu kwantowego, ponownie odkrył znane wcześniej, ale mało znane twierdzenie matematyczne: dla każdej liczby istnieje funkcja okresowa, której okresy są powiązane z czynnikami pierwszymi liczby. Jeśli więc istnieje liczba, którą chcesz rozłożyć na czynniki, możesz obliczyć odpowiednią funkcję, a następnie rozwiązać problem za pomocą znajdowania okresu — „dokładnie w tym, w czym komputery kwantowe są tak dobre” – powiedział Regev.

Na klasycznym komputerze byłby to boleśnie powolny sposób na rozkład dużej liczby na czynniki — nawet wolniejszy niż wypróbowanie każdego możliwego czynnika. Jednak metoda Shora przyspiesza ten proces wykładniczo, dzięki czemu znajdowanie okresu jest idealnym sposobem na skonstruowanie szybkiego algorytmu faktoryzacji kwantowej.

Algorytm Shora był jednym z kilku kluczowych wczesnych wyników, które przekształciły obliczenia kwantowe z mało znanej poddziedziny informatyki teoretycznej w molocha, jakim jest dzisiaj. Jednak wdrożenie algorytmu w praktykę jest trudnym zadaniem, ponieważ komputery kwantowe są notorycznie podatne na błędy: oprócz kubitów wymaganych do wykonywania obliczeń potrzebują wielu innych zadań dodatkowa praca żeby nie upadły. A Ostatni artykuł przez Ekerå i badacza Google Craiga Gidneya szacuje, że użycie algorytmu Shora do rozłożenia na czynniki standardowej liczby 2,048-bitowej (o długości około 600 cyfr) wymagałoby komputera kwantowego z 20 milionami kubitów. Dzisiejsze najnowocześniejsze maszyny mają ich najwyżej kilkaset.

Dlatego też niektóre krytyczne protokoły internetowe w dalszym ciągu opierają się na tym, jak trudno jest rozłożyć na czynniki duże liczby, ale badacze nie chcą popadać w samozadowolenie. teoretyczny i innowacje technologiczne mogłyby jeszcze bardziej skrócić wymagane odliczanie kubitów, a nie ma dowodu na to, że algorytm Shora jest optymalny — może istnieć lepszy algorytm faktoringu kwantowego, którego nikt nie odkrył.

Jeśli tak, powiedział Regev, „powinniśmy wiedzieć o tym tak wcześnie, jak to możliwe, zanim będzie za późno”.

Zagubiony w drzewach

Regev rozpoczął karierę akademicką pod koniec lat 1990., kiedy kryptografowie poszukiwali nowej formy kryptografii klucza publicznego, która nie byłaby podatna na działanie algorytmu Shora. Najbardziej obiecujące podejście, tzw kryptografia oparta na sieciach, opiera się na pozornej trudności problemów obliczeniowych obejmujących wielowymiarowe tablice punktów lub kraty. Jeden z takich problemów przypomina zadanie zlokalizowania drzewa najbliżej losowego punktu w lesie.

„Jeśli jest to las stuwymiarowy, jest to znacznie bardziej skomplikowane niż las dwuwymiarowy” – powiedział Grega Kuperberga, matematyk z Uniwersytetu Kalifornijskiego w Davis.

Regev zaczął studiować kryptografię opartą na sieciach jako postdoktor, początkowo jako osoba atakująca — chciał przetestować nowe podejście w warunkach skrajnych, znajdując słabe punkty, które mógłby wykorzystać komputer kwantowy. Nie mógł jednak poczynić żadnych postępów i wkrótce zaczął się zastanawiać, czy istnieje głębszy powód. W 2005 roku znalazł sposób na zamienienie tych nieudanych ataków na: forma kryptografii opartej na sieciach przewyższa wszystkie inne warianty.

„Oded jest absolutnie genialny w przypadku krat” – powiedział Kuperberg.

Przez lata, gdy Regev uczył algorytmu Shora kolejne pokolenia studentów, zaczął się zastanawiać, czy techniki, których użył do atakowania kryptografii opartej na sieciach, mogą faktycznie okazać się przydatne w algorytmach faktoringu. Dzieje się tak, ponieważ jeden krok w ostatnim, klasycznym etapie algorytmu Shora sprowadza się do znalezienia najbliższego punktu w jednowymiarowej siatce. Ten jednowymiarowy problem jest banalnie łatwy, ale podobieństwo do analogicznego problemu w setkach wymiarów, których twardość leży u podstaw kryptografii opartej na sieciach, było niewątpliwe.

„Jeśli tak jak ja zajmujesz się tworzeniem krat, myślisz: «OK, tu dzieje się jakaś krata»” – powiedział Regev. „Ale nie było dla mnie jasne, jak to wykorzystać”. Przez lata bawił się innymi pomysłami na nowe algorytmy faktoringu kwantowego, ale nigdy do niczego nie doszedł. Zeszłej zimy powrócił do problemu i postanowił ustalić to kuszące powiązanie między faktoringiem a kryptografią opartą na sieciach. Tym razem odniósł sukces.

Dodatkowe wymiary

Regev wiedział, że musi zacząć od uogólnienia funkcji okresowej będącej sercem algorytmu Shora z jednego wymiaru na wiele wymiarów. W algorytmie Shora funkcja ta polega na wielokrotnym mnożeniu liczby losowej, tzw g, sobą. Ale okres tej funkcji — liczba razy, przez którą należy pomnożyć g zanim wynik funkcji zacznie się powtarzać — może być bardzo duży, a to oznacza, że ​​komputer kwantowy musi pomnożyć duże liczby w niektórych składnikach superpozycji, której używa do obliczenia funkcji okresowej. Te duże mnożenia są najbardziej kosztowną obliczeniowo częścią algorytmu Shora.

Zamiast tego analogiczna funkcja dwuwymiarowa wykorzystuje parę liczb, g₁ i g₂. Polega na mnożeniu g₁ ze sobą wiele razy, a następnie wielokrotnie mnożąc przez g₂. Okres tej funkcji jest również dwuwymiarowy — wyznaczany jest przez liczbę g₁ mnożenia i g₂ mnożenia, które razem powodują, że dane wyjściowe funkcji zaczynają się powtarzać. Istnieje wiele różnych kombinacji g₁ i g₂ mnożenia, które załatwią sprawę.

Regev pracował nad szczegółami technicznymi, aby uogólnić algorytm na dowolną liczbę wymiarów, a nie tylko dwa, ale jego początkowe wyniki nie były zachęcające. Aby obliczyć funkcję okresową w wielu wymiarach, komputer kwantowy nadal musiałby pomnożyć wiele liczb przez siebie. Każda liczba nie musiałaby być mnożona tyle razy, jak w przypadku jednowymiarowym, ale było więcej odrębnych liczb do pomnożenia. Całość wyglądała jak pranie.

„Myślisz: «Świetnie, właśnie zrobiłem wszystko w dużych wymiarach i czas trwania jest dokładnie taki sam jak Shora»” – powiedział Regev. „Utknąłem w tym przez jakiś czas.” Potem zdał sobie sprawę, że może obejść ten problem, zmieniając kolejność mnożenia. Zamiast wielokrotnie łączyć liczby w pojedynczy iloczyn, który w miarę obliczeń kwantowych stawał się coraz większy, zaczął od par małych liczb, pomnożył otrzymane iloczyny przez siebie i szedł w górę. Całkowita liczba mnożeń nie uległa większym zmianom, ale obecnie prawie wszystkie dotyczą stosunkowo małych liczb, co przyspiesza obliczenia.

„To robi różnicę na całym świecie” – powiedział Vinod Vaikuntanathan, kryptolog w MIT.

Na początku wyglądało na to, że Regev właśnie zastąpił jeden problem innym. Przyspieszył kwantowe obliczenia funkcji okresowej, zwiększając liczbę wymiarów, ale późniejsze klasyczne obliczenia wymagane do wyodrębnienia okresu przypominały teraz lokalizowanie najbliższego punktu sieci w przestrzeni wielowymiarowej – powszechnie uważa się, że to zadanie być twardym. Wydawało się, że analogia do kryptografii opartej na kratach, która motywowała jego nowe podejście, skazała je na porażkę.

Pewnego zimnego marcowego poranka, przed wyjazdem na seminarium na Uniwersytecie Princeton, Regev czekał na kolegę, z którym podróżował. „Przyjechałem wcześniej, a on spóźnił się, aby odebrać samochód” – powiedział. Kiedy tak siedział i czekał, nagle dotarł do niego ostatni element układanki. „To był moment, kiedy wszystko się ułożyło, ale przez jakiś czas wszystko się palił”.

Wszystko sprowadzało się do odpowiedniej liczby wymiarów. Gdy wymiar sieci był zbyt mały, jego algorytm nie mógł w pełni wykorzystać przyspieszenia wynikającego z mnożenia mniejszych liczb. Kiedy było zbyt wysokie, obliczenia kwantowe były szybkie, ale część klasyczna wymagała rozwiązania zbyt trudnego problemu sieciowego. Regev wiedział od początku, że aby mieć jakąkolwiek nadzieję na sukces, będzie musiał pracować gdzieś pomiędzy, ale nie było jasne, czy istnieje złoty środek. Tego marcowego ranka zdał sobie sprawę, jak może ulepszyć szczegóły algorytmu, aby działał szybko w kilkudziesięciu wymiarach.

Pisanie na piasku

Poprawa była głęboka. Liczba elementarnych kroków logicznych w części kwantowej algorytmu Regeva jest proporcjonalna do n^1.5 podczas faktoringu n-bitowa liczba, zamiast n² jak w algorytmie Shora. Algorytm powtarza tę część kwantową kilkadziesiąt razy i łączy wyniki, aby utworzyć wielowymiarową siatkę, z której może wydedukować okres i rozłożyć liczbę na czynniki. Zatem algorytm jako całość może nie działać szybciej, ale przyspieszenie części kwantowej poprzez zmniejszenie liczby wymaganych kroków mogłoby ułatwić zastosowanie go w praktyce.

Oczywiście czas potrzebny na uruchomienie algorytmu kwantowego to tylko jeden z kilku czynników. Równie ważna jest liczba wymaganych kubitów, która jest analogiczna do pamięci wymaganej do przechowywania wartości pośrednich podczas zwykłych klasycznych obliczeń. Liczba kubitów wymagana przez algorytm Shora do uwzględnienia an n-bitowa liczba jest proporcjonalna do n, podczas gdy algorytm Regeva w swojej pierwotnej formie wymaga liczby kubitów proporcjonalnych do n^1.5 — duża różnica w przypadku liczb 2,048-bitowych.

W klasycznym przetwarzaniu szybkość jest zwykle ważniejszym czynnikiem niż pamięć, ponieważ klasyczne bity są niezwykle wytrzymałe: możesz zapisać plik na swoim komputerze i nie martwić się, że ulegnie on przypadkowej zmianie przy późniejszym ponownym otwarciu. Badacze zajmujący się obliczeniami kwantowymi nie zawsze mają tyle szczęścia.

„Nasze kubity nieustannie próbują się rozpaść, a my staramy się je powstrzymać” – powiedział Gidney. „To tak, jakbyś próbował pisać na piasku, a wiatr go rozwiewał”. Oznacza to, że dodatkowe kubity wymagane przez algorytm Regeva mogą być główną wadą.

Ale artykuł Regeva to nie koniec historii. Dwa tygodnie temu Vaikuntanathan i jego student Seyoon Ragavan znaleźli sposób na zmniejszenie zużycia pamięci przez algorytm. Ich wariant algorytmu Regeva, podobnie jak oryginalny algorytm Shora, wymaga liczby kubitów proporcjonalnej do n zamiast n^1.5. Ekerå napisała w e-mailu, że praca „znacznie przybliża nas do wdrożenia, które byłoby bardziej wydajne w praktyce”.

Szersza lekcja płynąca z nowego algorytmu Regeva, wykraczająca poza implikacje dla faktoringu, jest taka, że ​​badacze zajmujący się obliczeniami kwantowymi powinni zawsze być otwarci na niespodzianki, nawet w przypadku problemów badanych od dziesięcioleci.

„Ten wariant mojego algorytmu był nieodkryty przez 30 lat i pojawił się niespodziewanie” – powiedział Shor. „Prawdopodobnie wciąż można znaleźć wiele innych algorytmów kwantowych”.

Nota wydawcy: Oded Regev otrzymuje fundusze od Fundacja Simonsa, które również finansuje ten niezależny redakcyjnie magazyn. Decyzje Fundacji Simonsa nie mają wpływu na nasz zasięg. Więcej szczegółów dostępny tutaj.

Quanta przeprowadza serię ankiet, aby lepiej służyć naszym odbiorcom. Weź nasze ankieta dla czytelników informatyki i zostaniesz wpisany, aby wygrać za darmo Quanta towar.