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

'''Коллизия в графе''' [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> запросов [ ], однако соответствующая нижняя граница не найдена. Существует ли лучший алгоритм? Если будет найден лучший алгоритм для задачи поиска коллизии в графе, то сразу же будет разработан лучший алгоритм для задачи о треугольнике.