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

Предположим, алгоритм Гровера используется для нахождения (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> квантовых запросов.