Algorytm Grovera: co wprowadzić do Oracle?

Nie wiem, co wprowadzić do Oracle w algorytmie Grovera.

Czy oprócz superpozycjonowanych stanów kwantowych nie musimy wprowadzać tego, czego szukamy i gdzie znaleźć to, czego szukamy?

Załóżmy na przykład, że mamy listę nazwisk osób {„Alice”, „Bob”, „Corey”, „Dio”} i chcemy sprawdzić, czy na liście znajduje się „Dio”. Następnie Oracle powinien przyjąć jako dane wejściowe i wyjściowe . W pewnym sensie to rozumiem. $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$

Ale czy nie musimy także wpisywać słowa „Dio” i listy {„Alice”, „Bob”, „Corey”, „Dio”} do Oracle? W przeciwnym razie, w jaki sposób Oracle może zwrócić dane wyjściowe? Czy nie jest to wyraźnie wspomniane, ponieważ Oracle to czarna skrzynka i nie musimy myśleć o tym, jak ją wdrożyć?

Rozumiem co do Oracle,

Oracle ma możliwość rozpoznania, czy słowo „Dio” znajduje się na liście.
Aby to zrobić, Oracle przyjmuje jako dane wejściowe superpozycjonowane stany kwantowe, przy czym każdy stan kwantowy reprezentuje indeks listy.
Tak więc wpisanie do Oracle oznacza, sprawdź, czy słowo „Dio” znajduje się w indeksie 0 listy i zwróć jeśli tak, i zwróć przeciwnym razie. $|00\rangle$ $-|00\rangle$ $|00\rangle$
W naszym przypadku Oracle zwraca . $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$
Ale co z listą i słowem?

algorithm grovers-algorithm oracles Bick
źródło

Chociaż nie jest sformułowany w ten sam sposób, uważam, że twoje pytanie jest mniej więcej takie samo: Algorytm Grovera: gdzie jest lista?

DaftWullie

Odpowiedzi:

Chociaż popularne wyjaśnienia algorytmu Grovera mówią o przeszukiwaniu listy, w rzeczywistości używa się jej do przeszukiwania możliwych wejść 0..N-1 do funkcji. Koszt algorytmu wynosi gdzie to liczba danych wejściowych, które chcesz przeszukać, a to koszt oceny funkcji. Jeśli chcesz, aby ta funkcja przeszukiwała listę, musisz zakodować listę w funkcji. $O(\sqrt{N} \cdot F)$ $N$ $F$

Twarde kodowanie funkcji w celu użycia listy elementów jest zwykle bardzo złym pomysłem, ponieważ zwykle powoduje, że ma wartość . Co oznaczałoby całkowity koszt algorytmu Grovera . Jaki rodzaj klęsk głównym celem, ponieważ . $N$ $F$ $O(N)$ $O(\sqrt{N} \cdot F) = O(\sqrt{N} \cdot N) = O(N^{1.5})$ $N^{1.5} > N$

Craig Gidney
źródło

Czy nie wprowadziłbyś uporządkowanej listy, co znacznie przyspieszyłoby wyszukiwanie? Oczywiście możesz chcieć uwzględnić koszt zamówienia listy, ale wydaje mi się, że nadal tak jest

O (\sqrt{N} \log (N))

$O(\sqrt{N}\log(N))$ ogólnie.

DaftWullie

@DaftWullie Problem polega na tym, że Grover musi przeprowadzić przegląd w superpozycji, a to wymaga obwodu multipleksera z bramkami N AND (lub innymi operacjami innymi niż Clifford). Bramka kwantowa ORAZ (tj. Toffoli) ma znaczący koszt podczas przeprowadzania korekcji błędów. Koszt ten jest technicznie obecny również w klasycznej maszynie (tj. RAM ma bramki O (N) ORAZ), po prostu zdarza się, że w tym kontekście jest nieistotny, a nawet można go uniknąć.

Craig Gidney

Nie rozumiem co mówisz. Czy byłbyś w stanie wyrazić pytanie i odpowiedzieć na nie, aby pokazać szczegóły? (Nie sądzę, żebym mógł w tej chwili sformułować wystarczająco dobre pytanie)

DaftWullie

@DaftWullie Myślę, że pytanie brzmiałoby mniej więcej tak: „jak przyznać komputerowi kwantowemu dostęp do odczytu do klasycznej bazy danych i ile to kosztuje”.

Craig Gidney