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

Общая сложность классического алгоритма составляет <math>S + t_2(t_1 U + C)</math>. Необходимые <math>t_1</math> и <math>t_2</math> могут быть вычислены из характеристик цепи Маркова P, а именно:

Предложение 1 [13]. Пусть P – эргодическая, но симметричная цепь Маркова. Пусть <math>\delta > 0</math> – зазор собственных значений P, и предположим, что всякий раз, когда множество помеченных состояний M непусто, мы имеем <math>|M| / |X| \ge \epsilon</math>. Тогда существуют <math>t_1 = O(1 / \delta)</math> и <math>t_2 = O(1 / \epsilon)</math>, такие, что алгоритм 1 находит помеченный элемент с высокой вероятностью.

Задача различения элементов решается частным случаем этого алгоритма – поиском по графу Джонсона. Такое название носит граф, вершины которого <math>v_T</math> соответствуют подмножествам <math>T \subseteq \{ 1, ..., N \}</math> размера |T| = r. Вершина <math>v_T</math> соединена с вершиной <math>v_T'</math>, если подмножества T и T' отличаются ровно одним элементом. Вершина <math>v_T</math> ''помечена'', если T содержит индексы i, j, такие, что <math>x_i = x_j</math>.

Рассмотрим следующую цепь Маркова на графе Джонсона. Начальное распределение вероятностей s является равномерным распределением по вершинам графа Джонсона. На каждом шаге цепь Маркова выбирает следующую вершину <math>v_T'</math> из всех вершин, смежных с текущей вершиной <math>v_T</math>, равномерно случайным образом. Во время работы цепи Маркова ведется список всех <math>x_i, i \in T</math>. Таким образом, стоимости классической цепи Маркова следующие:

• Стоимость обновления U = 1 запрос (для запроса значения <math>x_i, i \in T' - T</math>, где <math>v_T</math> – вершина перед шагом, а <math>v_T'</math> – новая вершина).

Для этой цепи Маркова можно показать, что разрыв собственных значений составляет <math>\delta = O(1/r)</math>, а доля помеченных состояний равна <math>\epsilon = O((r^2)/(N^2))</math>. Таким образом, квантовый алгоритм выполняется за время <math>O \bigg( S' + \frac{1}{\sqrt{\epsilon}} \bigg( \frac{1}{\sqrt{\delta}} U' + C' \bigg) \bigg) = O \bigg( S' + \sqrt{r} \bigg( \frac{N}{r} U' + C' \bigg) \bigg) = O \bigg( r + \frac{N}{\sqrt{r}} \bigg) .</math>

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