Komputery kwantowe

Na niniejszej stronie krótko zaprezentowałem podstawowe pojęcia z zakresu informatyki kwantowej, na których opierają się zasady działania przyszłych komputerów kwantowych. Szczegółowy opis większości z tych zagadnień można znaleźć w mojej pracy magisterskiej „Wykorzystanie metod ewolucyjnych sztucznej inteligencji w projektowaniu algorytmów kwantowych”, której początkowe rozdziały mają charakter monografii tego obszaru, oraz w niektórych moich bieżących publikacjach.

Informatyka kwantowa[11] jest dziedziną nauki z pogranicza informatyki teoretycznej i mechaniki kwantowej, zajmującą się wykorzystaniem unikalnych własności miniaturowych układów podlegających prawom mechaniki kwantowej. Od pewnego czasu stało się jasne, iż istnieje klasa problemów, które mogą być rozwiązywane w sposób znacznie bardziej efektywny, dzięki wykorzystaniu możliwości obliczeniowych takich miniaturowych układów. Poprzez zastosowanie unikalnych efektów mechaniki kwantowej (takich jak np. interferencja funkcji falowych, kwantowy paralelizm, superpozycja stanów, kwantowe splątanie i koherencja) niektóre problemy obliczeniowe mogłyby być rozwiązywane w sposób niezwykle efektywny, bardziej efektywny niż będzie to kiedykolwiek możliwe za pomocą jakiejkolwiek klasycznej maszyny obliczeniowej. Przykładowe zadania należące do tej klasy to faktoryzacja liczb[15] oraz przeszukiwanie nieposortowanego zbioru[7]. Oprócz zadań algorytmicznych rozpatruje się także możliwość wykorzystania układów, podlegających prawom mechaniki kwantowej, m.in. w teorii informacji (protokół teleportacji kwantowej[1,2,3], kodowanie supergęste[11]), w teorii gier oraz w sztucznej inteligencji[5,6,17]. Według niektórych hipotez (postawionych m.in. przez Rogera Penrose’a[12,13] i Stuarta Hameroff’a[8,9]), zjawiska kwantowe mogą być niezbędne do wyjaśnienia tajemnic niealgorytmicznego działania ludzkiego umysłu, ludzkiej świadomości, wyobraźni i inteligencji. Z drugiej strony sztuczna inteligencja dostarcza narzędzi pozwalających na automatyczne projektowanie elementów obliczeń kwantowych[5,6], które ze względu na swoją naturę są nieintuicyjne i trudne do uchwycenia przez ludzki umysł. Informatyka kwantowa oraz sztuczna inteligencja wzajemnie się zatem inspirują oraz wzbogacają.

Podstawowymi jednostkami informacji w informatyce kwantowej są kubity oraz rejestry kwantowe. Kubit (ang. qubit) to znormalizowany wektor w dwuwymiarowej, zespolonej przestrzeni Hilberta stanów dwupoziomowego układu kwantowego. Współrzędne takiego wektora określają prawdopodobieństwo otrzymania jednego ze stanów bazowych po wykonaniu obserwacji stanu kubitu. Kubit |\Phi\rangle pozwala zatem przechowywać superpozycję dwóch stanów bazowych oznaczanych jako |0\rangle i |1\rangle:

|\Phi\rangle = \alpha |0\rangle + \beta |1\rangle

gdzie \alpha, \beta \in \mathbb{C} oraz |\alpha|^2+|\beta|^2=1. Liczby \alpha i \beta nazywa się amplitudami prawdopodobieństwa, a prawdopodobieństwo odczytu stanów bazowych z kubitu to odpowiednio |\alpha|^2 i |\beta|^2. Wektory |0\rangle i |1\rangle tworzą bazę standardową dwuwymiarowej, zespolonej przestrzeni stanów kubitu. Korzystając z notacji Diraca, stan kubitu można także zapisać jako wektor kolumnowy |\Psi\rangle = \left[\alpha \atop \beta\right]. Geometryczna ilustracja przykładowego stanu kubitu została przedstawiona na Rysunku 1 (po lewej stronie).

Rys. 1. Geometryczna reprezentacja kubitu oraz trzykubitowego rejestru kwantowego

Układ wielu kubitów tworzy rejestr kwantowy (ang. quantum registers), który — zgodnie z jednym z podstawowych postulatów mechaniki kwantowej — może być rozpatrywany jako układ izolowany złożony z wielu układów składowych (poszczególne kubity należące do rejestru). Przestrzenią stanów takiego rejestru jest przestrzeń, będąca iloczynem tensorowym przestrzeni stanów poszczególnych kubitów. Stan n-kubitowego rejestru kwantowego |\Psi\rangle jest zatem opisywany jako wektor znormalizowany w 2n-wymiarowej, zespolonej przestrzeni Hilberta. Pozwala to zapisać superpozycję 2n różnych stanów bazowych |0\rangle \ldots |2^n - 1\rangle:

|\Psi\rangle = \sum_{i=0}^{2^n-1} \omega_i|i\rangle

gdzie \omega_i \in \mathbb{C} jest amplitudą prawdopodobieństwa odczytu i-tego stanu bazowego podczas obserwacji stanu rejestru kwantowego. Prawdopodobieństwo odczytu stanu bazowego |i\rangle wynosi |\omega_i|^2 i oczywiście |\omega_0|^2 + |\omega_1|^2 + \ldots + |\omega_{2^n-1}|^2=1. Geometryczna reprezentacja stanu przykładowego trzykubitowego rejestru kwantowego została przedstawiona na Rysunku 1 (po prawej stronie). Jedną ze szczególnych własności informatyki kwantowej jest fakt, iż wraz z liniowym wzrostem liczby kubitów w rejestrze kwantowym, rośnie w tempie wykładniczym wymiar przestrzeni stanów takiego rejestru.

Kwantowe bramki logiczne i obwody kwantowe

Jednym z formalnych modeli obliczeń kwantowych, pozwalającym zapisać dowolny algorytm kwantowy, są układy kwantowych bramek logicznych czyli tzw. obwody kwantowe (ang. quantum circuits). Równoważnym, ale zazwyczaj znacznie mniej użytecznym, formalnym modelem obliczeń kwantowych jest np. Kwantowa Maszyna Turinga. Kwantowa bramka logiczna (ang. quantum gate), działająca na n-kubitowym rejestrze, to dowolne odwzorowanie  2n-wymiarowej przestrzeni Hilberta nad ciałem liczb zespolonych w taką samą 2n -wymiarową przestrzeń, opisywane za pomocą macierzy unitarnej o elementach zespolonych i wymiarze 2^n \times 2^n. Podstawowe bramki kwantowe to m.in. bramka negacji (NOT) i sterowanej negacji (CNot), bramka obrotu amplitudy prawdopodobieństwa, bramka Hadamarda (H), bramka o macierzy jednostkowej. Macierze unitarne, opisujące te bramki kwantowe, to odpowiednio:

Przykładowe schematy dwóch układów kwantowych bramek logicznych zostały przedstawione na Rysunku 2.

Rys. 2. Przykładowe obwody kwantowe

Z punktu widzenia programowania obiektowego podstawowe pojęcia informatyki kwantowej i relacje między nimi można przedstawić na diagramie w języku UML (Rysunek 3). Diagram ten przedstawia zaproponowany przeze mnie model obiektowy dla obliczeń kwantowych, w oparciu o który można tworzyć symulatory komputerów kwantowych takie jak moja biblioteka qclib.

Rys. 3. Diagram klas UML systemu obliczeń kwantowych

Algorytmy kwantowe

Jak dotąd odkryto jedynie kilka algorytmów kwantowych, mogących mieć praktyczne zastosowanie. Najpopularniejsze z nich to:

  1. Algorytm Grovera[7] — przeszukiwanie nieuporządkowanego zbioru ze złożonością O(\sqrt{N}), podczas gdy dowolny klasyczny algorytm dla tego problemu wymaga złożoności obliczeniowej O(N).
  2. Algorytm Shora[15] — pozwalający na faktoryzację liczb ze złożonością obliczeniową mniejszą niż wykładnicza, O(log^3 N). Jak dotąd nie został odkryty jakikolwiek klasyczny algorytm o takiej złożoności i przypuszcza się, że taki algorytm nie istnieje.
  3. Protokół teleportacji kwantowej[3] — pozwala na przesłanie dokładnego stanu kubitu za pomocą jedynie dwóch bitów informacji oraz kwantowego kanału komunikacji (czyli rozdzielonej w przestrzeni pary kubitów w stanie splątanym). Protokół teleportacji kwantowej wykorzystuje unikalne własności kwantowych stanów splątanych w konfiguracji EPR[4] (zobacz także: paradoks Einsteina-Podolskiego-Rosena).
  4. Kodowanie supergęste[11] — Kodowanie supergęste pozwala na przesłanie dwóch klasycznych bitów w pojedynczej jednostce informacji kwantowej, czyli za pomocą pojedynczego kubitu. Jest to zatem działanie komplementarne w stosunku do protokołu teleportacji kwantowej.

Tworzenie algorytmów kwantowych jest zadaniem trudnym z kilku względów. Istnieje bardzo słaba analogia do algorytmów klasycznych z powodu wykorzystania nieintuicyjnych efektów mechaniki kwantowej, takich jak superpozycja stanów, interferencja amplitud prawdopodobieństwa (będących liczbami zespolonymi), kwantowe splątanie i paralelizm. Algorytmy kwantowe to algorytmy probabilistyczne, czyli oparte na rozkładzie prawdopodobieństwa i jego ewolucji w czasie. Podstawowym klasom złożoności, jak P, NP, BPP odpowiadają w przypadku obliczeń kwantowych klasy złożoności: EQP, NQP oraz BQP. Elementy algorytmów kwantowych mogą być projektowane częściowo automatycznie za pomocą nowoczesnych metod sztucznej inteligencji. Kwantowe bramki logiczne, reprezentowane za pomocą zespolonych macierzy unitarnych, mogą być efektywnie optymalizowane za pomocą algorytmów ewolucyjnych[5,6], a projektowanie pełnych obwody kwantowe może być wspomagane przez techniki programowania genetycznego[14,17].

Budowa rzeczywistego komputera kwantowego

Rys 4. Spektroskopia Magnetycznego Rezonansu Jądrowego

Stworzenie pełnego, funkcjonalnego komputera kwantowego jest wciąż dalekie od realizacji, mimo że istnieje obecnie wiele ścieżek, dających nadzieję na zrealizowanie tego celu w przyszłości. Podstawową trudność stanowią obecnie problemy, pojawiające się wraz z przekraczaniem pewnej, aktualnie niewielkiej, liczby kubitów w rejestrze kwantowym. Do zbudowania komputera kwantowego niezbędny jest dowolny układ fizyczny, pozwalający utrzymywać „delikatny” stan koherencji kwantowej. Zjawiska fizyczne, oferujące taką własność to m.in.: magnetyczny rezonans jądrowy NMR[10,16] (ang. Nuclear Magnetic Resonance), stany energetyczne elektronów na powłokach elektronowych, polaryzacja światła, kropki kwantowe, pułapki jonowe, kondensat Bosego-Einsteina i wiele innych zjawisk. Dużo badań poświęcono jak dotąd zwłaszcza wykorzystaniu magnetycznego rezonansu jądrowego. Rysunek 4 przestawia spektrometr NMR, oraz cząsteczkę składającą się z atomów posiadających wewnętrzny moment magnetyczny czyli tzw. spin. Spiny magnetyczne tej cząsteczki mogą być traktowane jako wektory bazowe w przestrzeni stanów siedmiokubitowego rejestru kwantowego i mogą być one ustawiane za pomocą zewnętrznego pola elektromagnetycznego. Odczyt wyników jest realizowany poprzez badanie widma przy pomocy spektrometru.

