Optymalność algorytmu Grovera z dużym prawdopodobieństwem powodzenia

Dobrze wiadomo, że złożoność kwantowej kwerendy błędu ograniczonego funkcji to . Teraz pytanie brzmi: czy chcemy, aby nasz algorytm kwantowy odniósł sukces dla każdego wejścia z prawdopodobieństwem a nie ze zwykłą . Jeśli chodzi o jakie byłyby odpowiednie górne i dolne granice? $OR(x_1,x_2,\ldots, x_n)$ $\Theta(\sqrt{n})$ $1-\epsilon$ $2/3$ $\epsilon$

Natychmiastowe zapytanie wystarcza do wykonania tego zadania poprzez powtórzenie algorytmu Grovera. Ale z tego, co pamiętam, nie jest to wcale optymalne, ponieważ nawet zwykły algorytm Grovera, jeśli jest uruchamiany ostrożnie, tj. Dla odpowiedniej liczby iteracji, może osiągnąć coś takiego jak pomocą tylko iteracje. I dzięki temu można uzyskać poprawę dla wszystkich . Z drugiej strony nie oczekuję, że będzie właściwą odpowiedzią na bardzo małe . $O(\sqrt{n} \log(1/\epsilon))$ $\epsilon=O(1/n)$ $O(\sqrt{n})$ $\epsilon$ $\Omega(\sqrt{n})$ $\epsilon$

Ale jestem zainteresowany, aby zobaczyć, co można pokazać w kategoriach zależnej od kresy dolny i górny dla różnych zakresów zwłaszcza gdy jest bardzo mała, powiedzmy lub dla dużych . $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon= \exp(-\Omega(n))$ $\epsilon=1/n^k$ $k$

(Aby dać kontekst, ogólnym zjawiskiem, do którego dochodzę, jest wzmocnienie w kontekście złożoności kwantowych zapytań.)

cc.complexity-theory ds.algorithms quantum-computing lower-bounds Mohammad Bavarian
źródło

Ten artykuł powinien dostarczyć odpowiedzi na twoje pytania: arxiv.org/abs/cs/9904019v2

John Watrous,

Hmmm Jestem teraz trochę zdezorientowany w przypadku . Wygląda na to, że ten dokument arxiv.org/pdf/quant-ph/9605034v1.pdf stwierdza, że przy iteracjach około można uzyskać wysoki wynik prawdopodobieństwa, tj. . (strona 2 na dole pierwszej kolumny) Z drugiej strony, wspomniany artykuł mówi, na stronie 4 końca sekcji 3, że prawdopodobieństwo błędu jest niemożliwe dla zapytań .

ϵ = \frac{1}{N}

$\epsilon=\frac{1}{N}$

\frac{π}{4} \sqrt{N}

$\frac{\pi}{4}\sqrt{N}$

ϵ = \frac{1}{N}

$\epsilon=\frac{1}{N}$

o (1)

$o(1)$

O (\sqrt{N})

$O(\sqrt{N})$

Mohammad Bavarian

@MohammadBavarian: Myślę, że dzieje się tak tylko w przypadku, gdy znana jest liczba rozwiązań (lub istnieje unikalne rozwiązanie).

Robin Kothari,

Dla kompletności, oto odpowiedź.

Niech oznacza złożoność kwantyfikatora -error obliczania funkcji i będzie funkcją OR na bitach, zdefiniowaną jako . (Zauważ, że różni się to od problemu, w którym obiecano, że dane wejściowe mają dokładnie jeden 1, a celem jest znalezienie tego 1. Problem ten można rozwiązać bez błędów w zapytaniach .) $Q_\epsilon(f)$ $\epsilon$ $f$ $\mathsf{OR}_n$ $n$ $\mathsf{OR}_n(x_1,\ldots,x_n)=\bigvee_{i=1}^n x_i$ $\Theta(\sqrt{n})$

Następnie mamy dla wszystkich , $\epsilon \in [2^{-n},1/3]$

$Q_\epsilon(\mathsf{OR}_n) = \Theta(\sqrt{n\log(1/\epsilon)})$ .

Wynika to z granic dla algorytmów kwantowych o małym błędzie i zerowym błędzie .

W rzeczywistości wiemy coś bardziej ogólnego. Dla wszystkich funkcji symetrycznych , które są funkcjami zależnymi tylko od ciężaru Hamminga wejściowego, mamy to dla wszystkich , $f$ $\epsilon \in [2^{-n},1/3]$

$Q_\epsilon(f) = \Theta(Q_{1/3}(f)+\sqrt{n\log(1/\epsilon)})$ .

Pokazano to w Uwadze na temat algorytmów kwantowych i minimalnego stopnia wielomianów błędów epsilon dla funkcji symetrycznych .

Robin Kothari
źródło

Optymalność algorytmu Grovera z dużym prawdopodobieństwem powodzenia

Odpowiedzi: