Квантовый алгоритм различения элементов
Постановка задачи
В задаче различения элементов дается список из 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] в порядке возрастания. Если имеются два одинаковых элемента xi = xj, то в отсортированном списке они будут находиться рядом друг с другом. Поэтому после сортировки набора [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(NlogN) запросов о сравнении) и O(NlogN) времени. Любому классическому алгоритму требуется £2(N) запросов о значениях или £2(NlogN) запросов о сравнении. Для алгоритмов, ограниченных пространством o(N), известны более сильные нижние границы [15].
В квантовом контексте Бурман и коллеги [5] предложили первый нетривиальный квантовый алгоритм, использующий O(N3/4) запросов. Затем Амбайнис [2] разработал новый алгоритм, основанный на новаторской идее использования квантовых блужданий. Алгоритм Амбайниса использует O(N2/3) запросов и, как известно, является оптимальным: Ааронсон и Ши [1,3,10] показали, что любой квантовый алгоритм для задачи различения элементов должен использовать Q(N213) запросов.
Для квантовых алгоритмов, которые ограничены хранением r значений xi (где r < N2/3), время работы лучшего алгоритма составляет O(N/pr).
Все эти результаты получены для запросов о значениях. Они могут быть адаптированы к модели запросов о сравнениях, при этом сложность увеличится в logN раз. Временная сложность с точностью до полилогарифмического коэффициента O(logc N) соответствует сложности в запросах, если только вычислительная модель имеет достаточно общий характер [ ]. (Для реализации любого из двух известных квантовых алгоритмов необходима квантовая память с произвольным доступом).
Задача о различении k элементов (и нахождении k-подмножества) может быть решена с помощью O(Nk/(k+1)) запросов о значениях и использования O(Nk/(k+1)) памяти. Для случая, когда память ограничена r < Nk/(k+1) значениями xi, достаточно использовать O(r + (Nkl2)/(r(k~1)l2)) запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов).
Различение элементов: методы
Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями jTi для всех наборов индексов T С {1,... ; Ng с jTj = r. Алгоритм начинает с равномерной суперпозиции всех j Ti и многократно применяет последовательность из двух преобразований: 1. Условный переворот фазы: j T -> - T i для всех T, таких, что Г содержит i, j с xi = xj, и j Ti !j T i для всех остальных T; 2. Квантовое блуждание: выполнить O(pr) шагов квантового блуждания согласно определению в работе [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] обобщили его для поиска на решетках (см. ссылку). Их алгоритм основан на тех же математических идеях, но имеет несколько иную структуру. Вместо чередования шагов квантового блуждания с переворотами фаз, он выполняет квантовое блуждание с двумя различными правилами – «нормальным» и «возмущенным». («Нормальное» правило соответствует блужданию без переворота фазы, а «возмущенное» – комбинации блуждания с переворотом фазы).
1. Инициализировать x состоянием, выбранным из некоторого начального распределения по состояниям P. 2. h раз повторить: (а) Если текущее состояние y помечено, вывести y и остановить работу алгоритма; (б) Смоделировать t\ шагов случайного блуждания, начиная с текущего состояния y. 3. Если алгоритм не завершил выполнение, вывести «Нет помеченного состояния».
Алгоритм 1. Поиск с помощью классического случайного блуждания
Обобщение на произвольные цепи Маркова
Шегеди [14] и Маньез и др. [ ] обобщили алгоритмы из [ ] и [ ], соответственно, для ускорения поиска по произвольной цепи Маркова. Основной результат работы [13] состоит в следующем.
Пусть P – несводимая цепь Маркова с пространством состояний X. Предположим, что некоторые состояния в пространстве состояний P помечены. Наша цель – найти помеченное состояние. Это можно сделать с помощью классического алгоритма, который обрабатывает цепь Маркова P до тех пор, пока она не достигнет помеченного состояния (алгоритм 1).
В сложность алгоритма 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) запросов.
2. Рассмотрим следующий пример: Коллизия в графе [ ]. Начальными условиями являются граф G (произвольный, но известный заранее) и переменные x 1...: ; xN 2 f0; 1g, доступные путем запросов к оракулу. Задача состоит в том, чтобы определить, содержит ли граф G ребро uv, такое, что xu = xv = 1. Сколько запросов необходимо для ее решения? Алгоритм различения элементов может быть адаптирован для решения этой задачи с помощью O(N2/3) запросов [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)