Jak zaimplementowana jest wyrocznia w algorytmie wyszukiwania Grovera?

Algorytm wyszukiwania Grovera zapewnia udowodnione kwadratowe przyspieszenie dla nieposortowanego wyszukiwania w bazie danych. Algorytm jest zwykle wyrażany przez następujący obwód kwantowy:

W większości przedstawień kluczową częścią protokołu jest „wyrocznia” $U_\omega$ , która „magicznie” wykonuje operację $|x\rangle\mapsto(-1)^{f(x)}|x\rangle$ . Często jednak nie wiadomo, jak trudno byłoby zrealizować taką bramę. Rzeczywiście mogłoby się wydawać, że takie użycie „wyroczni” jest tylko sposobem na pokonanie trudności pod dywanem.

Skąd wiemy, czy taka cudowna operacja jest rzeczywiście możliwa do zrealizowania? A jeśli tak, to jaka jest jego złożoność (na przykład pod względem złożoności rozkładu bramek)?

Funkcja $f$ jest po prostu dowolną funkcją boolowską ciągu bitowego: $f\colon \{0,1\}^n \to \{0,1\}$ . W przypadku aplikacji przełamujących kryptografię, takich jak[1],[2]lub[3], nie jest to tak naprawdę „wyszukiwanie bazy danych”, które wymagałoby w jakiś sposób przechowywania całej bazy danych jako obwodu kwantowego, ale raczej funkcji takiej jak

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $\operatorname{SHA-256}(x) = y$;} \\ 0, & \text{otherwise,} \end{cases} \end{equation*}$$

dla ustalonego $y$ , które nie ma żadnej struktury, którą możemy wykorzystać do klasycznego wyszukiwania, w przeciwieństwie do, powiedzmy, funkcji

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $2^x \equiv y \pmod{2^{2048} - 1942289}$}, \\ 0, & \text{otherwise}, \end{cases} \end{equation*}$$

który ma strukturę, którą można wykorzystać do szybszego odwrócenia go nawet na klasycznym komputerze.

Na pytanie o konkretny koszt nie można ogólnie odpowiedzieć, ponieważ $f$ może być dowolnym obwodem - to tylko kwestia wykonania obwodu kwantowego z obwodu klasycznego . Ale zwykle, jak w powyższym przykładzie, funkcja $f$ jest bardzo tania do oceny na klasycznym komputerze, więc nie powinna stanowić szczególnie uciążliwego obciążenia na komputerze kwantowym, dla którego wszystko inne w algorytmie Grovera mieści się w twoim budżecie.

Jedynym ogólnym kosztem nad $f$ jest dodatkowa warunkowa bramka NIE

$$C\colon \left|a\right> \left|b\right> \to \left|a\right> \left|a \oplus b\right>$$ gdzie $\oplus$ jest xor, a dodatkowy qubit pomocniczy dla niego. W szczególności, jeśli mamy obwód $$F\colon \left|x\right> \left|a\right> \lvert\text{junk}\rangle \mapsto \left|x\right> \left|a \oplus f(x)\right> \lvert\text{junk}'\rangle$$ zbudowany z $C$ i obwodu dla $f$1 ⟩ = ( 1 / √, to jeśli zastosujemy to do $\left|x\right>$ wraz z qubit pomocniczy początkowo w stanie $\left|-\right> = H\left|1\right> = (1/\sqrt{2})(\left|0\right> - \left|1\right>)$ gdzie$H$ jest brama Hadamard, wtedy otrzymujemy

$$\begin{align*} F\left|x\right> \left|-\right> \lvert\text{junk}\rangle &= \frac{1}{\sqrt{2}}\bigl( F\left|x\right> \left|0\right> \lvert\text{junk}\rangle - F\left|x\right> \left|1\right> \lvert\text{junk}\rangle \bigr) \\ &= \frac{1}{\sqrt{2}}\bigl( \left|x\right> \left|f(x)\right> \lvert\text{junk}'\rangle - \left|x\right> \left|1 \oplus f(x)\right> \lvert\text{junk}'\rangle \bigr). \end{align*}$$

Jeśli $f(x) = 0$ to $1 \oplus f(x) = 1$ , więc poprzez uproszczenie otrzymujemy

$$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = \left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ natomiast jeśli $f(x) = 1$ to $1 \oplus f(x) = 0$ , więc $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = -\left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ a zatem ogólnie $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = (-1)^{f(x)} \left|x\right> \left|-\right> \lvert\text{junk}'\rangle.$$

Cóż, oryginalny artykuł Grovera, „Mechanika kwantowa pomaga w szukaniu igły w stogu siana” wyraźnie stwierdza, że zakłada, że C (S) można oceniać w stałym czasie. W wyszukiwaniu Grovera nie chodzi o implementowalność, ale o wielomianowe zmniejszenie złożoności zapytań (ile razy konsultujesz wyrocznię, jak w klasycznej bazie danych)

W rzeczywistości koncepcja Oracle w informatyce została zaproponowana przez Alana Turinga w celu opisania konstruktów, dla których opis na UTM może być niemożliwy do zrealizowania (Wikipedia). To jest w pewnym sensie magiczne.

Ale oczywiście, wracając do twojego pytania, w jaki sposób stworzymy obwód do wyszukiwania Grovera (lub innego algorytmu)? Czy musimy znać odpowiedź z wyprzedzeniem, aby wyszukać wynik? W pewnym sensie musisz. Właśnie nad tym próbuje pracować sprytne ulepszenia w wyszukiwaniu Grovera, dlatego nie musimy znać z góry dokładnej odpowiedzi, ale niektóre jej właściwości. Pozwól mi zilustrować przykładem.

W przypadku problemu z rozpoznawaniem wzorców za pomocą wyszukiwania Grovera, jeśli mam 4 wzory na 2 kubitach (00, 01, 10, 11) i chcę zaznaczyć i wzmocnić 11, przekątna mojej jednostki wyroczni powinna być jak (1,1,1 , -1), aby zająć się przesunięciem fazowym pi dla rozwiązania. Tak więc, w przypadku tej prostej implementacji, aby zbudować jednostkę, musisz znać pełną odpowiedź z góry.

Sprytna poprawa ukończenia wzoru, jeśli podana w artykule „Kwantowe dopasowanie wzoru” autorstwa Mateasa i Omara. Zasadniczo konstruuje tyle stałych wyroczni, ile jest alfabetów w zestawie. Tak więc dla naszego ciągu binarnego pojawi się wyrocznia, która zaznacza wszystkie 1, i kolejna, która zaznacza wszystkie 0. Wyrocznie są przywoływane warunkowo na podstawie tego, co chcę przeszukać. Jeśli chcę przeszukać 11, wzywam oracle 1 na LSqubit i oracle 1 ponownie na MSqubit. W pierwszej wyroczni amplifikowałbym stany (01, 11), tj. Stany z LSQ jako 1, aw drugim wywołaniu amplifikowałby (10, 11). Jak widać, 11 jest jedynym stanem, który jest wzmacniany dwukrotnie, co kończy się większym prawdopodobieństwem pomiaru. Chociaż skompilowany obwód kwantowy zmieniłby się w zależności od mojego wzorca wyszukiwania wejściowego, ogólny opis algorytmu kwantowego pozostaje taki sam. Wyrocznie można traktować jako wywołania funkcji na podstawie wielkości liter w zestawie alfabetu wywoływanym dla każdego znaku w ciągu wyszukiwania.