O modelach obliczeń komputerowych

Zastanówmy się nad następującym pytaniem: czym jest komputer? Sądzę, że odpowiedź na tak zadane pytanie może zależeć w znacznej mierze od tego, kogo o to pytamy. Taka sytuacja nie jest, oczywiście, czymś wyjątkowym. Jeśli zamiast informatyką zajmiemy się cukiernictwem i zapytamy: czym jest tort, to też różne osoby będą różnie odpowiadać...

Cukiernik opisujący tort widzi go jako kolejne poziome warstwy, które musi odpowiednio przygotować i w dobrej kolejności ułożyć. Łakomczuch - raczej widzi jego przekrój pionowy, stanowiący brzeg konkretnego kawałka. Jeśli zostaniemy przy gastronomii, ale przeskoczymy tym razem do piecyków kuchennych, znowu zaobserwujemy postulowaną dwoistość. Inżynier projektujący piecyk myśli o jego wydajności, o precyzji nastawienia temperatury, o tym, jak sprawić, żeby piecyk odpowiednio szybko się nagrzał itp., itd. Z kolei kucharz zakłada, że piecyk spełnia założenia podane w jego instrukcji i skupia się przede wszystkim na myśleniu, jak za jego pomocą wyczarować coś pysznego.

Spojrzenie na komputery jest w jakimś stopniu podobne do tego opisywanego wyżej. To znaczy mamy konstruktorów (fizyków, inżynierów), którzy chcą zbudować odpowiednio szybką i sprawną maszynę. Z drugiej strony, mamy użytkowników (informatyków, matematyków), którzy chcieliby z tego urządzenia po prostu korzystać. Te dwa spojrzenia mogą być bardzo różne, dlatego potrzebujemy czegoś, co jest odpowiednikiem instrukcji obsługi piecyka. To znaczy czegoś na tyle konkretnego, żeby konstruktorzy wiedzieli, co mają stworzyć, a z drugiej strony - na tyle abstrakcyjnego, żeby użytkownicy mogli z komputera korzystać, wcale nie znając szczegółów jego budowy. Tym czymś jest właśnie tytułowy formalny model obliczeń.

Zanim przejdziemy do opisów konkretnych modeli obliczeń - mała dygresja. Otóż przykład przejścia od świata fizyków i inżynierów do świata informatyków to szczególny przykład ogólniejszego zjawiska - tak zwanego abstrahowania. Pojęcie to ma, pozwolę sobie tutaj na arbitralne stwierdzenie, fundamentalne znaczenie w całej informatyce. Więcej - często występuje szeregowo, jako zbiór tak zwanych kolejnych warstw abstrakcji. Jest to z pewnością temat na cały oddzielny szczegółowy artykuł. Tym razem podam tylko ogólnikowy przykład: sieć Internet składa się z warstw abstrakcji: fizycznej, łącz danych, sieciowej, transportowej, sesji, prezentacji i aplikacji. Zawsze polega to na tym, że projektując pewną warstwę, zapominamy o szczegółach warstwy niższej, pozostawiając w naszej głowie tylko ogólną instrukcję jej obsługi. I dalej: efektem naszej pracy ma być nie tylko jakiś bardziej złożony produkt, ale również uproszczona instrukcja obsługi do niego. Czyli jak w życiu: równie ważne (a może i ważniejsze) od tego, z kim warto się znać i z kim się spotykać, jest to, kogo nie warto znać i gdzie nie bywać.

Po tym (przyznaję, przydługim) wstępie czas już przejść do konkretów. Zacznijmy więc od modelu obliczeń klasycznego komputera.

Obwód obliczający, czy liczba $|b4b3b2b1 2$ zapala zaznaczony segment na wyświetlaczu kalkulatora

Dla programisty komputer to coś, co:

ma pamięć, do której potrafimy wpisać jakieś dane;
potrafi uruchomić zaprojektowany (w specjalnym języku) przez użytkownika program i jego wynik zapisać do pamięci;
pozwala na odczytanie zawartości pamięci.

Oczywiście, modele takie jak wyżej mogą się istotnie różnić, zależnie od tego, jaki charakter ma pamięć (zwykle ciąg bitów ustalonej długości) oraz - przede wszystkim - jaki język opisu programu dopuszczamy. Przykładowe modele w tym duchu to: model maszyny Turinga, model maszyny RAM (random-access machine), interpreter języka Java czy model oparty o obwody logiczne złożone z bramek. Skupmy się na chwilę na tym ostatnim.

