Algorytm Deutscha-Jozsy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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ę . Gwarantowane jest, że 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 jest stała, czy zbalansowana.

Klasyczny algorytm[edytuj | edytuj kod]

Konwencjonalny, deterministyczny algorytm rozwiązujący problem Deutscha-Jozsy wymaga w najgorszym przypadku ewaluacji funkcji , gdzie n jest liczbą bitów/kubitów. Aby udowodnić, że 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 jest zbalansowana. Konwencjonalny algorytm randomizowany wymaga wykonania stałej liczby ewaluacji funkcji, aby uzyskać poprawną odpowiedź z dużym prawdopodobieństwem (błąd z prawdopodobieństwem ). Aby na pewno uzyskać poprawną odpowiedź (algorytm deterministyczny), wymagane jest wyznaczenie wartości funkcji. Algorytm Deutscha-Jozsy zwraca zawsze poprawną odpowiedź już po jednej ewaluacji funkcji .

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ą funkcję binarną, której dziedziną jest 1 bit: i pytamy, czy 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 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 . 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 z musi być wyrocznią kwantową, która nie dokonuje dekoherencji . Wyrocznia w swoim wywołaniu musi również niszczyć informację o stanie .

Algorytm Deutscha[edytuj | edytuj kod]

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

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

Dana jest kwantowa implementacja funkcji , która przekształca w . Zastosowanie tej funkcji do stanu B daje:

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

Zastosowanie przekształcenia Hadamarda do tego stanu daje:

wtedy i tylko wtedy, jeśli zmierzono 0, a wtedy i tylko wtedy, jeśli zmierzono 1. Wynika z tego, iż z prawdopodobieństwem równym 100% wiemy, czy jest stała, czy zbalansowana.

Algorytm Deutscha-Jozsy[edytuj | edytuj kod]

Ustalmy bitowy stan A: . (pierwsze bitów jest w stanie , a ostatni ). Do każdego bitu A stosowane jest przekształcenie Hadamarda, w wyniku czego powstaje stan B:

Obwód kwantowy algorytmu Deutscha-Jozsy
.

Następnie, kwantowa wyrocznia przekształca stan w, co daje:

.

Po podstawieniu w miejsce oraz , ten wzór przekształca się do:

.

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

gdzie

Na koniec sprawdźmy prawdopodobieństwo zmierzenia ,

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

Przypisy[edytuj | 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, 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. 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. 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]