Квантовый алгоритм различения элементов
Постановка задачи
В задаче различения элементов дается список из 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] запросов. Маньез и коллеги [12] показали, что она может быть решена с помощью [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 ребро [math]\displaystyle{ uv }[/math], такое, что [math]\displaystyle{ x_u = x_v = 1 }[/math]. Сколько запросов необходимо для ее решения?
Алгоритм различения элементов может быть адаптирован для решения этой задачи с помощью [math]\displaystyle{ O(N^{2/3}) }[/math] запросов [12], однако соответствующая нижняя граница не найдена. Существует ли лучший алгоритм? Если будет найден лучший алгоритм для задачи поиска коллизии в графе, то сразу же будет разработан лучший алгоритм для задачи о треугольнике.
См. также
Литература
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)
