Квантовый алгоритм различения элементов
Постановка задачи
В задаче различения элементов дается список из N элементов [math]\displaystyle{ x_1, ..., x_N \in \{ 1, ..., m \} }[/math] и требуется определить, содержит ли список два одинаковых элемента. Доступ к списку предоставляется путем подачи запросов в «черный ящик», причем возможны два типа запросов.
Запросы о значениях. В этом типе запросов входными данными для черного ящика является индекс i, а в качестве ответа он выдает [math]\displaystyle{ x_i }[/math]. В квантовой версии этой модели входные данные представляют собой квантовое состояние, которое может быть запутано с рабочим пространством алгоритма. Совместное состояние запроса, регистра ответа и рабочего пространства может быть представлено в виде [math]\displaystyle{ \sum_{i, y, z} a_{i, y, z} | i, y, z \rangle }[/math], где y – это дополнительный регистр, который будет содержать ответ на запрос, а z – рабочее пространство алгоритма. Черный ящик преобразует это состояние в [math]\displaystyle{ \sum_{i, y, z} a_{i, y, z} | i, (y + x_i) \; mod \; m, z \rangle }[/math]. Простейшим частным случаем является случай, когда входные данные для черного ящика имеют вид [math]\displaystyle{ \sum_i a_i | i, 0 \rangle }[/math]. Тогда черный ящик выдает [math]\displaystyle{ \sum_i a_i | i, x_i \rangle }[/math]. То есть квантовое состояние, состоящее из индекса i, преобразуется в квантовое состояние, каждый компонент которого содержит [math]\displaystyle{ x_i }[/math] вместе с соответствующим индексом i.
Запросы о сравнениях. В этом типе запросов входные данные для черного ящика состоят из двух индексов i, j, и он выдает один из трех возможных ответов: "[math]\displaystyle{ x_i \gt x_j }[/math]", "[math]\displaystyle{ x_i \lt x_j }[/math]" или "[math]\displaystyle{ x_i = x_j }[/math]". В квантовой версии на вход подается квантовое состояние, состоящее из базисных состояний [math]\displaystyle{ |i, j, z \rangle }[/math], где i, j – два индекса, а z – рабочее пространство алгоритма.
Задача различения элементов интересна для изучения по нескольким причинам. Во-первых, она связана с сортировкой. Возможность сортировки набора [math]\displaystyle{ x_1, ... , x_N }[/math] позволяет решить задачу различения элементов, сначала отсортировав [math]\displaystyle{ x_1, ... , x_N }[/math] в порядке возрастания. Если имеются два одинаковых элемента [math]\displaystyle{ x_i = x_j }[/math], то в отсортированном списке они будут находиться рядом друг с другом. Поэтому после сортировки набора [math]\displaystyle{ x_1, ... , x_N }[/math] нужно только проверить отсортированный список, чтобы убедиться, что каждый элемент отличается от следующего. Из-за этой связи между задачами сложность различения элементов равносильна сложности сортировки. Результатом стал длинный список исследований нижних границ классических алгоритмов для задачи различения элементов (см. [6, 8, 15] и многие другие работы).
Во-вторых, центральным понятием алгоритмов для решения задачи различения элементов является понятие коллизии. Это понятие может быть обобщено разными способами, и его обобщения полезны для построения квантовых алгоритмов для решения разных теоретико-графовых (например, поиска треугольников [12]) и матричных задач (например, проверки матричных тождеств [7]).
Обобщением задачи различения элементов является задача о k-различении элементов [2], в которой нужно определить, существует ли k различных индексов [math]\displaystyle{ i_1, ..., i_k \in \{ 1, ..., N \} }[/math], таких, что [math]\displaystyle{ x_{i_1} = x_{i_2} = \cdots = x_{i_k} }[/math]. Дальнейшим обобщением является задача нахождения k-подмножества [9], в которой задается функция [math]\displaystyle{ f(y_1, ..., y_k) }[/math] и нужно определить, существуют ли [math]\displaystyle{ i_1, ..., i_k \in \{ 1, ..., N \} }[/math], такие, что [math]\displaystyle{ f(x_{i_1}, x_{i_2}, ..., x_{i_k}) = 1 }[/math].
Основные результаты
Различение элементов: краткое изложение результатов
В классическом (неквантовом) контексте естественное решение задачи различения элементов осуществляется путем сортировки, как описано в предыдущем разделе. При этом используется O(N) запросов о значениях (или O(N log N) запросов о сравнении) и O(N log N) времени. Любому классическому алгоритму требуется [math]\displaystyle{ \Omega }[/math](N) запросов о значениях или [math]\displaystyle{ \Omega }[/math](N log N) запросов о сравнении. Для алгоритмов, ограниченных пространством o(N), известны более сильные нижние границы [15].
В квантовом контексте Бурман и коллеги [5] предложили первый нетривиальный квантовый алгоритм, использующий [math]\displaystyle{ O(N^{3/4}) }[/math] запросов. Затем Амбайнис [2] разработал новый алгоритм, основанный на новаторской идее использования квантовых блужданий. Алгоритм Амбайниса использует [math]\displaystyle{ O(N^{2/3}) }[/math] запросов и, как известно, является оптимальным: Ааронсон и Ши [1,3,10] показали, что любой квантовый алгоритм для задачи различения элементов должен использовать [math]\displaystyle{ \Omega(N^{2/3}) }[/math] запросов.
Для квантовых алгоритмов, которые ограничены хранением r значений [math]\displaystyle{ x_i }[/math] (где [math]\displaystyle{ r \lt N^{2/3} }[/math]), время работы лучшего алгоритма составляет [math]\displaystyle{ O(N / \sqrt{r}) }[/math].
Все эти результаты получены для запросов о значениях. Они могут быть адаптированы к модели запросов о сравнениях, при этом сложность увеличится в log N раз. Временная сложность с точностью до полилогарифмического коэффициента [math]\displaystyle{ O(log^c \; N) }[/math] соответствует сложности в запросах, если только вычислительная модель имеет достаточно общий характер [2]. (Для реализации любого из двух известных квантовых алгоритмов необходима квантовая память с произвольным доступом).
Задача о различении k элементов (и нахождении k-подмножества) может быть решена с помощью [math]\displaystyle{ O(N^{k/(k+1)}) }[/math] запросов о значениях с использованием [math]\displaystyle{ O(N^{k/(k+1)}) }[/math] памяти. Для случая, когда память ограничена [math]\displaystyle{ r \lt N^{k/(k+1)} }[/math] значениями [math]\displaystyle{ x_i }[/math], достаточно использовать [math]\displaystyle{ O(r + (N^{k/2})/(r^{(k - 1)/2)}) }[/math] запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов).
Различение элементов: методы
Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями [math]\displaystyle{ |T \rangle }[/math] для всех наборов индексов [math]\displaystyle{ T \subseteq \{ 1, ..., N \} }[/math], |T| = r. Алгоритм начинает с равномерной суперпозиции всех [math]\displaystyle{ |T \rangle }[/math] и многократно применяет последовательность из двух преобразований:
1. Условный переворот фазы: [math]\displaystyle{ |T \rangle \to - |T \rangle }[/math] для всех T, таких, что в нем содержатся i, j, [math]\displaystyle{ x_i = x_j }[/math], и [math]\displaystyle{ |T \rangle \to |T \rangle }[/math] для всех остальных T;
2. Квантовое блуждание: выполнить [math]\displaystyle{ O(\sqrt{r}) }[/math] шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое [math]\displaystyle{ |T \rangle }[/math] на комбинацию базисных состояний [math]\displaystyle{ |T' \rangle }[/math] для T', которые отличаются от T на один элемент.
Алгоритм ведет еще один квантовый регистр, в котором хранятся все значения [math]\displaystyle{ x_i, i \in T }[/math]. Этот регистр обновляется с каждым шагом квантового блуждания.
Если имеются два элемента i, j такие, что [math]\displaystyle{ x_i = x_j }[/math], то повторение этих двух преобразований O(N/r) раз увеличивает амплитуды [math]\displaystyle{ |T \rangle }[/math], содержащих i, j. Измерение состояния алгоритма в этот момент с высокой вероятностью дает множество T, содержащее i, j. Затем из множества T мы можем найти i и j.
Основная структура алгоритма из [2] похожа на квантовый поиск Гровера, но с одним существенным отличием. В алгоритме Гровера вместо квантового блуждания применяется диффузионное преобразование Гровера. Реализация алгоритма диффузии Гровера требует [math]\displaystyle{ \Omega(r) }[/math] обновлений регистра, хранящего [math]\displaystyle{ x_i, i \in T }[/math]. В отличие от алгоритма диффузии Гровера, каждый шаг квантового блуждания изменяет T на один элемент, требуя только одного обновления списка [math]\displaystyle{ x_i, i \in T }[/math]. Таким образом, [math]\displaystyle{ O(\sqrt{r}) }[/math] шагов квантового блуждания могут быть выполнены с [math]\displaystyle{ O(\sqrt{r}) }[/math] обновлениями, что квадратично быстрее, чем при преобразовании диффузии Гровера. И, как показано в [2], квантовое блуждание обеспечивает достаточно хорошую аппроксимацию диффузии, чтобы алгоритм работал правильно.
Это было одно из первых применений квантовых блужданий для построения квантовых алгоритмов. Затем Амбайнис, Кемпе и Ривош [4] обобщили его для поиска на решетках (см. ссылку). Их алгоритм основан на тех же математических идеях, но имеет несколько иную структуру. Вместо чередования шагов квантового блуждания с переворотами фаз, он выполняет квантовое блуждание с двумя различными правилами – «нормальным» и «возмущенным». («Нормальное» правило соответствует блужданию без переворота фазы, а «возмущенное» – комбинации блуждания с переворотом фазы).
1. Инициализировать x состоянием, выбранным из некоторого начального распределения по состояниям P. 2. [math]\displaystyle{ t_2 }[/math] раз повторить: (а) Если текущее состояние y помечено, вывести y и остановить работу алгоритма; (б) Смоделировать [math]\displaystyle{ t_1 }[/math] шагов случайного блуждания, начиная с текущего состояния y. 3. Если алгоритм не завершил выполнение, вывести «Нет помеченного состояния».
Алгоритм 1. Поиск с помощью классического случайного блуждания
Обобщение на произвольные цепи Маркова
Шегеди [14] и Маньез и др. [13] обобщили алгоритмы из [4] и [2], соответственно, для ускорения поиска по произвольной цепи Маркова. Основной результат работы [13] состоит в следующем.
Пусть P – несводимая цепь Маркова с пространством состояний X. Предположим, что некоторые состояния в пространстве состояний P помечены. Наша цель – найти помеченное состояние. Это можно сделать с помощью классического алгоритма, который обрабатывает цепь Маркова P до тех пор, пока она не достигнет помеченного состояния (алгоритм 1).
В сложность алгоритма 1 вносят вклад три типа стоимости:
1. Стоимость настройки S: стоимость выборки начального состояния x из начального распределения.
2. Стоимость обновления U: стоимость моделирования одного шага случайного блуждания.
3. Стоимость проверки C: затраты на проверку помеченности текущего состояния x.
Общая сложность классического алгоритма составляет [math]\displaystyle{ S + t_2(t_1 U + C) }[/math]. Необходимые [math]\displaystyle{ t_1 }[/math] и [math]\displaystyle{ t_2 }[/math] могут быть вычислены из характеристик цепи Маркова P, а именно:
Предложение 1 [13]. Пусть P – эргодическая, но симметричная цепь Маркова. Пусть [math]\displaystyle{ \delta \gt 0 }[/math] – зазор собственных значений P, и предположим, что всякий раз, когда множество помеченных состояний M непусто, мы имеем [math]\displaystyle{ |M| / |X| \ge \epsilon }[/math]. Тогда существуют [math]\displaystyle{ t_1 = O(1 / \delta) }[/math] и [math]\displaystyle{ t_2 = O(1 / \epsilon) }[/math], такие, что алгоритм 1 находит помеченный элемент с высокой вероятностью.
Таким образом, стоимость нахождения помеченного элемента классическим способом составляет [math]\displaystyle{ O(S + 1 / \epsilon (1 / \delta U + C)) }[/math]. Маньез и коллеги [13] построили квантовый алгоритм, который находит помеченный элемент за [math]\displaystyle{ O(S' + 1 / \epsilon (1 / \sqrt{\delta} U' + C')) }[/math] шагов, где S', U', С' – это квантовые версии затрат на установку, обновление и проверку (в большинстве вариантов применения они того же порядка, что и S, U и C). Это позволяет добиться квадратичного улучшения зависимости как от [math]\displaystyle{ \epsilon }[/math], так и от [math]\displaystyle{ \delta }[/math].
Задача различения элементов решается частным случаем этого алгоритма – поиском по графу Джонсона. Такое название носит граф, вершины которого [math]\displaystyle{ v_T }[/math] соответствуют подмножествам [math]\displaystyle{ T \subseteq \{ 1, ..., N \} }[/math] размера |T| = r. Вершина [math]\displaystyle{ v_T }[/math] соединена с вершиной [math]\displaystyle{ v_T' }[/math], если подмножества T и T' отличаются ровно одним элементом. Вершина [math]\displaystyle{ v_T }[/math] помечена, если T содержит индексы i, j, такие, что [math]\displaystyle{ x_i = x_j }[/math].
Рассмотрим следующую цепь Маркова на графе Джонсона. Начальное распределение вероятностей s является равномерным распределением по вершинам графа Джонсона. На каждом шаге цепь Маркова выбирает следующую вершину [math]\displaystyle{ v_T' }[/math] из всех вершин, смежных с текущей вершиной [math]\displaystyle{ v_T }[/math], равномерно случайным образом. Во время работы цепи Маркова ведется список всех [math]\displaystyle{ x_i, i \in T }[/math]. Таким образом, стоимости классической цепи Маркова следующие:
• Стоимость установки S = r запросов (для опроса всех [math]\displaystyle{ x_i, i \in T }[/math], где [math]\displaystyle{ v_T }[/math] – начальное состояние).
• Стоимость обновления U = 1 запрос (для запроса значения [math]\displaystyle{ x_i, i \in T' - T }[/math], где [math]\displaystyle{ v_T }[/math] – вершина перед шагом, а [math]\displaystyle{ v_T' }[/math] – новая вершина).
• Стоимость проверки C = 0 запросов (значения [math]\displaystyle{ x_i, i \in T }[/math] уже известны алгоритму, дальнейших запросов не требуется).
Квантовые стоимости S', U', С' имеют тот же порядок, что и S, U, C.
Для этой цепи Маркова можно показать, что разрыв собственных значений составляет [math]\displaystyle{ \delta = O(1/r) }[/math], а доля помеченных состояний равна [math]\displaystyle{ \epsilon = O((r^2)/(N^2)) }[/math]. Таким образом, квантовый алгоритм выполняется за время [math]\displaystyle{ 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 вершинах, доступный путем запросов к оракулу, и нужно определить, содержит ли граф треугольник (три вершины [math]\displaystyle{ v_1, v_2, v_3 }[/math], причем [math]\displaystyle{ v_1 v_2, v_1 v_3 }[/math] и [math]\displaystyle{ v_2 v_3 }[/math] являются ребрами). Классический подход к решению этой задачи требует [math]\displaystyle{ \Omega(n^2) }[/math] запросов. Маньез и коллеги показали, что она может быть решена с помощью [math]\displaystyle{ O(n^{1,3} \; log^c \; n) }[/math] квантовых запросов, с использованием модифицированного алгоритма различения элементов в качестве подпрограммы. Затем в работе [13] это значение было улучшено до [math]\displaystyle{ O(n^{1,3}) }[/math].
Методы Шегеди [14] и Маньеза и коллег [13] могут быть использованы в качестве подпрограмм для квантовых алгоритмов проверки матричных тождеств [7, 11].
Открытые вопросы
1. Сколько запросов необходимо для решения задачи различения элементов, если доступная алгоритму память ограничена r элементами, [math]\displaystyle{ r \lt N^{2/3} }[/math]? Алгоритм из [2] дает [math]\displaystyle{ O(N/ \sqrt{r}) }[/math] запросов, а лучшей нижней границей является [math]\displaystyle{ \Omega(N^{2/3}) }[/math] запросов.
2. Рассмотрим следующий пример:
Коллизия в графе [12]. Начальными условиями являются граф G (произвольный, но известный заранее) и переменные [math]\displaystyle{ x_1, ..., x_N \in \{ 0, 1 \} }[/math], доступные путем запросов к оракулу. Задача состоит в том, чтобы определить, содержит ли граф G ребро uv, такое, что [math]\displaystyle{ x_u = x_v = 1 }[/math]. Сколько запросов необходимо для ее решения?
Алгоритм различения элементов может быть адаптирован для решения этой задачи с помощью [math]\displaystyle{ O(N^{2/3}) }[/math] запросов [ ], однако соответствующая нижняя граница не найдена. Существует ли лучший алгоритм? Если будет найден лучший алгоритм для задачи поиска коллизии в графе, то сразу же будет разработан лучший алгоритм для задачи о треугольнике.
См. также
Литература
1. Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51 (4), 595-605 (2004)
2. Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210-239 (2007)
3. Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theor. Comput. 1,37-46(2005)
4. Ambainis, A., Kempe, J., Rivosh, A.: In: Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'06), 2006, pp. 1099-1108
5. Buhrman, H., Durr,C., Heiligman, M., Hayer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324-1330 (2005)
6. Borodin, A., Fischer, M., Kirkpatrick, D., Lynch, N.: A time-space tradeoff for sorting on non-oblivious machines. J. Comput. Syst.Sci.22,351-364(1981)
7. Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'06), 2006, pp. 880-889
8. Beame, P., Saks, M., Sun, X., Vee, E.: Time-space trade-off lower bounds for randomized computation of decision problems. J.ACM 50(2), 154-195(2003)
9. Childs, A.M., Eisenberg, J.M.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5,593 (2005)
10. Kutin, S.: Quantum lower bound for the collision problem with small range. Theor. Comput. 1, 29-36 (2005)
11. Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. In: Proceedings of the International Colloquium Automata, Languages and Programming (ICALP'05), 2005, pp. 1312-1324
12. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413^24 (2007)
13. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search by quantum walk. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC'07), 2007, pp. 575-584
14. Szegedy, M.: Quantum speed-up of Markov Chain based algorithms. In: Proceedings of the IEEE Conference on Foundations of Computer Science (FOCS'04), 2004, pp. 32^1
15. Yao, A.: Near-optimal time-space tradeoff for element distinctness. SIAM J. Comput. 23(5), 966-975 (1994)
