Strona główna

Wykład 4 Minimalny zestaw odwracalnych bramek


Data18.06.2016
Rozmiar46 Kb.
Wykład 4
Minimalny zestaw odwracalnych bramek

Chociaż wiemy jak skonstruować uniwersalny zbiór nieodwracalnych bramek istnieją kilku przyczyn zbadać alternatywne odwracalne bramki. Najpierw, kwantowe bramki są odwracalne, a po drugie, odwracalne obliczenia możliwe są w zasadzie bez dyssypacji energii.

Odwracalny komputer oblicza - bitową odwracalną funkcję - bitów. Zwróćmy uwagę, że każda nierewersyjna funkcja może być przekształcona w rewersyjną za pomocą dodawania dodatkowych bitów: nieodwracalna funkcja (dla ) mapująca bitów na bitów

bitów)  f(m bitów) (4.1)

zostaje zastąpiona zwykłą odwracalną funkcją mapując n + m bitów na n +m bity

(x, m times 0)  (x , f) . (4.2)

Odwracalne n – bitowe funkcje są permutacjami 2n możliwych sekwencji bitów. Istnieje (2n)! takich funkcji. Dla porównania, liczba dowolnych n – bitowych funkcji wynosi . Ilość odpowiednio rewersyjnych bramek 1, 2 i 3 – bitowych wynosi 2, 24 0 40320. Ponieważ nieodwracalne klasyczne obliczenia wykonują się za pomocą dwu-bitowych operacji, odwracalne klasyczne obliczenia potrzebują trzech – kubitowych bramek dla tego, żeby obliczenia były uniwersalne. Jak można widzieć, 24 odwracalne dwu –kubitowe bramki są wszystkie liniowe i mogą być zapisane w postaci



, (4.3)

gdzie wszystkie macierzowe i wektorowe elementy są bitami i wszystkie dopełnienia są modulo 2. Ponieważ dwie jednobitowe bramki są zwykle też liniowe, dowolna kombinacja jedno- i dwubitowych operacji zastosowanych do składowych - bitowego wektora może tylko dać wynik linowy w . Z drugiej strony, dla istnieją odwracalne - bitowe bramki, które nie są liniowe, na przykład, bramka Toffoli, którą rozważmy niżej. Niżej zobaczymy, że kwantowe obliczenia, chociaż odwracalne również, nie potrzebują, żeby bramki działający na trzech-kwantowych kubitach bramkach były uniwersalne. Dalej wszystkie bramki kwantowe są ściśle liniowe ponieważ mechanika kwantowa jest teorią liniową.



Bramka CNOT

Jedną z interesujących odwracalnych klasycznych dwu-bitowych bramek jest kontroler (controlled) NOT albo CNOT, znany również jako „rewersyjny XOR”, który wykonuje XOR operację odwracalną zachowując jeden argument

(x, y)  (x, x XOR y) , (4.4)

Tablica 4.1 wykazuje dla czego (4.4) nosi nazwę CNOT: celowy (target) bit y zostaje odwrócony (is flipped) tylko wtedy, kiedy kontrolny bit x = 1. Drugim zastosowaniem CNOT jest przywrócenie początkowego stanu, co działa tą bramkę odwracalną.

Bramka CNOT może kopiować bit, ponieważ ona mapuje

(x, 0)  (x, x) . (4.5)

Tabela 4.1. Bramka CNOT

Sieć zawierająca trzy bramki XOR pokazana na rys.4.1 realizuje SWAP (wymianę) z dwoma bitami wejściowymi



Rys.4.1. Z lewej strony – pojedyncza bramka CNOT. Z prawa – bramka SWAP (wymiany)


(x, y)  (x, x XOR y)  ((x XOR y) XOR x, x XOR y) 

 (y, y XOR (x XOR y)) = (y, x) . (4.6)


Bramka Toffoli

Pokażemy teraz, że funkcjonalność uniwersalnej bramki NAND/NOT może być osiągnięta za pomocą dodawania trzech bitów, czyli bramki Toffoli (3), do naszego panelu, która znana jest też jako kontrola – kontrola -NOT, (CCNOT) i która mapuje