Model obwodów logicznych moglibyśmy opisać, na przykład, tak (modele tego typu są bardzo często stosowane do opisu układów scalonych):

pamięć stanowią dwa wektory: $n vin∈ {0,1}$ oraz $m vout∈{0,1} .$ Użytkownik potrafi dowolnie ustalić wartość wektora $|vin$ (czyli, żargonowo, "mamy $|n$ bitów wejściowych").
Użytkownik może opisać dowolną sieć co najwyżej $T$ bramek OR, AND oraz NOT łączących wektor $vin$ z wektorem $|vout.$ Wówczas komputer jest w stanie przypisać do wektora $v out$ wynik obliczeń opisanej sieci na wektorze $vin.$
Użytkownik po skończonym obliczeniu potrafi poznać wartość wektora $v . out$

Przykład programu w tym modelu pokazuje rysunek obok.

Poziom abstrakcji w tym przykładzie jest chyba dość jasny. Inżynier projektujący tak zdefiniowany komputer (Czytelnik Lubiący Konkrety może zapoznać się z technologią FPGA) ma na celu zastanowienie się, w jaki sposób stworzyć urządzenie, które:

zawiera i potrafi (na żądanie użytkownika) ustawić dowolnie $T$ bramek logicznych;
potrafi przyjąć podane przez użytkownika dane wejściowe (opis wektora $v in$ );
potrafi dokonać obliczenia i zwrócić użytkownikowi wynik obliczeń, czyli $|vout.$

Powyższe zadanie zapewne jest bardzo trudne, wymaga znajomości fachowej wiedzy z elektroniki, wiedzy o działaniu tranzystorów itp., itd.

Z drugiej strony: informatyk, który z takiego urządzenia chce korzystać, może zupełnie nie znać fizyki i już myśleć tylko o algorytmice, czyli - w tym przypadku - nauce o takim przestawianiu klocków (bramek), żeby obliczało się dokładnie to, co chcemy i to możliwie szybko (a więc przy użyciu możliwie małej liczby bramek).

Przejdźmy teraz do tego, co stanowi esencję całego tego numeru Delty, czyli do komputerów kwantowych. Za chwilę przedstawimy formalny model obliczeń dla komputera kwantowego (czyli jego "instrukcję obsługi"). To, jakie problemy natury fizycznej napotykają projektanci takich potencjalnych komputerów, opisuje Rafał Demkowicz-Dobrzański. Z drugiej strony - jakie cuda potrafiłby zdziałać informatyk mający dostęp do takiego (hipotetycznego) urządzenia opisuje Wojciech Czerwiński, przybliżając szczegóły algorytmu Shora na rozkład dużych liczb na czynniki pierwsze. Prezentowany model korzysta z języka abstrakcyjnej algebry liniowej. Podstawy tej dziedziny prezentują Maciej Zdanowicz oraz Marek Kordos, przy okazji dowodząc, że programiści za kilkadziesiąt lat będą musieli znać chyba trochę więcej matematyki niż ci obecni. Na ile blisko (a na ile daleko) od stworzenia Prawdziwego Komputera Kwantowego jesteśmy w tej chwili pisze Piotr Zalewski. Dodatkowo kwartet Gardas, Jałowiecki, Dajka, Mierzejewski oraz (solo) Łukasz Rajkowski próbują przybliżyć Czytelnikowi, co już dziś jest komercyjnie dostępne. Po pierwsze omawiamy komputer D-Wave, który jednak realizuje (na 2048 kubitach) inny niż tu opisany model obliczeń kwantowych. Po drugie: omawiamy praktyczny protokół BB84, zakładający istnienie oraz możliwość szybkiego i taniego tworzenia "komputerów jednokubitowych" na żądanie.

Gorąco zachęcam do lektury tych i innych artykułów z tego numeru i bezzwłocznie przystępuję do prezentacji modelu obliczeń kwantowych.

