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

Маньез и коллеги [12] показали, как использовать идеи алгоритма различения элементов в качестве подпрограммы для решения ''задачи о треугольнике'' [12]. В этой задаче дается граф G на n вершинах, доступный путем запросов к оракулу, и нужно определить, содержит ли граф треугольник (три вершины <math>v_1, v_2, v_3</math>, причем <math>v_1 v_2, v_1 v_3</math> и <math>v_2 v_3</math> являются ребрами). Классический подход к решению этой задачи требует <math>\Omega(n^2)</math> запросов. Маньез и коллеги показали, что она может быть решена с помощью <math>O(n^{1,3} \; log^c \; n)</math> квантовых запросов, с использованием модифицированного алгоритма различения элементов в качестве подпрограммы. Затем в работе [13] это значение было улучшено до <math>O(n^{1,3})</math>.