Informatyka, komputery i kryptografia kwantowa

Abstract

W pracy przedstawiono podstawowe pojęcia informatyki kwantowej jakimi są qbity oraz ich in-terpretację fizyczną, taką jak polaryzacja. Opisano rejestr kwantowy, charakteryzując jego właściwości i możliwości zastosowania wynikające z właściwości superpozycji. Zastosowanie pojedynczych kwantów do kodowania i bezpiecznego przesyłania kluczy kryptograficznych przedstawiono na przy-kładzie algorytmu kwantowej dystrybucji klucza kryptograficznego. Opisano protokół BB84 oraz omówiono współpracę kwantowego i tradycyjnego kanału komunikacyjnego, występujących w tym protokole.
Autor: Maciej Nikodem

1. Informatyka i komputery kwantowe

Początku rozwoju informatyki kwantowej należy doszukiwać się w latach siedemdziesiątych ubiegłego stulecia. Rozwój tej, nadal nowoczesnej, dziedziny stał się możliwy dzięki wynalezieniu i coraz szerszych zastosowaniach światłowodów jako medium komunikacyjnego. Ze względu na kiepskie parametry (przede wszystkim dużą tłumienność) pierwsze światłowody (stosowane np. w medycynie) nie nadawały się do przesyłania informacji na rozsądne (w kontekście usług telekomunikacyjnych) odległości. Parametry stosowanych obecnie światłowodów są znacznie lepsze i w typowych roz-wiązaniach telekomunikacyjnych umożliwiają przesyłanie sygnałów na odległości około 100km, bez konieczności stosowania dodatkowych urządzeń regenerujących czy wzmacniających sygnał. W komunikacji światłowodowej (tradycyjnej) nośnikiem informacji są wiązki fotonów emitowane przez laser.

W odróżnieniu od tradycyjnej komunikacji światłowodowej, nośnikiem informacji kwantowej są pojedyncze fotony. Ta, mogłoby się wydawać, nieduża zmiana technologii pociąga za sobą szereg zmian zarówno korzystnych jak i utrudniających realizację komunikacji. Niewątpliwą zaletą dla komunikacji jest wzrost prędkości przesyłania danych, a trudnościami są np.: konieczność budowania dział fotonowych emitujących na żądanie pojedyncze fotony (ang. photon-on-demand) czy odbiorników potrafiących poprawnie odebrać przesyłane do nich fotony. Inną zaletą komunikacji za pośrednictwem pojedynczych kwantów jest możliwość (na razie tylko teoretyczna) budowy komputerów kwantowych. W odróżnieniu do klasycznych komputerów, które informacje kodują w sposób binarny, reprezentując ją jako poziomy napięć o odpowiedniej wartości (np.:w standardzie TTL 0-0.8V -> „0”, a 2-5V ->„1”), komputery kwantowe reprezentują informację jako superpozycję stanów bazowych. W najprostszym przypadku kwant może mieć dwa stany bazowe, które odpowiadają logicznym wartościom „0” oraz „1”. Taka jednostka informacji nazywana jest qbitem. Fizyczna interpretacja stanów bazowych może być różna i dla qbitu może być interpretowana jako: droga optyczna, polaryzacja fotonu czy spin fotonu.

Najważniejszą cechą komputerów kwantowych jest superpozycja czyli możliwość ustawienia ich rejestrów nie na określoną wartość (w sensie binarnym) lecz na superpozycję wszystkich wartości jakie mogą być w takim rejestrze zapisane. Rozważmy 3-bitowy rejestr klasycznego komputera i 3-qbitowy rejestr komputera kwantowego. Podczas gdy w komputerze klasycznym w jednej chwili czasu w rejestrze może być zapisana tylko jedna wartość to rejestr komputera kwantowego może jednocześnie zawierać wszystkie możliwe do zapisania (a więc 8) wartości.



Konsekwencją powyższego faktu jest możliwość wykonania operacji (np.: mnożenia, dzielenia, dodawania itd.) nie na konkretnej liczbie, ale na wszystkich liczbach zapisanych w rejestrze kwantowym jednocześnie.



Korzyść z zastosowania komputera kwantowego jest więc oczywista – jednocześnie można wyliczyć wartość pewnej funkcji (operacji) dla wielu argumentów. Pozostaje pytanie czy taka możliwość jest nam przydatna (w gruncie rzeczy ogromna większość obliczeń polega na wyliczaniu wartości dla konkretnych argumentów)? Odpowiedź na to pytanie jest twierdząca, jednak jak dotąd istnieje praktycznie jeden znany algorytm, który mógłby być na takim komputerze zaimplementowany [3]. Ironizując można więc powiedzieć, że na dzień dzisiejszy komputer kwantowy byłby maszyna liczącą wykonującą tylko jedną operację. Czemu więc naukowcy nie zarzucą pomysłu budowy komputera kwantowego? Odpowiedź tkwi w algorytmie, który ten komputer miałby wykonywać – algorytmie faktoryzacji liczb.

Zagadnienie faktoryzacji liczb jest zadaniem złożonym (należy do grupy zadań NP-trudnych), a najlepsze znane dziś algorytmy poszukiwania dzielników mają złożoność wykładniczą. Ze względu na tą trudność, problem faktoryzacji znalazł zastosowanie m.in. w kryptografii, gdzie pozwolił na stworzenie asymetrycznych algorytmów kryptograficznych. Obecnie jest on podstawą bezpieczeństwa niemal wszystkich systemów komputerowych (sklepy i bankowość elektroniczna, PGP itd.) oraz podstawą funkcjonowania podpisu elektronicznego, który w Polsce, UE i wielu innych krajach niesie takie same skutki prawne jak podpis odręczny. Zaletą implementacji algorytmu faktoryzacji na komputerze kwantowym jest możliwość sprowadzenia problemu szukania podzielników liczby do grupy problemów o wykładniczej złożoności obliczeniowej. W praktyce oznacza to znaczne skrócenie czasu potrzebnego do jego wykonania. Ponieważ znajomość tych podzielników pozwala na złamanie asymetrycznych algorytmów kryptograficznych to skrócenie czasu faktoryzacji jest równoznaczne zmniejszeniu bezpieczeństwa tych algorytmów.

Z jednej strony więc prace nad ujarzmieniem informatyki kwantowej stwarzają zagrożenie bezpieczeństwa, z drugiej - pozwalają rozwijać technologię, która daje możliwość poprawiania tego bezpieczeństwa. Tą możliwością i zarazem pewną odpowiedzią na zagrożenia ze strony komputera kwantowego (jednak nie 100% rozwiązaniem wszystkich problemów) jest kwantowa dys-trybucja kluczy, zwana znacznie częściej (choć nie do końca słusznie) kryptografią kwantową.