66-68_komputery_kwantowe.pdf

Warsztaty

Komputery kwantowe

przyszłość informatyki?

Każdy z nas z pewnością słyszał o komputerach kwantowych, próbach

ich zbudowania oraz niemalże nieograniczonych możliwościach, jakie

miałoby dać ich wykorzystanie. W tym artykule zapoznasz się z podstawami

technologii przetwarzania informacji przy użyciu komputerów kwantowych.

Zapraszam do lektury!

Dowiesz się:

• Czym są komputery kwantowe;

• W jaki sposób przebiegał rozwój tej dziedziny;

• Czym różni się budowa komputera kwanto-

wego od komputera klasycznego;

• Czym są i jak działają algorytmy kwantowe

oraz poznasz najważniejsze z nich;

• Dlaczego zbudowanie komputera kwanto-

wego jest tak trudne.

agencje wojskowe oraz uniwersytety. Pomimo

dość znacznych postępów, jakich udało się do-

konać na przestrzeni ostatnich kilkunastu lat,

wciąż jesteśmy daleko od zbudowania kompu-

tera kwantowego, który mógłby zostać efek-

tywnie zastosowany do rozwiązywania kon-

kretnych problemów.

Pewnie zadajesz sobie teraz pytanie: dlacze-

go zbudowanie komputera kwantowego jest ta-

kie trudne? Otóż okazuje się, że problemy nie

wynikają w głównej mierze z niedoskonałości

technologii. Te same zjawiska, które powodu-

ją, że wizja kwantowego przetwarzania infor-

macji wydaje się tak atrakcyjna, są również

odpowiedzialne za problemy przy budowie

urządzeń je realizujących. Aby zrozumieć tę

poniekąd paradoksalną sytuację, musimy po-

znać podstawy fizyki kwantowej. Nie martw

się jednak – pomimo iż zachęcam Cię, abyś

zapoznał się z aparatem matematycznym wy-

korzystywanym w tej dziedzinie, zrozumie-

nie tego artykułu nie będzie wymagało jego

znajomości.

Naszą podróż do świata komputerów

kwantowych rozpoczniemy od zapoznania

się z podstawami fizyki kwantowej. Omó-

wimy najważniejsze zjawiska, których od-

krycie na zawsze zmieniło myślenie o bu-

dowie materii, a które znajdują ogrom-

ne zastosowanie w dziedzinie kwantowe-

go przetwarzania informacji. Następnie

przyjrzymy się klasycznej architekturze

komputerów oraz algorytmom determini-

stycznym – poznamy również sposób ich

realizacji we współczesnych urządzeniach.

Po zapoznaniu się z tymi informacjami bę-

dziemy już mogli skupić się na właściwym

temacie artykułu – komputerach kwanto-

wych.

Poziom

trudności

w problemie komiwojażera, lecz o problemy,

których rozwiązanie wymaga ogromnej mocy

obliczeniowej. Rozwiązanie dużej liczby po-

zornie banalnych zadań na standardowych

komputerach jest praktycznie niemożliwe.

Część genialnych naukowców, zajmują-

cych się budową pierwszych komputerów,

pracowało również nad powstałą w XX wie-

ku nową dziedziną fizyki – fizyką kwanto-

wą. Jednym z nich był John von Neumann,

znany głównie jako twórca architektury von

Neumanna – komputera mogącego wykony-

wać wiele różnych programów, bez potrzeby

zmiany jego budowy. W architekturze von

Neumanna, dane i instrukcje, przechowywa-

ne w jednym typie pamięci, przetwarzane są

przez jednostkę arytmetyczno-logiczną, zaś

wyniki operacji i polecenia operatora prze-

kazywane są przy użyciu urządzeń wejścia/

wyjścia. Pomimo faktu, że John von Neu-

mann sformalizował cały aparat matema-

tyczny wykorzystywany w fizyce kwantowej

oraz był zaangażowany w rozwój wczesnych

technologii komputerowych, nie wpadł na

pomysł połączenia ze sobą tych dwóch dzie-

