Przeskocz do treści

Delta mi!

Loading

Co to jest?

Jak to działa?

Komputery kwantowe

Jakub Zieliński

o artykule ...

  • Publikacja w Delcie: sierpień 2005
  • Publikacja elektroniczna: 17-04-2011
  • Autor: Jakub Zieliński
    Afiliacja: Instytut Fizyki Teoretycznej, Uniwersytet Warszawski

Wszyscy wiemy, że wiele problemów nie daje się rozwiązać za pomocą komputera tylko z powodu ich zbyt dużej „złożoności obliczeniowej”. Pod tym poważnym stwierdzeniem kryje się prosta i smutna prawda. Nawet najszybsze komputery są zbyt wolne, aby uporać się z niejednym zadaniem. Wiemy też, że nie da się w nieskończoność zwiększać szybkości komputerów. Rozmiary atomów wyznaczają możliwą do wyobrażenia skalę miniaturyzacji. Jako że żaden sygnał nie może rozchodzić się szybciej niż światło w próżni, czas potrzebny na przesłanie informacji między fragmentami procesora też jest ograniczony od dołu. Czy komputer kwantowy może stać się remedium na powyższy problem?

Pierwszy raz z nazwą „komputer kwantowy” zetknąłem się 9 lat temu, na pierwszym roku studiów. Wydała mi się nieco podejrzana. Przecież zasada nieoznaczoności Heisenberga wyklucza dokładne pomiary obiektów kwantowych, powinna więc uniemożliwiać działanie takiego urządzenia. Tak naprawdę to wymienione ograniczenia są, obok gwałtownie rosnącego zużycia energii, główną przeszkodą przy tworzeniu coraz mniejszych i szybszych komputerów „klasycznych”. Celowo użyłem cudzysłowu, bowiem w obecnie produkowanych procesorach prawa mechaniki kwantowej odgrywają już znaczącą rolę – tak naprawdę trudno opisać klasycznie działanie pojedynczego tranzystora math Na czym więc ma polegać owa kwantowość? Na zupełnie odmiennym sposobie przetwarzania informacji. We współczesnych komputerach informacja jest zapamiętywana jako ciąg bitów, czyli zer i jedynek. Obliczenia zatem sprowadzają się do odpowiedniego zamieniania jednych bitów na inne.

W komputerze kwantowym bity są zastąpione przez qubity (quantum bits). Każdy qubit math może być w tak zwanej superpozycji pomiędzy zerem i jedynką. Zapisujemy to w ten sposób:

display-math

Jeśli dokonamy pomiaru wartości qubitu, to możemy otrzymać math lub math z prawdopodobieństwami równymi odpowiednio: math oraz math Przykładem tu może być elektron ze spinem skierowanym w górę lub w dół.

Takie uogólnienie bitu można jednak osiągnąć klasycznie. Wystarczy zbudować klasyczny komputer analogowy. Każdy bit będzie przybierał wartości z przedziału math i gotowe.

Nie chodzi jednak o operowanie wartościami między 0 i 1, lecz o wykorzystanie praw mechaniki kwantowej, pozwalających na superpozycję stanów jednego lub więcej qubitów.

Zobaczmy, jak to wygląda na przykładzie dwóch qubitów. Najprostsza baza układu dwóch qubitów to oczywiście: math  math  math oraz math Przykładowy stan to pewna kombinacja liniowa wektorów bazy; np.

display-math

Pierwszy qubit może być zerem lub jedynką. Obie możliwości są jednakowo prawdopodobne. Drugi tak samo. Wiemy jednak, że zawsze będą miały przeciwne wartości. Zaczyna robić się ciekawie, ale po chwili zastanowienia możemy zaproponować klasyczny odpowiednik tej sytuacji. Weźmy dwie kule: białą i czarną. Włóżmy je, nie patrząc, do dwóch kieszeni. Nie wiemy jednak, gdzie znajduje się któraś z nich, ale wiemy, że kule w kieszeniach są różne.

Aby pokazać różnicę między mechaniką kwantową a klasyczną statystyką, zamienię oznaczenia. Zamiast math będę pisał math natomiast math zastąpię przez math Wprowadzę również dwa nowe stany, będące superpozycjami powyższych: math oraz math Są to stany spinu skierowanego odpowiednio w lewo i prawo. Prosty rachunek (zachęcam!) pokazuje:

display-math

Wynik jest dość dziwny. Wygląda bowiem na to, że elektrony „nie wiedzą”, czy zostały „złożone” z elektronów o spinach góra-dół, czy też lewo-prawo. Co gorsza, my też tego nie wiemy! To tak, jakbyśmy po sprawdzeniu, że kulka z lewej kieszeni jest czerwona, wiedzieli, że ta z prawej jest zielona. Co więcej, moglibyśmy wybrać dowolną parę kolorów dopełniających. Jest tylko jedno ograniczenie: takiego „magicznego” pomiaru możemy dokonać tylko raz. Po pierwszym pomiarze owo połączenie czy też „splątanie” – jak mawiają fizycy – pomiędzy elektronami znika. Każdy z nich ma już określony stan.

Owa przedziwna własność stanów splątanych jest kluczowa – jest tym, co naprawdę odróżnia komputer kwantowy od klasycznego. Aby ją lepiej zrozumieć, musimy najpierw dowiedzieć się, na czym polega pomiar w mechanice kwantowej.

Nie możemy „zapytać”, jak skierowany jest spin elektronu. Możemy spytać się jedynie, czy jest skierowany w górę czy w dół. Możemy także wybrać inny pomiar: w lewo czy w prawo albo w przód czy w tył. Ale nie możemy zadać tych pytań naraz. Tego typu zakazy wynikają z zasady nieoznaczoności. Ograniczenie powyższe nie wynika z niedoskonałości przyrządów pomiarowych. Popatrzmy na definicję spinów skierowanych w bok. Widać, że elektron o spinie skierowanym w prawo niejako składa się z elektronów o spinach skierowanych w górę i w dół. Zatem jeśli mamy przyrząd, który rozróżnia elektrony math od math to elektron math „musi się zdecydować” na jedną z tych możliwości. Nie mamy i mieć nie możemy na to wpływu. Każde urządzenie, które wykrywa wszystkie elektrony math musi wykryć co najmniej połowę elektronów math To, czy wykryje połowę czy więcej, zależy tylko od tego, jak reaguje na elektrony math

Budując algorytmy kwantowe, mamy do dyspozycji dodatkowe stany. Wydawać by się mogło, że z łatwością powinno dać się skonstruować mnóstwo algorytmów znacznie efektywniejszych niż klasyczne. Problemem jest jednak brak możliwości rozróżniania dowolnych stanów. Co z tego, że otrzymamy wspaniały rezultat, jeśli nie będziemy go w stanie odczytać. Dlatego obecnie znamy tak naprawdę tylko dwa algorytmy kwantowe.

Pierwszym jest algorytm Shora. Nie będę tutaj tłumaczył całego algorytmu, gdyż jego opis jest długi i raczej żmudny. Pozwala on rozłożyć liczbę na czynniki pierwsze. Jak wiadomo, jest to kluczowy element łamania tak zwanych szyfrów z kluczem publicznym RSA (używanych powszechnie do szyfrowania informacji w Internecie, np. przez banki). Nie ma wątpliwości, że to jedna z ważniejszych przyczyn zainteresowania informatyką kwantową.

W algorytmie zaproponowanym przez Shora najpierw sprowadza się problem rozłożenia liczby math  na czynniki pierwsze do problemu znalezienia okresu pewnej funkcji. Jest ona zadana dla math  wartości. Procedura ta jest w pełni klasyczna – pomijam ją tutaj. Po szczegóły odsyłam do oryginalnej pracy [1]. Standardową metodą znajdywania okresu funkcji jest obliczenie jej transformaty Fouriera. W wyniku tej operacji znajdujemy tak zwane widmo. Gdyby funkcja opisywała falę dźwiękową, to dzięki transformacji Fouriera dostalibyśmy informację, jakie tony zawiera dźwięk. Podobnie, dla światła, byłby to rozkład na fale płaskie o określonych częstościach (czyli barwach). Transformacja Fouriera pozwala po prostu wyrazić funkcję przez szereg sinusów i kosinusów o różnych okresach. W wyniku transformacji funkcji, określonej dla math  punktów, dostajemy funkcję (również math -punktową), której każdy punkt dostarcza informacji, „ile jest danej częstości”.

I tak oto dostajemy wynik – rozkład liczby na czynniki pierwsze. Zaniepokoić powinny nas dwie rzeczy. Po pierwsze, transformatę Fouriera umiemy obliczać klasycznie – gdzie więc jest mechanika kwantowa? Po drugie, czas potrzebny na jej obliczenie jest proporcjonalny do math  Widać więc, że jest to fatalny algorytm. Najprostszy pomysł na rozłożenie math  to sprawdzać wszystkie liczby od math do math Rzecz w tym, że transformatę Fouriera można obliczyć bardzo szybko kwantowo. Realizuje to odpowiedni układ „bramek kwantowych”, czyli po prostu można wykonać stosowne obliczenia za pomocą manipulacji na spinach elektronów. Jak każde rachunki, można je przeprowadzić na różne sposoby. Jednak niezależnie od tego, jak byśmy się starali, zawsze musimy uwzględnić operacje „splątujące”, a więc takie, które z dwóch nieskorelowanych elektronów zrobią splątaną parę. Stanowi to ogromną trudność eksperymentalną.

A jak duży musi być komputer kwantowy, aby poradzić sobie z rozkładem liczby math ? Przede wszystkim liczba ta musi zmieścić się w jego „pamięci”. Oznacza to, że math  gdzie math jest właśnie liczbą qubitów. To bardzo ważne, bowiem w wielu przypadkach obowiązuje „zasada zachowania trudności”: zwiększenie szybkości algorytmu osiągane jest za cenę większej „pamięciożerności”.

Rzeczywiście, transformację Fouriera możemy wykonać bardzo łatwo, kodując funkcję za pomocą fali elektromagnetycznej, a widmo uzyskać natychmiast, przepuszczając światło przez pryzmat lub siatkę dyfrakcyjną. Problemem jest tu jednak ogromna liczba częstości, jakie musielibyśmy rozróżniać. Liczby pierwsze stosowane w kryptografii mają często po kilkaset cyfr. Nie ma najmniejszych szans na rozróżnianie częstości światła z tak ogromną precyzją. W algorytmach klasycznych czas potrzebny na rozłożenie liczby rośnie wykładniczo z liczbą jej cyfr (jej logarytmem). Przy zastosowaniu algorytmu Shora i optyki klasycznej wykładniczo rośnie liczba potrzebnych częstości światła. W algorytmie kwantowym, dzięki splątaniu, czas obliczeń i ilość qubitów rosną potęgowo wraz z logarytmem rozkładanej liczby.

Widać więc, że algorytm Shora to w zasadzie szukanie okresu funkcji. Nie jest to raczej problem fascynujący sam w sobie. Zawdzięcza on swoją popularność temu, że Shor potrafił powiązać ten pozornie czysto akademicki problem z kryptografią. To uczy, że bardzo ryzykowne jest „spisywanie na straty” jakiegoś działu nauki, mówiąc, że „to się do niczego nie przyda”.

Na koniec jedna uwaga. Dlaczego upieram się, że komputer kwantowy ma szukać okresu funkcji, a nie po prostu obliczyć transformatę Fouriera? Ten ostatni problem jest ważny w niezliczonych zastosowaniach. Od diagnostyki medycznej, poprzez analizę zdjęć satelitarnych, na symulacjach układów chemicznych kończąc. Otóż komputer kwantowy potrafi obliczyć transformatę Fouriera zawsze, ale wynik możemy odczytać tylko jeśli funkcja jest okresowa. Powód jest prosty: tylko dla funkcji okresowej widmo zawiera niewiele częstości. Jeśli będziemy próbować obliczać transformatę Fouriera z funkcji nieokresowej, to otrzymamy widmo złożone z niezliczonej ilości długości fal. A podczas pomiaru możemy dostać tylko jedną wartość częstości... Drugim zaproponowanym algorytmem kwantowym [2] jest sposób przeszukania zbioru N-elementowego w poszukiwaniu jednego „dobrego” elementu. W wielu przypadkach jest tak, że łatwo sprawdzić, czy zaproponowane rozwiązanie jest dobre. Trudno je jednak znaleźć. Często pozostaje nam jedynie sprawdzanie po kolei wszystkich możliwych przypadków. Kłopot zaczyna się, gdy jest ich dużo.

Klasyczny średni czas szukania jednego „dobrego” elementu spośród math  jest proporcjonalny do math Czas potrzebny dla komputera kwantowego to tylko math Wszystkie math  sprawdzanych odpowiedzi możemy ponumerować. Od tej pory będziemy sprawdzać, która z math  liczb jest „dobra”. math  liczb zakodujemy za pomocą math qubitów. Pokażę to na prostym przykładzie math  ( math ):

display-math

Kodowanie jest więc takie, jak w komputerze klasycznym. Następnie tworzymy stan będący superpozycją wszystkich możliwych odpowiedzi:

display-math

Zwracam uwagę, że jest to stan bardzo silnie splątany. Sprawdzanie, czy dana liczba jest dobra, można zdefiniować jako obliczenie funkcji. Jeśli liczba jest dobra, to funkcja ma wartość math a jeśli zła, to math Oczywiście, możemy przypisać inne wartości obu odpowiedziom – byleby tylko były różne.

Widać więc, że wszystkie math  złych stanów będzie zawsze traktowane tak samo, a inaczej jeden stan dobry. Możemy więc ogólnie zapisać

display-math

Jak widać, jeśli zmierzymy, w którym stanie jest układ math  qubitów, to z prawdopodobieństwem math dostaniemy „złą” odpowiedź, a „dobrą” jedynie z prawdopodobieństwem math Jest to dość oczywiste – nic jeszcze nie zrobiliśmy i szansa wylosowania stanu o szukanym numerze jest znikoma.

Zwróćmy uwagę, że otrzymany stan jest nieco podobny do pojedynczego spinu. Jeśli przyjmiemy

display-math

to otrzymamy:

display-math

a więc spin skierowany prawie idealnie do dołu. Spin możemy obrócić o 180 stopni i dostaniemy elektron o spinie skierowanym niemal idealnie do góry. Obrotu pojedynczego spinu można dokonać, np. włączając jednorodne pole magnetyczne lub pole magnetyczne połączone z falą elektromagnetyczną. Jest to technika powszechnie stosowana w obrazowaniu i spektroskopii, opartych na zjawisku rezonansu magnetycznego (zazwyczaj spiny pochodzą tam od jąder, a nie od elektronów – jest to dla nas bez znaczenia. Elektron jest tylko przykładem cząstki ze spinem. Do budowy komputera można użyć innych cząstek).

Oczywiście, w przypadku układu math  spinów nie jest tak prosto. Co więcej, problemem jest to, że nie znamy dokładnie stanu math Po prostu nie wiemy, co oznacza math gdyż to jest nasza niewiadoma. Ale znamy nasz stan z bardzo dobrym przybliżeniem, dlatego też możemy z niezłym przybliżeniem go „obrócić”. Zajmuje to math kroków. Niestety, nie możemy obrócić układu w jednym kroku. Musimy „drobić”, bo gdybyśmy „robili zbyt duże kroki”, moglibyśmy pójść nieco za daleko. To cena, jaką płacimy za niedokładną znajomość stanu początkowego.

Niestety, pomimo ogromnego wysiłku, nie udało się dotąd zbudować działającego komputera kwantowego i nie wiadomo, czy będzie to kiedykolwiek możliwe. Jak już wspomniałem, nie musimy koniecznie używać elektronów. Próbowano rozmaitych schematów, w tym jądrowego rezonansu magnetycznego.

W tej chwili najbardziej obiecujące wydają się próby z jonami umieszczonymi w pułapce [3, 4]. Można już w sposób kontrolowany umieścić jeden za drugim kilka jonów w próżni. Ich pozycja jest kontrolowana za pomocą odpowiednio uformowanego pola elektromagnetycznego. Co więcej, możliwe jest dokonywanie manipulacji na wybranym jonie oraz ich splątywanie! Niestety, problemem jest tak zwana dekoherencja: po czasach rzędu milisekund w niezwykle przecież delikatny układ wkrada się jakieś zaburzenie. Powoduje to utratę informacji. Nie wiadomo, czy kiedykolwiek uporamy się praktycznie z tym problemem. Wraz ze wzrostem komputera, problem będzie się nasilał. Już jednak zbudowanie układu kilku qubitów i precyzyjna nimi manipulacja pokazuje, jak niesamowity rozwój technik eksperymentalnych nastąpił w ostatnich latach.

Z pewnością komputer kwantowy nie będzie kolejną zabawką stojącą na biurku, lecz urządzeniem służącym do wykonywania najbardziej zaawansowanych obliczeń, umieszczonym w najlepszych światowych laboratoriach. Trzeba jednak pamiętać, że taką samą przyszłość wieszczono klasycznym komputerom...


Bibliografia
[1]
Peter Shor, Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press (1994), 124-134.
[2]
Lov K. Grover, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, (1996), 212-219.
[3]
D. Kielpinski, C.R. Monroe and D.J. Wineland, Nature 417, 709-711 (2002).
[4]
D. Leibfried et al., Nature 422, 412-415 (2003).
Notice: Undefined index: story_alias_uuid in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 23 Notice: Undefined index: story_alias_uri in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 24