W „Obliczeniach kwantowych i informacjach kwantowych” Mike'a i Ike'a algorytm Grovera został szczegółowo wyjaśniony. Jednak w książce i we wszystkich wyjaśnieniach, które znalazłem w Internecie dla algorytmu Grovera, wydaje się, że nie ma wzmianki o tym, jak zbudowana jest Wyrocznia Grovera, chyba że już wiemy, w jakim stanie szukamy, pokonując cel algorytm. Konkretnie, moje pytanie brzmi: biorąc pod uwagę pewne f (x) takie, że dla pewnej wartości x, f (x) = 1, ale dla wszystkich innych, f (x) = 0, w jaki sposób buduje się wyrocznię, która nas od nich wyrwie nasz początkowy, dowolny stan | x> | y> do | x> | y + f (x)>? Doceniona zostanie jak najwięcej wyraźnych szczegółów (być może przykład?). Jeśli taka konstrukcja dowolnej funkcji jest możliwa w przypadku Hadamarda, Pauliego lub innych standardowych bram kwantowych,
Konstrukcja Oracle dla algorytmu Grovera
Odpowiedzi:
Wyrocznia jest po prostu implementacją predykatu, w którym chcesz znaleźć satysfakcjonujące rozwiązanie.
Załóżmy na przykład, że masz problem z 3-sat:
(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
(x2 ∨ x3 ∨ ¬x4) ∧
(x1 ∨ ¬x2 ∨ x4) ∧
(x1 ∨ x3 ∨ x4) ∧
(¬x1 ∨ x2 ∨ ¬x3)
Lub w formie tabeli, gdzie każdy wiersz jest 3-klauzulą, x oznacza „ta zmienna fałsz”, o oznacza „ta zmienna prawda”, a spacja oznacza „nie w klauzuli”:
1 2 3 4
-------
x x x
o o x
o x o
x o x
Teraz utwórz obwód, który oblicza, czy dane wejściowe są rozwiązaniem, takie jak to:
Teraz, aby zmienić obwód w wyrocznię, uderz w bit wyjściowy bramką Z i odznacz wszelkie śmieci, które zrobiłeś (tj. Uruchom obwód obliczeniowy w odwrotnej kolejności):
To wszystko. Obliczyć predykat, trafić wynik w Z, odliczyć predykat. To wyrocznia.
Iteruj kroki dyfuzji krokami wyroczni, a będziesz szukał groverów :
... chociaż powinieneś prawdopodobnie wybrać przykład z mniejszą liczbą rozwiązań, więc postęp jest stopniowy (zamiast obracać się wzdłuż płaszczyzny stanu początkowego-stanu-rozwiązania o więcej niż 90 stopni na krok, jak w moim przykładzie).