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

Маньез и коллеги [12] показали, как использовать идеи алгоритма различения элементов в качестве подпрограммы для решения задачи о треугольнике [12]. В этой задаче дается граф G на n вершинах, доступный путем запросов к оракулу, и нужно определить, содержит ли граф треугольник (три вершины v1, v2, v3, причем v1 v2, v1 v3 и v2 v3 являются ребрами). Классический подход к решению этой задачи требует Q(n2) запросов. Маньез и коллеги показали, что она может быть решена с помощью O(n1:3 logc n) квантовых запросов, с использованием модифицированного алгоритма различения элементов в качестве подпрограммы. Затем в работе [13] это значение было улучшено до O(n1.3).

Методы Шегеди [14] и Маньеза и коллег [ ] могут быть использованы в качестве подпрограмм для квантовых алгоритмов проверки матричных тождеств [7, 11].