(x, y, z)  (x, y, xy XOR z) , (4.7)

tj. z zmienia się tylko wtedy kiedy x i y są równe 1. Nieliniowa natura bramki Toffoli pochodzi z tego, że mamy iloczyn xy. Ta bramka jest uniwersalną, przy warunku, że możemy przygotować określone (fixed) wejściowe bity i ignorujemy bity wyjściowe



  • Dla z = 1 mamy (x, y, 1)  (x, y, 1 - xy) = (x, y, x NAND y),

  • Dla x = 1 otrzymujemy z XOR y, co może być wykorzystywane dla kopiowania, wymiany itd.

  • Dla x = y = 1 otrzymujemy NOT.

A zatem możemy zrobić dowolne obliczenie odwracalnym. Faktycznie, jest możliwość wyeliminować (w zasadzie) dyssypacyjne kroki czyszczenia pamięci: zachować wszystko co jest „niepotrzebne” i co było wygenerowane w ciągu odwracalnego obliczenia, skopiować końcowy wynik obliczeń a zatem wykonać odwrotne obliczenia czyszcząc niepotrzebny dane bez dyssypacji. Chociaż to może potrzebować niektórej energii dyssypacji, to ma przewagę w porównaniu z odwracalnym obliczeniem przy końcowym czyszczeniu pamięci:

  • Czas (liczba kroków) rośnie ze wzrostem T jako w przybliżeniu 2T.

  • Potrzebne jest dodatkowa pamięć do zachowania, która rośnie w przybliżeniu jako .

Istnieją jednak podejścia rozszczepić obliczenia na kilku kroków, które inwertują się indywidualnie, tak że dodatkowa pamięć rośnie tylko proporcjonalnie do log T, ale w tym przypadku potrzebne jest większy czas obliczeniowy.

Bramka Fredkina

Inna rewersyjna trzech-bitowa bramka, która może być wykorzystywana do budowy zbioru bramek jest bramka Fredkina. W odróżnieniu od bramki Torffoli, która ma dwa kontrolne bity i jeden celowy bit, bramka Fredkina ma jeden kontrolny kubit i dwa bity celowe. Celowe bity wymieniają się jeżeli kontrolny bit jest równy 1, w przeciwnym wypadku one pozostają bez zmian. W tablice 4.2 jest pokazane wejściowe i wyjściowe bramki Fredkina, gdzie x jest kontrolny bit, a, odpowiednio, y i z są bity celowe.

Tablica 4.2. Bramka Fredkina

Dla realizacji odwracalnej bramki AND, na przykład, z bit na wejściu przyjmuje się równą 0. Na wyjściu wtedy z zawiera x AND y, jak można przeczytać z tabeli 4.2. Jeżeli drugie dwa kubity x i y były skasowane, ta bramka musi być nierewersyjną; zachowanie wejściowych bitów działa operację odwracalną. Bramka NOT również może być wbudowana w bramkę Fredkina: przyjmując y = 0 i z = 1 na wejściu widzimy, że na wyjściu z = NOT x i y = x; a zatem mamy jednocześnie realizację bramki COPY.



Komputery uniwersalne

Maszyna Turinga działa na taśmę (albo sekwencję symbolów) jak nośnik wejście/wyjście. Ona ma skończoną liczbę początkowych stanów. Jeżeli maszyna czyta symbol s z taśmy, kiedy znajduje się w stanie G, ona zamieni s na inny symbol s/ i zmieni swój stan na G/, a zatem przesuwa taśmę na jeden krok w kierunku d (na lewo albo na prawo). Maszyna jest całkowicie określona za pomocą skończonego zbioru reguł przejściowych

(s, G)  (s/, G/, d) (4.8)

Maszyna ma jeden specjalny początkowy stan, „halt” (zatrzymanie) stan, w którym maszyna przestaje wykonywać wszystkie pozostałe operacje. Na wejściu, taśma zawiera „program” i „wejściowe dane”, a na wyjściu – wynik obliczeń.

