Math
Jedno pytanie, zadane raz
Czarna skrzynka liczy f z n bitów na jeden bit, a pytać ją wolno tylko o wejścia. Pewność, czy f jest stała czy zrównoważona, kosztuje klasycznie pół tablicy plus jedno wywołanie. Hadamard na wszystko, JEDNO wywołanie z odpowiedzią w postaci znaku, znowu Hadamard - i wynik same zera rozstrzyga. Tablica prawdy jest tu klikalna, więc obietnicę można złamać ręcznie: dla dowolnej tablicy odpowiedź wypada z prawdopodobieństwem (1 − 2k/N)². A gdy tablica okaże się f(x) = s·x, to jedno wywołanie zwraca samo s.
Co się dzieje
Czarna skrzynka liczy jakąś funkcję f z n bitów na jeden bit. Obiecano, że jest albo stała, albo zrównoważona - ta sama odpowiedź wszędzie, albo jedna odpowiedź na dokładnie połowie wejść - i trzeba powiedzieć, która. Klasycznie nie ma skrótu: pół tablicy może się zgadzać, a następny wpis wszystko zepsuć, więc pewność kosztuje N/2 + 1 wywołań. Dziewięć przy szesnastu wejściach, trzydzieści trzy przy sześćdziesięciu czterech. Teraz wersja kwantowa, i mieści się w trzech linijkach. Hadamard na każdy kubit, żeby zapytać o wszystkie N wejść naraz. Wywołaj wyrocznię - która odpowiada nie bitem, lecz ZNAKIEM: minus na każdym wejściu, gdzie f jest jedynką. Znowu Hadamard na każdy kubit. Zmierz. Jeśli wszystkie kubity czytają zero, f była stała; cokolwiek innego oznacza zrównoważoną, a całość kosztowała jedno wywołanie. Ten moduł jest czymś więcej niż pokazem, bo tablicę u góry można klikać. Złam obietnicę: odwróć jedną komórkę, a f nie jest ani stała, ani zrównoważona - i algorytm nie zawodzi, tylko pogarsza się o wielkość, którą da się wypisać. Dla DOWOLNEJ tablicy wynik same zera ma prawdopodobieństwo (1 − 2k/N)², gdzie k liczy jedynki tablicy. Stała to k = 0 i daje jeden. Zrównoważona to k = N/2 i daje dokładnie zero. Jedna odwrócona komórka przy szesnastu wejściach daje 4/256, jeden przebieg na sześćdziesiąt cztery, a panel podaje liczbę, zanim zaczniesz liczyć. Tyle warta jest obietnica wewnątrz algorytmu, w liczbach. Kryje się tu jeszcze jedno. Gdy tablica jest liniowa - f(x) = s·x mod 2 dla ukrytego ciągu s - te same trzy kroki nie odpowiadają tylko tak lub nie: wynikiem JEST s, z prawdopodobieństwem jeden, a każdy inny wynik ma dokładnie zero. To Bernstein-Vazirani, a klasycznie kosztuje n wywołań, po jednym na bit. Zapytaj raz, przeczytaj cały ciąg. Pod obydwoma faktami leży jeden wzór: amplituda wyniku y to transformata Walsha-Hadamarda z (−1)^f, a moduł liczy ją drugi raz wprost z tablicy, żeby dało się je zestawić.
Równania modułu
Równania trzy kroki: H na każdym kubicie; jedno wywołanie wyroczni jako znak, |x> -> (−1)^f(x) |x>; H znów na każdym kubicie amplituda wyniku y: (1/N) suma po x z (−1)^(f(x) + x·y) - transformata Walsha-Hadamarda funkcji (−1)^f P(wszystkie zera) = (1 − 2k/N)² gdzie k to liczba jedynek w tablicy prawdy - DOKŁADNIE, dla dowolnej tablicy stała (k = 0 lub N): 1; zrównoważona (k = N/2): 0; jedna komórka zrównoważonej tablicy odwrócona: 4/N² = 1/64 przy N = 16 koszt klasyczny, by mieć PEWNOŚĆ: N/2 + 1 wywołań (3, 5, 9, 17, 33 dla n = 2…6) wobec 1 tablica liniowa f(x) = s·x mod 2 (Bernstein-Vazirani): wynikiem JEST s, prawdopodobieństwo 1, każdy inny wynik dokładnie 0; koszt klasyczny n wywołań, po jednym na bit f = 1 wszędzie daje dokładnie te same prawdopodobieństwa co f = 0 wszędzie - różnica to globalny znak, a globalny znak nie jest mierzalny zliczenia, 2000 uruchomień przy n = 4: stała 2000 z 2000 na wyniku z samych zer; ukryte s = 11, 2000 z 2000 na 11; zrównoważona 0 na wyniku z samych zer; jedna komórka odwrócona 30 (dokładnie 31.25)
