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

Задача различения элементов решается частным случаем этого алгоритма – поиском по графу Джонсона. Такое название носит граф, вершины которого vT соответствуют подмножествам TC{1;::::; Ng размера jTj = r. Вершина vT соединена с вершиной vT0, если подмножества T и T отличаются ровно одним элементом. Вершина vT помечена, если T содержит индексы i,j с xi = xj.

Рассмотрим следующую цепь Маркова на графе Джонсона. Начальное распределение вероятностей s является равномерным распределением по вершинам графа Джонсона. На каждом шаге цепь Маркова выбирает следующую вершину vT0 из всех вершин, смежных с текущей вершиной vT, равномерно случайным образом. Во время работы цепи Маркова ведется список всех xi ; i 2 T. Таким образом, стоимости классической цепи Маркова следующие:

• Стоимость установки S = r запросов (для опроса всех xi ; i 2 T, где vT – начальное состояние).

• Стоимость обновления U = 1 запрос (для запроса значения xi ; i 2 T - T, где vT – вершина перед шагом, а vT0 – новая вершина).

• Стоимость проверки C = 0 запросов (значения xi ;i 2 T уже известны алгоритму, дальнейших запросов не требуется).

Квантовые стоимости S0, U', С имеют тот же порядок, что и S, U,C.

Для этой цепи Маркова можно показать, что разрыв собственных значений составляет S = O(1/r), а доля помеченных состояний равна e = O((r2)/(N2)). Таким образом, квантовый алгоритм выполняется за время