Skończony zbiór reguł przejściowych dla danej maszyny Turinga T może być zakodowany za pomocą binarnej liczby d[T] (opis T). Załóżmy T(x) jest wyjście T dla danego wejścia taśmy x. Turing pokazał, że istnieje uniwersalna maszyna Turinga U dla której

U(d[T]..x) = T(x) (4.9)

a liczba kroków U potrzebnych do symulacji każdego kroku T jest tylko wielomianową funkcją długości d[T].



Rys.4.2. Maszyna Turinga działająca na taśmie z binarnymi symbolami, zawierająca kilku wewnętrznych stanów, łącznie ze stanem „halt”


A zatem musimy przedstawić „opis” d[T] dla T i oryginale wejście x na taśmie U, a U będzie wykonywać to same zadanie jako dowolna maszyna T z prawie wielomianowym zahamowaniem.

Hipoteza Churcha - Turinga

Drugie modele obliczeń (na przykład modele sieciowe) są z punktu widzenia obliczeniowego ekwiwalentne do modelu Turinga: podobne zadania rozwiązuje się z tą samą efektywnością. W 1936 roku Alonzo Church i Alan Turing niezależnie stwierdzili



Church-Turing hipoteza: Dowolna funkcja, która może być uznawana za naturalnie obliczeniową musi być wyliczona za pomocą uniwersalnej maszyny Turinga.

Tutaj termin obliczeniowa funkcja łączy w siebie ekstremalnie szeroką klasę problem. Dowolne mapowanie skończonej sekwencji bitów na drugą skończoną sekwencję bitów należy do tej klasy. Wejściowa sekwencja może być stworzona jako długa sekwencja za pomocą naciśnięciem guzika, a wyjściowa sekwencja bitów drukuje się na tej stronie. Drugi przykład, sekwencją wejściową może być niektóra tabel zawierająca liczbowe dane, a wyjściową sekwencją reprezentacja graficzna tych danych, takich jak obróbka tekstu itd. Hipoteza Churcha i Turinga nie jest udowodniona, ale nie znalezione kontrprzykłady chociaż przeszło dużo czasu.



Złożoność i algorytmy

Złożoność ma wielu aspektów i problemy obliczeniowe mogą być kwalifikowane względem kilku mierzalnych złożoności. Tutaj rozważmy tylko kilku przykładów z szerokiej klasy złożoności.

Rozważmy niektóre zadanie wykonane na całkowitej liczbie wejściowej x; na przykład, znaleźć x2 albo określić czy x jest głównym (prime). Liczba bitów dla zapisu x jest równa

L = log2 x. (4.10)

Obliczeniowa złożoność zadania charakteryzuje się tym, jak dla rozwiązania zadania szybko zmienia się liczba s kroków maszyny Turinga ze wzrostem L. Na przykład, metoda którą większość z nas stosuje dla wyliczenia kwadratu „dużej” liczby ma ściśle



sL2 (4.11)

(jeżeli identyfikujecie s z liczbą cyfr zapiszcie na waszej kartce papieru). To jest typowy problem z klasy złożoności P; istnieją algorytmy dla których s jest wielomianową funkcją L. Jeżeli s rośnie eksponencjalnie z L problem do rozważanie jest trudnym. (Zauważmy, jednak, że nie można powiedzieć, że nie będą odkryte nowe algorytmy, które wcześniej trudne problemy rozwiążą!).

Często znaczniej łatwiej sprawdzić rozwiązanie niż jego znaleźć; przykładem jest faktoryzacja dużych liczb. Klasa złożoności NP. zawiera problemy, dla których rozwiązania mogą być sprawdzone w czasie wielomianowym. Oczywiście P znajduje się w NP , jednak nie wiadomo czy NP zwykle większe niż P, głównie z powodu tego, że nowe algorytmy mogą być odkryte każdy dzień. NP oznacza niedeterministyczny wielomian. Niedeterministyczny wielomianowy algorytm może na dowolnym kroku rozgałęzić się na dwie trajektorie, każda z których będą poruszać się paralelnie. Taki drzewopodobny algorytm może wykonać eksponencjalną liczbę kroków obliczeniowych w czasie wielomianowym (przy stratach eksponencjalnie rosną paralelnie pojemność obliczeniowa!). Dla sprawdzania rozwiązania, jednak, musimy wykorzystywać „prawidłowe gałęzi” drzewa, a to zwykle jest możliwe w czasie wielomianowym.

