Twoja wyszukiwarka

JERZY KOWALSKI-GLIKMAN
KOMPUTERY - SZYBKIE I NIEZAWODNE
Wiedza i Życie nr 7/1998
Artykuł pochodzi z "Wiedzy i Życia" nr 7/1998

Już niedługo może pojawić się nowa generacja komputerów, zwanych komputerami kwantowymi, znacznie szybszych i efektywniejszych od dziś stosowanych. Te nowe maszyny wykorzystywać będą egzotyczne własności mikroskopowych układów materialnych podlegających prawom mechaniki kwantowej i w pewnym sensie można je będzie sobie wyobrażać jako komputery z nieskończoną liczbą równolegle pracujących procesorów.

Idea komputera kwantowego zaproponowana została na początku lat osiemdziesiątych przez jednego z najwybitniejszych fizyków XX wieku, nieżyjącego już Richarda Feynmana. W jego przekonaniu mogłyby one służyć do efektywnego modelowania własności złożonych układów cząstek, rozważanych na przykład w fizyce statystycznej i biofizyce. Kilka lat później David Deutsch zdał sobie sprawę, że dzięki komputerom kwantowym można będzie rozwiązywać problemy nierozwiązywalne na zwykłych maszynach.

Aby zilustrować potęgę komputerów kwantowych, wyobraźmy sobie następujący problem. Mamy dwie kule, czarną i białą, oraz dwa pudełka, z których każde podzielone jest na dwie przegródki. Dostajemy kartkę z instrukcją, jak umieścić kule w pudełkach (np. czarną w pudełku pierwszym, a białą w drugim, lub też obie w drugim pudełku). Ile operacji trzeba wykonać, aby inna osoba mogła się zorientować, czy obie kule są w tym samym pudełku, czy też każda z nich włożona została do innego? Zdrowy rozsądek podpowiada, że trzeba dokonać dwóch operacji polegających na wyjęciu jednej kuli z jakiejkolwiek przegródki któregokolwiek pudełka bez zaglądania do środka: na przykład bierzemy pudełko i sprawdzamy, czy w pierwszej przegródce jest kula, a następnie sprawdzamy drugą przegródkę tego samego pudełka.

Zalecenie jest precyzyjne i zawsze prowadzi do rozwiązania problemu - procedury takie nazywać będziemy dalej algorytmami. Okazuje się, że, mając do dyspozycji komputer kwantowy, można znaleźć algorytm, który rozwiązuje ten problem (w jego abstrakcyjnej formie) w jednym kroku! Istotą komputera kwantowego jest bowiem to, że stany czarnej i białej kuli nie są niezależne: znając na przykład stan czarnej kuli, możemy określić, w jakim stanie znajduje się kula biała.

Bardziej imponująca jest efektywność komputerów kwantowych przy rozwiązywaniu naprawdę trudnych problemów, mających ważne zastosowania praktyczne (np. w kryptografii). Już starożytni Grecy wiedzieli, że każdą liczbę przedstawić można jednoznacznie jako iloczyn liczb pierwszych (np. 174 353 458 989 = 3 x 29 x 601 x x 953 x 3499). Okazuje się, że największym współcześnie istniejącym komputerom rozkład 130-cyfrowej liczby, która ma 65-cyfrowy czynnik pierwszy, zajmuje wiele miesięcy, a rozwiązanie podobnego problemu dla liczby 400-cyfrowej trwałoby dłużej niż wiek Wszechświata. W 1994 roku Peter Shor napisał algorytm dla komputera kwantowego (gdyby istniał), umożliwiający rozwiązanie tego problemu w zaledwie kilka lat.

Innym zagadnieniem jest przeszukiwanie dużych baz danych. Jeśli baza liczy N elementów, to dzisiejszy komputer potrzebuje na wyszukanie konkretnego elementu czasu proporcjonalnego do N, zaś komputer kwantowy czasu proporcjonalnego do ˆN. W przypadku bazy składającej się z 10 mld fiszek komputer kwantowy jest sto tysięcy razy szybszy! Jest również zupełnie oczywiste, że przewidziane przez Feynmana zastosowanie komputerów kwantowych do modelowania zachowań układów wielu cząstek doprowadzi do niewyobrażalnego postępu w fizyce, chemii i biologii.

Pomimo tych niezwykłych perspektyw do zeszłego roku teorią komputerów kwantowych zajmowała się jedynie wąska grupka zapaleńców. Powód był prosty: wydawało się, że komputery kwantowe są omylne. Problem polega na tym, iż elementarne stany kwantowe, które wykorzystane być muszą do konstrukcji tych urządzeń, są niezwykle niestabilne; innymi słowy - podatne na błędy. Oczywiście, błędy pojawiają się również w przypadku zwykłych komputerów, ale istnieją proste algorytmy korygujące. W przypadku komputerów kwantowych wydawało się, że algorytmy takie po prostu nie istnieją. Rewolucja nastąpiła pod koniec 1996 roku, kiedy naukowcy z Los Alamos National Laboratory podali prosty i efektywny algorytm korekcji błędów popełnionych przez komputer kwantowy.

Kiedy więc "przesiądziemy" się z poczciwych pecetów na błyskawiczne komputery kwantowe? Zapewne nieprędko. Dotychczas udało się skonstruować jedynie pojedyncze "kwantowe bramki logiczne", będące podstawowymi elementami budowy procesora komputera (procesor Pentium zawiera ich miliony). Zdaniem optymistów, pierwszego działającego komputera nowego typu doczekamy się w ciągu kilkunastu lat. Na jego powszechne zastosowanie trzeba będzie jednak poczekać zapewne jeszcze kilkadziesiąt lat, choć warto przypomnieć, że 20 lat temu nawet najwięksi optymiści (może z wyjątkiem Billa Gatesa i paru jego kolegów) nie wyobrażali sobie, iż już w latach dziewięćdziesiątych komputer osobisty będzie niemalże takim samym standardowym wyposażeniem domowym jak pralka czy telewizor.

PS Obszerny artykuł poświęcony komputerom kwantowym ukaże się w sierpniowym "Świecie Nauki".