Do opisu stanu pamięci komputera kwantowego potrzebne są liczby zespolone, których zbiór oznaczamy symbolem $C$ (więcej o nich pisze Marek Kordos na stronie 4). Zazwyczaj operować będziemy ciągami $m$ liczb zespolonych (tak zwanymi zespolonymi wektorami wymiaru $m$ ), których zbiór oznaczamy $Cm .$ (Przykładowo: $ϕ = (2+ i,6,10− 3i,i)∈ C4.$ ) Dla wektorów określamy ich długość jako pierwiastek z sumy kwadratów modułów jego kolejnych współrzędnych. W naszym przykładzie długość $|ϕ$ wynosi więc: $√ -----2----2---------2----2 √ -------------- √ --- 2+ i + 6 + 10− 3i + i = 5 + 36+ 109 +1 = 151.$
Opisem stanu pamięci komputera kwantowego jest jeden wektor o długości $1$ z przestrzeni $n C2 ,$ np. $1 i 2 −i 3 ψ = (0,0,0,2,0,-2-,0, 2 ) ∈ C2 .$ W świecie kwantowym często zapisujemy to samo w nieco innym (równoważnym) języku, mianowicie:
$1 i√ 2- −i ψ = -- 011⟩+---- 101⟩ +-- 111⟩, 2 2 2$
gdzie (jak łatwo się domyślić) $bin(k)⟩$ oznacza wektor złożony z $n |(2 − 1)$ zer i jedynki na $(k + 1)$ -szej współrzędnej, np. $011⟩= (0,0,0,1,0,0,0,0),$ przy czym $|bin(k)$ oznacza binarny zapis liczby $|k.$

Wektory $bin(k)⟩$ nazywamy wektorami bazy standardowej. Stany pamięci, które nie są takimi wektorami, a więc są sumą co najmniej dwóch różnych wektorów bazowych, fizycy lubią nazywać superpozycją. Jeśli stan pamięci jest opisany wektorem z $C2n,$ to mówimy, że nasz komputer operuje $|n$ kubitami. Warto zwrócić uwagę, że stan pamięci klasycznego komputera operującego $n$ bitami opisujemy po prostu jednym ciągiem zer i jedynek długości $|n$ (np. $b1b2...bn$ ), co możemy interpretować jako ustalenie jednego wektora bazy standardowej $2n b1b2...bn⟩∈ C .$ Przewaga komputera kwantowego polega zaś na tym, że w pamięci możemy trzymać bardziej wyrafinowane obiekty, a więc kombinacje liniowe takich wektorów (superpozycje), jak chociażby opisany wyżej wektor $ψ ,$ będący przykładem stanu pamięci komputera trójkubitowego.

Stan początkowy komputera użytkownik może ustalić zupełnie dowolnie, przy czym może używać iloczynu tensorowego do opisu (ta uwaga jest o tyle istotna, że cała przestrzeń ma wymiar wykładniczy, więc sam opis może czasem być ogromny; iloczyn tensorowy jest tu więc potencjalnym ułatwieniem). Iloczyn tensorowy $⊗$ wektorów to bardzo prosta operacja, o której więcej piszemy na stronie 5. Na razie wystarczy nam tylko własność $b1...bn⟩⊗ b′1...b′m⟩ = b1...bnb′1...b′m ⟩,$ by zrozumieć, że ten sam wektor można opisać długo bądź zwięźle:
$pict$

lub
$1 α= --( 0⟩ + 1⟩)⊗ ( 0⟩− 1⟩)⊗ ( 0⟩+ 1⟩ ) ⊗ ( 0⟩ + 1⟩). 4$

