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

'''Запросы о значениях'''. В этом типе запросов входными данными для черного ящика является индекс i, а в качестве ответа он выдает <math>x_i</math>. В квантовой версии этой модели входные данные представляют собой квантовое состояние, которое может быть запутано с рабочим пространством алгоритма. Совместное состояние запроса, регистра ответа и рабочего пространства может быть представлено в виде <math>\sum_{i, y, z} a_{i, y, z} | i, y, z \rangle</math>, причем y – это дополнительный регистр, который будет содержать ответ на запрос, а z – рабочее пространство алгоритма. Черный ящик преобразует это состояние в <math>\sum_{i, y, z} a_{i, y, z} | i, (y + x_i) mod \; m, z \rangle</math>. Простейшим частным случаем является случай, когда входные данные для черного ящика имеют вид <math>\sum_i a_i | i, 0 \rangle</math>. Тогда черный ящик выдает <math>\sum_i a_i | i, x_i \rangle</math>. То есть квантовое состояние, состоящее из индекса i, преобразуется в квантовое состояние, каждый компонент которого содержит <math>x_i</math> вместе с соответствующим индексом i.

Есть несколько причин, в силу которых задача различения элементов интересна для изучения. Во-первых, она связана с сортировкой. Возможность сортировки набора <math>x_1, ... , x_N</math> позволяет решить задачу различения элементов, сначала отсортировав <math>x_1, ... , x_N</math> в порядке возрастания. Если имеются два одинаковых элемента xi = xj, то в отсортированном списке они будут находиться рядом друг с другом. Поэтому после сортировки набора <math>x_1, ... , x_N</math> нужно только проверить отсортированный список, чтобы убедиться, что каждый элемент отличается от следующего. Из-за этой связи между задачами сложность различения элементов равносильна сложности сортировки. Результатом стал длинный список исследований классических нижних границ для задачи различения элементов (см. [6, 8, 15] и многие другие работы).

Задача о различении k элементов (и нахождении k-подмножества) может быть решена с помощью <math>O(N^{k/(k+1)})</math> запросов о значениях с использованием <math>O(N^{k/(k+1)})</math> памяти. Для случая, когда память ограничена <math>r < N^{k/(k+1)}</math> значениями <math>x_i</math>, достаточно использовать <math>O(r + (N^{k/2})/(r^{(k - 1)/2)})</math> запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов).

1. Условный переворот фазы: <math>|T \rangle \to - |T \rangle</math> для всех T, таких, что в нем содержатся i, j, <math>x_i = x_j</math>, и <math>|T \rangle \to |T \rangle</math> для всех остальных T;

2. Квантовое блуждание: выполнить <math>O(\sqrt{r})</math> шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое <math>|T \rangle</math> на комбинацию базисных состояний <math>|T' \rangle</math> для T', которые отличаются от T на один элемент.

Алгоритм ведет еще один квантовый регистр, в котором хранятся все значения <math>x_i, i \in T</math>. Этот регистр обновляется с каждым шагом квантового блуждания.

Это было одно из первых применений квантовых блужданий для построения квантовых алгоритмов. Затем Амбайнис, Кемпе и Ривош [4] обобщили его для поиска на решетках (см. ссылку). Их алгоритм основан на тех же математических идеях, но имеет несколько иную структуру. Вместо чередования шагов квантового блуждания с переворотами фаз, он выполняет квантовое блуждание с двумя различными правилами – «нормальным» и «возмущенным». («Нормальное» правило соответствует блужданию без переворота фазы, а «возмущенное» – комбинации блуждания с переворотом фазы).

Пусть P – несводимая цепь Маркова с пространством состояний X. Предположим, что некоторые состояния в пространстве состояний P ''помечены''. Наша цель – найти помеченное состояние. Это можно сделать с помощью классического алгоритма, который обрабатывает цепь Маркова P до тех пор, пока она не достигнет помеченного состояния (алгоритм 1).

Общая сложность классического алгоритма составляет <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 вершинах, доступный путем запросов к оракулу, и нужно определить, содержит ли граф треугольник (три вершины v1, v2, v3, причем v1 v2, v1 v3 и v2 v3 являются ребрами). Классический подход к решению этой задачи требует Q(n2) запросов. Маньез и коллеги показали, что она может быть решена с помощью O(n1:3 logc n) квантовых запросов, с использованием модифицированного алгоритма различения элементов в качестве подпрограммы. Затем в работе [13] это значение было улучшено до O(n1.3).

Методы Шегеди [14] и Маньеза и коллег [ ] могут быть использованы в качестве подпрограмм для квантовых алгоритмов проверки матричных тождеств [7, 11].

1. Сколько запросов необходимо для решения задачи различения элементов, если доступная алгоритму память ограничена r элементами, r < N2/3? Алгоритм из [2] дает O(N/pr) запросов, а лучшей нижней границей является Q(N213) запросов.

Коллизия в графе [ ]. Начальными условиями являются граф G (произвольный, но известный заранее) и переменные x 1...: ; xN 2 f0; 1g, доступные путем запросов к оракулу. Задача состоит в том, чтобы определить, содержит ли граф G ребро uv, такое, что xu = xv = 1. Сколько запросов необходимо для ее решения?

Алгоритм различения элементов может быть адаптирован для решения этой задачи с помощью O(N2/3) запросов [12], однако соответствующая нижняя граница не найдена. Существует ли лучший алгоритм? Если будет найден лучший алгоритм для задачи поиска коллизии в графе, то сразу же будет разработан лучший алгоритм для задачи о треугольнике.