Dowiedz się, co to jest algorytm Shora, który dowodzi, że obliczenia kwantowe są niezwykle wydajne w porównaniu z metodami klasycznymi.
Każdy zainteresowany poznaniem obliczeń kwantowych słyszał o algorytmie faktoryzacji Shora. Jest to jeden z niewielu podręcznikowych algorytmów kwantowych, co oznacza, że pozostaje jednym z rzadkich przykładów kwantowej wyższości obliczeniowej.
Innymi słowy, algorytm ten może obliczyć coś kwantowego, co jest trudniejsze i wolniejsze do obliczenia klasycznie. W rzeczywistości, ten konkretny algorytm może obliczyć coś, co dla wszystkich praktycznych celów, o ile nam wiadomo, nie może być wykonane klasycznie w żadnej użytecznej skali.
Co to jest algorytm Shora?
Algorytm faktoryzacji Shora wyróżnia się na tle innych algorytmów. Są ku temu dwa powody.
Po pierwsze, może on faktoryzować liczby wykładniczo szybciej niż jakikolwiek znany klasyczny algorytm.
Podczas gdy wszystkie podręcznikowe algorytmy kwantowe mają zalety obliczeniowe, algorytm Shora jest jednym z niewielu elitarnych algorytmów z wykładniczym przyspieszeniem i jednym z niewielu elitarnych algorytmów z praktycznymi zastosowaniami.
Jaka jest prędkość światła i tajemnice jej zrozumienia
Co najważniejsze, jego potencjał w zakresie faktoryzacji liczb w rozsądnych ramach czasowych bezpośrednio zagraża najpopularniejszym kryptosystemom na świecie.
Znaczenie tego faktu jest nie do przecenienia. Szyfrowanie RSA, które chroni transakcje finansowe na całym świecie, działa poprzez mnożenie dwóch ogromnych liczb pierwszych.
Liczby pierwsze nie mogą być podzielone na liczby całkowite inne niż one same i liczba jeden. Ich iloczyny są tak duże, że nie ma znanego sposobu na ich efektywną faktoryzację w klasyczny sposób.
Potraktuj faktoryzację jako odwrotność mnożenia, identyfikując użyte liczby pierwsze, co pozwala odszyfrować wiadomości internetowe bez możliwości ich zobaczenia.
W tym artykule na blogu omawiany algorytm jest czasami nazywany algorytmem faktoryzacji Shora, a nie po prostu algorytmem Shora, ponieważ istnieje również kwantowy kod korekcji błędów nazwany na cześć Shora, o tej samej nazwie, który został odkryty w wyniku publikacji algorytmu faktoryzacji. W tym artykule, aby uniknąć niejasności, należy wiedzieć, że algorytm Shora i algorytm faktoryzacji Shora odnoszą się do tego samego algorytmu.
Co to jest algorytm Shora w obliczeniach kwantowych?
Algorytm faktoryzacji Shora zwrócił uwagę opinii publicznej na obliczenia kwantowe. Jego zagrożenia zmusiły rządy krajowe, całe branże i opinię publiczną do zwrócenia uwagi na tę stosunkowo nową technologię.
Dziesiątki lat później algorytm ten pozostaje punktem odniesienia dla algorytmów kwantowych. Przez długi czas podejmowano znaczne wysiłki w celu ochrony globalnych systemów finansowych, bezpieczeństwa narodowego i wszystkich innych zastosowań kryptografii.
Istnieje wyraźne zagrożenie geopolityczne, że ktokolwiek, zwłaszcza podmiot państwowy, opracuje wystarczającą moc obliczeniową kwantową, aby wykorzystać algorytm Shora, zanim bezpieczne kryptosystemy kwantowe będą mogły zostać wdrożone powszechnie.
Co równie ważne, algorytm Shora doprowadził do zainwestowania miliardów dolarów w technologie kwantowe, w tym w obliczenia kwantowe. Trzy dekady po odkryciu algorytmu trwają poszukiwania innych praktycznych zastosowań, dla których można osiągnąć wykładnicze przyspieszenie.
Jeśli przynajmniej jeden algorytm może to osiągnąć, naukowcy uważają, że muszą istnieć inne. Po tych wszystkich latach najbardziej prawdopodobni kandydaci czerpią swoje pomysły z algorytmu Shora.
Pełna historia odkrycia algorytmu faktoryzacji Shora, opowiedziana przez samego profesora Petera Shora, znajduje się tutaj na kanale YouTube Qiskit, a krótka, animowana wersja tej historii znajduje się tutaj.
Jak działa elektrownia jądrowa?
Jak działa algorytm Shora?
Faktoryzacja liczb przy użyciu algorytmu Shor rozpoczyna się od wyboru losowej liczby całkowitej mniejszej niż liczba, która ma być faktoryzowana. Następnie, klasycznie obliczony największy wspólny dzielnik (GCD) dwóch liczb, liczby losowej i żądanej liczby, jest używany do określenia, czy żądana liczba została już przypadkowo sfaktoryzowana.
W przypadku mniejszych liczb jest to możliwe. W przypadku większych liczb może być potrzebny superkomputer. A w przypadku liczb, które są uważane za bezpieczne kryptograficznie, potrzebny jest komputer kwantowy.
Rolą komputera kwantowego jest określenie okresu liczby, która ma zostać poddana faktoryzacji. Wyniki obliczeń określają, czy należy sprawdzić nową losową liczbę całkowitą, czy też pożądane czynniki zostały już znalezione. Po uwzględnieniu liczby docelowej rola algorytmu Shor jest zakończona
Na wysokim poziomie cały ten proces może wydawać się dość prosty. I na wysokim poziomie tak jest. Jeśli jednak każdy krok zostanie szczegółowo wyjaśniony, można go podzielić na serię wykładów. Implementacja algorytmu może być wykonana po ukończeniu krótkiego samouczka, ale pełne zrozumienie algorytmu może zająć wiele godzin nauki.
Jak zaimplementowany jest algorytm Shora?
Algorytm Shora nie jest łatwy w implementacji. Po pierwsze, algorytm składa się z trzech głównych komponentów: jeden wykorzystuje obliczenia klasyczne, drugi obliczenia kwantowe, a trzeci obliczenia klasyczne. W sumie algorytm składa się z sześciu ważnych kroków opisanych powyżej.
Jednakże, dodając do tej złożoności, komponent kwantowy algorytmu faktoryzacji Shora ma cztery podkomponenty, z których każdy mógłby mieć cały artykuł do wyjaśnienia. Podczas gdy dwa z tych podskładników kwantowych są stosunkowo łatwe do wyjaśnienia, pozostałe dwa są niezwykle ważnymi podprogramami kwantowymi. W rzeczywistości są to prawdopodobnie dwa najważniejsze podprogramy kwantowe.
Jeden z najważniejszych podkomponentów kwantowych nazywany jest kwantową estymacją fazy (QPE). Co ważne, wykonuje on arytmetykę modularną niezbędną do znalezienia okresu liczby, którą należy rozłożyć na czynniki. Innymi słowy, to właśnie stąd pochodzi moc faktoryzacji algorytmu Shor.
Innym kluczowym podkomponentem kwantowym jest odwrotna kwantowa transformata Fouriera (iQFT). Mówiąc najprościej, iQFT pobiera kwantowy wynik arytmetyki modułowej, która bezpośrednio go poprzedza, i przekształca go w klasyczną informację, którą można wydobyć z obwodu kwantowego w procesie znanym jako pomiar.
Ogólnie rzecz biorąc, algorytm faktoryzacji Shora rozpoczyna się od kilku klasycznych kroków. Następnie komponent kwantowy znajduje okres liczby, która ma zostać poddana faktoryzacji.
Odbywa się to za pomocą kwantowej arytmetyki modularnej, której wynik jest konwertowany z informacji kwantowej na klasyczną, dzięki czemu można go wykorzystać. Na koniec jest jeszcze kilka klasycznych kroków. Jeśli odpowiedź nie zostanie znaleziona, a liczba nie może zostać rozłożona na czynniki, algorytm jest w pełni dostosowywany i powtarzany.
Ilu kubitów wymaga algorytm Shora?
Aby odpowiedzieć na to pytanie, konieczne jest rozróżnienie między kubitami fizycznymi i logicznymi. Wszystkie współczesne kubity są kubitami fizycznymi. Są one niezwykle “zaszumione”, to znaczy podatne na błędy. Wyniki obliczeń kwantowych o jakimkolwiek znaczeniu nie pozwalają nam odróżnić odpowiedzi poprawnych od niepoprawnych. Każde możliwe rozwiązanie ma takie samo prawdopodobieństwo bycia poprawnym, co jest równoznaczne z brakiem odpowiedzi.
W tym miejscu do gry wkraczają kubity logiczne. Fizyczne kubity muszą być połączone i zorganizowane w taki sposób, aby wspólnie zapewniały wystarczającą korekcję błędów, aby można je było uznać za “odporne na błędy”. W tym momencie te kolektywy kubitów stają się znane jako “kubity logiczne” lub czasami jako “kubity idealne”.
Te logiczne kubity są abstrakcjami. Obecnie obwód kwantowy z pięcioma kubitami reprezentuje pięć bardzo hałaśliwych, podatnych na błędy kubitów fizycznych. Twórcy algorytmów kwantowych w niedalekiej przyszłości będą chcieli, aby te pięć kubitów reprezentowało logiczne, odporne na błędy, wolne od błędów kubity.
Szacunki dotyczące liczby fizycznych kubitów potrzebnych do reprezentowania jednego logicznego kubitu są różne, ale rozsądną liczbą, z którą można pracować, jest 1000. Większość uważa, że komputer kwantowy potrzebowałby około 1000 fizycznych kubitów do reprezentowania jednego logicznego kubitu.
Dla porównania, największy dotychczasowy komputer kwantowy ma tylko 127 fizycznych kubitów. I chociaż IBM zamierza wprowadzić urządzenie 1000-kubitowe do przyszłego roku, to wciąż jest to tylko 1000 fizycznych kubitów. Przed stworzeniem pierwszego logicznego kubitu jest jeszcze wiele do zrobienia.
Szacunki dotyczące liczby kubitów wymaganych dla algorytmu faktoryzacji Shora znacznie się różnią. Po pierwsze, jak już wspomniano, konieczne jest rozróżnienie między szacunkami dla kubitów logicznych i szacunkami dla kubitów fizycznych. W zależności od celów badacza, liczbę wymaganych kubitów można zmniejszyć, poświęcając czas wykonania i głębokość schematu.
Z drugiej strony, liczbę kubitów można znacznie zwiększyć, skracając czas wykonania i głębokość obwodu. Różnice polegają na tym, że mniej kubitów będzie dostępnych szybciej, podczas gdy najszybszy czas wykonania będzie najbardziej opłacalny. Poniżej znajduje się kilka szacunków.
W artykule Davida Beckmana, Amalavoyala N. Chari, Srikrishny Devabhaktuni i Johna Preskilla “Efficient Networks for Quantum Factoring” z 1 sierpnia 1996 roku autorzy obliczyli, że faktoryzacja liczby K-bitowej zajęłaby K3 czasu i wymagałaby 5K+1 logicznych kubitów.
Zatem faktoryzacja 2,048-bitowej liczby, co oznacza złamanie szyfrowania RSA, zajęłaby 8,6 miliarda godzin i wymagałaby 10,241 logicznych qubitów, czyli około 10 milionów fizycznych qubitów. Niestety, nie jest jasne, ile czasu zajęłoby 8,6 miliarda, ponieważ różne technologie pracy z kubitami działają z różną prędkością.
Następnie, w artykule Stéphane’a Beauregarda “A Scheme for Shor’s Algorithm Using 2n+3 qubits” z 21 lutego 2003 roku, autorzy obliczyli, że faktoryzacja liczby K-bitowej wymagałaby 2n+3 logicznych qubitów. Zatem faktoryzacja 2048-bitowej liczby wymagałaby jedynie 4099 logicznych kubitów, czyli około 4 milionów fizycznych kubitów. Ponownie, obecnie nie istnieje zero kubitów logicznych. Artykuł ten przybliżył jednak algorytm faktoryzacji Shora do wdrożenia.
Następnie, w książce “Fast Quantum Modular Exponentiation Architecture for the Shor Factorisation Algorithm” autorstwa Archimedesa Pavlidisa i Dimitrisa Gizopoulosa (s. 0649-0682), opublikowanej w maju 2014 roku, autorzy zaproponowali implementację 9n+2 poprzez dodanie znacznej liczby kubitów w celu zmniejszenia głębokości obwodu. Aby złamać 2048-bitowe szyfrowanie RSA, potrzeba 18 434 logicznych kubitów, czyli około 18 milionów fizycznych kubitów.
Jednym z powodów minimalizacji głębokości schematu jest fakt, że z czasem kubity tracą swoją “łączność”. Im dłużej trwa wykonanie obwodu, co częściowo zależy od głębokości obwodu, tym więcej szumów może przedostać się do systemu i tym więcej błędów może pojawić się w wynikach. Nawet dzisiaj jednym ze sposobów na zmniejszenie liczby błędów jest zminimalizowanie głębokości kodu.
Ostatnio, 13 kwietnia 2021 roku, w artykule zatytułowanym “How to Compute a 2048-bit RSA Integer in 8 Hours Using 20 Million Noisy Qubits”, autorzy Craig Gidney i Martin Ecker oszacowali, że do złamania szyfrowania RSA potrzeba około 20 000 logicznych qubitów lub około 20 milionów fizycznych qubitów. Autorzy poszli jeszcze dalej i oszacowali czas działania swojej konfiguracji na zaledwie osiem godzin.
Porównując to z szacowanym czasem wymaganym przez najpotężniejsze superkomputery na świecie do złamania szyfrowania RSA, który znacznie przekracza czas życia człowieka, moc algorytmu Shor staje się jasna. Inne szacunki dotyczące liczby kubitów dla algorytmu Shora można znaleźć w odnośnikach w tym artykule.
Ponownie, czas działania algorytmu Shora jest odwrotnie proporcjonalny do liczby dostępnych kubitów logicznych. Zależy on również od zastosowanej technologii kwantowej, ponieważ różne komputery kwantowe wykonują operacje z bardzo różnymi prędkościami. Im mniej kubitów, tym dłużej algorytm będzie działał, ale tym szybciej nowoczesne kryptosystemy staną się przestarzałe. I odwrotnie, im więcej kubitów, tym szybciej nowoczesne kryptosystemy zostaną zhakowane. Na szczęście te czasy są jeszcze odległe.
Jak uruchomić algorytm Shora?
Nie da się.
Największą liczbą, jaką do tej pory obliczono za pomocą algorytmu Shora, jest 21. Najmniejszą możliwą liczbą, którą można obliczyć za pomocą algorytmu, jest 15. Jest to bardzo wąski zakres z dwóch powodów. Po pierwsze, algorytm Shora wymaga dużej liczby kubitów, jak wspomniano powyżej, a duża liczba kubitów nie istnieje.
Po drugie, współczesne kubity są “zaszumione”, co oznacza, że są bardzo podatne na błędy. Głębokość schematu wymagana przez algorytm daje wyniki z tak wieloma błędami, że niemożliwe jest rozróżnienie między poprawnymi i niepoprawnymi rozwiązaniami.
Innymi słowy, RSA i inne potencjalnie podatne na ataki kryptosystemy są bezpieczne. Na razie. NIST kontynuuje prace nad wyborem standardu post-kwantowego, znanego również jako standard “bezpieczny kwantowo”, który, mamy nadzieję, zostanie powszechnie wdrożony na długo przed udostępnieniem wystarczającej liczby odpornych na błędy kubitów, aby to zagrożenie stało się rzeczywistością.
Pomimo długiego okresu czasu i prac podejmowanych w celu ograniczenia ryzyka, algorytm faktoryzacji Shora pozostaje równie dobrym sposobem na podniesienie świadomości na temat obliczeń kwantowych, jak wtedy, gdy został odkryty po raz pierwszy.
Dyrektorzy we wszystkich branżach powinni być zaniepokojeni potencjalnymi zagrożeniami dla wrażliwej komunikacji i danych, a ryzyko jest realne. Miejmy nadzieję, że w trakcie tego procesu dowiedzą się o dziesiątkach innych potencjalnych zastosowań obliczeń kwantowych, które pewnego dnia mogą przynieść znaczące korzyści ich przedsiębiorstwom.
Źródło: https://www.classiq.io
