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

'''Запросы о значениях'''. В этом типе запросов входными данными для черного ящика является индекс 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]. Каждый шаг представляет собой преобразование, которое отображает каждое jTi на комбинацию базисных состояний jT0i для T, которые отличаются от T на один элемент.

Алгоритм ведет еще один квантовый регистр, в котором хранятся все значения xi ;i 2 T. Этот регистр обновляется с каждым шагом квантового блуждания.

Если имеются два элемента i,j такие, что xi = xj, то повторение этих двух преобразований O(N/r) раз увеличивает амплитуды j Ti, содержащих i, j. Измерение состояния алгоритма в этот момент с высокой вероятностью дает множество T, содержащее i, j. Затем из множества T мы можем найти i и j.

Основная структура алгоритма из [ ] похожа на квантовый поиск Гровера, но с одним существенным отличием. В алгоритме Гровера вместо квантового блуждания применяется диффузионное преобразование Гровера. Реализация алгоритма диффузии Гровера требует Q{r) обновлений регистра, хранящего xi ;i 2 T. В отличие от алгоритма диффузии Гровера, каждый шаг квантового блуждания изменяет T на один элемент, требуя только одного обновления списка xi; i 2 T. Таким образом, O(pr) шагов квантового блуждания могут быть выполнены с O(pr) обновлениями, что вчетверо лучше, чем при преобразовании диффузии Гровера. И, как показано в [2], квантовое блуждание обеспечивает достаточно хорошую аппроксимацию диффузии, чтобы алгоритм работал правильно.

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

   2. h раз повторить:

   (б) Смоделировать t\ шагов случайного блуждания, начиная с текущего состояния y.

Обобщение на произвольные цепи Маркова

Шегеди [14] и Маньез и др. [ ] обобщили алгоритмы из [ ] и [ ], соответственно, для ускорения поиска по произвольной цепи Маркова. Основной результат работы [13] состоит в следующем.

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

1. Стоимость настройки S: стоимость выборки начального состояния x из начального распределения.

2. Стоимость обновления U: стоимость моделирования одного шага случайного блуждания.

3. Стоимость проверки C: затраты на проверку помеченности текущего состояния x.

Общая сложность классического алгоритма составляет S + t2(t1U + C). Необходимые t1 и t2 могут быть вычислены из характеристик цепи Маркова P, а именно:

Предложение 1 [ ]. Пусть P – эргодическая, но симметричная цепь Маркова. Пусть S > 0 – зазор собственных значений P, и предположим, что всякий раз, когда множество помеченных состояний M непусто, мы имеем jMj/jXj > e. Тогда существуют t1 = O(l/<5) и t2 = O(l/e), такие, что алгоритм 1 находит помеченный элемент с высокой вероятностью.

Таким образом, стоимость нахождения помеченного элемента классическим способом составляет O(S+ l/e(l/SU + C)). Маньез и коллеги [ ] построили квантовый алгоритм, который находит помеченный элемент за O(S0 + l/e(l/VSU' + C0)) шагов, причем S0, U', С – это квантовые версии затрат на установку, обновление и проверку (в большинстве вариантов применения они того же порядка, что и S, U и C). Это позволяет добиться квадратичного улучшения зависимости как от ", так и от (5.

Задача различения элементов решается частным случаем этого алгоритма – поиском по графу Джонсона. Такое название носит граф, вершины которого 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)). Таким образом, квантовый алгоритм выполняется за время

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