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

Перейти к навигации Перейти к поиску
Строка 83: Строка 83:




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




Строка 92: Строка 92:




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


• Стоимость установки S = r запросов (для опроса всех <math>x_i, i \in T</math>, где <math>v_T</math> – начальное состояние).
• Стоимость установки S = r запросов (для опроса всех <math>x_i, i \in T</math>, где <math>v_T</math> – начальное состояние).


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


• Стоимость проверки C = 0 запросов (значения <math>x_i, i \in T</math> уже известны алгоритму, дальнейших запросов не требуется).
• Стоимость проверки C = 0 запросов (значения <math>x_i, i \in T</math> уже известны алгоритму, дальнейших запросов не требуется).
Строка 107: Строка 107:




Для этой цепи Маркова можно показать, что разрыв собственных значений составляет <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>
Для этой цепи Маркова можно показать, что зазор собственных значений составляет <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>


== Применение ==
== Применение ==
4501

правка

Навигация