4446
правок
Квантовый алгоритм различения элементов: различия между версиями
Материал из WEGA
Квантовый алгоритм различения элементов (посмотреть исходный код)
Версия от 15:43, 8 марта 2023
, 8 марта 2023→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 110: | Строка 110: | ||
== Применение == | == Применение == | ||
Маньез и коллеги [12] показали, как использовать идеи алгоритма различения элементов в качестве подпрограммы для решения задачи о треугольнике [12]. В этой задаче дается граф G на n вершинах, доступный путем запросов к оракулу, и нужно определить, содержит ли граф треугольник (три вершины | Маньез и коллеги [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>. | ||
Методы Шегеди [14] и Маньеза и коллег [ ] могут быть использованы в качестве подпрограмм для квантовых алгоритмов проверки матричных тождеств [7, 11]. | Методы Шегеди [14] и Маньеза и коллег [13] могут быть использованы в качестве подпрограмм для квантовых алгоритмов проверки матричных тождеств [7, 11]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
