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

Маньез и коллеги [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>.

'''Коллизия в графе''' [12]. Начальными условиями являются граф G (произвольный, но известный заранее) и переменные <math>x_1, ..., x_N \in \{ 0, 1 \}</math>, доступные путем запросов к оракулу. Задача состоит в том, чтобы определить, содержит ли граф G ребро uv, такое, что <math>x_u = x_v = 1</math>. Сколько запросов необходимо для ее решения?

Алгоритм различения элементов может быть адаптирован для решения этой задачи с помощью <math>O(N^{2/3})</math> запросов [ ], однако соответствующая нижняя граница не найдена. Существует ли лучший алгоритм? Если будет найден лучший алгоритм для задачи поиска коллизии в графе, то сразу же будет разработан лучший алгоритм для задачи о треугольнике.