Pojedyncze obliczenie na komputerze kwantowym odpowiada przemnożeniu stanu pamięci przez podaną przez użytkownika (nie byle jaką) macierz. W tym miejscu Czytelnik Algebraicznie Kulejący bardzo proszony jest o nieprzerażanie się tym pojęciem. Okazuje się, że nawet nie musimy dokładnie wiedzieć, jak się mnoży dowolną macierz przez wektor, bo wystarczą nam tylko trzy przykłady (dla macierzy H, T i CNOT oraz macierz identyczności I):
$1 H(a 0⟩+ b 1⟩ ) = √-((a + b) 0⟩ + (a− b) 1⟩ ), 2 T(a 0 ⟩+ b 1⟩) = a 0⟩ +beiπ~4 1⟩, CNOT(a 00 ⟩+ b 01⟩ +c 10⟩+ d 11⟩) = a 00⟩ + b 01⟩+ d 10⟩+ c 11⟩.$
Jak widzimy macierze H i T dotyczą tylko wektorów jednokubitowych, a macierz CNOT - dwukubitowych. Aby opisać operację w wyższych wymiarach znów wolno nam się posłużyć iloczynem tensorowym, tym razem zastosowanym do macierzy. Ponownie jest to dość naturalna operacja (opisana szerzej późnej), a nam na razie wystarczy tylko własność $|(M1⊗ M2)( ϕ1⊗ ϕ 2) = M1(ϕ1)⊗ M2( ϕ2),$ która jest prawdziwa, gdy wymiary się zgadzają. Intuicyjnie oznacza ona, że rozpatrywane macierze można przykładać lokalnie do dowolnie wybranych współrzędnych wielowymiarowego wektora stanu pamięci. Podajmy przykład, który powinien rozjaśnić tę operację:
$1 (H ⊗ H ⊗ CNOT ⊗ I) (√--( 01101⟩ + 10011⟩ )) = 2 1 =√---((H ⊗ H ⊗ CNOT ⊗ I)( 0⟩ ⊗ 1⟩⊗ 10⟩ ⊗ 1⟩)+ 2 +(H ⊗ H ⊗ CNOT ⊗ I)( 1⟩⊗ 0 ⟩⊗ 01⟩ ⊗ 1⟩)) = --1 =√ --(H( 0⟩)⊗ H( 1⟩ ) ⊗ CNOT( 10⟩ ⊗ I( 1⟩))+ 2 +H( 1⟩ ) ⊗ H( 0⟩)⊗ CNOT( 01⟩⊗ I( 1⟩ ))) = =√-1-(√1-( 0⟩+ 1⟩) ⊗ √1-( 0⟩− 1⟩)⊗ 11⟩ ⊗ 1⟩+ 2 2 2 1 1 + √--( 0⟩ − 1⟩)⊗ √-( 0⟩ + 1⟩ ) ⊗ 01⟩ ⊗ 1⟩) = 2 2 =-√1--( 00111⟩− 01111⟩+ 10111⟩ − 11111⟩+ 2 2 + 00011⟩+ 01011⟩− 10011⟩− 11011⟩).$
Użytkownik może wybrać do opisu obliczenia dowolnie wybrany iloczyn tensorowy opisanych wyżej macierzy.

Odczyt z pamięci jest w tym modelu bardzo nietrywialny. Przede wszystkim pomiar (zwykle) nie jest deterministyczny i może zwrócić różne wyniki dla tego samego stanu pamięci. Spróbujemy zaprezentować tutaj pewien uproszczony (ale wystarczający, by śledzić chociażby artykuł o faktoryzacji Shora) opis odczytu z komputera kwantowego. Użytkownik, chcąc dokonać pomiaru pamięci w pewnym $|n$ -kubitowym komputerze, musi podać pewien podzbiór indeksów $(i ,...,i ) ⊂(1,...,n). 1 k$ Jeśli teraz stan komputera to po prostu $b1 ...bn ⟩$ (czyli pewien wektor bazowy), to uzyskamy wynik $|(bi1,...,bik).$ Jeśli natomiast stan komputera jest superpozycją $Pv> 0,1 nαv v⟩,$ gdzie $αv ∈C$ są współczynnikami przy wektorach bazowych $v⟩,$ to pomiar jest istotnie niedeterministyczny. Uzyskamy wynik $u = (bi1,...,bik)$ z prawdopodobieństwem $Pu = Pv> Su αv 2,$ gdzie $|Su$ to zbiór tych wektorów $v ∈{0,1},$ które na współrzędnych $|i,...,i 1 k$ mają dokładnie wartości $|bi1,...,bik.$
W komputerze kwantowym stan pamięci po pomiarze zmienia się (w świecie kwantowym pomiar musi zmienić stan pamięci!) na superpozycję tych składowych starego stanu, które są zgodne z pomiarem. Oczywiście niektóre stare składowe nie są zgodne z pomiarem, w związku z tym te, które są zgodne, muszą mieć zmienione współczynniki, aby długość całego wektora pamięci pozostała równa 1. Konkretnie rzecz biorąc, nowy stan pamięci po pomiarze to:
$1 √----Q α v v⟩. Pu v>Su$
Zauważmy, że po pomiarze współrzędne $i1,...,ik$ nie będą już nigdy istotne, bo są i tak zawsze takie same dla każdej składowej.
Użytkownik może wykonać dowolną sekwencję wielu obliczeń i odczytów (może je przeplatać).