Квантовый алгоритм различения элементов

Постановка задачи

В задаче различения элементов дается список из 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(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-подмножества) может быть решена с помощью 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)