Niektóre problemy można sprowadzić do innych problemów, tj. rozwiązanie problemu P1 może być wykorzystane jako „krok” albo „podprogram” w algorytmie dla rozwiązania drugiego problemu P2. Często można pokazać, że P2 może być rozwiązane za pomocą wykorzystywania podprogramu P1 wielomianową liczbę raz; wtedy P2 sprowadza się wielomianowo ku P1: P2P1. (Czytaj: „P2 nie może być najtrudniejszym od P1.”) Niektóre dobre przykłady pochodzą z problem teorii grafów, kiedy szuka się trajektorii o niektórych własnościach przez określony graf (albo sieć). Problem nosi nazwę NP – złożoności jeżeli dowolny NP problem może być sprowadzony do niego. Wiadome setki NP –złożonych problem, jednym z najwięcej wiadomych problem jest problem podróżującego menedżera - znaleźć najkrótszy marszrut pomiędzy określoną liczbą miast związanych między sobą, startując i finiszując w tym samym mieście. Jeżeli ktoś znajdzie rozwiązanie wielomianowe jakiegoś NP – złożonego problemu, wtedy „P = NP” i jeden z samych fundamentalnych problemów nauki teoretycznej o komputerach będzie rozwiązany. Jednak, to ma bardzo małe prawdopodobieństwo, ponieważ wielu wybitnych naukowców bez powodzenia próbowali znaleźć takie rozwiązanie.

Warto podkreślić, że teoretyczna komputerowa nauka bazuje swoje rozważania klas złożoności na najgorszym przykładzie złożoności. W zastosowaniach praktycznych, bardzo często istnieje możliwość znalezienia bardzo dobrego przybliżenia dla rozwiązania, powiedźmy, problemu podróżującego menedżera w granicach rozumnego czasu.

Ciężkie i niemożliwe problemy

Słynnym przykładem ciężkiego problemu jest problem faktoryzacji (znalezienie głównych mnożników danej dużej całkowitej cyfry). Zgodnie z odkryciem Shora, rośnie obawa, że problem faktoryzacji może być problemem klasy NPI (I - pośredni), tj. cięższy niż P, no nie NP – złożoności. Jeżeli ten klas istnieje wtedy P NP.

Niektóre funkcje możliwie nie są ciężkie dla obliczeń, ale nie możliwość obliczenia jest związana z tym, że algorytm nigdzie nie skończy pracę, albo nikt nie wie czy kiedyś obliczenia zatrzymają się. Przykładem jest algorytm:

Jeżeli x jest równe sumie dwóch prostych, dodajemy 2 do x, w przeciwnym przypadku drukujemy x i po zatrzymaniu (halt) zaczynamy od x = 8.

Jeżeli ten algorytm zatrzymuje się będziemy mieli kontrprzykład do słynnej hipotezy Goldbacha, że każda parzysta liczba jest sumą dwóch prostych. Drugi słynny nierozwiązany problem jest problem zatrzymywania, który formułuje się bardzo prosto:

Czy istnieje ogólny algorytm dla decyzji maszyny Turinga T z charakterystyką (regułami przejścia) d[T] zatrzymać się na niektórym wejściu x?

Istnieje dobry argument Turinga, pokazujący, że taki algorytm nie istnieje. Załóżmy, że taki algorytm istnieje. Wtedy można będzie zrobić maszynę Turinga TH , która zatrzymuje się wtedy i tylko wtedy, jeżeli T(d[T]) (tj. T wykorzystuje swoje określenie jako wejście) nie zatrzymuje się

TH (d[T]) zatrzymuje się  T(d[T]) nie zatrzymuje się (4.12)

To jest możliwe ponieważ opis d[T] zawiera wystarczająco informacji o metodzie T pracy. Teraz wybierzemy opis TH samo dla siebie, tj. wybierzemy T = TH



TH (d[T]) zatrzymuje się  TH(d[TH]) nie zatrzymuje się (4.13)

Ta sprzeczność pokazuje, że nie istnieje algorytm, który rozwiązuje problem zatrzymywania się. To jest dobry rekursywny argument: niech znaleźliśmy algorytm czegoś o jej własną strukturze. Ten rodzaj rozważań jest typowym z obszaru dotyczącego twierdzenia Gödela o niemożliwości udowodnienia.



Mechanika kwantowa

Mechanika kwantowa powstała prawie dwa stulecia temu, kiedy Wollaston i Fraunhofer po raz pierwszy zaobserwowali dyskretne linie w optycznych widmach. Później Kirchhoff i Bunsen wykazali, że linie spektralne są charakterystyczne dla różnych chemicznych elementów, a zatem ustalili związek między optyką i tym, co później stało nazywać się fizyką atomową. Po upływie prawie stu lat teoria kwantowa ustaliła, że



  1. elektromagnetyczne promieniowanie jest emitowane albo absorbowane kwantami, czyli fotonami, których energia proporcjonalna do ich częstości i

  2. atomy posiadają niektóre stacjonarne stany o określonych energiach. Różnica między tymi wartościami energii odpowiadają energiom fotonów emitowanych albo absorbowanych przy przejściach.

Schrödinger pokazał, że stacjonarne stany można opisać za pomocą funkcji falowych, dynamikę których opisuje równanie nazwane później jego imieniem. Możliwe (skwantowane) wartości energii powstają z rozwiązania problemu na wartości własne, który jest związany z równaniem Schrödingera. Potem okazało się, że teoria Schrödingera jest całkowicie równoważna z podejściem Heisenberga i Pauli’jego, które rozważali algebraicznie problem własnych wartości.

Wektory w przestrzeni Hilberta

Jedną z głównych cech mechaniki kwantowej jest liniowa struktura przestrzeni jej stanów. Okazuje się, że ta własność jest również bardzo ważne przy wykorzystywaniu mechaniki kwantowej w procesach informacyjnych. W mechanice klasycznej stan skończonej liczby oddziałujących punktowych cząstek jednoznacznie określa wektor uogólnionych współrzędnych i pędów. W mechanice kwantowej, stan układu też jednoznacznie jest określony w każdej chwili przez wektor w przestrzeni Hilberta. W obydwóch przypadkach, liniowe kombinacje dwóch dozwolonych wektorów znów dają dozwolone wektory. Różnica polega na oznaczeniu i interpretacji składowych wektora. Klasyczne składowe są współrzędnymi i składowymi pędu, które mają określone wartości w każdym dozwolonym stanie i które mogą być dokładnie przepowiedziane oraz zmierzone we wszystkich możliwych fizycznych doświadczeniach. W przypadku kwantowym, składowe wektora przestrzeni Hilberta oznaczają amplitudy prawdopodobieństwa związane z możliwymi wynikami pomiarów. Z tego wynika standardowa probabilistyczna interpretacja superpozycji wektorów w przestrzeni Hilberta.

Ważne jest podkreślić, że przestrzeń Hilberta nawet bardzo prostego układu ma nieskończony wymiar. Pojedynczy atom wodoru w przestrzeni pustej ma nieskończoną liczbę stanów związanych plus kontinuum stanów rozproszonych. Zwykle odrzucamy spektrum ciągły, zakładając, że możemy nie rozważać przejścia w stany ciągłe. W celu uproszczenia matematycznego nawet przypuszczamy, że rozmiar d przestrzeni Hilberta jest skończony. Przypadek d = 2 jest ważnym przykładem jednego bitu kwantowego, czyli kubitu.

A zatem przestrzeń Hilberta jest d – wymiarowej urojoną liniową przestrzenią: każda liniowa kombinacja stanów (wektorów przestrzeni Hilberta) jest stanem też; iloczyn skalarny, norma itd. Mogą być określone w sposób zwykły. Ogólnym kwantowo-mechanicznym oznaczeniem urojonego wektora kolumnowego jest ket Diraca



