Algorytm Deutscha-Jozsy


Algorytm Deutscha-Jozsy w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do 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ź.

Spis treści

Sformułowanie problemu | edytuj kod

W problemie Deutscha-Jozsy mamy daną wyrocznię – komputer kwantowy reprezentowany przez czarną skrzynkę, który implementuje funkcję f : { 0 , 1 } n { 0 , 1 } . {\displaystyle f:\{0,1\}^{n}\to \{0,1\}.} Gwarantowane jest, że f {\displaystyle 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 {\displaystyle f} jest stała, czy zbalansowana.

Klasyczny algorytm | edytuj kod

Konwencjonalny, deterministyczny algorytm rozwiązujący problem Deutscha-Jozsy wymaga w najgorszym przypadku 2 n 1 + 1 {\displaystyle 2^{n-1}+1} ewaluacji funkcji f , {\displaystyle f,} gdzie n {\displaystyle n} jest liczbą bitów/kubitów. Aby udowodnić, że f {\displaystyle f} jest stała, potrzebne jest obliczenie funkcji w ponad połowie punktów i obserwacja, że otrzymane 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 {\displaystyle f} jest zbalansowana. Konwencjonalny algorytm randomizowany wymaga wykonania stałej liczby k {\displaystyle k} ewaluacji funkcji, aby uzyskać poprawną odpowiedź z dużym prawdopodobieństwem (błąd z prawdopodobieństwem ϵ 1 / 2 k 1 {\displaystyle \epsilon \leqslant 1/2^{k-1}} ). Aby na pewno uzyskać poprawną odpowiedź (algorytm deterministyczny), wymagane jest wyznaczenie k = 2 n 1 + 1 {\displaystyle k=2^{n-1}+1} wartości funkcji. Algorytm Deutscha-Jozsy zwraca zawsze poprawną odpowiedź już po jednej ewaluacji funkcji f . {\displaystyle f.}

Historia | edytuj kod

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

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

Późniejsze ulepszenia algorytmu Deutscha wprowadził Cleve (i inni)[2], czego efektem było powstanie deterministycznego algorytmu, który wymaga jednokrotnej ewaluacji funkcji f . {\displaystyle 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 kod

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

Algorytm Deutscha | edytuj kod

Algorytm Deutscha to szczególny przypadek algorytmu Deutscha-Jozsy. Sprawdza się w nim warunek: f ( 0 ) = f ( 1 ) . {\displaystyle f(0)=f(1).} Jest to równoważne sprawdzeniu f ( 0 ) f ( 1 ) {\displaystyle f(0)\oplus f(1)} (gdzie {\displaystyle \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 {\displaystyle f} jest stała, w przeciwnym przypadku f {\displaystyle f} nie jest stała.

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

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

Dana jest kwantowa implementacja funkcji f , {\displaystyle f,} która przekształca | x | y {\displaystyle |x\rangle |y\rangle } w | x | f ( x ) y . {\displaystyle |x\rangle |f(x)\oplus y\rangle .} Zastosowanie tej funkcji do stanu B daje:

1 2 ( | 0 ( | f ( 0 ) 0 | f ( 0 ) 1 ) + | 1 ( | f ( 1 ) 0 | f ( 1 ) 1 ) ) {\displaystyle {}\quad {\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 ))} = 1 2 ( ( 1 ) f ( 0 ) | 0 ( | 0 | 1 ) + ( 1 ) f ( 1 ) | 1 ( | 0 | 1 ) ) {\displaystyle ={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))} = ( 1 ) f ( 0 ) 1 2 ( | 0 + ( 1 ) f ( 0 ) f ( 1 ) | 1 ) ( | 0 | 1 ) . {\displaystyle =(-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 ϕ {\displaystyle e^{i\phi }} ) otrzymujemy stan:

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

Zastosowanie przekształcenia Hadamarda do tego stanu daje:

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

f ( 0 ) f ( 1 ) = 0 {\displaystyle f(0)\oplus f(1)=0} wtedy i tylko wtedy, jeśli zmierzono 0, a f ( 0 ) f ( 1 ) = 1 {\displaystyle f(0)\oplus f(1)=1} wtedy i tylko wtedy, jeśli zmierzono 1. Wynika z tego, iż z prawdopodobieństwem równym 100% wiemy, czy f ( x ) {\displaystyle f(x)} jest stała, czy zbalansowana.

Algorytm Deutscha-Jozsy | edytuj kod

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

Obwód kwantowy algorytmu Deutscha-Jozsy

1 2 n + 1 x = 0 2 n 1 | x ( | 0 | 1 ) . {\displaystyle {\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 | y {\displaystyle |x\rangle |y\rangle } w | x | y f ( x ) , {\displaystyle |x\rangle |y\oplus f(x)\rangle ,} co daje:

1 2 n + 1 x = 0 2 n 1 | x ( | f ( x ) | 1 f ( x ) ) . {\displaystyle {\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 ) {\displaystyle f(x)} 0 {\displaystyle 0} oraz 1 , {\displaystyle 1,} ten wzór przekształca się do:

1 2 n + 1 x = 0 2 n 1 ( 1 ) f ( x ) | x ( | 0 | 1 ) . {\displaystyle {\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 {\displaystyle n} bitach otrzymuje się:

1 2 n x = 0 2 n 1 ( 1 ) f ( x ) y = 0 2 n 1 ( 1 ) x y | y = 1 2 n y = 0 2 n 1 x = 0 2 n 1 ( 1 ) f ( x ) ( 1 ) x y | y {\displaystyle {\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 y = x 0 y 0 x 1 y 1 x n 1 y n 1 {\displaystyle 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 n , {\displaystyle |0\rangle ^{\otimes n},}

| 1 2 n x = 0 2 n 1 ( 1 ) f ( x ) | 2 {\displaystyle {\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 ) {\displaystyle f(x)} jest stała (interferencja konstruktywna), i do 0, jeśli f ( x ) {\displaystyle f(x)} jest zbalansowana (interferencja destruktywna).

Przypisy | edytuj kod

  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. a b c R. Cleve, A. Ekert, C. Macchiavello, M. Mosca. Quantum algorithms revisited. „Proceedings of the Royal Society of London A”. 454, s. 339–354, 1998. DOI: 10.1098/rspa.1998.0164. arXiv:quant-ph/9708016. 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.L.K. Grover Lov K.L.K., Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996, s. 212–219, DOI10.1145/237814.237866, ISBN 0-89791-785-5, arXiv:quant-ph/9605043 .???
  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 kod

Na podstawie artykułu: "Algorytm Deutscha-Jozsy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy