Strona główna

Wykład 1 Krótki wstęp


Pobieranie 43.55 Kb.
Data18.06.2016
Rozmiar43.55 Kb.
Wykład 1
Krótki wstęp

Komputery kwantowe są urządzeniami, które wykonują logiczne operacje nad stanami kwantowymi za pomocą unitarnych, liniowych przekształceń. Przy tym w ciągu tych obliczeń superpozycje kwantowe pozostają bez zmian. Komputer kwantowy wykonuje operacje na całym rejestrze, czyli na wszystkich liczbach jednocześnie. Ta właściwość komputera kwantowego nazywa się kwantowym paralelizmem i może być wykorzystana dla równoległych obliczeń kwantowych.

Historia wyliczeń kwantowych zaczęła się z pytania „akademickiego”, – jaką minimalną ilość ciepła wydziela komputer wykonując jeden krok w obliczeniach? W 1961 roku Landauer udowodnił, że tylko operacje logiczne, które potrzebują dyssypacji energii są operacjami nieodwracalnymi. To doprowadziło Benneta do odkrycia możliwości wyliczeń na podstawie operacji odwracalnych bez dyssypacji energii. Zatem Toffoli zaproponował słynną bramkę Control – Not (CN-bramka), która zmienia wartość wybranego bitu ( albo ) jeżeli kontrolny bit ma wartość 1. Toffoli pokazał również, że trójbitowa bramka (control-control-not albo bramka Toffoli) jest uniwersalnym narzędziem do obliczeń cyfrowych (digital), tj. kombinacje z tych bramek daje możliwość wykonać dowolne obliczenie cyfrowe.

Idea komputera kwantowego powstała na początku lat 1980–tych i była wysunięta przez Benioffa i Feynmana. Oni wykazali, że bity reprezentujące stany kwantowo-mechaniczne mogą ewoluować przy działaniu na nich operatorami kwantowo-mechanicznymi bez strat energii, co daje możliwość wykonywać wyliczenia odwracalne. W 1989 roku Deutsch zaproponował uniwersalną trójkubitową kwantową logiczną bramkę i pokazał, że wskutek tego, że w obliczeniach kwantowych wykorzystują się superpozycyjne stany kwantowe, obliczenia kwantowe są najmocniejsze w porównaniu z obliczeniami cyfrowymi. W 1993 roku Lloyd zaproponował przy obliczeniach kwantowych stosować impulsy elektromagnetyczne, które powodują przejścia rezonansowe w łańcuchu słabo oddziałujących między sobą atomów.

W 1994 roku „wybuchowe” zainteresowanie obliczeniami kwantowymi było spowodowane odkryciem przez Shor’a pierwszego algorytmu kwantowego, który pozwala szybką faktoryzację liczb całkowitych. (Przypomnijmy, że uproszczono faktoryzacja to jest proces, który dla danego liczby znajduje takie prostsze od cyfry (), że ich iloczyn jest równy (na przykład )). Wykonanie algorytmu Shor’a wymaga dla faktoryzacji liczby z cyframi ( dla liczby 210, a ) czasu proporcjonalnego do . Natomiast najlepsze klasyczne cyfrowe komputery wymagają czasu ~ (dla - ). Komputery kwantowe stwarzają potencjalne zagrożenie dla obecnej kryptografii, która zakłada, że bystra faktoryzacja nie może istnieć.
Maszyna Turinga

Maszyna Turinga ma trzy części (rys.1.1) – taśma podzielona na kwadraty, skaner i cyferblat (dial). Maszyna marze zapisać i odczytać symbol albo 1 w oknie kwadratu taśmy. Dowolna całkowita liczba zapisuje się jako ciąg jedynek. Na przykład liczbie 5 odpowiada sekwencja 11111. Symbol określa miejsce, gzie liczba zaczyna się i gdzie kończy się.



Rys.1.1. Maszyna Turinga. Na taśmie są zapisane dwie liczby 1 do dodawania.



Program dodawania liczb jest przedstawiony w tabeli 1.1. Symbol D oznacza „zapisać cyfrę 1” w odpowiednim kwadracie na taśmie; symbol oznacza „zapisać ”; oznacza „skasować”; oznacza „przesuń taśmę o jeden kwadrat w prawą stronę”; oznacza „przesuń taśmę o jeden kwadrat w lewą stronę”. Cyfry od 1 do 6 po literze oznaczają rozkaz „ustaw na cyferblacie tą cyfrę”.

Znak zapytania (?) oznacza „błąd”; znak wykrzyknika (!) oznacza „praca jest skończona”.

