Algorytm Grovera służy między innymi do wyszukiwania elementu na nieuporządkowanej liście elementów o długości . Mimo że jest tu wiele pytań dotyczących tego tematu, nadal nie rozumiem tego. $\mathbf{y}$ $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ $n$

Przeszukiwanie listy, klasyczny sposób

Zwykle zaprojektowałbym funkcję wyszukiwania w ten sposób Więc podaję listę i poszukiwany element jako dane wejściowe i otrzymuję pozycję pozycji na liście jako danych wyjściowych. Chyba się, że informacje o jest osadzony w algorytmie przez wyrocznią bramy , dlatego naszym funkcją staje Zróbmy praktyczny przykład. Rozważ przeszukanie asa pik

s e a r c h ([x_{0}, x_{1}, . . ., x_{n - 1}], y) = i \in N such that x_{i} = y

$\mathrm{search}([\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}], \mathbf{y}) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

y

$\mathbf{y}$

O

$O$

{s e a r c h}_{y} ([x_{1}, x_{2}, . . ., x_{n}]) = i \in N such that x_{i} = y

$\mathrm{search}_\mathbf{y}([\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n] ) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

1 ♠

$1\spadesuit$ w sekwencji 8 kart ze standardowej talii 52 kart :

Lista długości to . $8$ $[ \mathbf{x}_0 = J\clubsuit,$ $\mathbf{x}_1 = 10\diamondsuit,$ $\mathbf{x}_2 = 4\heartsuit,$ $\mathbf{x}_3 = Q\clubsuit,$ $\mathbf{x}_4 = 3\spadesuit,$ $\mathbf{x}_5 = 1\spadesuit,$ $\mathbf{x}_6 = 6\spadesuit,$ $\mathbf{x}_7 = 6\clubsuit]$

Poszukiwany element to . Powinienem uzyskać . Każda karta może być kodowana za pomocą bitów, lista ma elementów, więc potrzebujemy bitów do zakodowania listy. W tym przypadku wyrocznia zaimplementuje funkcję: $\mathbf{x}_5$ $\mathrm{search}_{\spadesuit}(cards) = 5$ $\lceil{\log_2 52}\rceil = 6$ $8$ $6\times 8 = 48$ $O$

f (x) = {\begin{cases} 1, & x = 1 ♠ \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \mathbf{x} = 1\spadesuit \\ 0, & \text{otherwise} \end{cases}$

Jednak wejście algorytmu Grovera nie jest stanem $48$ kubitów.

(Uwaga: zdjęcie tasowanej talii jest pobierane stąd )

Grover i jego wyrocznia

Kilka źródeł (np. Tutaj - wyjaśnione graficznie) mówi, że dane wejściowe algorytmu są różne: dane wejściowe to stan pobrany z przestrzeni wyszukiwania gdzie jest liczbą elementów listy. Każdy numer odpowiada pozycji elementu na liście. $S = \{ 0, 1, 2, ..., N \} = \{0, 1, 2, ..., 7 \}$ $N$

Wejście jest teraz wektor , który musi być superpozycją wszystkich elementów w przestrzeni wyszukiwania . $\mathrm{search}_{\spadesuit}(\cdot)$ $\lceil \log_2 8 \rceil = 3$ $|\psi\rangle$ $S$

Wiemy

$|0_{3\text{qubits}}\rangle = |000\rangle$ odpowiada $J\clubsuit$ ;
$|1_{3\text{qubits}}\rangle = |001\rangle$ odpowiada; $10\diamondsuit$
$|2_{3\text{qubits}}\rangle = |010\rangle$ odpowiada $4\heartsuit$ ;
$|5_{3\text{qubits}}\rangle = |101\rangle$ odpowiada $1\spadesuit$ który to element dobre;
i tak dalej...

W tym przypadku mamy

{s e a r c h}_{♠} (| ψ ⟩) = | 5_{3 qubits} ⟩

$\mathrm{search}_{\spadesuit}(|\psi\rangle) = |5_{3\text{qubits}}\rangle$ Ale w tym przypadku nasza wyrocznia musiałby realizować funkcję

f (| ψ ⟩) = {\begin{cases} 1, & | ψ ⟩ = | 5_{3 qubits} ⟩ \\ 0, & otherwise \end{cases}

$f(|\psi\rangle) = \begin{cases} 1, & |\psi\rangle = |5_{3\text{qubits}}\rangle \\ 0, & \text{otherwise} \end{cases}$

Zbudowanie wyroczni wymaga od nas wiedzy, że $\spadesuit$ jest na pozycji 5. Jaki jest sens wykonania algorytmu, jeśli szukaliśmy już elementu w celu zbudowania wyroczni?

grovers-algorithm w tym
źródło

Mam również trudności ze zrozumieniem zalet algorytmu Grovera. Załóżmy, że mam N pozycji na liście. Czy przy każdym wezwaniu do Wyroczni oceniał wszystkie N możliwości? Nawet jeśli ocena jest bardzo szybka, ale jeśli nadal musimy powtarzać wszystkie konfiguracje, złożoność oceny Oracle wynosi O (N). Tak więc algorytm Grovera nie wydaje się być szybszy niż głupie wyszukiwanie. Czy to jest poprawne?

Sanparith Marukatat

@SanparithMarukatat To nie jest poprawne. Pozycje na liście są warunkami superpozycji państwa biorącego udział w wyszukiwaniu. Gdy Oracle działa w tym stanie, liczy się jako pojedyncza operacja. Zdolność Wyroczni do oznaczania wyszukiwanego terminu twojej superpozycji jest fundamentalną częścią wglądu Grovera. Aby zrozumieć algorytm Grovera, polecam najpierw zrozumieć, w jaki sposób odbywa się to zaznaczanie pożądanego stanu. Następnie upewnij się, że rozumiesz rolę państwa

w Oracle.

| - ⟩

$|- \rangle$

R. Chopin

Jeśli to zrozumiesz, powinieneś przestudiować operatora, który jest w stanie zwiększyć amplitudę pożądanego terminu w superpozycji, jednocześnie zmniejszając amplitudę niepożądanych warunków superpozycji. Dla mnie najprostszym sposobem na podejście Grovera jest spojrzenie na operatora odwrotnego do średniego. (Niektórzy uważają geometryczny widok, ale nie wydaje mi się to tak jasne.)

R. Chopin

10

Jeśli masz 8 pozycji na liście (jak w przykładzie twojej karty), wtedy wejście wyroczni to 3 (qu) bity. Liczba kart w talii (52) jest nieistotna, potrzebujesz tylko 3 bitów, aby zakodować 8 kart.

Możesz pomyśleć, że 3 bity kodują pozycję na liście szukanej karty; wtedy nie znacie pozycji, ale wyrocznia wie. Więc jeśli szukasz asa pik, wyrocznia wie, że as pik jest szóstą kartą (lub piątą licząc od zera) i implementuje funkcję

f (x) = {\begin{cases} 1, & if x = 5, or binary '101' \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \text{if x = 5, or binary '101'} \\ 0, & \text{otherwise} \end{cases}$

PS: Lepiej jest inaczej myśleć o algorytmie Grovera: masz wyrocznię implementującą funkcję logiczną, która wyprowadza dla pojedynczej kombinacji bitów wejściowych, w przeciwnym razie wyprowadza zero, a twoim zadaniem jest znalezienie tej kombinacji. Problem ma tę samą złożoność, co wyszukiwanie na nieposortowanej liście lub bazie danych, dlatego algorytm Grovera jest zwykle opisywany jako wyszukiwanie w nieposortowanej bazie danych. Ale zastosowanie algorytmu do wyszukiwania w rzeczywistej bazie danych rzeczywiście rodzi pytania, które wykraczają poza sam algorytm. Algorytm Grovera szuka tylko tego, co wie wyrocznia. $1$

kludg
źródło

Tak, przepraszam, że 6 pochodziło z poprzedniej edycji

tym

2

Dziękuję za Twoją odpowiedź. Naprawiłem błędne pisanie. Jaki jest sens wykonywania algorytmu, jeśli aby zbudować wyrocznię, muszę znać pozycję szukanego elementu?

tym

1

@incud Rzeczywiście nie ma to sensu. Zaktualizowałem odpowiedź.

kludg

„ Algorytm Grovera szuka tylko tego, co wie wyrocznia ”: niekoniecznie. Wyrocznia może sprawdzać tylko niektóre specyficzne właściwości danych wejściowych, tak że wynik, który uzyskuje się na końcu, zawiera więcej informacji niż ta zakodowana w wyroczni. Typowym przykładem jest wyszukiwanie w książce telefonicznej. Wyrocznia „prosi” o zapis dołączony do konkretnej nazwy, ale po znalezieniu poprawnego zapisu uzyskuje się także dodatkowe informacje o numerze telefonu dołączonym do tego zapisu, który w ogóle nie został zakodowany w wyroczni

glS

4

Chociaż być może najłatwiej jest nam pomyśleć o funkcji wyroczni, która już obliczyła wszystkie te wartości, to nie jest to, co robi. W opisanym przypadku wyrocznia ma 8 możliwych danych wejściowych (tj. Zakodowanych w 3 (qu) bitach), a wyrocznia wykonuje wszystkie obliczenia, których potrzebujesz w locie . Tak więc, w momencie, gdy próbujesz oszacować wyrocznię dla pewnej wartości , wyrocznia wyszukuje (w tym przypadku) kartę, że wartość $x$ $x$ odpowiada, a następnie sprawdza, czy ta karta jest kartą zaznaczoną. Chodzi o to, że za każdym razem, gdy wywołujecie wyrocznię, przechodzi on ten proces raz. Ogólnie rzecz biorąc, oceniasz tę funkcję tyle razy, ile razy wywołujesz wyrocznię. Celem każdego algorytmu wyszukiwania jest wywoływanie tej wyroczni jak najmniej razy.

W przypadku, gdy zabrzmi to trochę okrężnie (biorąc pod uwagę , znajdź, która karta odpowiada), pamiętaj, że twoja tabela wyszukiwania dla tego, co odpowiada karcie, którą można zamówić, to jest inne, prostsze i znacznie szybsze pytanie wyszukiwania. $x$ $x$

Kluczowe różnice w twoim przykładzie w porównaniu do bardziej realistycznego scenariusza użytkowania to:

Przestrzeń wyszukiwania jest zwykle ogromna. Nie ma realistycznych perspektyw na wstępne obliczenie wszystkich wartości. Rzeczywiście, właśnie tego staramy się uniknąć.
Zazwyczaj nie mówimy „znajdź asa pik”. Zamiast tego istnieje który nie jest trywialny do oceny w celu sprawdzenia, czy jest „zaznaczonym” elementem, czy nie. Fakt, że wyrocznia może zająć dość dużo czasu, nawet w przypadku pojedynczego wejścia, sprawia, że wyrocznia jest kosztowną częścią do wdrożenia (a wszystkie inne bramy są wydawane za darmo) i dlaczego musisz zminimalizować liczbę połączeń . $f(x)$ $x$

Tak więc tak naprawdę klasyczne wyszukiwanie zadziałałoby na twoim problemie: losowo wybierz . Oszacuj . Jeśli , zwróć , w przeciwnym razie powtórz. Podczas gdy efektem netto jest „jest wejście , zaznaczony wpis?”, To nie jest to rzeczywiste obliczenie, które robi. $x$ $y=f(x)$ $y=1$ $x$ $f(x)$ $x_0$

DaftWullie
źródło

2

Pytanie ostatecznie brzmi: „Jaki sens ma wykonanie algorytmu, jeśli szukaliśmy już elementu, aby zbudować wyrocznię?”

Chociaż ktoś wcześniej zbudował wyrocznię, być może nie była to osoba, która go używa.

$\sqrt{\text{size of list}}$

Pytamy wyrocznię: jaka jest już odpowiedź na pytanie, które już ma? Nawet Mateus i Omar pytaliby „symbol wyroczni dla konkretnego alfabetu” w czasie wykonywania, jakie są pozycje tego symbolu w ciągu, który już skompilował? Wyrocznia udzieli odpowiedzi na nasze zapytanie już po jednej konsultacji, ale w tej historii nie może na przykład po prostu napisać odpowiedzi jako ciągu binarnego i wysłać do nas klasycznym kanałem komunikacji. Ukryje swoją odpowiedź w superpozycji, abyśmy ją wyciągnęli.

Pozwalam sobie na ucieczkę fantazji lub metafory: za pierwszym razem nie słyszymy odpowiedzi i musimy prosić wyrocznię, aby powtarzała tę samą odpowiedź w kółko, dopóki nie będziemy pewni, co powiedziała wyrocznia: z wyjątkiem tego, że zaczynamy halucynować od dezinformacji w procesie dyfuzji, jeśli pytamy zbyt wiele razy.

Brendan M.
źródło

2

Biorąc pod uwagę wyrocznię, którą podałeś, poszukiwanie jest rzeczywiście bezcelowe. Jednak wyrocznia tęskni za algorytmem Grovera, ponieważ szukanie karty w talii kart nie jest wyszukiwaniem nieustrukturyzowanym, ponieważ, jak już powiedziałeś, znasz kolejność. Ergo, twoje wyszukiwanie jest uporządkowane. Powodem użycia tej wyroczni jest to, że pokazuje, w jaki sposób można zastosować Grovera bez konieczności omawiania wyroczni, która sprawiłaby, że Grover byłby użyteczny, ponieważ taka wyrocznia byłaby bardziej skomplikowana niż cenna. Dlatego lepsza wyrocznia do wykazania przydatności Grovera może być taka:

f (x) = {\begin{cases} 1, & x [0, \dots, 3] + x [4, \dots, 7] = 1010 \\ 0, & otherwise \end{cases}

$f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases}$

To wyrocznia implikuje to, że masz 8-kubitowe wyszukiwanie, w którym bierzesz pierwsze cztery kubity i dodajesz je do drugich czterech kubitów i odwracasz M, jeśli suma daje 10 (1010 dwójkowo). Różnica między tą wyrocznią a tą, którą podałeś, polega na tym, że wyrocznia testuje wzór (czy argumenty dodają do 10), podczas gdy twój testuje równość (jest to indeks 5). Wyrocznia ta jest znacznie trudniejsza do zbudowania, ale wykorzystuje prawdziwą moc Grovera, która jest w gruncie rzeczy poszukiwaniami brutalnymi, w których twoja wyrocznia określa przestrzeń poszukiwań.

Woody1193
źródło

Algorytm Grovera: gdzie jest lista?

Przeszukiwanie listy, klasyczny sposób

Grover i jego wyrocznia

Odpowiedzi: