Abstract

Już dziś wiadomo, że z chwilą udanej realizacji komputera kwantowego maszyna ta będzie pozwalała na znajdowanie rozwiązań problemów obliczeniowych leżących poza zasięgiem komputerów klasycznych. Opracowano szereg algorytmów kwantowych, z których największą sławą cieszy się procedura Shora, pozwalająca efektywnie dokonywać tzw. faktoryzacji, tj. rozkładu bardzo dużych liczb naturalnych na czynniki pierwsze. Na trudności obliczeniowej faktoryzacji opiera się bezpieczeństwo najpowszechniej dziś stosowanego szyfru z kluczem publicznym RSA, zatem udana realizacja komputera kwantowego uczyniłaby stosowane dziś systemy szyfrujące przezroczystymi. Z kolei procedura Grovera w nieuporządkowanej bazie danych rozmiaru n znajduje rekord spełniający wybrane kryterium w czasie rzędu n^0.5, co oczywiście jest niewykonalne w modelu klasycznym. Model obliczenia kwantowego na trwałe zadomowił się na gruncie informatyki teoretycznej. Wyniki z zakresu kwantowych algorytmów rozstrzygających zagadnienia kombinatoryczne, kwantowych klas złożoności obliczeniowej lub kwantowego kosztu komunikacyjnego obliczeń są dziś regularnie publikowane w renomowanych periodykach i prezentowane na międzynarodowych sympozjach poświęconych analizie algorytmów. Mimo niewątpliwie intensywnego rozwoju tego nowego obszaru wiedzy jego rezultaty wciąż pozostają dość hermetyczne i nieczytelne dla szerszego ogółu odbiorców. Jest to wynikiem silnie interdyscyplinarnego charakteru dziedziny, wymagającej od czytelnika znajomości szeregu pozornie niezwiązanych ze sobą faktów z zakresu informatyki (m.in. teorii algorytmów, modeli formalnych obliczeń), matematyki (w tym algebry abstrakcyjnej i teorii liczb) oraz podstaw fizyki kwantowej. Niniejsze opracowanie stawia sobie za cel odczarowanie tej dziedziny, precyzyjnie selekcjonując materiał potrzebny do zrozumienia pojęć obliczenia kwantowego, analizy kwantowych algorytmów oraz wprowadzając aparat formalny pozwalający na dalsze samodzielne studiowanie literatury. Dołożono też wszelkich starań, aby uczynić tę książkę spójną, zamkniętą konstrukcją tematyczną, niewymagającą od czytelnika stykającego się po raz pierwszy z informatyką kwantową poszukiwania pełniejszych wyjaśnień niezbędnych pojęć i wątków pobocznych, ani też przyjmowania na wiarę wykorzystywanych faktów.

Author (1)