Важная статья 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 ).