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 $ϵ⩽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⟩|1⟩$ i zaaplikowaniu przekształcenia Hadamarda do każdego kubitu, co daje stan B:

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

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

$\frac{1}{2}(|0⟩(|f(0)\oplus 0⟩-|f(0)\oplus 1⟩)+|1⟩(|f(1)\oplus 0⟩-|f(1)\oplus 1⟩))$

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

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

Ignorujemy ostatni bit i z dokładnością do globalnego czynnika fazowego (przemnożenia całości przez $e^{i\varphi }$) otrzymujemy stan:

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

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

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

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

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

$\frac{1}{2}(|0⟩+|1⟩+(-1{)}^{f(0)\oplus f(1)}|0⟩-(-1{)}^{f(0)\oplus f(1)}|1⟩)$

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

$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{⟩}^{\otimes n}|1⟩$ (pierwsze $n$ bitów jest w stanie $|0⟩,$ a ostatni $|1⟩$). 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⟩(|0⟩-|1⟩).$

Następnie, kwantowa wyrocznia przekształca stan $|x⟩|y⟩$ w $|x⟩|y\oplus f(x)⟩,$ co daje:

$\frac{1}{\sqrt{2^{n+1}}}\sum _{x=0}^{2^n-1}|x⟩(|f(x)⟩-|1\oplus f(x)⟩).$

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⟩(|0⟩-|1⟩).$

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⟩=\frac{1}{2^n}\sum _{y=0}^{2^n-1}[\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}(-1{)}^{x\cdot y}]|y⟩$

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

$|\frac{1}{2^n}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}{|}^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.)