Czym się zajmujemy?
Informatyka Kwantowa jest to dziedzina Informatyki zajmująca się informacją i jej przetwarzaniem z wykorzystaniem zjawisk kwantowych. Zajmuje się ona m.in.:
badaniem zjawisk kwantowych pod kątem możliwości ich wykorzystania do obliczeń, a w szczególności do budowy kubitów i bramek kwantowych
tworzeniem algorytmów wykorzystujących zjawiska kwantowe,
budowaniem i doskonaleniem urządzeń umożliwiających ich implementację,
praktycznymi zastosowaniami informatyki kwantowej np. w przetwarzaniu obrazów, systemach zabezpieczeń czy komunikacji
Kubit czyli kwantowy bit, jest podstawową jednostką informacji kwantowej. Najłatwiej go będzie zdefiniować poprzez pokazanie różnic między nim a klasycznym bitem.
Najpierw jednak zauważmy, że proces przetwarzania danych, niezależnie czy klasyczny, czy kwantowy, składa się z czterech faz: (1) inicjalizacji, (2) fazy obliczeń, którą nazwijmy ewolucją całego układu, (3) fazy pomiaru oraz (4) interpretacji wyników. Tę ostatnią na razie pomińmy.
W fazie inicjalizacji oraz pomiaru kubit ma podobne właściwości do bitu - oba mogą przyjmować dwie wartości, interpretowane jako 0 lub jedynka, w przypadku kubitu zapisywane nieco dziwnie, w tzw. notacji Diraca: |0> oraz |1>.
Jednak w fazie ewolucji (obliczeń) odróżnia się on znacznie od bitu:
(1) przyjmuje wartości będące "mieszaniną" |0> i |1>, co zapisujemy: |q>=a|0> + b|1> takie że a,b są liczbami zespolonymi,
(2) nie można odczytać tego stanu,
(3) aa*+bb*=1,
(4) aa*, bb* są rzeczywiste oraz
(5) w momencie pomiaru (odczytania wyniku), kubit przyjmie jedną z wartości: |0> z prawdopodobieństwem bb* albo |1> - z prawd. aa*
Kubit może być reprezentowany przez zapis w postaci kombinacji liniowej, tak jak zapisano powyżej: |q>=a|0> + b|1>, za pomocą wektora stanu |q>=[a,b]^T (czyli wektora kolumnowego), albo za pomocą macierzy gęstości (możesz o niej poczytać np. tutaj). W zapisie wektorowym |0>=[1,0]^T, |1>=[0,1]^T
Podsumowując, kubit w odróżnieniu od bitu, jest obiektem losowym, w którym najczęściej można określić tylko prawdopodobieństwa tego że reprezentuje zero albo jeden. Sterowanie tym prawdopodobieństwem jest, najogólniej pisząc, tożsame z programowaniem kwantowym.
Bramka kwantowa jest narzędziem do sterowania współczynnikami pojedynczego kubitu jak i ich większej liczby. Można je utożsamiać z kwantową wersją funkcji logicznej, która na podstawie wejścia oblicza prawdopodobieństwa uzyskania różnych wyników. W przypadku pojedynczego bita nie mamy zbyt wielkiego wyboru bramek - możemy albo jego wartość pozostawić taką samą, albo zmienić jego wartość na przeciwną (0->1 a 1->0). Zatem w przypadku bitu istnieją dwie bramki: id (identyczność) oraz NOT.
Zupełnie inaczej jest w przypadku kubitu. Nawet z jednego możemy wygenerować nieskończenie wiele (ba - continuum!) rozkładów prawdopodobieństwa, bo jest ono określane przez liczbę aa*. Zatem bramek kwantowych jedno kubitowych jest również nieskończenie wiele (continuum).
Bramki są, m.in. reprezentowane przez macierze. Ponieważ qubit ma dwa wymiary (bo są dwie wartości, które możemy zmierzyć), to bramka jest macierzą 2x2.
Przykład. Weźmy pod uwagę kubit, który inicjalizujemy tak by był równy zero, czyli będzie równy: |q>=1|0>+0|1>.
W procesie ewolucji będziemy na niego działali kolejno bramkami: H (Hadamarda) (1/sqrt(2))[1,1 ; 1,-1], P[x] (przesunięcia fazowego) [1,0; 0, exp(i*x)] i znów Hadamarda, to otrzymamy:
|0> --- H --> (|0>+|1>)/sqrt(2) -- P[x] ---> (|0>+exp(i*x)|1>)/sqrt(2) --- H ---> [(1+exp(i*x))|0>+(1-exp(i*x)|1>]/2.
Do sprawdzenia, że tak rzeczywiście jest, wystarczy że wykonasz mnożenia macierzy przez wektory, np H|0>= [1,1 ; 1,-1]*[1,0]/sqrt(2).
Teraz możemy dokonać pomiaru. Za każdym razem wyjdzie nam inny wynik - raz zero a raz jedynka, ale z częstotliwością zależną od rozkładu prawdopodobieństwa. I tak prawdopodobieństwo, że otrzymamy |0> wynosi: (1+exp(i*x))/2 * (1+exp(i*x))/2*=(1+exp(i*x))(1+exp(-i*x))/4=(1+exp(i*x)+exp(-i*x)+1)/4=(1+cos(x))/2. Komplementarnie, prawd. uzyskania |1> jest równe (1-cos(x))/2
Podsumowując, działając na pojedynczy kubit zainicjalizowany na |0> zestawem bramek HP[x]H zakodowaliśmy na jednym kubicie funkcję f(x)=(1+cos(x))/2, której wartości możemy zrekonstruować, wykonując wiele razy ten sam układ dla ustalonej wartości x. Dla innej wartości x musimy wykonać taki eksperyment jeszcze raz. Zestaw bramek HP[x]H to nic innego jak program kwantowy.
Stan złożony z wielu kubitów jest reprezentowany przez tzw. iloczyn tensorowy. Mając dane dwa qubity |q>=[a, b]^T oraz |q>=[c,d]^T ich iloczyn tensorowy jest równy |pq>=[ac, ad, bc, bd]^T=ac|00>+ad|01>+bc|10>+bd|11>. Przykładowo:
- |00>=[1, 0,0,0]^T
- |01>=[0, 1,0,0]^T
- |10>=[0, 0,1,0]^T
- |11>=[0, 0,0,1]^T
- |q>=(|0>-|1>)/sqrt(2), to:
- |q0>=(|00>-|10>)/sqrt(2)
- |q1>=(|01>-|11>)/sqrt(2)
Bramki kwantowe dla systemu wielu kubitów mogą być zbudowane również przez iloczyn tensorowy, zastosowany do macierzy, np. iloczyn tensorowy bramki Hadamarda i identyczności to: H⊗id=[1,0, 1, 0; 0,1,0,1; 1,0, -1, 0; 0,1,0,-1].
Na koniec warto zaznaczyć, że wraz ze wzrostem liczby kubitów liczba współrzędnych wektora stanu rośnie wykładniczo, jest równa 2^N, gdzie N to liczba kubitów.
Powyżej przedstawiliśmy metodę obliczeń nazywaną kwantowym próbkowaniem (ang. quantum sampling). Algorytmy kwantowe, które wymagają tej procedury nazywa się niedeterministycznymi, gdyż każde wykonanie takiego algorytmu, dla tych samych danych, może zwracać inny wynik. Zwróćmy uwagę, że w przypadku algorytmów klasycznych, takie algorytmy, co do zasady, uważa się za błędne! Dopiero wielokrotne jego wykonanie generuje rozkład prawdopodobieństwa, który może być interpretowany w kontekście problemu, który jest nim modelowany.
Jednak historycznie pierwszymi algorytmami kwantowymi, były algorytmy deterministyczne, czyli takie które po jednokrotnym wykonaniu zwracają (prawie zawsze) jeden wynik. to "prawie zawsze" oznacza bardzo wysokie prawdopodobieństwo uzyskania prawidłowego wyniku. W niektórych przypadkach to prawd. jest równe 1 - np. Algorytm Deutsch - Jozsa, w innych jest bliskie 1, np. 1-1/sqrt(2^N), gdzie N oznacza liczbę kubitów w systemie dla algorytmu Grovera, wzmacniania amplitudy. Oznacza to, że dla dwóch kubitów nasz algorytm pomyli się 1 raz na 4 ale już dla 20 kubitów tylko 1 raz na milion.
Jest też trzeci typ algorytmów kwantowych, które nie manifestują wyników wprost, w procesie pomiaru. Są one używane tylko do zmiany stanu systemu kwantowego, jako elementy większego potoku przetwarzania, tak jak pojedyncze funkcje w programowaniu klasycznym. Są to np. Kwantowa Transformata Fouriera (QFT, ang. quantum Fourier Transform), służąca do zmiany bazy obliczeniowej, czy HHL - do rozwiązania układu równań liniowych.
Superpozycja potocznie (np. na bazie kota Schroedingera), jest rozumiana jako "bycie jednocześnie w kilku stanach" - np. kot Schroedingera jest jednocześnie "żywy i martwy", elektron znajduje się w kilku miejscach jednocześnie. Jest to jednak spojrzenie bardzo dziwne - nie intuicyjne. Na dodatek może ono przeszkadzać w zrozumieniu jak działa komputer kwantowy. Dlatego najpierw podamy matematyczną definicję, następnie wyjaśnimy jakie ma to zastosowanie w obliczeniach kwantowych a na koniec podamy inną, może bardziej przydatną intuicję.
Matematycznie, każdy kubit (stan kwantowy) jest w stanie superpozycji, jeśli nie jest w stanie bazowym, czyli |q>!=|0> i |q>!=|1>. Skoro kubit |q>=a|0>+b|1> i a, b !=0. Zatem jeśli mamy dany qubit w stanie bazowym |0> działając na niego bramką Hadamarda sprawiamy, że wpada on w stan superpozycji (|0>+|1>)/sqrt(2). Podobnie stan dwu-kubitowy: (|00>-|10>)/sqrt(2) jest superpozycją dwóch stanów bazowych |00> i |10>.
W obliczeniach kwantowych superpozycja tworzy tyle ścieżek obliczeniowych, ile mamy współrzędnych wektora opisującego stan takiego systemu. Szczególną pozycję zajmuje tzw. jednorodna superpozycja, którą można zbudować w następujący sposób. Najpierw dla każdego z naszych N kubitów, tworzymy superpozycję za pomocą bramki Hadamarda, a następnie wykonujemy na nich operację iloczynu tensorowego. Efektem takiej procedury jest stan o długości 2^N: [1,1,...,1]^T/sqrt(2^N). Stan taki jest punktem wyjścia dla wielu algorytmów kwantowych, choćby wspomniane wyżej: algorytm Grovera, czy algorytm wzmacniania fazy.
Zauważmy, że superpozycja tworzy 2^N ścieżek obliczeniowych. Dzięki temu można uzyskać ich liczbę fizycznie niemożliwą do osiągnięcia dla komputerów klasycznych. Jest tak dlatego, że posiadając 266 kubitów można stworzyć 118 quinvigintilionów ;), czyli 1,18e80, co oznacza że będzie ich 1,18 razy tyle co atomów we wszechświecie.
Na koniec - nieco inna intuicja superpozycji. Po pierwsze, trzeba zauważyć, że patrząc okiem fizyka (czy też informatyka), nie jesteśmy w stanie stwierdzić, czy pomiędzy inicjalizacją a pomiarem nasz umowny kot jest w stanie jednoczesnego życia i śmierci. Jest tak dlatego, że jakakolwiek próba sprawdzenia tego faktu, oznacza konieczność dokonania pomiaru, a więc kot będzie w którymś ze stanów bazowych z odpowiednim prawdopodobieństwem. Zatem to wszystko co dzieje się z kotem po zamknięciu pudełka, nie jest fizycznie weryfikowalne i jest przedmiotem interpretacji a nie eksperymentalnej wiedzy. Dlatego Feynman mówił: "Shut up and compute". Zatem, z punktu widzenia informatyki kwantowej, matematyczne zasady, te które opisujemy, bardzo zgrubnie, na tej stronie, są jedynie modelem a nie opisem rzeczywistości. Model ten pozostanie modelem zawsze, w kontekście nauki kwantowej, bo taki obraz świata wynika z samej natury teorii kwantowej a nie z naszej niewiedzy. Dowodem na to jest m.in. twierdzenie Bella.
Interferencja jest to zjawisko nakładania się na siebie fal o różnych epicentrach. Powoduje to, że w niektórych miejscach fale się wzajemnie wzmacniają a w innych wygaszają. Można to zaobserwować np. wrzucając dwa kamienie do wody.
No dobrze, ale jakie to ma powiązanie z kubitami, bramkami, itp.? Otóż powiązanie to jest umocowane w fakcie, że za każdym stanem kwantowym, np. kubitem |q> stoi pewna funkcja falowa, czyli element przestrzeni Hilberta. Na ten moment powiedzmy tylko, że mają one postać sum funkcji eksponencjalnych w przestrzeni zespolonej, czyli funkcji exp(i*x) /uwaga: bardzo zgrubne wyjaśnienie/. Funkcję taką można przedstawić jako cos(x)-i*sin(x), zatem w postaci fali. Stąd bierze się interferencja w systemach kwantowych.
Czy interferencja przejawia się jakoś w wyglądzie wektora stanu? Tak. Weźmy pod uwagę jednorodną superpozycję dwóch kubitów |s>=[1,1,1,1]^T (pomińmy końcówkę /2, czyli tzw. normalizację; można ją dodać na koniec, a jej pozbycie się rozjaśni obliczenia). Weźmy też qubit |q>=[a,b]^T. Teraz możemy policzyć |sq>=[a,b,a,b,a,b,a,b]^T. Oczywiście, gdyby |s> było dłuższe, to liczba par również byłaby większa. To rozprzestrzenienie współrzędnych |q> na cały stan jest rozpoznawane jako interferencja.
Interferencja ma dwie twarze w odniesieniu do obliczeń kwantowych. Jedną dobrą - pozwala za pomocą prostej operacji przenieść wartość, dajmy na to "a" do połowy współrzędnych wektora stanu. Zauważmy, że w przypadku klasycznym musielibyśmy wykonać 2^(N1) iteracji pętli, by osiągnąć ten efekt. W takim przypadku mówimy o tzw. interferencji chcianej (ang. wanted interference). Z drugiej strony dzieje się to jednak zawsze - nie możemy wykonać iloczynu tensorowego "do połowy", czyli np. z połową kubitów. Umieszczenie N kubitów w systemie obliczeniowym powoduje zawsze powstanie iloczynu tensorowego z nich wszystkich. W wielu przypadkach, może to niszczyć nasze obliczenia, dlatego taki przypadek nazywamy interferencją niechcianą. Ze zjawiskiem tym możemy sobie poradzić wykorzystując technikę dekomputacji (ang. uncomputation) polegającej na wykorzystaniu tzw. bramek kontrolowanych. Bramki te tworzą splątanie, dlatego teraz zapraszamy do przeczytania następnej zakładki 😉
Splątanie wynika z głębszej analizy doświadczenia myślowego Schroedingera. Zauważmy bowiem, że w pudełku jest nie tylko kot, ale: licznik Geigera, który przy detekcji uwalnia porcję trucizny i atom pierwiastka promieniotwórczego. Po upływie okresu połowicznego rozpadu atom albo się rozpadnie, albo nie (z prawdopodobieństwem 1/2). Jeśli atom się rozpadnie, licznik stwierdzi obecność cząstki promieniowania, uwolni truciznę a kot umrze. W przeciwnym przypadku nic takiego się nie stanie a kot będzie żył. Zatem po otwarciu pudełka nie musimy sprawdzać, czy żyje kot - możemy sprawdzić stan licznika Geigera, albo czy w pudełku jest atom, czy produkty jego rozpadu. Właśnie taką zależność nazywamy splątaniem.
Matematycznie, w kontekście informatyki kwantowej, splatanie jest efektem działania operatora wielo kubitowego, który nie jest rozkładalny w sensie iloczynu tensorowego.
