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

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

'''Теорема 1 (Бурман и коллеги [6]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи <math>O(n + \sqrt{nm} ) \;</math> квантовых запросов.'''