Losowa złożoność zapytań problemu drzew połączonych

Ważny artykuł z 2003 roku autorstwa Childsa i in.wprowadził „problem drzew połączonych”: problem dopuszczający wykładnicze przyspieszenie kwantowe, który nie jest podobny do żadnego innego znanego nam problemu. W tym problemie otrzymaliśmy wykładniczo duży wykres, taki jak ten pokazany poniżej, który składa się z dwóch kompletnych dwójkowych drzewek głębokości n, których liście są połączone losowo. Dostarczono nam etykietę wierzchołka WEJŚCIE. Dostarczono nam również wyrocznię, która podana jako dane wejściowe etykiety dowolnego wierzchołka informuje nas o etykietach sąsiadów. Naszym celem jest znalezienie wierzchołka WYJŚCIA (który można łatwo rozpoznać jako jedyny wierzchołek stopnia 2 na wykresie inny niż wierzchołek WEJŚCIA). Możemy założyć, że etykiety są długimi ciągami losowymi, więc z ogromnym prawdopodobieństwemWierzchołek inny niż WEJŚCIE otrzyma go od wyroczni.

Childs i in. pokazał, że algorytm chodzenia kwantowego jest w stanie po prostu przejść przez ten wykres i znaleźć wierzchołek EXIT po krokach poli (n). Z drugiej strony wykazali również, że dowolny klasyczny algorytm losowy wymaga kroków exp (n), aby znaleźć wierzchołek EXIT z dużym prawdopodobieństwem. Podali swoją dolną granicę jako Ω (2 ^{n / 6} ), ale uważam, że dokładniejsze badanie ich dowodu daje Ω (2 ^{n / 2} ). Intuicyjnie dzieje się tak, ponieważ z ogromnym prawdopodobieństwem losowy spacer na wykresie (nawet samowystarczalny spacer itp.) Utknie w rozległym środkowym obszarze przez wykładniczy czas: za każdym razem, gdy piechur zaczyna zmierzać w kierunku EXIT , znacznie większa liczba krawędzi skierowanych od wyjścia będzie działać jak „siła odpychająca”, która popycha ją z powrotem w kierunku środka.

Sposób, w jaki sformalizowali argument, polegał na pokazaniu, że dopóki nie zostanie odwiedzony ~ 2 ^{n / 2} wierzchołków, losowy algorytm nawet nie znalazł żadnych cykli na wykresie: indukowany podgraph, który jest do tej pory widziany, jest tylko drzewem, nie zapewniając informacje o tym, gdzie może być wierzchołek EXIT.

Interesuje mnie bardziej precyzyjne określenie złożoności losowych zapytań tego problemu. Moje pytanie brzmi:

Czy ktoś może wymyślić klasyczny algorytm, który znajduje wierzchołek EXIT w mniej niż ~ 2 ⁿ krokach - powiedzmy, w O (2 ^{n / 2} ) lub O (2 ^{2n / 3} )? Alternatywnie, czy ktoś może podać dolną granicę lepiej niż Ω (2 ^{n / 2} )?

(Zauważ, że zgodnie z paradoksem urodzinowym nie jest trudno znaleźć cykle na wykresie po krokach O (2 ^{n / 2} ). Pytanie brzmi, czy można użyć cykli, aby uzyskać wskazówki na temat tego, gdzie jest wierzchołek EXIT.)

Jeśli ktokolwiek może poprawić dolną granicę przeszłości Ω (2 ^{n / 2} ), to według mojej wiedzy, byłby to pierwszy możliwy do udowodnienia przykład problemu czarnej skrzynki z wykładniczym przyspieszeniem kwantowym, którego złożoność losowych zapytań jest większa niż √N . (Gdzie N ~ 2 ⁿ jest rozmiarem problemu.)

Aktualizacja: Dowiedziałem się od Andrew Childsa, że ​​w tej notatce Fenner i Zhang wyraźnie poprawiają losową dolną granicę dla drzew połączonych do Ω (2 ^{n / 3} ). Gdyby byli gotowi zaakceptować stałe (raczej niż wykładniczo małe) prawdopodobieństwo sukcesu, uważam, że mogliby jeszcze bardziej poprawić granicę, do Ω (2 ^{n / 2} ).

$O(n2^{n/2})$

$n/2$$O(2^{n/2})$$n+1$$X$$n+1$

$X$$Y$$O(2^{n/2})$$n/2$$Y$$n/2$$X$$Y$$Y$$O(2^{n/2})$$X_2$$n+2$

$n+3$$X_2$$n/2$$n/2$$X_2$

$n$$O(n2^{n/2})$

$X_t$$X_{t+1}$$t$$n/2$$t+2^{n/2}$$t$$n/2$$t+2^{n/2}$$X_t$.