Czy istnieje wyjaśnienie dla laika, dlaczego algorytm Grovera działa?

Ten blog autorstwa Scotta Aaronsona jest bardzo przydatnym i prostym wyjaśnieniem algorytmu Shora .

Zastanawiam się, czy istnieje takie wytłumaczenie drugiego najbardziej znanego algorytmu kwantowego: algorytmu Grovera do przeszukiwania nieuporządkowanej bazy danych o wielkości w O ( $O(n)$$O(\sqrt{n})$ czas.

W szczególności chciałbym zobaczyć zrozumiałą intuicję początkowo zaskakującego wyniku czasu!

Jest to dobre wytłumaczenie Craig Gidney tutaj (ma on również inne świetne materiały, w tym symulatorze obwodzie, na swoim blogu ).

Zasadniczo algorytm Grovera ma zastosowanie, gdy masz funkcję, która zwraca Truejedno z możliwych danych wejściowych i Falsewszystkie pozostałe. Algorytm ma za zadanie znaleźć ten, który zwracaTrue .

Aby to zrobić, wyrażamy dane wejściowe jako ciągi bitów i kodujemy je za pomocą $|0\rangle$ i $|1\rangle$ stany ciąg qubitach. Zatem ciąg bitów 0011byłby zakodowany w stanie czterech kubitów $|0011\rangle$ , na przykład.

Musimy także być w stanie zaimplementować tę funkcję za pomocą bramek kwantowych. W szczególności musimy znaleźć sekwencję bramek, które zaimplementują jednostkowe $U$ takie jak

$U | a \rangle = - | a \rangle, \,\,\,\,\,\,\,\,\,\,\,\,\, U | b \rangle = | b \rangle$

gdzie $a$ jest łańcuchem bitowym, dla którego funkcja zwróci, Truea $b$ to dowolny, dla którego zwróci False.

Jeśli zaczniemy od superpozycji wszystkich możliwych ciągów bitów, co jest dość łatwe do zrobienia, po prostu Hadamarding wszystkiego, wszystkie wejścia zaczynają się z tą samą amplitudą $\frac{1}{\sqrt{2^n}}$ (gdzie$n$jest długością szukanych ciągów bitów, a zatem liczbą używanych kubitów). Ale jeśli zastosujemy następnie wyrocznię$U$, amplituda szukanego stanu zmieni się na$-\frac{1}{\sqrt{2^n}}$ .

Nie jest to żadna łatwa do zauważenia różnica, więc musimy ją wzmocnić. Aby to zrobić, używamy Grover Diffusion Operator , $D$ . Efektem tego operatora jest przede wszystkim sprawdzenie, w jaki sposób każda amplituda różni się od średniej amplitudy, a następnie odwrócenie tej różnicy. Więc jeśli pewna amplituda była o pewną wartość większą niż średnia amplituda, stanie się o tę samą wartość mniejszą niż średnia i odwrotnie.

W szczególności, jeśli masz superpozycję ciągach bitów $b_j$ , operator ma skutek dyfuzji

$D: \,\,\,\, \sum_j \alpha_j \, | b_j \rangle \,\,\,\,\,\, \mapsto \,\,\,\,\,\, \sum_j (2\mu \, - \, \alpha_j) \, | b_j \rangle$

gdzie $\mu = \sum_j \alpha_j$ jest średnią amplitudą. Tak więc każda amplituda $\mu + \delta$ zamienia się w $\mu - \delta$ . Aby zobaczyć, dlaczego ma taki efekt i jak go wdrożyć, zapoznaj się z notatkami z wykładów .

Większość amplitud będzie nieco większa niż średnia (z powodu efektu pojedynczego $-\frac{1}{\sqrt{2^n}}$ ), więc dzięki tej operacji staną się nieco mniejsze niż średnia. Niewielka zmiana.

Stan, którego szukamy, będzie silniej dotknięty. Jego amplituda jest znacznie mniejsza niż średnia, a więc stanie się znacznie większa po zastosowaniu operatora dyfuzji. Efektem końcowym operatora dyfuzji jest zatem wywołanie efektu interferencji w stanach, które przesuwają się o amplitudzie $\frac{1}{\sqrt{2^n}}$ od wszystkich błędnych odpowiedzi i dodaje je do właściwej. Powtarzając ten proces, możemy szybko dojść do punktu, w którym nasze rozwiązanie wyróżnia się z tłumu tak bardzo, że możemy je zidentyfikować.

Oczywiście wszystko to pokazuje, że cała praca jest wykonywana przez operatora dyfuzji. Wyszukiwanie to tylko aplikacja, z którą możemy się połączyć.

Zobacz odpowiedzi na inne pytania, aby uzyskać szczegółowe informacje na temat implementacji funkcji i operatora dyfuzji .

Uważam, że podejście graficzne jest całkiem dobre, jeśli chodzi o dawanie wglądu bez nadmiernej wiedzy technicznej. Potrzebujemy danych wejściowych:

• możemy stworzyć stan z niezerową pokrywają się z „oznaczone” państwa | x ⟩ : ⟨ x | * F ⟩ ≠ $|\psi\rangle$$|x\rangle$$\langle x|\psi\rangle\neq 0$ .
• można realizować operację $U_1=-(\mathbb{I}-2|\psi\rangle\langle\psi|)$
• możemy zaimplementować operację .$U_2=\mathbb{I}-2|x\rangle\langle x|$

Ta ostatnia operacja może oznaczać nasz zaznaczony przedmiot fazą -1. Możemy również zdefiniować stan być ortonormalna do | x ⟩ taki, że { | x ⟩ , | * F ⊥ ⟩ } tworzy ortonormalną bazę dla rozpiętości { | x ⟩ , | * F ⟩ } . Obie zdefiniowane przez nas operacje zachowują tę przestrzeń: zaczynasz od jakiegoś stanu w zakresie { | x ⟩ , | * F ⊥ ⟩ $|\psi^\perp\rangle$$|x\rangle$$\{|x\rangle,|\psi^\perp\rangle\}$$\{|x\rangle,|\psi\rangle\}$$\{|x\rangle,|\psi^\perp\rangle\}$i zwracają stan w obrębie zakresu. Co więcej, oba są jednolite, więc zachowana jest długość wektora wejściowego.

Wektor o stałej długości w dwuwymiarowej przestrzeni można zwizualizować jako obwód koła. Ustawmy okrąg z dwoma prostopadłymi kierunkami odpowiadającymi i | x ⟩ . $|\psi^\perp\rangle$$|x\rangle$

$|\psi\rangle$$|x\rangle$$|\psi^\perp\rangle$$|\psi\rangle$$|\psi\rangle$$|\psi^\perp\rangle$$\theta$

$U_1$$|\psi\rangle$$U_2$$|\psi^\perp\rangle$

$U_2$$U_1$$2\theta$$|x\rangle$

$|\psi\rangle$$\theta$$|x\rangle$$x$

$|x\rangle$$|\psi\rangle$$p\ll 1$$O(1/p)$$\sqrt{p}=\sin\theta\approx\theta$$\theta$$r$$\sin((2r+1)\theta)\approx 1$$r\approx \frac{\pi}{2\theta}\approx \frac{\pi}{2\sqrt{p}}$

$1/\sqrt{N}$$\sqrt{N}$$1$