Algorytm Deutscha-Jozsy

Algorytm Deutscha-Jozsy – algorytm kwantowy utworzony przez Dawida Deutscha i Richarda Jozsa 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

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

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

• ${\displaystyle f}$ jest funkcją zbalansowaną^[3] (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 ${\displaystyle f}$ jest stała, czy zbalansowana.

Klasyczny algorytm

Deterministyczny algorytm rozwiązujący problem Deutscha-Jozsy wymaga w najgorszym przypadku ${\displaystyle 2^{n-1}+1}$ ewaluacji funkcji ${\displaystyle f,}$ gdzie ${\displaystyle n}$ jest liczbą bitów. Aby udowodnić, że ${\displaystyle 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 ${\displaystyle f}$ jest zbalansowana. Konwencjonalny algorytm randomizowany wymaga wykonania ${\displaystyle k}$ ewaluacji funkcji, aby uzyskać poprawną odpowiedź z dużym prawdopodobieństwem (błąd z prawdopodobieństwem ${\displaystyle \epsilon \leqslant 1/2^{k-1}}$). Aby na pewno uzyskać poprawną odpowiedź (algorytm deterministyczny), wymagane jest wyznaczenie ${\displaystyle k=2^{n-1}+1}$ wartości funkcji. Algorytm Deutscha-Jozsy zwraca zawsze poprawną odpowiedź już po jednej ewaluacji funkcji ${\displaystyle 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: ${\displaystyle f:\{0,1\}\to \{0,1\}}$ i pytamy, czy ${\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 ${\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 ${\displaystyle f.}$ Temu algorytmowi nadano imiona Deutscha-Jozsy, aby uczcić innowacyjne zmiany wprowadzone przez tych naukowców^[2].

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

Dekoherencja

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

Algorytm Deutscha

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

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

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

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

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

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

${\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 ${\displaystyle e^{i\phi }}$) otrzymujemy stan:

${\displaystyle {\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 ${\displaystyle |0\rangle }$ i ${\displaystyle |1\rangle }$ :

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

${\displaystyle 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:

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

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

${\displaystyle f(0)\oplus f(1)=0}$ wtedy i tylko wtedy, jeśli zmierzono 0, a ${\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 ${\displaystyle f(x)}$ jest stała, czy zbalansowana.

Algorytm Deutscha-Jozsy

Ustalmy ${\displaystyle n+1}$ kubitowy stan A: ${\displaystyle |0\rangle ^{\otimes n}|1\rangle }$ (pierwsze ${\displaystyle n}$ bitów jest w stanie ${\displaystyle |0\rangle ,}$ a ostatni ${\displaystyle |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:

${\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 ${\displaystyle |x\rangle |y\rangle }$ w ${\displaystyle |x\rangle |y\oplus f(x)\rangle ,}$ co daje:

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

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

${\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 ${\displaystyle 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 ${\displaystyle |0\rangle ^{\otimes n}}$ wynosi:

${\displaystyle {\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 ${\displaystyle f(x)}$ jest stała (interferencja konstruktywna). Jeżeli zaś funkcja ${\displaystyle f(x)}$ jest zbalansowana, to przyjmuje wartość 0 (interferencja destruktywna).

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