dzin. Dokonali tego inni naukowcy niemal

30 lat później.

Wróćmy jednak do czasów współczesnych.

Obecnie nad rozwojem teorii informaty-

ki kwantowej oraz praktycznej realizacji za-

dań obliczeniowych na komputerach kwanto-

wych zajmują się duże grupy naukowców. Roz-

wojem tej dziedziny zainteresowane są nie tyl-

ko wielkie firmy, takie jak IBM, lecz również

skich pionierów informatyki,

Howard Aiken, przewidywał,

że sześć standardowych komputerów cyfro-

wych powinno zaspokoić potrzeby oblicze-

niowe całych Stanów Zjednoczonych. Oczy-

wiście, z naszego punktu widzenia prognoza

ta jest rażąco nierealistyczna, musimy jednak

brać pod uwagę zastosowanie komputerów w

tamtych czasach – były one bowiem budo-

wane głównie na użytek wojskowy oraz aka-

demicki. Howard Aiken, podobnie jak inni

twórcy komputerów z tego okresu, nie mógł

przewidzieć, że ich pomysły, chociaż w nie-

znacznie zmodyfikowanej formie, zrewolu-

cjonizują oblicze świata.

Wraz z postępem technologii budowy

komputerów, następował rozwój informa-

tyki teoretycznej, a w szczególności algoryt-

miki. Bardzo szybko okazało się, że sama me-

todologia przetwarzania danych wykorzy-

stywana w klasycznych komputerach cyfro-

wych, budowanych w oparciu o podzespo-

ły elektroniczne, powoduje duże trudności

w rozwiązywaniu pewnych klas problemów.

Chodzi tu nie tylko o zagadnienia, w których

nie udaje się skonstruować algorytmu, jak np.

Fizyka kwantowa

Fizyka kwantowa to dwa słowa, na których

dźwięk cierpnie skóra każdego, komu fizy-

11/2009

W 1947 roku, jeden z amerykań-

Komputery kwantowe – przyszłość informatyki?

ka kojarzy się jedynie ze spadającymi jabłka-

mi oraz rzędami niezrozumiałych równań,

służących do opisu bardzo prostych zjawisk.

Na fizyce kwantowej opiera się jednak cała

współczesna chemia, elektronika oraz bar-

dzo wiele innych dziedzin. Co ciekawe, jest

to bardzo młoda gałąź wiedzy – jej początki

datujemy na początek wieku XX.

śle określonych orbitach, a przejścia pomię-

dzy nimi mogą zachodzić jedynie wskutek

absorbcji lub emisji odpowiednich kwantów

energii (równych różnicy energii pomiędzy

powłokami).

Skoro fala elektromagnetyczna może

być interpretowana jako strumień cząstek

o określonym pędzie, to strumień cząstek

powinien posiadać właściwości falowe – do

takiego wniosku doszedł Louis de Broglie

w swojej pracy opublikowanej w 1924 ro-

ku. Jego hipoteza została potwierdzona do-

świadczalnie przez Davissona i Germera w

1927 roku, gdy po skierowaniu wiązki elek-

tronów na strukturę krystaliczną (działają-

cą jako trójwymiarowa siatka dyfrakcyjna)

zaobserwowali oni zjawisko dyfrakcji, cha-

rakterystyczne dla fal elektromagnetycz-

nych. Cechę fal elektromagnetycznych, po-

legającą na jednoczesnej obecności własno-

ści korpuskularnych (cząsteczkowych) i fa-

lowych, nazywamy dualizmem korpusku-

larno-falowym.

Jednym z najważniejszych kroków na dro-

dze do opracowania kompletnej teorii fizyki

kwantowej było opublikowanie przez Erwina

Schrödingera równania Schrödingera. Przy je-

go wykorzystaniu stało się możliwe opisanie

ewolucji stanu układu kwantowego wraz z

upływem czasu.

Bardzo ważna, z punktu widzenia kon-

strukcji komputerów kwantowych, jest zasa-

da nieoznaczoności Heisenberga. Mówi ona,

że nie można jednocześnie i z dowolną do-

kładnością dokonać pomiaru dwóch wiel-

kości, takich jak pęd i położenie lub czas i

energia. W świecie kwantowym nigdy nie

poznamy wszystkich parametrów cząstecz-

ki – możemy mówić jedynie o prawdopodo-

bieństwie, że cząstka w danej chwili znajduje

się w określonym stanie.

Następne lata przyniosły duże postępy w

zakresie formułowania formalizmu mate-

matycznego, niezbędnego do pełnego opisu

praw fizyki kwantowej. W 1927 roku Paul

Dirac połączył prawa mechaniki kwanto-

wej ze szczególną teorią względności Einste-

ina oraz wprowadził notację stanów układów

kwantowych. W 1932 roku wspominany już

John von Neumann zaproponował komplet-

ny sposób opisu mechaniki kwantowej w ję-

zyku matematyki.

Od tego czasu rozwój fizyki kwantowej

przebiegał już bardzo szybko – wielu na-

ukowców zaangażowanych w jej rozwój pra-

cowało przy projektach zbrojeniowych pro-

wadzonych przez Stany Zjednoczone, mię-

dzy innymi w projekcie Manhattan (mającym

na celu budowę bomby atomowej). Jednym z

najważniejszych, późniejszych dokonań, było

opracowanie teorii elektrodynamiki kwanto-

wej (ang. QED – Quantum Electrodynamics )

przez Richarda Feynmanna.

Pomimo ogromnej drogi, jaką przebyła fi-

zyka kwantowa od momentu jej powstania,

dalej mamy do czynienia z wieloma nie-

wiadomymi. Duże wysiłki ukierunkowa-

ne są również na opracowanie tzw. Teorii

Wszystkiego – wyrażającej wszystkie pra-

wa przyrody i łączącej cztery oddziaływa-

nia podstawowe (grawitację, elektromagne-

tyzm, oddziaływanie silne oraz oddziały-

wanie słabe).

Krótka historia izyki kwantowej

Pod koniec XIX wieku fizycy byli bardzo

dumni ze stopnia rozwoju tejże dziedziny na-

uki. Większość problemów, które frapowały

już starożytnych filozofów przyrody, została

dawno rozwiązana i potwierdzona odpowied-

nimi eksperymentami. Nikt nie przejmował

się kilkoma doświadczeniami, które dawa-

ły zaskakujące, niezgodne z przewidywania-

mi wyniki – prawdopodobnie uważano, że z

pewnością znajdzie się ktoś, kto zinterpretu-

je je w odpowiedni sposób na gruncie istnieją-

cej teorii. Paradoksalnie, wyjaśnienie tych zja-

wisk stało się przyczyną obalenia większości

ówczesnych poglądów na temat funkcjono-

wania przyrody.

Za pioniera fizyki kwantowej uznaje się

Maxa Plancka – to on pierwszy zapostulo-

wał, że energia fali elektromagnetycznej (kon-

kretnie światła) jest skwantowana, tzn. może

przyjmować lub zmieniać się jedynie o cał-

kowite wielokrotności pewnej elementarnej

porcji, zwanej kwantem.

Badania Plancka zostały następnie wyko-

rzystane przez Alberta Einsteina w celu wyja-

śnienia zjawiska fotoelektrycznego, polegają-

cego na emisji elektronów z powierzchni me-

talu pod wpływem padającego światła. Ein-

stein wytłumaczył je w następujący sposób:

wiązka światła niesie ze sobą dyskretne war-

tości energii w postaci cząstek zwanych fo-

tonami, które przy zderzeniu z elektronami

sieci krystalicznej danej substancji powodu-

ją ich wybicie. Należy mieć na uwadze, że je-

den foton przekazuje całą swą energię jedne-

mu elektronowi, a następnie znika. Elektro-

ny uzyskują przy tym energię równą różnicy

energii fotonu i pracy wyjścia elektronu z me-

talu. Zjawisko fotoelektryczne nie zachodzi

dla częstości fali elektromagnetycznej niższej

od pewnej granicy, niezależnie od natężenia

