Kwantowe łamacze szyfrów – rozmowa z Jerzym Dajką

Większość z nas na co dzień nie martwi się o to, czy używając karty płatniczej lub dokonując zakupów online nie padnie ofiarą włamania na konto bankowe. Czujemy się w miarę pewnie, bo nie licząc awarii albo ludzkiego błędu, ufamy obecnym systemom szyfrowania danych. Zasada ich działania opiera się na prostym fakcie, że niektóre operacje matematyczne łatwiej jest wykonać w jedną stronę niż w drugą. O ile całkiem szybko możemy obliczyć, że wynikiem mnożenia liczb 31 i 69931 jest 2167861, o tyle rozłożenie liczby 2167861 na czynniki pierwsze to nieco cięższa sprawa. Przeprowadzenie podobnej operacji na naprawdę dużej liczbie, mającej kilkaset cyfr, mogłoby zająć współczesnym superkomputerom całe tysiące lat.

Szkopuł w tym, że znajdujemy się coraz bliżej skonstruowania maszyny, która z podobnymi łamigłówkami upora się mgnieniu oka. Czy to oznacza, że aktualne zabezpieczenia staną się bezużyteczne? Jak wielki postęp i jak wielkie zamieszanie zwiastuje nadejście informatyki kwantowej? Na ten temat rozmawialiśmy z prof. Jerzym Dajką, fizykiem kwantowym i wykładowcą Wydziału Nauk Ścisłych i Technicznych UŚ.


Panie Profesorze, kto obecnie zajmuje się informatyką kwantową? To nadal głównie działka fizyków, czy już informatyków?

To coraz bardziej praca dla informatyków lub „informatycznie zorientowanych” fizyków, a coraz mniej dla fizyków w tradycyjnym znaczeniu tego fachu. Pierwsze klasyczne komputery, jak np. MANIAC I von Neumanna były wielkimi urządzeniami na usługach wojska, z ogromną ilością lamp i grupą żołnierzy, którzy na bieżąco wymieniali podzespoły, gdy te się przepalały. Informatyka była więc w swej wczesnej warstwie implementacyjnej zajęciem raczej dla elektryków i elektroników. Z czasem, gdy komputery stały się coraz bardziej uniwersalne, pracować na nich zaczęli przede wszystkim informatycy i matematycy.

Z komputerami kwantowymi będzie podobnie. Oczywiście samo zbudowanie komputera wymaga obecności fizyków i to najwyższej, światowej klasy doświadczalników, specjalistów z zakresu nanofizyki i optyki kwantowej. Dążymy jednak do tego, by komputery kwantowe gwarantowały łatwy i wolny od koniecznej znajomości detali technologicznych dostęp dla informatyków, speców od myślenia algorytmicznego. Docelowo będą oni mogli korzystać z komputerów kwantowych tak, jak teraz korzystamy z komputerów klasycznych.

W przypadku maszyn kwantowych fizycy, po pierwsze umiejętnie wykorzystali opisane mechaniką kwantową własności świata, dla stworzenia pionierskich algorytmów kwantowych przewyższających możliwościami znane algorytmy klasyczne. Po drugie, zastosowali zaawansowane techniki doświadczalne dla stworzenia pierwszych implementacji obliczeń kwantowych. Z przymrużeniem oka można powiedzieć, że rosnące zainteresowanie obliczeniami kwantowymi, które dziś wykazują informatycy, jest pośrednim dowodem skuteczności działań fizyków. Informatycy – ludzie praktyczni – oczekują konkretnych wyników działania. Ich obecność w tej dziedzinie sugeruje, że informatyka kwantowa dobrze rokuje.

Rozwój informatyki w dwóch fotografiach. U góry John von Neumann, genialny matematyk i współtwórca architektury komputerów opartych o lampy elektronowe. Na dole jeden z dyrektorów Google, Sundar Pichai, obok prototypu komputera kwantowego.

Jednak w tej chwili dla przeciętnego użytkownika komputery kwantowe nadal są – i pewnie jeszcze długo pozostaną – niedostępne. Ale załóżmy, że komuś naprawdę zależy, żeby popracować na takim urządzeniu. Jakie ma szansę na realizację takiego marzenia?

Kanadyjskie D-Wave Systems posiada wielokubitowy kwantowy wyżarzacz służący implementacji pewnej klasy algorytmów optymalizacyjnych. Istnieją też oparte na modelu kwantowych bramek logicznych uniwersalne maszyny Google’a Quantum AI oraz IBM’u Quantum; czy wreszcie usługa Microsoft Azure Quantum. Swoistą zachętą dla programistów jest oferowana możliwość darmowego (w ograniczonym zakresie mocy obliczeniowej) użytkowania infrastruktury wspomnianych urządzeń dla przeprowadzenia obliczeń kwantowych.

Dostęp do komputerów kwantowych jest możliwy poprzez narzędzia, które mogą (powtórzmy, w mocno okrojonym zakresie) symulować ich działania. Narzędziem takim może być stojący na naszym biurku laptop. Przykładowo dla języka Python istnieje pakiet bibliotek Qiskit (IBM) lub Cirq (Google), z pomocą których daje się programować komputery kwantowe lub ich symulatory. Warto zaznaczyć, że kosmetyczna zmiana kodu przetestowanego na symulatorze pozwala wykorzystać go później na prawdziwym komputerze kwantowym. Spłycając zagadnienie, można powiedzieć, że do programowania obecnie istniejących komputerów kwantowych wystarczy znać Pythona i kwantową algorytmikę.

To brzmi jak kolejna przesłanka wskazująca, że rewolucja zbliża się wielkimi krokami. Ale właśnie: mediach dość regularnie – przynajmniej raz na kilka tygodni – serwują informację, że oto dokonano kolejnego przełomu w rozwoju komputerów kwantowych. Ile prawdy jest w tych wszystkich doniesieniach i czy można na przestrzeni ostatnich lat faktycznie mówić o jakimś przełomie?

Trudno w obliczeniach kwantowych wskazać coś, co dziś można nazwać przełomem. Mimo wszystko, wciąż jesteśmy daleko od praktycznych implementacji. Powodów jest kilka: nie radzimy sobie z dekoherencją, która skutecznie „zabija” kwantowość; wciąż mamy też za mało kubitów do wykorzystania w naszych obliczeniach. Nawet D-Wave, operujący na ponad 2 tysiącach kubitów i ograniczony do pewnej klasy algorytmów, nam nie wystarcza. Efektywne obliczenia kwantowe wymagają korekty błędów, do której przeprowadzenia wymagane są dodatkowe kubity. I nagle okazuje się, że 2 tysiące kubitów to wcale nie tak dużo.

Klasyczne komputery opierają całe swoje działanie o bity, czyli ciągi zer i jedynek. Kubit natomiast, niczym sławny kot Schrödingera, jest kwantowomechaniczną mieszaniną wszystkich dostępnych możliwości. Problem polega na tym, że stan superpozycji pozostanie niezmiernie delikatny i może zostać zburzony przez najmniejszy bodziec z zewnątrz.

A jak traktować powtarzające się doniesienia o tym, że jakaś firma lub państwo osiągnęło supremację/przewagę kwantową?

Rzeczywiście, znane są przykłady obliczeń wykazujących coś, co dumnie nazywa się „przewagą kwantową”. Świadczyłoby to, że pewne stosunkowo proste zagadnienia rzeczywisty i istniejący komputer kwantowy rozwiązuje lepiej niż jakikolwiek komputer klasyczny. Fakt, że za pomocą kubitów jesteśmy w stanie zrobić coś relatywnie prostego szybciej i lepiej niż używając bitów, jest pięknym wynikiem. Jednak wciąż nie dysponujemy wystarczającą ilością kubitów, gdy musimy zmierzyć się z zagadnieniem wymagającym dużych klasycznych zasobów obliczeniowych. Ciągle jeszcze jesteśmy na etapie bardzo wstępnym i teoretycznym, jeżeli chodzi o obliczenia kwantowe.

Kiedy mowa o komputerach kwantowych zawsze wskazuje się na ich nieprawdopodobne możliwości. Architektura oparta o kubity ma pozwalać na dokonywanie błyskawicznych operacji, w tempie niedostępnym dla maszyn korzystających z klasycznych bitów. Czy ta różnica w potencjale obliczeniowym jest w praktyce naprawdę AŻ TAK kolosalna?

Spójrzmy na wspomniany wcześniej kwantowy komputer D-Wave. Jest inny niż jakikolwiek klasyczny komputer, ale specjalizuje się w szczególnej klasie obliczeń. Komputery IBM czy Google’a są maszynami uniwersalnymi, których działanie opisuje model bramek logicznych – podobnych jak w przypadku komputerów klasycznych. Nie wnikając w to jak są zbudowane komputery klasyczne, ich działanie opiera się o podejście zdominowane przez tzw. model bramkowy: istnieje pewien uniwersalny zbiór bramek logicznych, który wystarcza do przeprowadzenia dowolnych obliczeń.

Obliczenia prowadzone na istniejących uniwersalnych komputerach kwantowych można opisać modelem, w jakim oprócz bramek klasycznych występują również bramki kwantowe. Te ostatnie pozwalają np. na wykorzystanie potencjału obliczeniowego kwantowej superpozycji bitów. Skutek jest taki, że pula bramek, za pomocą których modelujemy obliczenia, poszerza się o bramki pozwalające wykonywać operacje, których nie da się przeprowadzić w klasycznych komputerach. Innymi słowy: używając komputera kwantowego jesteśmy w stanie zrobić to, co z wykorzystaniem komputera klasycznego oraz dużo, dużo więcej. Wobec tego, w oczywisty sposób próbuje się je wykorzystać do zagadnień, przy których klasyczne komputery z różnych przyczyn słabo sobie radzą.

Prosta wizualizacja tego, jak działają klasyczne bramki typu NOT (odwraca sygnał wejściowy), OR (daje 1, gdy przynajmniej jeden sygnał jest włączony) i AND (daje 1 tylko, gdy oba sygnały wejściowe są włączone).

Czyli haczyk jest taki, że istnieją klasy operacji skrojone lepiej lub gorzej pod bramki kwantowe.

Maszyna D-Wave’a wyróżnia się pośród samych komputerów kwantowych, gdyż specjalizuje się w implementacji algorytmu „wyżarzania kwantowego” – kwantowej wersji znanego informatykom kłopotu optymalizacyjnego, występującego czasem pod nazwą problemu szkła spinowego. Jako przykład zastosowania kanadyjskiego urządzenia może posłużyć rozwiązanie problemu kolorowania pewnej mapy. Jest to tylko pozornie proste zadanie, w którym poszczególne miejsca na mapie należy oznaczać w taki sposób, by sąsiadujące ze sobą powierzchnie nie pokryć tą samą barwą i to przy ograniczonej liczbie kolorów. Z drugiej strony D-Wave nie jest najlepiej przystosowany do faktoryzacji liczb (grupie algorytmów wykorzystywanej w kryptografii), a zatem – choć dysponuje dużą liczbą pracujących kubitów – potencjalnie stanowi mniejsze zagrożenie dla klasycznych kryptosystemów niż uniwersalne maszyny wykorzystujące model bramkowy.

Nie zawsze jest łatwo pokazać, że tego, co robi komputer kwantowy, nie dałoby się wykonać na komputerze klasycznym. Niektórym rozwiązaniom proponowanym przez D-Wave’a zarzucano, że w istocie dałoby się je również otrzymać „klasycznie”.

Problem czterech kolorów
Jaka jest minimalna liczba kolorów konieczna do skutecznego pokolorowania mapy (tak żeby sąsiadujące państwa nie miały identycznej barwy)? Tzw. twierdzenie o czterech kolorach, to przykład problemu matematycznego, z którym D-Wave radzi sobie lepiej od konwencjonalnych komputerów.

Wspomniał Pan Profesor o zagrożeniu. Przy okazji dyskusji o możliwościach komputerów kwantowych równie często pojawia się kwestia bezpieczeństwa danych. W mediach zdarza się słyszeć np. Chińczycy, jako pierwsi na świecie mogliby wykorzystać nowatorską technologię do ataków na klasyczne systemy zabezpieczeń spotykane w bankach, administracji czy służbie zdrowia. W ten sposób uzyskaliby dostęp do bezcennych informacji.

Wiele krajów inwestuje duże środki na badania w zakresie implementacji obliczeń i komunikacji kwantowej. Chiny są tutaj dobrym przykładem. Tam w ostatnich latach dokonał się znaczący postęp w zakresie badań teoretycznych i eksperymentalnych z dziedziny informacji kwantowej. Wielu wybitnych młodych chińskich badaczy, po latach spędzonych na post-dokach na całym świecie, gdzie uczyli się kwantowego know-how, zostało profesorami we własnym kraju. Tam wyposażono ich w odpowiednie zasoby materialne do prowadzenia badań.

Czy w obliczu potencjalnego ataku kwantowego jesteśmy zupełnie bezbronni?

Gdybyśmy podryfowali w stronę teorii spiskowych moglibyśmy zastanawiać się, czy ktoś dysponujący odpowiednimi zasobami w jakimś pokątnym miejscu i ukrywający wyniki badań przed społecznością naukową świata, mógł zbudować dostatecznie sprawny komputer kwantowy. Dla tej osoby świat nagle  stałby się „jednostronnie przezroczysty”. Byłaby to dominacja w świecie, porównywalna jedynie do tego, co się wydarzyło po zbudowaniu bomby atomowej przez Stany Zjednoczone.

