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

27

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(n) czas.

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

Dyskretna jaszczurka
źródło

Odpowiedzi:

20

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 i |1 stany ciąg qubitach. Zatem ciąg bitów 0011byłby zakodowany w stanie czterech kubitów |0011 , 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|za=-|za,U|b=|b

gdzie za 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ą 12)n (gdzienjest 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-12)n .

Nie jest to żadna łatwa do zauważenia różnica, więc musimy ją wzmocnić. Aby to zrobić, używamy Grover Diffusion Operator , re . 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 bjot , operator ma skutek dyfuzji

re:jotαjot|bjotjot(2)μ-αjot)|bjot

gdzie μ=jotαjot jest średnią amplitudą. Tak więc każda amplituda μ+δ zamienia się w μ-δ . 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 -12)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 12)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 .

James Wootton
źródło
4

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 0|ψ|xx|ψ0 .
  • można realizować operację U1=-(ja-2)|ψψ|)
  • możemy zaimplementować operację .U2)=ja-2)|xx|

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 }|ψ|x{|x,|ψ}{|x,|ψ}{|x,|ψ}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 . |ψ|xwprowadź opis zdjęcia tutaj

|ψ|x|ψ|ψ|ψ|ψθwprowadź opis zdjęcia tutaj

U1|ψU2)|ψwprowadź opis zdjęcia tutaj

U2)U12)θ|xwprowadź opis zdjęcia tutaj

|ψθ|xx

|x|ψp1O(1/p)p=grzechθθθrgrzech((2)r+1)θ)1rπ2)θπ2)p

DaftWullie
źródło
3

1/N.N.1

piramidy
źródło