Naukowcy donoszą, iż technika zadziałała w demonstracji na małą skalę, ale inni specjaliści są sceptyczni, czy procedurę można zwiększyć, aby pokonać zwykłe komputery w zadaniu. Mimo to ostrzegają, iż artykuł opublikowany pod koniec zeszłego miesiąca w repozytorium arXiv przypomina o wrażliwości prywatności w Internecie.
Wiadomo, iż komputery kwantowe stanowią potencjalne zagrożenie dla obecnych systemów szyfrowania, ale technologia ta jest wciąż w powijakach. Naukowcy zwykle szacują, iż upłynie wiele lat, zanim komputery kwantowe będą w stanie złamać klucze kryptograficzne szybciej niż zwykłe komputery.
W latach 90. ubiegłego wieku naukowcy zdali sobie sprawę, iż komputery kwantowe mogą wykorzystywać osobliwości fizyki do wykonywania zadań, które wydają się być poza zasięgiem „klasycznych” komputerów. Peter Shor, matematyk, który w tej chwili pracuje w Massachusetts Institute of Technology w Cambridge, pokazał w 1994 roku, jak zastosować zjawiska superpozycji kwantowej – opisującej zdolność obiektów wielkości atomowej do istnienia w kombinacji wielu stanów w tym samym czasie – oraz interferencji kwantowej, która jest analogiczna do tego, jak fale na stawie mogą dodawać się do siebie lub wzajemnie się znosić, do faktoryzacji liczb całkowitych na pierwiastki, czyli liczby całkowite, których nie można dalej dzielić bez reszty.
Algorytm Shora sprawiłby, iż komputer kwantowy byłby wykładniczo szybszy od klasycznego w łamaniu systemu szyfrowania opartego na dużych liczbach pierwszych, zwanego Rivest-Shamir-Adleman lub RSA, od inicjałów jego wynalazców, a także kilku innych popularnych technik kryptograficznych, które w tej chwili chronią prywatność i bezpieczeństwo w Internecie. Jednak wdrożenie techniki Shora wymagałoby komputera kwantowego znacznie większego niż dostępne prototypy. Rozmiar komputera kwantowego mierzy się w bitach kwantowych, czyli qubitach. Naukowcy twierdzą, iż do złamania RSA może być potrzebny milion lub więcej qubitów. Największa dostępna w tej chwili maszyna kwantowa – układ Osprey, ogłoszony w listopadzie przez IBM – ma 433 qubity.
Świeże podejście
Shijie Wei z Pekińskiej Akademii Nauk Informatyki Kwantowej i współpracownicy obrali inną drogę do pokonania RSA, opierając się nie na algorytmie Shora, ale Schnorra – procesie faktoryzacji liczb całkowitych opracowanym przez matematyka Clausa Schnorra na Uniwersytecie Goethego we Frankfurcie w Niemczech, również w latach 90. Algorytm Schnorra został zaprojektowany do działania na klasycznym komputerze, ale zespół Wei zaimplementował część procesu na komputerze kwantowym, używając procedury zwanej kwantowym algorytmem przybliżonej optymalizacji, lub QAOA.
W pracy, która nie została jeszcze zrecenzowana, autorzy twierdzą, iż ich algorytm może złamać silne klucze RSA – liczby zawierające ponad 600 cyfr dziesiętnych – używając tylko 372 qubitów. W e-mailu do Nature w imieniu wszystkich autorów, Guilu Long, fizyk z Uniwersytetu Tsinghua w Chinach, ostrzegł, iż posiadanie wielu qubitów nie jest wystarczające, a obecne maszyny kwantowe są przez cały czas zbyt podatne na błędy, aby skutecznie wykonywać tak duże obliczenia. „Samo zwiększenie liczby qubitów bez zmniejszenia stopy błędu nie pomaga”.
Chao-Yang Lu, fizyk, który buduje komputery kwantowe na University of Science and Technology of China w Hefei i który nie był zaangażowany w projekt, mówi, iż uruchomienie algorytmu QAOA na tak małej maszynie wymagałoby, aby każdy z 372 qubitów działał bezbłędnie przez 99,9999% czasu. Najnowocześniejsze qubity ledwie osiągnęły dokładność 99,9%.
Kontrowersyjny dokument
Kłopot w tym, iż nikt nie wie, czy QAOA sprawia, iż faktoryzacja dużych liczb jest szybsza niż zwykłe uruchomienie klasycznego algorytmu Schnorra na laptopie. „Należy zaznaczyć, iż kwantowe przyspieszenie algorytmu jest niejasne” – piszą autorzy. Innymi słowy, chociaż algorytm Shora ma gwarancję skutecznego złamania szyfrowania, gdy (i jeśli) wystarczająco duży komputer kwantowy stanie się dostępny, technika oparta na optymalizacji może działać na znacznie mniejszej maszynie, ale może nigdy nie ukończyć zadania.
Michele Mosca, matematyk z University of Waterloo w Kanadzie, zwraca również uwagę na to, iż QAOA nie jest pierwszym znanym algorytmem kwantowym, który jest w stanie obliczać liczby całkowite przy użyciu małej liczby qubitów. On i jego współpracownicy opisali taki w 2017 roku. Badacze wiedzieli już więc, iż nie ma nic fundamentalnego, co wymagałoby, by komputery kwantowe były bardzo duże, by mogły czynnikować liczby.
Nawet jeżeli technika oparta na Schnorrze nie złamie Internetu, komputery kwantowe mogłyby to w końcu zrobić, uruchamiając algorytm Shora. Badacze bezpieczeństwa zajęli się opracowaniem szeregu alternatywnych systemów kryptograficznych, które są postrzegane jako mniej podatne na atak kwantowy, nazywane post-quantum lub quantum-safe. Ale badacze mogą również odkryć w przyszłości lepsze algorytmy kwantowe, które mogą pokonać te systemy, co może mieć katastrofalne skutki.
„Zaufanie do infrastruktur cyfrowych załamałoby się” – mówi Mosca. „Nagle przestawilibyśmy się z zarządzania migracją bezpieczną kwantowo, poprzez zarządzanie cyklem życia technologii, na zarządzanie kryzysowe” – dodaje. „To nie będzie ładne w żaden sposób”.
