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

Алгоритм Шегеди и др. [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>. Таким образом: