Konstrukcja Oracle dla algorytmu Grovera

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,

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).