Algorytm Runtime of Grover

19

Jaka jest złożoność czasowa (nie złożoność zapytań) algorytmu Grovera? Wydaje mi się jasne, że jest to ponieważ istnieją iteracje i każda iteracja wymaga użycia operacji odbicia, która z kolei wymaga czasu przy użyciu dowolnego standardowego zestawu bram uniwersalnych. $\Omega(\log(N) \sqrt{N})$ $\Omega(\sqrt{N})$ $\Omega(\log(N))$

Problem polega na tym, że nie mogę znaleźć ani jednego odniesienia, które mówi, że złożoność algorytmu Grovera to . Wikipedia i kilka innych stron internetowych mówi złożoności czasowej . Artykuł Grovera twierdzi, że „kroki” to . $\Omega(\log(N) \sqrt{N})$ $O(\sqrt{N})$ $O(\sqrt{N})$

Czy coś brakuje? Być może ludzie określają operację odbicia, aby zajmowała czas jednostkowy. Ale to nie ma dla mnie sensu, ponieważ jeśli możemy zagrać w grę pozwalającą arbitralnym jednostkom zajmować czas jednostkowy, nie byłoby różnicy między złożonością zapytania a złożonością czasową.

reference-request quantum-computing time-complexity

— Dan Stahlke
źródło

11

Nie mogę wymyślić odniesienia, które mówi o złożoności czasowej algorytmu Grovera, ale to, co napisałeś, jest prawdą. W rzeczywistości, dla dowolnego zestawu skończonych bram, operacje wykonywane między zapytaniami w algorytmie Grovera wymagają co najmniej bramek , ponieważ każda brama ma skończoną szerokość, ale musimy wykonać bramę, która wpływa na wszystkie kubity

Ω (\log N)

$\Omega(\log N)$

\log N

$\log N$

— Robin Kothari

11

Pytanie jest zwykle uważane za dyskusyjne z następującego powodu. Algorytm Grovera jest kombinatorycznym algorytmem wyszukiwania służącym do znalezienia rozwiązania dla dowolnego predykatu. Chociaż tak, jest złożonością bramki kwantowej na każdym etapie algorytmu czarnej skrzynki, należy również obliczyć predykat. Złożoność bramki kwantowej to , ponieważ inaczej nie odczytałby całego wejścia i można by odrzucić niektóre bity wejściowe z wyszukiwania. Z drugiej strony ciekawy predykat może zająć o wiele więcej czasu. Stąd liczba połączeń do predykatu jest uważana za standardową monetę, podobnie jak w przypadku klasycznego analogu algorytmu Grovera, a mianowicie losowego zgadywania. $\Theta(\log N)$ $\Omega(\log N)$

— Greg Kuperberg
źródło

6

$O(\sqrt{N}\log N)$ $\Omega(\sqrt{N}\log N)$

$O(\sqrt{N})$ $O(\sqrt{N}\log(\log^* N))$

$\log(\log^* N)$ $N$ $\log(\log^* N)$

— Robin Kothari
źródło