promieniowania padającego na płytkę. Dowo-

dzi to jednoznacznie, że energia przenoszona

przez falę elektromagnetyczną jest skwanto-

wana i zależy jedynie od długości fali.

W 1913 roku Niels Bohr ogłosił swoje po-

stulaty dotyczące budowy atomu wodoru.

Oprócz wyjaśnienia paradoksu związane-

go ze stabilnością jądra atomowego (według

praw mechaniki klasycznej, elektrony krą-

żące wokół jądra powinny wypromieniowy-

wać energię, wskutek czego po krótkim cza-

sie musiałyby spaść na jądro), model Bohra

zakładał, że elektrony poruszają się po ści-

Zastosowanie izyki kwantowej

Większości osób niezainteresowanych na-

ukami przyrodniczymi i pewnymi dzie-

dzinami techniki fizyka kwantowa kojarzy

się z naukami znacznie bardziej abstrakcyj-

nymi i niemającymi praktycznych zastoso-

wań, np. kosmologią. Rzeczywistość jest

jednak zupełnie inna – bez rozwoju fizy-

Rysunek 1. Przedstawienie maszyny Turinga

Tabela 1. Tabele funktorów logicznych

p q p AND q p OR q NOT p p XOR q

1 1 1

1 0 0

0 1 0

0 0 0

www.sdjournal.org

Warsztaty

ki kwantowej nie można mówić o rozwoju

wielu dziedzin chemii oraz – co powinno

być dla nas szczególnie interesujące – elek-

troniki. Okazuje się bowiem, że większość

podzespołów używanych we współcze-

snych komputerach korzysta ze zjawisk

wytłumaczalnych za pomocą mechaniki

kwantowej.

Bez znajomości praw fizyki kwantowej

niemożliwa byłaby produkcja podstawo-

wych podzespołów półprzewodnikowych,

takich jak diody i tranzystory, nie wspomi-

nając o nawet najprostszych układach sca-

lonych. Jeżeli weźmiemy pod uwagę, jak

ogromną rolę odgrywa technologia półprze-

wodnikowa w rozwoju informatyki, oraz jak

duży popyt na nowe technologie elektro-

niczne generuje informatyka, to nie będzie-

my mogli zignorować roli odkryć z dziedzi-

ny fizyki kwantowej dla kształtu wspołcze-

snego świata.

Zastanawiasz się teraz zapewne nad nastę-

pującym problemem – skoro współczesne

komputery w tak dużym stopniu korzystają z

odkryć fizyki kwantowej, to dlaczego nie na-

zywamy ich komputerami kwantowymi? Jest

to bardzo dobre pytanie – aby jednak na nie

odpowiedzieć, przypomnimy najpierw budo-

wę i zasadę działania współczesnych kompu-

terów i algorytmów.

Maszyna Turinga

a współczesne komputery

Jednym z podstawowych, abstrakcyjnych mo-

deli komputera jest maszyna Turinga, stwo-

rzona przez matematyka Alana Turinga. Jak

zaraz się przekonasz, jest ona modelem ściśle

teoretycznym – nie do końca oddaje zasadę

działania rzeczywistych komputerów cyfro-

wych. Nie będziemy zajmowali się nią zbyt

długo – matematyczne szczegóły jej działa-

nia są dość skomplikowane, nie mówiąc już o

jej zastosowaniu w celu określania złożoności

obliczeniowej lub rozwiązywalności konkret-

nych problemów.

Maszyna Turinga składa się z nieskoń-

czenie długiej taśmy podzielonej na pola,

służącej jako pamięć (Rysunek 1). Każde z

pól taśmy może znajdować się w jednym z

określonej liczby stanów. W trakcie realiza-

cji procesu obliczeniowego, maszyna Tu-

ringa znajduje się w jednym ze skończonej

liczby stanów, z głowicą ustawioną nad jed-

nym z pól taśmy. Po wykonaniu instrukcji

(polegającej na zmianie wartości pola) gło-

wica przesuwana jest o jedno pole w prawo

lub w lewo.

