Komputer odwracalny

Z miniaturyzacją informatyki do obszaru atomowego łączy się również pytanie o teoretyczne granice takiego procesu. Uważa się, że przesuwanie tych granic wymaga stosowania nie tylko nowych technologii w sensie fizycznym, ale również poszukiwania nowych paradygmatów dla samej logiki budowy komputerów. Do dzisiaj opiera się ona na modelach zaproponowanych w latach 30. i 40. (Allan Turing). Tymczasem związki między koncepcją budowy komputerów a ich ograniczeniami są wyraźne. Miniaturyzacja to problem odprowadzania ciepła wydzielanego podczas obliczeń, a więc strat energii i informacji.

Komputer, który ma być szybki, a jednocześnie nie powodować strat energetycznych, powinien działać w sposób odwracalny (reversible). Co to znaczy? Dla przykładu rozważmy działanie prostej bramki logicznej AND, dwa wejścia, jedno wyjście. Jeśli na wyjściu widzimy zero, to możemy tylko zgadywać, co było na wejściu: 1/0, 0/1 czy 0/0. Wprowadzamy dwa bity informacji, otrzymujemy tylko jeden. A to jest właśnie proces nieodwracalny związany ze stratą informacji. No tak, ale po pierwsze - co ma wspólnego strata informacji ze stratami energii; po drugie - jeśli chcemy wnioskować o wejściu na podstawie wyjścia, to możemy zapamiętywać odpowiednie stany tymczasowe komputera.

Odpowiedzmy na te pytania zaczynając od końca. Zapamiętywanie "między-informacji" ograniczyłoby znacznie szybkość działania komputera. Druga kwestia wynika z modeli opisujących entropię systemu, a prace Bennetta i Toffoliego wskazują nawet na teoretyczne możliwości budowy komputerów pracujących bez zużycia energii. Jak to, zapyta każdy praktyk. Przecież jakiś "prąd" z zewnątrz zawsze będzie potrzebny, a perpetuum mobile nie istnieje. To prawda, wszakże istnieje subtelna różnica między informatyką, która "produkuje" bity (patrz bramka AND), a tą, którą można sprowadzić do ich "przestawiania". Przykładem takiej koncepcji jest tzw. przełącznik Fredkina.

Z odwracalnych bramek można by budować całe komputery, pracujące w sposób odwracalny. To są twierdzenia formułowane jeszcze w latach 70. i 80. Niezależnie jednak od koncepcji logicznej użytej do budowy komputera kwantowego pozostaje pytanie o oprogramowanie dla takiej maszyny. Sam fakt kwantowej rów noległości to jeszcze za mało, aby górować nad sekwencyjnie liczącym procesorem. Potrzebne są również nowe algorytmy, które potrafią efektywnie wykorzystać specyfikę qbitów. I właśnie taki algorytm przed trzema laty ujrzał światło dzienne.

Złamany klucz

Twórcą algorytmu był pracownik AT&T (USA) Peter Shor, a zaproponowane przezeń rozwiązanie pozwala na bardzo szybką faktoryzację liczb, czyli ich rozkład na czynniki. Spróbujmy np. pomnożyć 6700417 przez 641. Proste, prawda? Ale jeśli zaczniemy od wyniku 4294967297 i będziemy próbować znaleźć podane czynniki, to problem się komplikuje. Podana wartość jest akurat jednym z wyjątków (dla n=5) wzoru na liczby pierwsze Fermata, ale to zupełnie inna historia. Faktem jest, że w teorii liczb nadal istnieją znaki zapytania co do liczb pierwszych, natomiast ich własności, w połączeniu z faktoryzacją, wykorzystywane są w technikach kryptograficznych.

