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