Z pewnością dostrzegasz już główną ide-

alizację w budowie maszyny Turinga, doty-

czącą nieskończoności taśmy – żaden kom-

puter nie dysponuje nieskończoną pamię-

cią. Maszyna Turinga jest więc jedynie mo-

delem, który z zasadą działania współcze-

snych komputerów ma jedynie kilka wspól-

nych cech charakterystycznych. Najważniej-

szymi z nich są determinizm oraz operowa-

nie na wartościach dyskretnych.

Determinizm jest jedną z podstawowych

cech współczesnych komputerów. Zakłada-

jąc, że maszyna działa poprawnie oraz zna-

jąc kod programu i dane wejściowe, jesteśmy

w stanie dokładnie przewidzieć tok jej dzia-

łania oraz wynik końcowy. Na działanie kom-

putera deterministycznego nie ma wpływu

przypadek, lecz jest ono ściśle zdefiniowa-

ne poprzez jego budowę, przetwarzany kod

oraz dane.

Kolejną ważną cechą komputerów cyfro-

wych jest jest działanie na wartościach dys-

kretnych – czyli należących do skończone-

go zbioru. Elementarną jednostką infor-

macji przechowywanej w komputerze jest

bit (0 albo 1), zaś wszystkie bardziej zło-

żone typy danych są ciągami bitów. Wi-

dać więc, że niezależnie od długości takie-

go ciągu (oznaczmy ją przez n) może on

przyjmować jedynie 2 n wartości. Każdy sy-

gnał przed przetworzeniem przez kompu-

ter musi zostać zamieniony na postać cy-

frową – reprezentowaną poprzez skończo-

ną ilość bitów.

Realizacja sprzętowa

Wiemy już, jakie są podstawowe cechy współ-

czesnych komputerów cyfrowych. Zastanów-

my się jednak bliżej nad tym, w jaki sposób

realizowane są w nich wszystkie podstawowe

funkcje związane z przetwarzaniem danych.

Nie będziemy oczywiście opisywali żadnej

konkretnej architektury – posiadają one bar-

dzo wiele cech wspólnych, które nie zmienia-

ją się wraz z coraz to nowszymi i bardziej wy-

dajnymi modelami.

Produkowane obecnie komputery korzy-

stają z podzespołów zbudowanych przy uży-

ciu układów scalonych. Układy scalone za-

wierają (w zależności od skali integracji) od

kilkudziesięciu do setek milionów elemen-

tarnych podzespołów elektronicznych, ta-

kich jak tranzystory, diody, rezystory i kon-

densatory. Dzięki postępowi technologicz-

nemu w elektronice, możliwe jest budowa-

nie układów, w których elementy te mają co-

raz to mniejsze rozmiary, co z kolei prowadzi

do zmniejszenia zużycia energii i zwiększe-

nia mocy obliczeniowej (przynajmniej teo-

retycznie).

Budowa współczesnych układów scalo-

nych jest niezwykle skomplikowana, ma jed-

nak bardzo wiele cech wspólnych z prostymi

układami scalonymi realizującymi funkcje lo-

giczne. Jedną z nich jest wykorzystanie dys-

kretnych poziomów napięć w celu reprezen-

tacji stanów logicznych, np. 1 – 5V, 0 – 0V

(w układach TTL – Transistor-to-Transistor-Lo-

gic ). Napięcie podane na dane wejście może

mieć oczywiście dowolną wartość – istnieje

jednak pewien próg, powyżej którego napię-

cie interpretowane jest jako logiczna 1.

Architektura

współczesnych komputerów

Pełne zrozumienie zasady działania współ-

czesnych komputerów i programów przez nie

przetwarzanych wymaga poznania podstawo-

wych paradygmatów leżących u podstaw in-

formatyki. Zajmiemy się teraz teoretycznymi

i praktycznymi podstawami działania współ-

czesnych komputerów.

Rysunek 2. Algorytm faktoryzacji Shora w symulatorze QCL

Więcej do przeczytania w papierowym wyda-

niu Software Developer’s Journal.

11/2009

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: