Algorytm Grovera: co wprowadzić do Oracle?

9

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+|01+|10+|11)1/2)(|00+|01+|10-|11)

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-|00|00
  • W naszym przypadku Oracle zwraca .1/2)(|00+|01+|10-|11)
  • Ale co z listą i słowem?
Bick
źródło
1
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:

4

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(N.fa)N.fa

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.faO(N.)O(N.fa)=O(N.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 jestO(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