Algorytm Deutscha-Jozsy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm Deutscha–Jozsyalgorytm kwantowy utworzony przez Dawida Deutscha i Richarda Jozsę w 1992[1] poprawiany później przez Richarda Cleve, Artura Ekerta, Chiarę Macchiavello i Michele Mosca w 1998[2]. Sam algorytm nie ma dużej wartości praktycznej - jest to jeden z pierwszych przykładów algorytmu kwantowego, który jest wykładniczo szybszy od każdego możliwego deterministycznego, klasycznego algorytmu. Algorytm Deutscha-Jozsy jest również deterministyczny, to znaczy zawsze zwraca poprawną odpowiedź.

Sformułowanie problemu[edytuj | edytuj kod]

W problemie Deutscha-Jozsy mamy daną wyrocznię – komputer kwantowy reprezentowany przez czarną skrzynkę, który implementuje funkcję f:\{0,1\}^n\rightarrow \{0,1\}. Gwarantowane jest, że f jest funkcją stałą lub zbalansowaną[3] (zwraca 0 dla połowy dziedziny i 1 dla drugiej połowy). Zadanie polega na określeniu, korzystając z wyroczni, czy f stała, czy zbalansowana.

Klasyczny algorytm[edytuj | edytuj kod]

Konwencjonalny, deterministyczny algorytm rozwiązujący problem Deutscha-Jozsy wymaga w najgorszym przypadku 2^{n-1} + 1 ewaluacji funkcji f, gdzie n jest liczbą bitów/kubitów. Aby udowodnić, że f jest stała, potrzebne jest obliczenie funkcji w ponad połowie punktów i obserwacja, że otrzymana wyniki są identyczne (przy założeniu, że funkcja jest stała lub zbalansowana). W najlepszym przypadku, już pierwsze dwie sprawdzone wartości funkcji będą różne, co dowodzi, że f jest zbalansowana. Konwencjonalny algorytm randomizowany wymaga wykonania stałej liczby k ewaluacji funkcji, aby uzyskać poprawną odpowiedź z dużym prawdopodobieństwem (błąd z prawdopodobieństwem \epsilon \leq 1/2^{k-1}). Aby na pewno uzyskać poprawną odpowiedź (algorytm deterministyczny), wymagane jest wyznaczenie k=2^{n-1} + 1 wartości funkcji. Algorytm Deutscha-Jozsy zwraca zawsze poprawną odpowiedź już po jednej ewaluacji funkcji f.

Historia[edytuj | edytuj kod]

Algorytm Deutscha-Jozsy jest uogólnieniem wcześniejszej (1985) pracy Dawida Deutscha, która pokazuje rozwiązanie prostszego problemu.
Konkretnie, mamy daną binarną funkcję, której dziedziną jest 1 bit: f: \{0,1\} \rightarrow \{0,1\} i pytamy, czy f jest stała[4].

Algorytm proponowany początkowo przez Deutscha nie był właściwie deterministyczny. Algorytm dawał poprawną odpowiedź z 50%-owym prawdopodobieństwem. W 1992, Deutsch i Jozsa wymyślili deterministyczny algorytm, który został uogólniony na przypadek funkcji, której argumentem jest n bitów. W przeciwieństwie do dzisiejszego algorytmu, wymagał on dwukrotnego obliczenia wartości funkcji (zamiast jednego).

Późniejsze ulepszenia algorytmu Deutscha wprowadził Cleve (i inni)[2], czego efektem było powstanie deterministycznego algorytmu, który wymaga jednokrotnej ewaluacji funkcji f. Temu algorytmowi nadano imiona Deutscha-Jozsy, aby uczcić innowacyjne zmiany wprowadzone przez tych naukowców[2].

Algorytm Deutsha-Jozsy stanowił inspirację dla algorytmu Shora i Grovera, dwóch najbardziej rewolucyjnych algorytmów kwantowych[5][6]

Dekoherencja[edytuj | edytuj kod]

Aby algorytm Deutscha-Jozsy działał, wyrocznia obliczająca f(x) z  x musi być wyrocznią kwantową, która nie dokonuje dekoherencji x. Wyrocznia w swoim wywołaniu musi również niszczyć informację o stanie x.

Algorytm Deutscha[edytuj | edytuj kod]

Algorytm Deutscha to szczególny przypadek algorytmu Deutscha-Jozsy. Chcemy w nim sprawdzić warunek: f(0)=f(1). Jest to równoważne sprawdzeniu f(0)\oplus f(1) (gdzie \oplus to dodawanie modulo 2, na które można patrzeć jak na kwantową bramkę XOR zaimplementowaną jako kontrolowana bramka NOT) - jeśli wyjdzie zero, to f jest stała, wpp. f nie jest stała.

Algorytm zaczyna się ustaleniem dwukubitowego stanu A: |0\rangle |1\rangle i zaaplikowaniu przekształcenia Hadamarda do każdego kubitu, co daje stan B:

\frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle).

Mamy daną kwantową implementację funkcji f, która przekształca |x\rangle |y\rangle w |x\rangle |f(x)\oplus y\rangle. Zastosowanie tej funkcji do stanu B daje:

\frac{1}{2}(|0\rangle(|f(0)\oplus 0\rangle - |f(0)\oplus 1\rangle) + |1\rangle(|f(1)\oplus 0\rangle - |f(1)\oplus 1\rangle))
=\frac{1}{2}((-1)^{f(0)}|0\rangle(|0\rangle - |1\rangle) + (-1)^{f(1)}|1\rangle(|0\rangle - |1\rangle))
=(-1)^{f(0)}\frac{1}{2}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle)(|0\rangle - |1\rangle).

Ignorujemy ostatni bit i z dokładnością do globalnego czynnika fazowego (przemnożenia całości przez e^{i \phi}) otrzymujemy stan:

\frac{1}{\sqrt{2}}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle).

Zastosowanie przekształcenia Hadamarda do tego stanu daje:

\frac{1}{2}(|0\rangle + |1\rangle + (-1)^{f(0)\oplus f(1)}|0\rangle - (-1)^{f(0)\oplus f(1)}|1\rangle)
=\frac{1}{2}((1 +(-1)^{f(0)\oplus f(1)})|0\rangle + (1-(-1)^{f(0)\oplus f(1)})|1\rangle).

f(0)\oplus f(1)=0 wtedy i tylko wtedy, jeśli zmierzymy 0, a f(0)\oplus f(1)=1 wtedy i tylko wtedy, jeśli zmierzymy 1. A więc, ze 100%-owym prawdopodobieństem wiemy, czy f(x) jest stała, czy zbalansowana.

Algorytm Deutscha-Jozsy[edytuj | edytuj kod]

Obwód kwantowy algorytmu Deutscha-Jozsy

Ustalmy n+1 bitowy stan A: |0\rangle^{\otimes n} |1\rangle . (pierwsze n bitów jest w stanie |0\rangle , a ostatni |1\rangle ). Do każdego bitu A stosowane jest przekształcenie Hadamarda, w wyniku czego powstaje stan B:

\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle ).

Następnie, kwantowa wyrocznia przekształca stan  |x\rangle|y\rangle w  |x\rangle|y\oplus f(x) \rangle , co daje:

\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|f(x)\rangle - |1\oplus f(x)\rangle ).

Po podstawieniu w miejsce f(x) 0 oraz 1, ten wzór przekształca się do:

\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle (|0\rangle - |1\rangle ).

W tym momencie stan ostatniego kubitu może zostać zignorowany. Po zastosowaniu przekształcenia Hadamarda ponownie na pierwszych n bitach otrzymuje się:

\frac{1}{2^n}\sum_{x=0}^{2^n-1} (-1)^{f(x)} \sum_{y=0}^{2^n-1}(-1)^{x\cdot y} |y\rangle=
\frac{1}{2^n}\sum_{y=0}^{2^n-1} \left[\sum_{x=0}^{2^n-1}(-1)^{f(x)} (-1)^{x\cdot y}\right] |y\rangle

gdzie x\cdot y=x_0 y_0\oplus x_1 y_1\oplus\cdots\oplus x_{n-1} y_{n-1}

Na koniec sprawdźmy prawdopodobieństwo zmierzenia |0\rangle^{\otimes n},

\bigg|\frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\bigg|^2

Co sumuje się do 1 jeśli f(x) jest stała (interferencja konstruktywna) i do 0 jeśli f(x) jest zbalansowana (interferencja destruktywna).

Przypisy

  1. David Deutsch and Richard Jozsa. Rapid solutions of problems by quantum computation. „Proceedings of the Royal Society of London A”. 439, s. 553, 1992. doi:10.1098/rspa.1992.0167. Bibcode1992RSPSA.439..553D. 
  2. 2,0 2,1 2,2 R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. „Proceedings of the Royal Society of London A”. 454, s. 339–354, 1998. doi:10.1098/rspa.1998.0164. Bibcode1998RSPSA.454..339C. 
  3. Certainty from Uncertainty
  4. David Deutsch. The Church-Turing principle and the universal quantum computer. „Proceedings of the Royal Society of London A”. 400, s. 97, 1985. doi:10.1098/rspa.1985.0070. Bibcode1985RSPSA.400...97D. 
  5. . A fast quantum mechanical algorithm for database search. W: Lov K. Grover: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. 1996, s. 212–219. DOI:10.1145/237814.237866.
  6. Algorithms for quantum computation: discrete logarithms and factoring. W: Peter W. Shor: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. 1994, s. 124–134. DOI:10.1109/SFCS.1994.365700.

Linki zewnętrzne[edytuj | edytuj kod]