Transcript
Obwody kwantowe Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej 2008/2009 Obwody kwantowe Bramki kwantowe 1 Algorytmy kwantowe 2 3 4 Algorytmy kwantowe W chwili obecnej znamy dwie obszerne klasy algorytmów kwantowych, które wymagają mniejszych zasobów dla rozwiązania, niż ich odpowiedniki dla komputerów klasycznych: kwantowe przekształcenie Fouriera w tym algorytmy dla problemów rozkładu i dyskretnego logarytmu, dające wykładnicze przyspieszenie w stosunku do najlepszych znanych algorytmów klasycznych; kwantowe przeszukiwanie dające przyśpieszenie kwadratowe w stosunku do najlepszych algorytmów klasycznych. Znajdowanie dobrych algorytmów kwantowych jest dodatkowo obarczone wymaganiem, aby były one lepsze niż najlepsze znane algorytmy klasyczne! Algorytmy kwantowe Statystyka średnia, mediana, min Przeszukiwanie kwantowe Przyspieszenie dla problemów z NP Przekszt. Ukryta Fouriera podgrupa Kwantowe zliczanie Dyskr. log Wyzn. rzędu Poszukiwanie kluczy krypt. Rozkład Łamanie kryptosystemów Rysunek: Najważniejsze algorytmy kwantowe i relacje między nimi Pojedynczy qubit jest wektorem ψ = a 0 + b 1 sparametryzowanym przez dwie liczby zespolone spełniające a 2 + b 2 = 1. muszą zachowywać tę normę, zatem są macierzami 2 2. Najważniejsze z nich to macierze Pauliego: X ( ) 0 1 ; Y 1 0 ( ) ( ) 0 i 1 0 ; Z. (1) i Inne trzy ważne bramki kwantowe to bramka Hadamarda (H ), bramka fazowa (S) i bramka π/8 (T): H = 1 ( ) 1 1 ; S = ( ) ( ) ; T = 0 i 0 e iπ/4. (2) Warto pamiętać, że H = (X + Z)/ 2 i S = T 2. Bramka T nosi swoją nazwę dlatego, że z dokładnością do nieistotnego czynnika fazowego ma e ±iπ/8 na przekątnej: ( ) T = e iπ/8 e iπ/8 0 0 e iπ/8. (3) Pojedynczy qubit w stanie a 0 + b 1 można przedstawić jako punkt (θ, φ) na sferze jednostkowej, gdzie a = cos(θ/2), b = e iφ sin(θ/2). Przedstawienie to nazywamy reprezentacją Blocha, a wektor (cos φ sin θ, sin φ sin θ, cos θ) wektorem Blocha. Obroty Algorytmy kwantowe Macierze Pauliego pozwalają zdefiniować użyteczną klasę macierzy unitarnych, operatory obrotu wokół osi ˆx, ŷ i ẑ: R x (θ) e iθx/2 = cos θ 2 I i sin θ ( ) cos θ 2 X = 2 i sin θ 2 i sin θ 2 cos θ, 2 (4) R y (θ) e iθy /2 = cos θ 2 I i sin θ ( ) cos θ 2 Y = 2 sin θ 2 sin θ 2 cos θ, (5) 2 R z (θ) e iθz/2 = cos θ 2 I i sin θ ( ) e 2 Z = iθ/2 0 0 e iθ/2. (6) Obroty Algorytmy kwantowe Jeżeli ˆn = (n x, n y, n z ) jest rzeczywistym wektorem jednostkowym w trzech wymiarach, to uogólniamy poprzednie definicje do obrotu o θ wokół osi ˆn: ( ) iθˆn σ Rˆn (θ) exp 2 = cos ( θ 2) I i sin ( θ 2) (n x X + n y Y + n z Z), (7) gdzie σ oznacza wektor (X, Y, Z) utworzony z macierzy Pauliego. Rozkład Z-Y Twierdzenie (Rozkład Z-Y pojedynczego qubitu) Jeżeli U jest unitarną operacją na pojedynczym qubicie, to istnieją takie liczby rzeczywiste α, β, γ i δ, że Dowód. U = e iα R z (β)r y (γ)r z (δ). (8) Ponieważ U jest unitarna, to jej wiersze i kolumny są ortonormalne, skąd wynika, że istnieją liczby rzeczywiste α, β, γ i δ takie, że ) U = ( e i(α β/2 δ/2) cos γ 2 e i(α β/2+δ/2) sin γ 2 e i(α+β/2 δ/2) sin γ 2 e i(α+β/2+δ/2) cos γ 2 Równanie (8) wynika teraz bezpośrednio z definicji obrotów i mnożenia macierzy.. (9) Rozkład Z-Y Wniosek Jeżeli U jest unitarną bramką na jednym qubicie, to istnieją operatory unitarne A, B, C na jednym qubicie takie, że ABC = I oraz U = e iα AXBXC, gdzie α jest pewną globalną fazą. Dowód. W oznaczeniach z poprzedzającego twierdzenia, bierzemy A R z(β)r y( γ ), 2 B R y( γ δ+β δ β )Rz( ), C Rz( ). Wtedy ABC = R z(β)r y( γ 2 )Ry( γ 2 Ponieważ X 2 = I, to XBX = XR y( γ 2 (z XYX = Y wynika XR y(θ)x = R y( θ) itp.). Zatem AXBXC = R z(β)r y( γ 2 )Ry( γ 2 Czyli U = e iα AXBXC i ABC = I. )Rz( δ+β 2 δ+β δ β )Rz( )Rz( ) = I. (10) 2 2 )XXRz( δ+β 2 )X = Ry( γ 2 )Rz( δ+β 2 ), δ β )Rz( ) = Rz(β)Ry(γ)Rz(δ). (11) 2 Hadamard Pauli-X Pauli-Y Pauli-Z Faza Z S π/8 T H X Y ( ) ( 1 1 ) 0 1 ( 1 0 ) 0 i i 0 ( ) 1 0 ( 0 1) 1 0 ( 0 i ) e iπ/4 Rysunek: Nazwy, symbole i macierze unitarne dla popularnych bramek jednoqubitowych mają formę: jeżeli zachodzi A, to zrób B, i są jednymi z najdogodniejszych operacji obliczeniowych. Bramka cnot (kontrolowane-not), ma dwa qubity: qubit kontrolny i qubit celu. Działanie bramki cnot jest dane przez c t c c t i można je przedstawić przez macierz unitarną (12) Rysunek: Obwód reprezentujący bramkę cnot Ogólnie, jeżeli U jest dowolną jednoqubitową operacją unitarną, to kontrolowane U jest operacją dwuqubitową z qubitem kontrolnym i qubitem celu o działaniu c t c U c t. U Rysunek: Obwód reprezentujący bramkę kontrolowane U Naszym celem będzie implementacja kontrolowanego U dla dowolnej operacji jednoqubitowej U przy pomocy jedynie operacji jednoqubitowych i bramki cnot. Wykorzystamy w tym celu rozkład U = e iα AXBXC. Kontrolowane przesunięcie fazy Chcemy zastosować przesunięcie fazy exp(iα) na qubicie celu, kontrolowane przez qubit kontrolny. ( ) = e iα 0 0 e iα ( 1 0 ) 0 e iα Rysunek: Kontrolowane przesunięcie fazy Działanie obwodu: 00 00, 01 01, 10 e iα 10, 11 e iα 11. (13) Z ostatniego wniosku U = e iα AXBXC, gdzie ABC = I. = U ( 1 0 ) 0 e iα C B A Rysunek: Implementacja operacji kontrolowane U na pojedynczym qubicie Jeżeli qubit kontrolny jest ustawiony, to na qubicie celu jest wykonywana operacja e iα AXBXC = U ; jeżeli qubit kontrolny nie jest ustawiony, to na qubicie celu wykonywana jest operacja ABC = I. Operacje z wieloma qubitami kontrolnymi Przypuśćmy, że mamy n + k qubitów i że U jest operatorem unitarnym na k qubitach. Definiujemy operację kontrolowaną C n (U ) poprzez C n (U ) x 1 x 2... x n ψ = x 1 x 2... x n U x 1x 2 x n ψ, (14) x 1 x 2 x n w wykładniku przy U oznacza iloczyn bitów x 1, x 2,..., x n ; tzn. operator U stosujemy do ostatnich k qubitów, jeżeli pierwszych n są wszystkie równe jeden, w przeciwnym razie nie robimy nic. Operacje z wieloma qubitami kontrolnymi U Rysunek: Przykładowy obwód reprezentujący operację C n (U ) dla n = 4, k = 3 Kwantowa bramka Toffoliego Niech U będzie operatorem na pojedynczym qubicie, a V operatorem unitarnym takim, że V 2 = U. Wówczas operację C 2 (U ) można przedstawić przy pomocy obwodu: U = V V V Rysunek: Obwód dla bramki C 2 (U ) Bramka Toffoliego jest szczególnym przypadkiem takiej bramki, w tym przypadku C 2 (X); wówczas V (1 i)(i + ix)/2. Kwantowa bramka Toffoliego = T T T S H T T T T H Rysunek: Implementacja bramki Toffoliego przy pomocy bramek Hadamarda, fazy, cnot i π/8 = X X Rysunek: Operacja kontrolowana z bramką not wykonywaną na qubicie celu, gdy qubit kontrolny jest ustawiony na zero Rysunek: Operacja kontrolowana z wieloma bitami celu Algorytmy kwantowe Końcowym elementem obwodu kwantowego, najczęściej niejawnym, jest pomiar. ψ Rysunek: Symbol pomiaru rzutowego Mamy dwie ważne zasady dotyczące pomiaru, warte zapamiętania przy analizie obwodów kwantowych. Zasada odroczonego pomiaru Zasada odroczonego pomiaru W obwodzie kwantowym pomiar zawsze może być przeniesiony z etapu pośredniego na koniec obwodu; jeżeli wyniki pomiaru są używane na jakimkolwiek etapie obwodu, to klasycznie kontrolowane operacje mogą być zastąpione warunkowymi operacjami kwantowymi. Zasada odroczonego pomiaru Przykład ψ H β 00 X Z ψ Rysunek: Obwód teleportacji kwantowej z pomiarami przeniesionymi na koniec; górne dwa qubity należą do Alicji, dolny do Bolka Zasada niejawnego pomiaru Zasada niejawnego pomiaru Bez straty ogólności, można założyć, że każdy niezakończony przewód kwantowy (qubit, który nie został zmierzony) został na końcu obwodu kwantowego zmierzony. Wyobraźmy sobie, że mamy obwód kwantowy zawierający dwa qubity, i że na końcu obwodu został zmierzony tylko pierwszy qubit. Statystyki pomiarowe są więc całkowicie określone przez zredukowaną macierz gęstości pierwszego qubitu. Jednakże, jeżeli zostałby przeprowadzony także pomiar drugiego qubitu, to nie zmieni on statystyk pomiarowych pierwszego qubitu.
