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

Пусть <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> квантовых запросов.