Rozważmy teraz proces dodawania. Najpierw skaner widzi cyfrę 1 na taśmie i cyferblat ustawiony na 1. Zgodnie z instrukcją (tabela 1.1) na przecięciu (1,1) jest napisano : „” przesuń taśmę na jeden kwadrat w prawą stronę i ustaw na cyferblacie 1”.

Po wykonaniu tego rozkazu otrzymujemy wynik pokazany na rys.1.2a. Teraz skaner widzi na taśmie , a na cyferblacie – 1. Zgodnie z instrukcją mamy (1,) , czyli rozkaz „skasuj i ustaw na cyferblacie 2”. Wynik wykonania tego rozkazu jest pokazany na rys.1.2b. Trzecia instrukcja (2,) jest . Kolejne kroki po wykonaniu instrukcji są pokazane w tabeli 2.2. Cyfry w nawisach wewnątrz kwadratów oznaczają ustawienie cyferblatu na tą cyfrę. Na przykład, 1(5) oznacza, że skaner „łączy” kwadrat z indeksem 1 i cyferblat ustawiony na cyfrę 5. Jeżeli skaner widzi pusty kwadrat i cyfrę 6 na cyferblacie, to w tabeli 1.2 to oznaczono jako (6). Ostatni wiersz w tabeli 1.2 zawiera wynik dodawania : 1+1=2. Program mnożenia wymaga 15 cyfr na cyferblacie, ale idea programowania jest taka sama.

a


b


Rys.1.2. Kolejne kroki wykonania obliczeń

Tabela 1.1. Program dodawania dla maszyny Turinga



Wskaźnik dysku



Symbol skanera








1













1



















2





?













3



















4



?















5



?















6



!









Maszyna Turinga ma takie same komponenty, co i dowolny zwykły komputer. Elementy zapisu i kasowania przedstawiają arytmetyczne bloki, które wykonują obliczenia. Tabela instrukcji 1.2 jest blokiem sterowania (control unit). Taśma i cyferblat są blokami pamięci.

Tabela 1.2. Kolejne kroki wykonania obliczeń





Binarny system i algebra Boole’a

Większość komputerów wykorzystują system binarny. W tym systemie dowolna całkowita liczba może być zapisana w postaci



,

gdzie przyjmują wartości 0 albo 1. Na przykład, 59 = (111011) oznacza



.

Załóżmy, że komputer musi zsumować dwie liczby, 2 i 3. Ponieważ i , mamy w binarnym systemie dwie liczby (10) i (11). Najpierw sumując 0 i 1 (prawa kolumna) otrzymujemy 1. Zatem, sumując 1 i 1 (druga kolumna z prawej strony) otrzymujemy 0 w drugiej kolumnie i przenosimy 1 do trzeciej kolumny. A zatem suma jest równa (101). W układzie dziesiątkowym liczba (101) oznacza . Tabela 1.3 zawiera reguły dodawania binarnych cyfr (bitów).

Tabela 1.3. Reguły dodawania w binarnym systemie

A jest wartość bitu w dowolnej kolumnie z numerem pierwszym; B – wartość w tej samej kolumnie z drugim numerem; C – przeniesienie po dodawaniu w kolumnę z prawej strony; S – wartość bitu w sumie i D – wartość przeniesienia w następną kolumnę z lewej strony.

Przy pracę z tą tablicą, dogodniej wykorzystywać metody algebry Boole’a. Tę metody w znacznym stopniu są pożyteczne, ponieważ, jak będzie widać niżej, wzory zapisane w terminach algebry Boole’a są dostępny do realizacji w obwodach elektrycznych. Binarna algebra Boole’a jest określona za pomocą tabeli dodawania (rys.1.4a) i mnożenia (rys.1.4b).

Tabela 1.4. Reguły dodawania (a) i mnożenia (b) dla binarnej algebry Boole’a

W terminologii algebry Boole’a dwie operacje często oznaczają jako OR i AND operacje, odpowiednio. Cyfry w pierwszej kolumnie i pierwszym wiersze każdej tabeli 1.4 określają dwa bity na wejściu, czyli dwie cyfry nad którymi wykonuje się operacja; natomiast wewnątrz tabeli na przecięciu tych dwóch cyfr jest pokazany wynik wyjściowy.

W terminach algebry Boole’a, wzór na S w tabeli 1.3 możemy zapisać jako

, (1.1)

gdzie kreska oznacza „dopełnienie”. (Dopełnieniem do 0 jest 1, a do 1 jest 0).

Sprawdzimy jako przykład drugi wiersz w tabeli 1.3. Ponieważ

,

mamy


.

Korzystając z tabeli 1.4b znajdujemy



,

a zatem, korzystają c tabeli 1.4, mamy





.

Drugi człon w (1.1) jest równy . A więc, ostateczne wynik w prawej stronie (1.1) jest , co pokrywa się z wartością S w drugim wiersze tabeli 1.3. Wzór na D możemy zapisać jako



. (1.2)

Na przykład dla drugiego wierszu w tabeli 1.3 mamy wynik



,

który pokrywa się z wartością D w tym wierszu.

Rozważmy teraz najprostszy „komputer” do dodawania zgodnie z regułami algebry Boole’a. Komputer składa się z zespołu obwodów, z których każdy ma dwa stany, względem przepływu prądu – „jest prąd” albo „nie ma prąd”. Pierwszy stan odpowiada wartości binarnej jedynce 1, a drugi stan odpowiada 0. Stosując zespół takich obwodów możemy zapisać dowolną liczbę w binarnym systemie. W podobny sposób wykorzystując drugi zespół obwodów możemy zapisać drugą liczbę (rys.1.3).



Rys.1.3. Lewy zespół obwodów odpowiada liczbie 2. Prawy zespół obwodów odpowiada liczbie 3



Na rys.1.3 są przedstawione dwie liczby w systemie binarnym: i . Między prawym i lewym zespołami obwodów są ustalone układy obwodów S i D, które mogą chronić informację, odpowiednio, o sumie i przeniesieniu. Powstaje pytanie: jakie muszą być wykonane operacje nad wartościami bitów i (), żeby otrzymać ostateczny wynik? Dla tego, żeby wykonać te operację potrzebne są transformacje (logiczne bramki), które działają zgodnie ze wzorami (1.1) i (1.2).

Te bramki możemy stworzyć korzystając z zespołu obwodów. Załóżmy, że mamy trzy bity i , które są przedstawione za pomocą trzech obwodów i , odpowiednio. Na rys.1.4 jako przykład jest przedstawiona bramka, która transformuje wartości bitów w (pierwszy człon w (1.2)). Obwody i są związane „wiązaniem” indukcyjnym z sąsiednimi cewkami. Zakładamy, że wyłączniki „a” i „b” w tych cewkach są włączone, jeżeli prąd nie płynie w sąsiednich cewkach. Natomiast, jeżeli prąd płynie w sąsiedniej cewce, pole magnetyczne cewki wywołuje wyłączenie wyłącznika. Istnieją specjalne klucze, które otwierają wyłączniki „c”, „d”, „e”, „f”, „g” i „h” jeżeli nie płynie prąd w odpowiednie sąsiedniej cewce. Natomiast prąd w cewce powoduje zamknięcie odpowiedniego wyłącznika.

Załóżmy, na przykład, że wartość bitu wynosi 1, czyli w obwodzie płynie prąd (rys.1.4). W tym przypadku, klucz „a” jest otwarty i prąd nie płynie przez klucz. To oznacza, że stan prądu (płynie albo nie płynie) w obwodzie, zawierającym klucz „a”, odpowiada stanowi . Odpowiednio wartość prądu płynącego przez klucz „b” odpowiada stanowi .

A zatem, prąd płynie przez wyłączniki „e” i „f” tylko wtedy, jeżeli prąd płynie w obwodzie , a klucz „a” jest zamknięty. To oznacza, że prąd płynący przez klucze „e” i „f” odpowiada wartości (, jeżeli i . W przeciwnym przypadku ). Podobnie, jeżeli prąd płynie przez klucze „c” i „d”, to oznacza, że mamy . Klucz „g” jest zamknięty, jeżeli nie płynie prąd w odpowiedniej cewce, tj. jeżeli płynie



Rys.1.4. Bramka logiczna, która transformuje bity i



prąd chociażby przez klucze „ef” albo „dc”. To oznacza, że klucz „g” jest zamknięty, jeżeli albo jest równe 1. A zatem klucz „g” jest zamknięty, kiedy i jest otwarty, jeżeli . Otrzymaliśmy, więc operację dodawania Boole’a, czyli operację OR. Klucz „h” jest zamknięty jeżeli w obwodzie płynie prąd, tj. . Ten właśnie przypadek jest pokazany na rys.1.4. A zatem, prąd płynie przez klucze „g” i „h” tylko wtedy, kiedy i . To oznacza, że prąd płynący prze klucze „gh” odpowiada wartości . W podobny sposób, korzystając z boleje skomplikowanego schematu można skonstruować obwody odpowiadające operacjom (1.1) i (1.2). W nowoczesnych komputerach obwody budują z cienkich tranzystorów sylikonowych, jednak główna idea bramek logicznych, które transformują wartości bitów ostaje się taką samą.

Zadania do Wykładu 1.






©snauka.pl 2016
wyślij wiadomość