Kwantowe karty do głosowania jako alternatywa dla klasycznych, asymetrycznych algorytmów uzgadniania kryptograficznego klucza szyfrującego

Marcin Sobota

Marek Sobota

Marcin Sobota

Krzysztof Giaro

Juz dziś wiadomo, ze z chwilą udanej realizacji komputera kwantowego maszyna ta bedzie pozwalala na znajdowanie rozwiązan problemow obliczeniowych lezących poza zasiegiem komputerow klasycznych. Opracowano szereg algorytmow kwantowych, z ktorych najwiekszą slawą cieszy sie procedura Shora, pozwalająca efektywnie dokonywac tzw. faktoryzacji, tj. rozkladu bardzo duzych liczb naturalnych na czynniki pierwsze. Na trudności obliczeniowej faktoryzacji opiera sie bezpieczenstwo najpowszechniej dziś stosowanego szyfru z kluczem publicznym RSA, zatem udana realizacja komputera kwantowego uczynilaby stosowane dziś systemy szyfrujące przezroczystymi. Z kolei procedura Grovera w nieuporządkowanej bazie danych rozmiaru n znajduje rekord spelniający wybrane kryterium w czasie rzedu n^0.5, co oczywiście jest niewykonalne w modelu klasycznym. Model obliczenia kwantowego na trwale zadomowil sie na gruncie informatyki teoretycznej. Wyniki z zakresu kwantowych algorytmow rozstrzygających zagadnienia kombinatoryczne, kwantowych klas zlozoności obliczeniowej lub kwantowego kosztu komunikacyjnego obliczen są dziś regularnie publikowane w renomowanych periodykach i prezentowane na miedzynarodowych sympozjach poświeconych analizie algorytmow. Mimo niewątpliwie intensywnego rozwoju tego nowego obszaru wiedzy jego rezultaty wciąz pozostają dośc hermetyczne i nieczytelne dla szerszego ogolu odbiorcow. Jest to wynikiem silnie interdyscyplinarnego charakteru dziedziny, wymagającej od czytelnika znajomości szeregu pozornie niezwiązanych ze sobą faktow z zakresu informatyki (m.in. teorii algorytmow, modeli formalnych obliczen), matematyki (w tym algebry abstrakcyjnej i teorii liczb) oraz podstaw fizyki kwantowej. Niniejsze opracowanie stawia sobie za cel odczarowanie tej dziedziny, precyzyjnie selekcjonując material potrzebny do zrozumienia pojec obliczenia kwantowego, analizy kwantowych algorytmow oraz wprowadzając aparat formalny pozwalający na dalsze samodzielne studiowanie literatury. Dolozono tez wszelkich staran, aby uczynic te ksiązke spojną, zamknietą konstrukcją tematyczną, niewymagającą od czytelnika stykającego sie po raz pierwszy z informatyką kwantową poszukiwania pelniejszych wyjaśnien niezbednych pojec i wątkow pobocznych, ani tez przyjmowania na wiare wykorzystywanych faktow.

Krzysztof Giaro, Marcin Kamiński

Celem tej pracy jest prezentacja kwantowego modelu obliczen. Szczegolny nacisk polozono na zagadnienia matematyczne i informatyczne. Zadbano o wyjaśnienie podstaw teoretycznych, podanie pelnych dowodow poprawności algorytmow kwantowych oraz szacowanie zlozoności obliczeniowej.

Zuzanna Pietrzak