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

Общая сложность классического алгоритма составляет <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>