Квантовый алгоритм поиска треугольников: различия между версиями

Предположим, алгоритм Гровера используется для нахождения (a) ребра <math>(a, b) \in G \;</math> среди всех <math>\tbinom{n}{2} \;</math> потенциальных ребер и (b) вершины <math>c \in [n] \;</math>, такой, что (a, b, c) является треугольником в G. Стоимость шагов (a) и (b) составляет <math>O( \sqrt{n^2/m} ) \;</math> и <math>O( \sqrt{n} ) \;</math> квантовых запросов, соответственно. Если граф G содержит треугольник <math>\Delta \;</math>, то шаг (a) найдет ребро (a, b), принадлежащее <math>\Delta \;</math>, с вероятностью <math>\Omega (1/m) \;</math>, а шаг (b) найдет третью вершину с треугольника <math>\Delta = (a, b, c) \;</math> с константной вероятностью. Таким образом, шаги (a) и (b) совместно находят треугольник с вероятностью <math>\Omega (1/m) \;</math>. Повторяя эти шаги <math>O( \sqrt{m} ) \;</math> раз с использованием техники увеличения амплитуды (Брассар и коллеги [5]), можно найти треугольник с вероятностью 2/3. Общая стоимость составит <math>O( \sqrt{m} ( \sqrt{n^2/m} + \sqrt{n} )) = O( n + \sqrt{nm} ) \;</math> квантовых запросов. Таким образом:

Пусть <math>\mu^2 \;</math> – полный граф на вершинах <math>\mu \subseteq [n] \;</math>, <math>vV_G(v) \;</math> – множество вершин, смежных с вершиной v, а <math>deg_G(v) \;</math> – степень вершины v. Отметим, что для любой вершины <math>v \in [n] \;</math> можно либо найти треугольник в G, содержащий v, либо удостовериться в том, что <math>G \subseteq [n]^2 \setminus v_G(v)^2 \;</math>, при помощи <math>\tilde{O} (n) \;</math> квантовых запросов с вероятностью успеха <math>1 - 1/n^3 \;</math>. Для этого вначале необходимо вычислить <math>v_G(v) \;</math> классическим способом, а затем применить механизм поиска Гровера логарифмическое количество раз, чтобы найти ребро графа G в <math>v_G(v)^2 \;</math> с высокой вероятностью, если таковое существует. Шегеди и коллеги [13, 14] использовали это наблюдение для разработки алгоритма поиска треугольников, не использующего других квантовых процедур, кроме увеличения амплитуды (как и алгоритм Бурмана и др. [6]), но требующего только <math>\tilde{O} (n^{10/7} ) \;</math> квантовых запросов.

Алгоритм Шегеди и др. [13, 14] работает следующим образом. Вначале следует равномерно выбрать <math>k = \tilde{O} (n^{\epsilon} ) \;</math> вершин <math>v_1, ..., v_k \;</math> случайным образом из множества [n] без замены и вычислить каждое значение <math>v_G(v_i) \;</math>. За <math>\tilde{O} (n^{1 + \epsilon} ) \;</math> квантовых запросов можно либо найти треугольник в графе G, содержащий одну из вершин <math>v_i \;</math>, либо с высокой вероятностью заключить, что <math>G \subseteq G' := [n]^2 \setminus U_i v_G(v_i)^2 \;</math>. Предположим, что имеет место второй вариант. Тогда можно показать, что с высокой вероятностью может быть построено разбиение (T, E) графа G', такое, что T содержит <math>O(n^{3 - \epsilon ' } ) \;</math> треугольников и <math>E \cap G \;</math> имеет размер <math>O(n^{2 - \delta } + n^{2 - \epsilon + \delta + \epsilon ' } ) \;</math>, за <math>\tilde{O} (n^{1 + \delta + \epsilon '} ) \;</math> запросов (либо в процессе построения может быть найден треугольник в G). Поскольку <math>G \subseteq G' \;</math>, любой треугольник в G либо лежит в T, либо пересекает E. В первом случае треугольник можно найти в <math>G \cap T \;</math> за <math>O( \sqrt{n^{3 - \epsilon ' }} ) \;</math> квантовых запросов посредством поиска по G при помощи алгоритма Гровера для T, известного из процедуры разбиения. Во втором случае можно найти треугольник в G с ребром из E за <math>\tilde{O} ( n + \sqrt{n^{3 - min \{ \delta, \; \epsilon - \delta - \epsilon ' \} }} )</math> квантовых запросов при помощи алгоритма Бурмана и др. [6], где <math>m = | G \cap E | \;</math>. Таким образом:

Рассмотрим задачу поиска ''коллизии в графе'' на примере графа <math>G \subseteq [n]^2 \;</math>, где f определяет бинарное отношение <math>C \subseteq [n]^2 \;</math>, удовлетворяющее <math>C(u, u') \;</math>, если <math>f(u) = f(u') = 1 \;</math> и <math>(u, u') \in G \;</math>. Процедура поиска Амбайниса решает эту задачу за <math>\tilde{O} (n^{2/3}) \;</math> квантовых запросов при помощи следующих рассуждений. Зафиксируем <math>k = 2 \;</math> и <math>r = n^{2/3} \;</math> в алгоритме задачи k-коллизии и для каждого <math>U \subseteq [n] \;</math> определим <math>D(U) = \{ (v, f(v)) : v \in U \} \;</math> и <math>\Phi (D(U)) = 1 \;</math>, если некоторые <math>u, u' \in U \;</math> удовлетворяют C. В таком случае для построения D(U) необходимо s(r) = r начальных запросов f(v), u(r) = 1 новый запрос f(v) необходим для обновления D(U), c(r) = 0 дополнительных запросов f(v) необходимо для проверки условия <math>\Phi(D(U)) \;</math>. Таким образом, всего требуется <math>\tilde{O} (r + \frac{n}{r} ( \sqrt{r} )) = \tilde{O} ( n^{2/3} ) \;</math> запросов.

Маньез и коллеги [13] решают задачу нахождения треугольников, сводя ее к задаче поиска коллизии в графе. Вновь зафиксируем <math>k = 2 \;</math> и <math>r = n^{2/3} \;</math>. Пусть C – множество ребер, содержащее по меньшей мере один треугольник. Определим <math>D(U) = G|_U \;</math> и <math>\Phi(D(U)) = 1 \;</math>, если некоторое ребро в <math>G|_U \;</math> удовлетворяет С. Тогда для построения D(U) потребуется <math>s(r) = O(r^2) \;</math> начальных запросов, а для его обновления – u(r) = r новых запросов. Остается найти границу стоимости проверки c(r). Для любой вершины <math>v \in [n] \;</math> рассмотрим оракул <math>f_v \;</math>, связанный с коллизией в графе на <math>G|_U \;</math> и удовлетворяющий условию: <math>f_v(u) = 1 \;</math>, если <math>(u, v) \in G \;</math>. Ребро <math>G|_U \;</math> является треугольником в G в том и только том случае, если это ребро является решением задачи поиска коллизии в графе на <math>G|_U \;</math> для некоторого <math>v \in [n] \;</math>. Эта задача может быть решена для конкретной v за <math>\tilde{O} (r^{2/3} ) \;</math> запросов. Используя <math>\tilde{O} ( \sqrt{n}) \;</math> шагов увеличения амплитуды, можно с высокой вероятностью узнать, генерирует ли ''какая-либо'' из вершин <math>v \in [n] \;</math> приемлемое решение для задачи поиска коллизии в графе. Таким образом, стоимость проверки составляет <math>c(r) = \tilde{O} ( \sqrt{n} \cdot r^{2/3} ) \;</math> запросов, из чего следует:

Расширение алгоритма квантового блуждания для поиска треугольников использовалось для нахождения клик и других фиксированных подграфов, а также для определения выполнения монотонных свойств графа с малыми сертификатами при помощи меньшего числа квантовых запросов, чем у предыдущих алгоритмов.

Алгоритм Амбайниса для поиска k-коллизии [3] может найти копию любого графа H с k > 3 вершинами за <math>\tilde{O} (n^{2 - 2/(k + 1)}) \;</math> квантовых запросов. Для случая, когда H является k-кликой, Чайлдз и Айзенберг [9] предложили алгоритм, требующий <math>\tilde{O} (n^{2.5 - 6/(k + 2)}) \;</math> запросов. Простое обобщение алгоритма поиска треугольников (Маньез и др. [13] уменьшает их число до <math>\tilde{O} (n^{2 - 2/k}) \;</math>.

Наиболее очевидный из открытых вопросов касается решения проблемы сложности квантовых запросов при поиске треугольников; на данный момент лучшими верхней и нижней границей являются <math>O(n^{13/10}) \;</math> и <math>\Omega(n) \;</math>. Кроме того, остаются нерешенными следующие задачи:

Технология квантового блуждания успешно применялась при разработке более эффективных алгоритмов квантового поиска для нескольких задач – таких как различение элементов [3], поиск треугольников [13], верификация матричного произведения [7] и проверка коммутативности групп [11]. Было бы любопытно узнать, как подход на основе квантового блуждания может быть расширен для получения новых и улучшенных квантовых алгоритмов для решения различных вычислительных задач.