Shor podał algorytm, który potrafi faktoryzować liczby w sposób "kwantowy", to znaczy z wykorzystaniem jednoczesności stanów qbitowych rejestrów. Jak wiadomo, jeszcze przed opublikowaniem tej metody świat obiegła wiadomość o złamaniu 129-cyfrowego klucza RSA przez 1600 internetowych komputerów pracujących w ciągu 8. miesięcy. Właściwie potwierdziło to tylko bezpieczeństwo, jakie gwarantują współczesne metody kryptograficzne. W końcu przypadek sprzęgania tysięcy komputerów liczących miesiącami należy uznać za skrajny. Wystarczy zresztą wydłużyć klucz np. do 140 pozycji, aby odpowiednie czasy obliczeń wzrosły o całe rzędy wielkości.

Ale nawet wtedy algorytm Shora poradziłby sobie z tym problemem w ciągu kilku sekund! Oszacowania wskazują, że faktoryzacja liczby 1000-cyfrowej, przy użyciu komputera kwantowego, trwałaby niewiele więcej niż kwadrans. Stosowane w praktyce klucze RSA mają nawet ponad 300 pozycji. Konwencjonalna maszyna potrzebowałaby dosłownie wieczności, by je złamać. Dla przykładu rozważmy prosty algorytm łamiący takie klucze mnożeniami kolejnych liczb. Dla liczby N wystarczy zatem przetestować liczby nie większe niż ÖN.

Weźmy komputer wykonujący aż miliard operacji testowych na sekundę. Następnie połączmy miliard takich komputerów i każmy im liczyć. To daje 1018 prób na sekundę. Rok to ok. 30 milionów sekund. Możemy sobie jeszcze do naszej liczby dopisać kilka zer. I cóż z tego. Widać wyraźnie, że przy odpowiednio długim kluczu moglibyśmy nasze obliczenia wystartować razem z Wielkim Wybuchem, a nadal bylibyśmy "w szczerym polu". Są też efektywniejsze algorytmy, ale i wtedy trzeba by zaczynać gdzieś od epoki dinozaurów, zresztą klucz można wydłużyć o kilka miejsc, a czas na jego łamanie wzrośnie o kolejne rzędy wielkości. Trzeba jednak pamiętać, że wciąż mówimy tu tylko o teoretycznych prawdopodobieństwach złamania klucza.

Żywe komputery

Innym algorytmem, który pokazuje wyższość komputera kwantowego nad konwencjonalnym, jest algorytm Grovera, pozwalający na szybkie przeszukiwanie nie posortowanych baz danych. Już tylko te przykłady pokazują, że informatyka kwantowa może być ważnym uzupełnieniem metod dotychczasowych, co nie musi oznaczać, że rozwiązania tradycyjne są w każdym przypadku skazane na zagładę.

Wynalazek samochodu nie spowodował likwidacji kolejnictwa, a z tego, że samolot jest szybszy niż statek, nie wynika, iż transport powietrzny zdominuje jego wszelkie inne formy.

W kolejnych fazach rozwoju informatyki także będziemy obserwować raczej uzupełnianie się różnych technologii, często zresztą o hybrydowym charakterze. Fizyka mikroświata rozwija się. Niektóre z ostatnich doniesień nie wykluczają nawet występowania w przyrodzie prędkości większych niż światło. W tym kontekście komputer kwantowy jest bardzo obiecującą wizją dla informatyki przyszłości, choć nie jedyną. Inną możliwością są kierunki chemiczne czy bioinformatyczne: komputery oparte na łańcuchach DNA czy wykorzystujące bakterie.

W tym ostatnim przypadku mowa o bakteriach halobacterium halobium, zmieniających swą strukturę pod wpływem światła. Ich zachowanie przypomina działanie dwustanowych przełączników, co przecież jest podstawą działania systemów komputerowych. Stąd jeszcze długa droga do sprawnie działającej pamięci biologicznej, ale niewykluczone, że z czasem uda się wymusić na bakteryjnych mikroorganizmach kontrolowane mechanizmy samoreprodukcji. Kto wie, może supernowoczesne generacje mikrochipów przyszłości będą powstawać nie w sterylnych fabrykach, a po prostu na zwykłej pryzmie kompostowej?