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

Алгоритм Шегеди и др. [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). Поскольку G С G0, любой треугольник в G либо лежит в T, либо пересекает E. В первом случае треугольник можно найти за G \ Tin) квантовых запросов посредством поиска по G при помощи алгоритма Гровера для T, известного из процедуры разбиения. Во втором случае можно найти треугольник в G с ребром из E за O(n + Vn3"mln(*'e"s~c'l) квантовых запросов при помощи алгоритма Бурмана и др. [ ], где m = jG \ Ej. Таким образом:

Теорема 2 (Шегеди и коллеги [13, 14]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи O(n1+€ + n1+s+€' + Vn3"e' + ^/n^-^m{S,€-S-€'}) квантовых запросов.