Jak działa operator dyfuzji Grovera i dlaczego jest optymalny?

W tej odpowiedzi wyjaśniono algorytm Grovera. Wyjaśnienie wskazuje, że algorytm w dużej mierze opiera się na operatorze dyfuzji Grovera , ale nie podaje szczegółów na temat wewnętrznych działań tego operatora.

W skrócie, operator dyfuzji Grovera tworzy „inwersję względem średniej”, aby iteracyjnie sprawić, że drobne różnice we wcześniejszych krokach są wystarczająco duże, aby były mierzalne.

Pytania są teraz:

1. W jaki sposób operator dyfuzji Grovera to osiąga?
2. Dlaczego wynikowy w czasie całkowitym do przeszukania nieuporządkowanej bazy danych jest optymalny?$O(\sqrt{n})$

$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\braket}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}\newcommand{\proj}[1]{\left|#1\right>\left<#1\right|}$ Ponieważ oryginalne pytanie dotyczyło opisu laika, oferuję nieco inne rozwiązanie, być może łatwiejsze do zrozumienia (zależne od tła), oparte na ciągłym czasie ewolucja. (Nie udaję jednak, że nadaje się dla laika).

Zaczynamy od stanu początkowego, który jest jednolitą superpozycją wszystkich stanów, a my staramy się znaleźć stan który można rozpoznać jako poprawną odpowiedź (zakładając, że istnieje dokładnie jeden taki stan, chociaż można go uogólnić). Aby to zrobić, ewoluujemy w czasie pod wpływem hamiltonowskiego Naprawdę piękną cechą poszukiwań Grovera jest to, że w tym momencie możemy zredukować matematykę do podprzestrzeni składającej się tylko z dwóch stanów , zamiast wymagać wszystkich . Łatwiej jest to opisać, jeśli stworzymy ortonormalną podstawę z tych stanów, gdzie | x⟩H=| x⟩⟨x| +| * F⟩⟨* F| . {| x⟩,| * F⟩}2n{| x⟩,| * F⊥⟩}| * F⊥⟩=

$$\ket{\psi}=\frac{1}{\sqrt{2^n}}\sum_{y\in\{0,1\}^n}\ket{y}$$ $\ket{x}$ $$H=\proj{x}+\proj{\psi}.$$ $\{\ket{x},\ket{\psi}\}$$2^n$$\{\ket{x},\ket{\psi^\perp}\}$e-iHt| * F⟩E-It(I+2-nZ+ $$\ket{\psi^{\perp}}=\frac{1}{\sqrt{2^n-1}}\sum_{y\in\{0,1\}^n:y\neq x}\ket{y}.$$ Na tej podstawie ewolucję czasu można zapisać jako gdzie i są standardowymi macierzami Pauliego. Można to przepisać jako Jeśli więc ewoluujemy przez jakiś czas$e^{-iHt}\ket{\psi}$XZe-it(Icos( $$e^{-it\left(\mathbb{I}+2^{-n}Z+\frac{\sqrt{2^n-1}}{2^{n}}X\right)}\cdot\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right),$$ $X$$Z$t= $$e^{-it}\left(\mathbb{I}\cos\left(\frac{t}{2^{n/2}}\right)-i\frac{1}{2^{n/2}}\sin\left(\frac{t}{2^{n/2}}\right)\left(Z+X\sqrt{2^n-1}\right)\right)\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right).$$ $t=\frac{\pi}{2}2^{n/2}$i ignorując fazy globalne, stanem końcowym jest Innymi słowy, z prawdopodobieństwem 1 otrzymujemy stan którego szukaliśmy. Zwykle oparty na obwodzie opis poszukiwania Grovera to tak naprawdę ta ciągła ewolucja czasu podzielona na dyskretne kroki, z niewielką wadą, że zwykle nie można uzyskać dokładnie 1 prawdopodobieństwa dla wyniku, tylko bardzo blisko niego. $$\frac{1}{2^{n/2}}\left(Z+X\sqrt{2^n-1}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right)=\left(\begin{array}{c}\frac{1}{2^n} \\ -\frac{\sqrt{2^n-1}}{2^n} \end{array}\right)+\left(\begin{array}{c} 1-\frac{1}{2^n} \\ \frac{\sqrt{2^n-1}}{2^n}\end{array}\right)=\left(\begin{array}{c} 1 \\ 0 \end{array}\right).$$ $\ket{x}$

Jedno zastrzeżenie jest następujące: możesz przedefiniować i ewoluować używając a czas ewolucji byłby 5 razy krótszy. Jeśli chcesz być naprawdę radykalny, zamień 5 na , a wyszukiwanie Grovera trwa w stałym czasie! Ale nie wolno ci tego robić arbitralnie. Dowolny eksperyment miałby ustaloną maksymalną siłę sprzęgania (tj. Stały mnożnik). Różne eksperymenty mają różne czasy działania, ale ich skalowanie jest takie samo, . To tak, jakby powiedzieć, że koszt bramki w modelu obwodu jest stały, zamiast zakładać, że jeśli użyjemy obwodu o głębokości każdą bramę można uruchomić w czasie .$\tilde H=5H$$\tilde H$$2^{n/2}$$2^{n/2}$$k$$1/k$

Dowód optymalności zasadniczo polega na wykazaniu, że wykrycie jednego możliwego oznaczonego stanu jeszcze szybciej, spowoduje wykrycie innego oznaczonego stanu , wolniej. Ponieważ algorytm powinien działać równie dobrze bez względu na zaznaczony stan, to rozwiązanie jest najlepsze.$\ket{x}$$\ket{y}$

Jednym ze sposobów zdefiniowania operatora dyfuzji jest ¹ , gdzie jest wyrocznią fazową$D = -H^{\otimes n}U_0H^{\otimes n}$$U_0$

$$U_0\left|0^{\otimes n}\right> = -\left|0^{\otimes n}\right>,\,U_0\left|x\right> = \left|x\right>\,\text{for} \left|x\right>\neq\left|0^{\otimes n}\right>.$$

To pokazuje, że można również zapisać jako, co daje gdzie .$U_0$$U_0 = I-2\left|0^{\otimes n}\rangle\langle0^{\otimes n}\right|$

$$D= 2\left|+\rangle\langle+\right| - I,$$ $\left|+\right> = 2^{-n/2}\left(\left|0\right> + \left|1\right>\right)^{\otimes n}$

Zapisywanie stanu gdzie jest ortogonalne do (tj. daje, że .$\left|\psi\right> = \alpha\left|+\right> + \beta\left|+^\perp\right>$$\left|+^\perp\right>$$\left|+\right>$$\left<+^\perp\mid+\right> =0)$$D\left|\psi\right> = \alpha\left|+\right> - \beta\left|+^\perp\right>$

Daje to ^2, że operator dyfuzji jest refleksją na temat$\left|+\right>$

Ponieważ druga część algorytmu Grovera jest również odbiciem, łączą się one, aby obrócić aktualny stan bliżej wartości „poszukiwanej” . Kąt ten zmniejsza się liniowo wraz z liczbą obrotów (do momentu przekroczenia poszukiwanej wartości), co powoduje, że prawdopodobieństwo prawidłowego pomiaru prawidłowej wartości rośnie kwadratowo.$x_0$

Bennet i in. glin. pokazał, że jest to optymalne. Stosując klasyczne rozwiązanie problemu NP, algorytm Grovera można wykorzystać do kwadratowego przyspieszenia tego. Jednak biorąc język dla funkcji zachowania długości (tutaj, wyrocznia), dowolna ograniczona- błąd kwantowej maszyny Turinga nie może zaakceptować tego języka w czasie .$\mathcal L_A = \left\lbrace y:\exists x\, A\left(x\right) = y\right\rbrace$$A$$T\left(n\right)=\mathcal o\left(2^{n/2}\right)$

Osiąga się to poprzez pobranie zestawu wyroczni, w których nie ma odwrotności (więc nie jest zawarte w języku). Jest to jednak zawarte w nowym języku z definicji. Różnica w prawdopodobieństwach maszyny akceptującej i innej maszyny akceptującej w czasie jest wówczas mniejsza niż więc żaden język nie jest akceptowany, a algorytm Grovera jest rzeczywiście asymptotycznie optymalny. ³⁾$\left|1\right>^{\otimes n}$$\mathcal L_{A_y}$$\mathcal L_A$$\mathcal L_{A_y}$$T\left(n\right)$$1/3$

Zalka później wykazał, że algorytm Grovera jest dokładnie optymalny.

---

^{1 W algorytmie Grovera znaki minus można przesuwać dookoła, więc tam, gdzie jest znak minus, jest nieco arbitralne i niekoniecznie musi być w definicji operatora dyfuzji}

^{2 alternatywnie, zdefiniowanie operatora dyfuzji bez znaku minus daje refleksję na temat$\left|+^\perp\right>$}

^{3 Zdefiniowanie maszyny używającej wyroczni jako i maszyny używającej wyroczni jako , wynika to z faktu, że istnieje zbiór ciągów bitów, w których stany i w czasie są zamknij 4 , z licznością . Każdą wyrocznię, w której poprawnie decyduje, czy jest w można odwzorować na wyrocznie, gdzie zawodzi$A$$M^A$$A_y$$M^{A_y}$$S$$M^A$$M^{A_y}$$t$$\epsilon$$<2T^2/\epsilon^2$$M^A$$\left|1\right>^{\otimes n}$$\mathcal L_A$$2^n - \text{Card}\left(S\right)$$M^A$ aby poprawnie zdecydować, czy jest w języku tej wyroczni. Musi jednak podać jedną z pozostałych potencjalnych odpowiedzi, więc jeśli , maszyna nie jest w stanie określ członkostwo w .$\left|1\right>^{\otimes n}$$2^n-1$$T\left(n\right)=\mathcal o\left(2^{n/2}\right)$$\mathcal L_A$}

^{4 Używając odległości euklidesowej, dwukrotnie odległość śladu}