Algorytm Deutscha-Jozsy

Algorytm Deutscha-Jozsy – algorytm kwantowy utworzony przez Dawida Deutscha i Richarda Jozsa w 1992 poprawiany później przez Richarda Cleve, Artura Ekerta, Chiarę Macchiavello i Michele Mosca w 1998. 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

W problemie Deutscha-Jozsy mamy "czarną skrzynkę", która tworzy funkcję $f:\{0,1\}^{n}\to \{0,1\}$ taką że:

• $f$ jest funkcją stałą (tj. wszystkie wartości ma równe 0 albo wszystkie wartości ma równe 1) lub

• $f$ jest funkcją zbalansowaną (tj. przypisuje wartości 0 oraz 1 tak, że jest tyle samo wartości 0 co 1).

Innymi słowy: "czarna skrzynka" generuje n bitów w taki sposób, że (1) wszystkie bity są równe 0 albo wszystkie bity są równe 1, (2) albo 0 i 1 są wygenerowane w równych ilościach, ale w dowolnej kolejności.

Zadanie polega na określeniu, czy $f$ jest stała, czy zbalansowana.

Klasyczny algorytm

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. Aby udowodnić, że $f$ jest stała, potrzebne jest obliczenie funkcji w n/2+1 punktów. W najlepszym przypadku, jeżeli już pierwsze dwie sprawdzone wartości funkcji będą różne, to dowodzi, że $f$ jest zbalansowana. Konwencjonalny algorytm randomizowany wymaga wykonania $k$ ewaluacji funkcji, aby uzyskać poprawną odpowiedź z dużym prawdopodobieństwem (błąd z prawdopodobieństwem $\epsilon \leqslant 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

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\}\to \{0,1\}$ i pytamy, czy $f$ jest stała.

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$ bitów. W przeciwieństwie do aktualnego algorytmu, wymagał on dwukrotnego obliczenia wartości funkcji.

Późniejsze ulepszenia algorytmu Deutscha wprowadził Cleve (i inni), 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.

Algorytm Deutscha-Jozsy stanowił inspirację dla algorytmu Shora i Grovera, dwóch najbardziej rewolucyjnych algorytmów kwantowych.

Dekoherencja

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

Algorytm Deutscha to szczególny przypadek algorytmu Deutscha-Jozsy. Sprawdza się w nim 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, w przeciwnym przypadku $f$ nie jest stała.

Algorytm zaczyna się ustaleniem dwubitowego 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 ).$

Dana jest kwantowa implementacja 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:

${}\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 ))$

$={\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 ).$

Zastosujmy do każdego kubitu tego stanu bramkę Hadamarda; bramka ta tworzy następujące superpozycje stanów bazowych $|0\rangle$ i $|1\rangle$ :

$H\,|0\rangle ={\frac {1}{\sqrt {2}}}{\Big (}|0\rangle +|1\rangle {\Big )},$

$H\,|1\rangle ={\frac {1}{\sqrt {2}}}{\Big (}|0\rangle -|1\rangle {\Big )}.$

Działając bramkami Hadamarda na każdy kubit otrzyma się stan:

${}\quad {\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 zmierzono 0, a $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)$ jest stała, czy zbalansowana.

Algorytm Deutscha-Jozsy

Ustalmy $n+1$ kubitowy stan A: $|0\rangle ^{\otimes n}|1\rangle$ (pierwsze $n$ bitów jest w stanie $|0\rangle ,$ a ostatni $|1\rangle$). Do każdego kubitu A stosowana jest bramka Hadamarda, która z każdego kubitu tworzy superpozycję; w wyniku czego powstaje stan B:

Obwód kwantowy algorytmu Deutscha-Jozsy

${\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łceń Hadamarda ponownie na pierwszych $n$ bitach otrzyma 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}$

Prawdopodobieństwo zmierzenia stanu $|0\rangle ^{\otimes n}$ wynosi:

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

Wyrażenie to przyjmuje wartość 1, jeśli funkcja $f(x)$ jest stała (interferencja konstruktywna). Jeżeli zaś funkcja $f(x)$ jest zbalansowana, to przyjmuje wartość 0 (interferencja destruktywna).

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.)