. (4.14)

Odpowiednim wektorem wierszowym jest bra Diraca



, (4.15)

gdzie gwiazdka oznacza sprężenie urojone.

Ze względu na probabilistyczną interpretację mechaniki kwantowej, wystarczy rozważyć stany unormowane , tj. . Dalej stany i ( - rzeczywiste) są fizycznie ekwiwalentne: wspólny mnożnik fazowy nie jest ważny. Jednak względne fazy między składowymi stanu są wyjątkowo ważne: stany i (dla ) mogą mieć całkowicie różne własności fizyczne i największymi interesującymi zjawiskami mechaniki kwantowej są efekty interferencyjne związane z różnicą faz stanów.

Operatory w przestrzeni Hiberta

Operatory przekształcają stany w ich inną liniową superpozycję; a więc operatory możemy przedstawić macierzami urojonymi dd działającymi na d – wymiarowej przestrzeni Hilberta



, (4.16)

Własne stany (albo własne wektory) operatora spełniają równanie na własne wartości



, (4.17)

w którym wielkości urojone noszą nazwę własnych wartości. Wartości różnych własnych stanów mogą być równe; ten przypadek nazywają zwyrodnieniem (degeneracją). Trywialnym przykładem jest jednostkowy operator 1 (jednostkowa macierz ), dla którego wszystkie wartości własne są równe jedynce.

Obserwablom (wielkościom mierzalnym) odpowiadają samosprzężone albo Hermitowe macierzy, tj.

. (4.18)

Operatory samosprzężone mają rzeczywiste wartości własne (wartości własne są możliwymi wynikami pomiarów, a więc muszą być rzeczywistymi); stany własny odpowiadające własnym wartościom operatora są ortogonalne po dwojga (stany są ortogonalne nawet w przypadku zwyrodnienia). A zatem własne stany tworzą bazę przestrzeni Hilberta



, (4.19)

gdzie jest symbolem Kroneckera. (Musimy pamiętać, że rozważamy przestrzeń Hilberta skończonego wymiaru, w której wszystkie stany są unormowane na jedynkę).

Obserwabla jest całkowicie określona przez zbór swoich wartości własnych i stanów własnych, a dowolny stan może być rozwinięty w szereg względem własnych stanów , które spełniają (4.19). To prowadzi do reprezentacji spektralnej operatora . Dla określenia tej reprezentacji wprowadźmy kolejną klasę operatorów: operatory rzutowe albo krótko rzutniki. Rzutnik na stan własny (albo, ściślej) na podprzestrzeń rozpiętą na jest określony jako

. (4.20)

Zastosowanie do dowolnego stanu powoduje mnożenie



, (4.21)

gdzie - „długość” rzutu na jednostkowy wektor .

Dalej będziemy zakładać, że wektory są ortonoramalne, tj. . Wtedy mamy

; w szczególności . (4.22)

Te równania mają prosta interpretację geometryczną: dwa kolejne po siebie rzuty dają zero, gdy one rzutują na różne ortogonalne podprzestrzeni; gdy one rzutują na tą samą podprzestrzeń drugi rzut nic nie daje. Z równości natychmiast znajdujemy, że możliwymi wartościami własnymi rzutnika są równe tylko zeru albo jedynce. Rzutnik na podprzestrzeń rozpiętą na i jest wprost . Ten rzutnik też ma własność . Jeżeli obejmuje „wszystkie kierunki” przestrzeni Hilberta, otrzymujemy relację kompletności



. (4.23)

Teraz reprezentacja spektralna może być określona jako



. (4.24)

Stany tutaj są stany własne operatora , a są jego wartości własne. To oznacza fizycznie, że dowolny stan najpierw rozkłada się na składowe wzdłuż stanów własnych operatora , a zatem każda z tych składowych jest rozważana zgodnie z jej własnościami stanów własnych (4.19). Zwróćmy uwagę, że reprezentacja spektralna jest możliwa nie tylko dla obserwabli (4.18), ale dla dużej klasy normalnych operatorów , dla których .







©snauka.pl 2016
wyślij wiadomość