Dwa miesiące temu BT oraz Toshiba uruchomiły komercyjną sieć komunikacyjną, której bezpieczeństwo jest gwarantowane przez prawa przyrody, a w szczególności kwantowe własności świata. To przykład działania, którego celem jest przygotowanie do jakościowej zmiany, jaka nastąpi, gdy implementacja obliczeń kwantowych – idąca w parze z rozwojem funkcjonalności komputerów kwantowych – osiągnie poziom wystarczający dla praktycznych zastosowań.

Komunikacja kwantowa jest odpowiedzią na niebezpieczeństwa związane z używaniem komputerów kwantowych do ataków na klasyczne kryptosystemy dające nam dziś bezpieczeństwo. Wiemy, że informacja jest w stanie wpływać na wyniki konfliktów zbrojnych i podejmowanie decyzji handlowych. Przypomnijmy tylko, w jaki sposób złamanie kodu Enigmy wpłynęło na przebieg II wojny światowej.

Jak kryptograficzne zabezpieczenia wyglądają w praktyce obecnie? Na czym polega ich słabość?

Możemy wskazać najpopularniejsze grupy algorytmów, które wykorzystuje się dziś w kryptografii, a których bezpieczeństwo opiera się, mówiąc w pewnym uproszczeniu: 1) na naszej nieumiejętności dzielenia liczb na czynniki pierwsze, czyli wspomnianej już faktoryzacji liczb, 2) problemie logarytmu dyskretnego, a nawet 3) bardziej zaawansowanych metodach teorio-liczbowych opartych na krzywych eliptycznych. Tymczasem my, ludzie, w istocie nie wiemy, czy metody te są bezpieczne – wiemy jedynie, że w praktycznie wykorzystywanych przypadkach nie umiemy ich złamać w sensownym czasie, krótszym niż czas życia wszechświata.

Jednakże – i tu jest clou problemu – gdyby ktoś użył komputera kwantowego wykonującego algorytm Shora, będący kwantowym algorytmem faktoryzacji liczb, potrafiłby złamać klasyczne kryptosystemy niemal od ręki. Mając to na uwadze już w 2015 roku amerykańska Narodowa Agencja Bezpieczeństwa (NSA) rekomendowała wdrożenie rozwiązań, które nazywamy „kryptografią postkwantową”, a zatem stosowanie takich algorytmów klasycznych w kryptografii, które będą odporne na ataki przy użyciu komputera kwantowego, który umiałby robić to, co wyobrażamy sobie, że będzie robić. To podejście pozwala, jeśli nie rozwiązać, to odsunąć problem w przyszłość. Przynajmniej do czasu, aż pojawi się kolejny algorytm kwantowy…

Faktoryzacja liczb
Rozkład liczb na czynniki pierwsze (faktoryzacja) nie wydaje się specjalnie skomplikowanym problemem, jednak w przypadku naprawdę dużych liczb staje się zadaniem niewykonalnym w sensownym czasie dla konwencjonalnych maszyn. Doświadczenie z 2009 roku wykazało, że rozłożenie liczby złożonej z 232 cyfr zajęłoby najlepszemu dostępnemu wtedy superkomputerowi przynajmniej 2 tysiące lat.

Czyli konwencjonalna kryptografia nie znajduje się na zupełnie straconej pozycji. Jednak informatyczny wyścig zbrojeń trwa, a szansa na to, że klasyczne sposoby w końcu padną pod naporem ataków kwantowych, z czasem będzie tylko rosła?

Trwałą neutralizację zagrożenia, o którym mówimy zapewnia komunikacja kwantowa. Zamiast wymieniać tajny klucz przy użyciu starych metod klasycznych typu RSA lub bardziej zaawansowanych metod postkwantowych, można odwołać się do własności świata kwantów, które zapewniają bezpieczną procedurę kwantowej wymiany kluczy. Oczywiście najprościej byłoby komunikować się używając tajnego klucza: przesyła się informację, odbiorca ma klucz i tę informację deszyfruje. Metoda ta działa świetnie i jest niezwykle bezpieczna. Problem jednak w tym, jak bezpiecznie dostarczyć klucz przyszłemu odbiorcy wiadomości.

RSA, którą można się posłużyć, to najstarsza i wciąż popularna metoda kryptograficzna z kluczem jawnym. Opiera się na faktoryzacji liczb, niestety potencjalnie podatnej na ataki przeprowadzane przez komputer kwantowy. Jeżeli jednak w miejsce klasycznej kryptografii z kluczem jawnym zastosujemy którąś z metod kwantowej wymiany klucza, wówczas problem zniknie. To najprostsza i najpewniejsza z dróg – nie modyfikowanie czy szukanie nowych algorytmów kryptograficznych, lecz zastąpienie klasycznej komunikacji przez kwantową.

