Рандомизированная сложность запроса для проблемы со связанными деревьями

23

Важная статья 2003 года Childs et al.представил «проблему соединенных деревьев»: проблему, допускающую экспоненциальное квантовое ускорение, которое не похоже ни на одну другую подобную проблему, о которой мы знаем. В этой задаче нам дан экспоненциально большой граф, подобный изображенному ниже, который состоит из двух полных двоичных деревьев глубины n, листья которых связаны друг с другом случайным циклом. Нам предоставлена ​​метка вершины ВХОДА. Мы также снабжаем оракулом, который в качестве входных данных дает метку любой вершины, которая сообщает нам метки ее соседей. Наша цель - найти вершину EXIT (которую легко распознать как единственную вершину степени 2 в графе, отличную от вершины ENTRANCE). Мы можем предположить, что метки - это длинные случайные строки, так что с подавляющей вероятностьювершина, отличная от вершины ВХОДА, должна быть передана ему оракулом.

Чайлдс и соавт. показал, что алгоритм квантового блуждания способен просто проходить через этот граф и находить вершину EXIT после поли (n) шагов. Напротив, они также показали, что любой классический рандомизированный алгоритм требует exp (n) шагов, чтобы найти вершину EXIT с высокой вероятностью. Они указали свою нижнюю границу как Ω (2 n / 6 ), но я полагаю, что более тщательное изучение их доказательства дает Ω (2 n / 2 ). Интуитивно это объясняется тем, что с огромной вероятностью случайное блуждание на графике (даже самообучение и т. Д.) Застрянет в обширной средней области на экспоненциальный промежуток времени: всякий раз, когда бродяга начинает двигаться к выходу. гораздо большее число ребер, направленных в сторону от выхода, будет действовать как «сила отталкивания», которая отталкивает его назад к середине.

Они формализовали аргумент, чтобы показать, что до тех пор, пока он не посетил ~ 2 n / 2 вершин, рандомизированный алгоритм даже не нашел циклов в графе: индуцированный подграф, который он видел до сих пор, - это просто дерево, информация о том, где может быть вершина ВЫХОДА.

Я заинтересован в том, чтобы более точно определить сложность рандомизированных запросов. У меня вопрос такой:

Может кто-нибудь придумать классический алгоритм, который находит вершину EXIT менее чем за ~ 2 n шагов - скажем, в O (2 n / 2 ) или O (2 2n / 3 )? В качестве альтернативы, может ли кто-нибудь дать оценку ниже, чем Ω (2 n / 2 )?

(Обратите внимание, что по парадоксу дня рождения нетрудно найти циклы в графе после O (2 n / 2 ) шагов. Вопрос в том, можно ли использовать циклы, чтобы получить какие-либо подсказки о том, где находится вершина EXIT.)

Если кто-нибудь сможет улучшить нижнюю границу за Ω (2 n / 2 ), то, насколько мне известно, это послужит самым первым доказуемым примером проблемы черного ящика с экспоненциальным квантовым ускорением, сложность рандомизированного запроса которого превышает √N. , (Где N ~ 2 n - размер проблемы.)

Обновление: я узнал от Эндрю Чайлдса, что в этой заметке Феннер и Чжан явно улучшают рандомизированную нижнюю границу для соединенных деревьев до Ω (2 n / 3 ). Если бы они были готовы принять постоянную (а не экспоненциально малую) вероятность успеха, я полагаю, что они могли бы еще больше улучшить оценку до Ω (2 n / 2 ).

введите описание изображения здесь

Скотт Ааронсон
источник

Ответы:

22

Я думаю, что у меня есть детерминированный алгоритм, который находит выход в оракулов.O(n2n/2)

Сначала найдите метки для всех вершин расстояния от входа. Это берет запросов. Затем начните со входа и пройдите шаг, чтобы добраться до узла на расстоянии от входа. Мы постараемся добраться до выхода из этого узла.n/2O(2n/2)n+1Xn+1

У нас есть два варианта, куда идти от , и мы хотим выбрать тот, который ближе к выходу. Чтобы сделать это, выберите один из вариантов произвольно, прибыв в узле . Затем изучить все способы ходьбы шагов от . Если один из них дает метку расстояния от входа, мы знаем, что переход от к был неправильным выбором. В противном случае был правильным выбором. Таким образом, в мы нашли узел на расстоянии от входа.Y O ( 2XYO(2n/2)n/2Yn/2XYYO(2n/2)X2n+2

Мы можем продолжать идти по этому пути. Чтобы найти узел расстояния от входа, мы начинаем с и два произвольных шага. Затем изучить все варианты прогулок дополнительных шагов (при этом никогда не шел в обратном направлении), и проверить , если любой из них расстояние от входа. Это произойдет, если и только если первый шаг, который мы прошли от был неверным.n+3X2n/2n/2X2

Чтобы добраться до выхода, нужно сделать это раз, всего вызовов оракула. Кроме того, что может быть удивительно, этот алгоритм является детерминированным.O ( n 2 n / 2 )nO(n2n/2)

Редактировать: просто чтобы уточнить, чтобы перейти от к , мы пройдем произвольных шагов, затем запустим поиск на глубину , в общей сложности шагов. Если первый шаг отводил от выхода, то все первые шагов делались, и поэтому мы находим метку расстояния от входа. Это означает, что шагов достаточно для определения следующего отдельного шага, который нужно сделать из .XtXt+1tn/2t+2n/2tn/2t+2n/2Xt

Шалев
источник
Я не понимаю Чтобы найти , вы должны сделать произвольных шагов из а затем дополнительных шага? Разве это не даст шагов, что слишком много? Xt+1tXtn/22t2n/2
domotorp
У меня вторая домоторпская растерянность. Не правда ли, что чем ближе вы к выходу, тем длиннее путь, который вам понадобится, чтобы добраться до одной из точек, которые вы запрашивали в начале? Тем не менее, может быть, вы могли бы использовать тот факт, что пути, начинающиеся рядом с выходом, с большой вероятностью будут двигаться влево к центру, пока не достигнут его? (Это добавит немного рандомизации в ваш алгоритм.)2n/2
Скотт Ааронсон,
Если подумать, что если мы воспользуемся тем фактом, что из любой вершины в правой половине графика у вас есть 1/2 шанс выбрать направление, которое неизбежно приведет вас обратно к центру? Этого может быть достаточно, чтобы отвлечь нас от вершины EXIT на n / 2, что позволило бы нам найти саму вершину EXIT с помощью дальнейших запросов. 2n/2
Скотт Ааронсон
1
Чтобы найти , сделайте произвольных шагов из , но только один раз . Это занимает шагов, а не шагов. Затем сделайте шагов всеми возможными способами . Это занимает шагов. Итого: . Я использую тот факт , что если первые из шагов было не так, то все из этих шагов уводят от выхода (и обратно к входу). Это перестает иметь место после первых шагов, поэтому вам нужно начать исчерпывающий поиск. т Х т т 2 т н / 2 2 н / 2 т + 2 н / 2 т т тXt+1tXtt2tn/22n/2t+2n/2ttt
Шалев
1
Идея начать поиск с двух сторон и привести к улучшению функции sqrt () по сравнению с простым алгоритмом, известна как двунаправленный поиск и неоднократно открывалась независимо друг от друга в различных контекстах, например при планировании маршрута на картах Google. Оригинальная ссылка, кажется,: GB Dantzig. Линейное программирование и расширения. Издательство Принстонского университета, 1962.
Алекс Лопес-Ортис