Algorytm Runtime of Grover

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ą.

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.Ω ( log N $\Theta(\log N)$$\Omega(\log N)$

$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)$