Do tej pory nie udało się zbudować użytecznego, stabilnego i skalowalnego komputera kwantowego. Pomimo tego, informatyka kwantowa stanowi ciągłe wyzwanie i cenne źródło inspiracji dla współczesnej informatyki. Pracę komputera kwantowego można ponadto symulować, jednak takie symulacje są bardzo nieefektywne ze względu na wykładniczą złożoności obliczeniową oraz pamięciową. Tego rodzaju symulacje można wykonywać w środowisku do obliczeń numerycznych takich jak Matlab lub Python wraz z biblioteką Numerical Python. Na potrzeby mojej pracy magisterskiej stworzyłem symulator komputera kwantowego w języku Python i udostępniłem w postaci biblioteki qclib (quantum computing library).

Wszystkie powyższe zagadnienia zostały w sposób wyczerpujący zaprezentowane w mojej pracy magisterskiej „Zastosowanie metod ewolucyjnych w projektowaniu algorytmów kwantowych” i zainteresowane osoby serdecznie zapraszam do zapoznania się z jej treścią.

Bibliografia

  1. C. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W. Wootters. Teleporting an unknown quantum state via dual classical and EPR channels. Phys Rev Lett, pages 1895-1899, 1993.
  2. D. Bouwmeester, J. Pan, K. Mattle, M. Daniell, M. Eibl, H. Weinfurter, and Anton Zeilinger. Experimental quantum teleportation. Nature, 390:575-579, 1997.
  3. Gilles Brassard. Teleportation as a quantum computation, May 1996.
  4. A. Einstein, B. Podolsky, and N. Rosen. Can quantum mechanical description of physical reality be considered complete? Phys. Rev., 47(10):777-780, May 1935.
  5. J. Faber, R.N. Thess, and G. Giraldi. Learning linear operators by genetic algorithms, 2003.
  6. Gilson A. Giraldi, Renato Portugal, and Ricardo N. Thess. Genetic algorithms and quantum computation, Mar 2004.
  7. Lov K. Grover. A fast quantum mechanical algorithm for database search. In STOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219, New York, NY, USA, 1996. ACM Press.
  8. Stuart Hameroff, Consciousness, neurobiology and quantum mechanics, In: The Emerging Physics of Consciousness, (Ed.) Tuszynski, J. 2006
  9. Stuart Hameroff with Conrad Schneiker, Ultimate Computing: Biomolecular Consciousness and Nanotechnology, Elsevier-North Holland, 1987.
  10. M.A. Nielsen, E. Knill, and R. Laflamme. Complete quantum teleportation using nuclear magnetic resonance. NATURE: Nature, 396, 1998.
  11. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
  12. Roger Penrose, Shadows of the Mind. Oxford University Press, 1994
  13. Roger Penrose, The emperor’s new mind. Oxford, 1989.
  14. Ben I. P. Rubinstein. Evolving quantum circuits using genetic programming. In John R. Koza, editor, Genetic Algorithms and Genetic Programming at Stanford 2000, pages 325-334. Stanford Bookstore, Stanford, California, 94305-3079 USA, 2000.
  15. Peter W. Shor. Algorithms for quantum computation: Discrete log and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124-134. Institute of Electrical and Electronic Engineers Computer Society Press, 1994.
  16. Lieven M.K. Vandersypen, Costantino S. Yannoni, and Isaac L. Chuang. Liquid state nmr quantum computing, 2000.
  17. Taro Yabuki and Hitoshi Iba. Genetic algorithms for quantum circuit design – evolving a simpler teleportation circuit. In Darrell Whitley, editor, Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, pages 425-430, Las Vegas, Nevada, USA, 8 2000.