To znaczy, że najlepszą odpowiedzią na kwantowy atak będzie kwantowa ochrona.

Na szczęście w tej dziedzinie mamy już duże osiągnięcia. Nośnikami kwantowej informacji są zwykle fotony, które przesyła się za pomocą światłowodów (można to już robić na setki kilometrów), a nawet „luzem” w przestrzeni, tworząc w ten sposób podwaliny „kwantowego internetu”. 

Taka komunikacja kwantowa jest bezpieczna ze względu na specyfikę układów kwantowych, którą fizycy odkrywali od lat. Pierwsza istotna właściwość jest taka, że pomiar (potrzebny do pozyskania informacji), nieodwracalnie i zauważalnie zmienia nośnik informacji. Fakt ten wykorzystuje się dla potwierdzenia wiarygodności przesłanej informacji. Po drugie nie można kopiować informacji kwantowej – można to robić co najwyżej w przybliżeniu. Ta cecha kwantowej informacji istotnie odróżnia ją od jej klasycznej siostry. To własności przyrody, które wykorzystujemy, zapewniają naszym danym bezpieczeństwo.

Można bardzo łatwo weryfikować czy dane urządzenie faktycznie w sposób kwantowy przesyła informację. Jednym z najskuteczniejszych narzędzi jest kwantowa nielokalność skutkująca istnieniem stanów splątanych, wykorzystywanych skądinąd w teleportacji. Jeżeli kanał komunikacyjny zachowuje korelacje kwantowe między stronami komunikującymi się, to  jest prawdziwie kwantowy,  jeżeli zaś tego nie potrafi, to tylko kwantowy udaje i jest podatny na atak.

Splątanie kwantowe w kryptografii
Kiedy mamy do dyspozycji parę splątanych cząstek, zaburzenie kwantowego stanu jednej natychmiast wpływa na cały układ. Fakt ten służy przy opracowywaniu nowych metod kryptograficznych. Próba przechwycenia zaszyfrowanej informacji nie może pozostać niezauważona.

Czy jest jakikolwiek obszar, na którym komputery klasyczne wygrywają starcie z kwantowymi rywalami?

Cena i warunki, w których dobrze funkcjonują. Komputer klasyczny o całkiem poważnej mocy obliczeniowej może działać w warunkach pokojowych. Lepsze klastry wymagają odpowiedniej klimatyzacji. Natomiast komputery kwantowe, żeby nie przestać „być kwantowymi”, potrzebują do pracy temperatury rzędu ułamka kelwina. W środku D-Wave’a jest zimniej niż w przestrzeni kosmicznej. Przewagi komputerów klasycznych są zatem o ekonomicznym, a nie obliczeniowym charakterze.

Podczas rozmów o kwantowych komputerach padają głównie nazwy amerykańskich gigantów jak Google czy IBM, ewentualnie napomknie się o Chińczykach. Jaki wkład w rozwój tej dziedziny mają Europejczycy? Czy w te starania zaangażowane są również polskie placówki?

Rozwój informatyki kwantowej i kwantowej teorii informacji w jej warstwie teoretycznej dokonał się w wielkiej mierze dzięki wynikom polskich naukowców. Ryzykując pominięcie wielu poważnych graczy, można wskazać grupę gdańską, związaną z prof. Ryszardem Horodeckim. Zawdzięczamy im przełomowe wyniki w zakresie kwantowego splątania. Należy też wspomnieć prof. Artura Ekerta (kiedyś związanego z Uniwersytetem Jagiellońskim, a teraz przebywającego na Uniwersytecie Oxfordzkim). Jego nazwisko nosi jeden z najbardziej znanych kwantowych protokołów kryptograficznych.

Prof. Jerzy Dajka pozdrawia czytelników. 🙂

Badań Polaków nie można oddzielić od europejskich. Nauka nie ma i nie powinna mieć przynależności państwowej, ani tym bardziej narodowości. Osiągnięcia grup badawczych afiliowanych w krajach Unii Europejskiej stanowią najtwardszy rdzeń dojrzewającej kwantowej informatyki, zarówno teorii, jak i praktyki. Europa jako wspólnota przykłada dużą wagę do finansowania badań i innowacji w dziedzinie technologii kwantowych czego dowodem może być niedawny program QuantERA.

Bardzo dziękuję za rozmowę.

Z prof. Jerzym Dajką rozmawiała
Weronika Cygan

Katar, atom i mechanika kwantowa Maksymalnie poplątane wnętrze protonu Gluony, czyli kwantowe kolorowanki [+słowo o egzotycznych hadronach]