Algorytm Deutscha-Jozsy
Algorytm Deutscha-Jozsy to algorytm kwantowy stworzony przez Dawida Deutscha oraz Richarda Jozsa w 1992 roku, a następnie udoskonalony przez Richarda Cleve, Artura Ekerta, Chiarę Macchiavello i Michele Mosca w 1998. Chociaż algorytm ten nie ma dużego zastosowania praktycznego, jest jednym z pierwszych przykładów algorytmu kwantowego, który działa wykładniczo szybciej niż jakikolwiek możliwy klasyczny algorytm deterministyczny. Co więcej, algorytm Deutscha-Jozsy jest deterministyczny, co oznacza, że zawsze zwraca poprawną odpowiedź.
Sformułowanie problemu
W kontekście problemu Deutscha-Jozsy mamy do czynienia z „czarną skrzynką”, która definiuje funkcję:
f: {0, 1}n → {0, 1}
gdzie:
- f jest funkcją stałą (tj. wszystkie wartości są równe 0 lub wszystkie wartości są równe 1) lub
- f jest funkcją zbalansowaną (tj. przypisuje wartości 0 oraz 1 w równych ilościach).
Innymi słowy, „czarna skrzynka” produkuje n bitów w taki sposób, że (1) wszystkie bity są równe 0 albo wszystkie są równe 1, albo (2) wartości 0 i 1 są generowane w równych ilościach, ale w dowolnej kolejności. Celem jest określenie, czy f jest stała, czy zbalansowana.
Klasyczny algorytm
Klasyczny algorytm deterministyczny rozwiązujący problem Deutscha-Jozsy wymaga w najgorszym przypadku 2n – 1 + 1 ewaluacji funkcji f, gdzie n jest liczbą bitów. Aby dowieść, że f jest stała, należy obliczyć funkcję w n/2 + 1 punktach. W najlepszym przypadku, jeśli pierwsze dwie sprawdzone wartości funkcji będą różne, to dowodzi, że f jest zbalansowana. Klasyczny algorytm randomizowany wymaga wykonania k ewaluacji funkcji, aby uzyskać poprawną odpowiedź z wysokim prawdopodobieństwem (z błędem o prawdopodobieństwie ε ≤ 1/2k-1). Aby uzyskać pewną poprawną odpowiedź (algorytm deterministyczny), konieczne jest określenie k = 2n – 1 + 1 wartości funkcji. Algorytm Deutscha-Jozsy zwraca zawsze poprawną odpowiedź już po jednej ewaluacji funkcji f.
Historia
Algorytm Deutscha-Jozsy jest rozszerzeniem wcześniejszej pracy Dawida Deutscha z 1985 roku, która zajmowała się prostszym problemem. W szczególności rozpatrywana była funkcja binarna, której dziedziną jest 1 bit:
f: {0, 1} → {0, 1}
oraz pytanie, czy f jest stała. Początkowy algorytm zaproponowany przez Deutscha nie był w pełni deterministyczny, gdyż dawał poprawną odpowiedź z prawdopodobieństwem 50%. W 1992 roku Deutsch i Jozsa opracowali deterministyczny algorytm, który został uogólniony na przypadek funkcji, której argumentem jest n bitów. W przeciwieństwie do obecnego algorytmu, wymagał on dwukrotnego obliczenia wartości funkcji. Późniejsze ulepszenia algorytmu Deutscha wprowadził Cleve i inni, co doprowadziło do powstania deterministycznego algorytmu, który wymaga jednokrotnej ewaluacji funkcji f. Algorytm ten nosi nazwisko Deutscha-Jozsy, aby uczcić innowacyjne zmiany wprowadzone przez tych naukowców. Algorytm Deutscha-Jozsy zainspirował również algorytmy Shora i Grovera, które są uznawane za jedne z najważniejszych algorytmów kwantowych.
Dekoherencja
Aby algorytm Deutscha-Jozsy funkcjonował poprawnie, wyrocznia obliczająca f(x) musi być wyrocznią kwantową, która nie dokonuje dekoherencji x. Wyrocznia w swoim wywołaniu musi również zniszczyć informację o stanie x.
Algorytm Deutscha
Algorytm Deutscha jest szczególnym przypadkiem algorytmu Deutscha-Jozsy. Sprawdza on warunek:
f(0) = f(1).
Jest to równoważne sprawdzeniu:
f(0) ⊕ f(1) (gdzie ⊕ oznacza dodawanie modulo 2, które można interpretować jako kwantową bramkę XOR zaimplementowaną jako kontrolowana bramka NOT). Jeśli wynik to zero, oznacza to, że f jest stała, w przeciwnym wypadku f nie jest stała.
Algorytm rozpoczyna się od ustalenia dwubitowego stanu A:
|0⟩ |1⟩
i zastosowania przekształcenia Hadamarda do każdego kubitu, co daje stan B:
1/2 (|0⟩ + |1⟩)(|0⟩ – |1⟩).
Wykonywana jest kwantowa implementacja funkcji f, która przekształca:
|x⟩ |y⟩
w
|x⟩ |f(x) ⊕ y⟩.
Zastosowanie tej funkcji do stanu B daje:
{…}
(szczegóły obliczeń)
Przypisy
…
Zobacz też
algorytm kwantowy
bramka kwantowa
Linki zewnętrzne
Deutsch’s lecture about Deutsch algorithm (ang.)
Implementation of the Deutsch-Jozsa algorithm in the Scala programming language (ang.)
