Квантовый алгоритм поиска треугольников

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

Треугольник представляет собой клику размера 3 в неориентированном графе. Поиск треугольников является фундаментальной вычислительной проблемой, временная сложность которой тесно связана со сложностью умножения матриц. В последние годы она широко исследовалась как задача базового поиска, сложность квантовых запросов для которой все еще неясна – в противоположность задаче неструктурированного поиска [4, 10] и задаче различения элементов [1, 3]. Данный обзор рассматривает алгоритмы квантового поиска для нахождения треугольников.

Нотация и ограничения

Алгоритм квантового запроса [math]\displaystyle{ Q_f : | \psi_0 \rangle \mapsto | \psi_f \rangle \; }[/math] вычисляет свойство P функции f при помощи отображения исходного состояния [math]\displaystyle{ | \psi_0 \rangle = | 0 \rangle | 0 \rangle | 0 \rangle \; }[/math] (в котором регистры запроса, ответа и рабочего пространства очищены) на конечное состояние [math]\displaystyle{ | \psi_f \rangle = Q_f | \psi_0 \rangle \; }[/math] , применяя последовательность [math]\displaystyle{ Q_f = U_k O_f U_{k - 1} O_f ... U_1 O_f U_0 \; }[/math] унитарных операторов на комплексном векторном пространстве, натянутом на все возможные базисные состояния [math]\displaystyle{ | x \rangle | a \rangle | z \rangle \; }[/math]. Унитарные операторы могут быть двух типов: запросы оракула [math]\displaystyle{ O_f : | x \rangle | a \rangle | z \rangle \mapsto | x \rangle | a \oplus f(x) \rangle | z \rangle }[/math], приносящие информацию о f, и шаги без запросов [math]\displaystyle{ U_k \; }[/math], не зависящие от f. Сложность квантовых запросов P равна минимальному числу запросов оракула, требующихся квантовому алгоритму для вычисления P с вероятностью не менее 2/3.

Рассмотрим задачу поиска треугольников в неизвестном (простом, неориентированном) графе [math]\displaystyle{ G \subseteq \{ (a, b) : a, b \in [n], a \ne b \} \; }[/math] c вершинами [n] = {1, ..., n} и m = |G| неориентированных ребер, где (a, b) = (b, a) по соглашению. Функция f, к которой выполняются запросы, представляет собой матрицу смежности графа G, а свойство P, которое необходимо вычислить, заключается в том, содержит ли G треугольник.

Задача 1 (поиск треугольников)

Дано: матрица смежности графа G с n вершинами. Требуется: найти треугольник с вероятностью не менее 2/3, если таковой существует (версия с поиском) либо булево значение, показывающее, существует ли треугольник, с вероятностью не менее 2/3 (версия с принятием решений).

Нижняя граница сложности квантовых запросов [math]\displaystyle{ \Omega (n) \; }[/math] задачи поиска треугольников была найдена Бурманом и коллегами [6]. Тривиальная верхняя граница [math]\displaystyle{ O(n^2) \; }[/math] получается в результате классического опроса каждого элемента.

Классические результаты

Классический показатель сложности рандомизированных запросов определяется подобно сложности квантовых запросов, с той разницей, что операторы [math]\displaystyle{ U_k \; }[/math] являются стохастическими, а не унитарными; в частности, это означает, что запросы оракула могут выполняться в соответствии с классическим распределением, а не с квантовыми суперпозициями. Легко увидеть, что сложность рандомизированных запросов для задачи поиска треугольников (в версиях с поиском и принятием решений) составляет [math]\displaystyle{ \Theta (n^2) \; }[/math].

Основные результаты

Улучшение верхней границы сложности квантовых запросов для задачи поиска треугольников стало результатом двух подходов: более рационального использования структуры пространства поиска (в сочетании со стандартным увеличением квантовой амплитуды) и применением процедур поиска на основе квантового блуждания.

Алгоритм с увеличением амплитуды; сложность [math]\displaystyle{ O(n + \sqrt{nm} ) \; }[/math]

Поскольку в графе G имеется [math]\displaystyle{ \tbinom{n}{3} \; }[/math] потенциальных треугольников (a, b, c), тривиальное применение алгоритма квантового поиска Гровера [10] решает задачу поиска треугольников при помощи [math]\displaystyle{ O(n^{3/2}) \; }[/math] квантовых запросов. Бурман и коллеги [6] улучшили эту верхнюю границу для специального случая, когда граф G является разреженным (т.е. [math]\displaystyle{ m = o (n^2)) \; }[/math], при помощи следующего рассуждения.

Предположим, алгоритм Гровера используется для нахождения (a) ребра [math]\displaystyle{ (a, b) \in G \; }[/math] среди всех [math]\displaystyle{ \tbinom{n}{2} \; }[/math] потенциальных ребер и (b) вершины [math]\displaystyle{ c \in [n] \; }[/math], такой, что (a, b, c) является треугольником в G. Стоимость шагов (a) и (b) составляет [math]\displaystyle{ O( \sqrt{n^2/m} ) \; }[/math] и [math]\displaystyle{ O( \sqrt{n} ) \; }[/math] квантовых запросов, соответственно. Если граф G содержит треугольник [math]\displaystyle{ \Delta \; }[/math], то шаг (a) найдет ребро (a, b), принадлежащее [math]\displaystyle{ \Delta \; }[/math], с вероятностью [math]\displaystyle{ \Omega (1/m) \; }[/math], а шаг (b) найдет третью вершину с треугольника [math]\displaystyle{ \Delta = (a, b, c) \; }[/math] с константной вероятностью. Таким образом, шаги (a) и (b) совместно находят треугольник с вероятностью [math]\displaystyle{ \Omega (1/m) \; }[/math]. Повторяя эти шаги [math]\displaystyle{ O( \sqrt{m} ) \; }[/math] раз с использованием техники увеличения амплитуды (Брассар и коллеги [5]), можно найти треугольник с вероятностью 2/3. Общая стоимость составит [math]\displaystyle{ O( \sqrt{m} ( \sqrt{n^2/m} + \sqrt{n} )) = O( n + \sqrt{nm} ) \; }[/math] квантовых запросов. Таким образом:

Теорема 1 (Бурман и коллеги [6]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи [math]\displaystyle{ O(n + \sqrt{nm} ) \; }[/math] квантовых запросов.

Алгоритм с увеличением амплитуды; сложность [math]\displaystyle{ \tilde{O} (n^{10/7} ) \; }[/math]

Пусть [math]\displaystyle{ \mu^2 \; }[/math] – полный граф на вершинах [math]\displaystyle{ \mu \subseteq [n] \; }[/math], [math]\displaystyle{ vV_G(v) \; }[/math] – множество вершин, смежных с вершиной v, а [math]\displaystyle{ deg_G(v) \; }[/math] – степень вершины v. Отметим, что для любой вершины [math]\displaystyle{ v \in [n] \; }[/math] можно либо найти треугольник в G, содержащий v, либо удостовериться в том, что [math]\displaystyle{ G \subseteq [n]^2 \setminus v_G(v)^2 \; }[/math], при помощи [math]\displaystyle{ \tilde{O} (n) \; }[/math] квантовых запросов с вероятностью успеха [math]\displaystyle{ 1 - 1/n^3 \; }[/math]. Для этого вначале необходимо вычислить [math]\displaystyle{ v_G(v) \; }[/math] классическим способом, а затем применить механизм поиска Гровера логарифмическое количество раз, чтобы найти ребро графа G в [math]\displaystyle{ v_G(v)^2 \; }[/math] с высокой вероятностью, если таковое существует. Шегеди и коллеги [13, 14] использовали это наблюдение для разработки алгоритма поиска треугольников, не использующего других квантовых процедур, кроме увеличения амплитуды (как и алгоритм Бурмана и др. [6]), но требующего только [math]\displaystyle{ \tilde{O} (n^{10/7} ) \; }[/math] квантовых запросов.

Алгоритм Шегеди и др. [13, 14] работает следующим образом. Вначале следует равномерно выбрать [math]\displaystyle{ k = \tilde{O} (n^{\epsilon} ) \; }[/math] вершин [math]\displaystyle{ v_1, ..., v_k \; }[/math] случайным образом из множества [n] без замены и вычислить каждое значение [math]\displaystyle{ v_G(v_i) \; }[/math]. За [math]\displaystyle{ \tilde{O} (n^{1 + \epsilon} ) \; }[/math] квантовых запросов можно либо найти треугольник в графе G, содержащий одну из вершин [math]\displaystyle{ v_i \; }[/math], либо с высокой вероятностью заключить, что [math]\displaystyle{ G \subseteq G' := [n]^2 \setminus U_i v_G(v_i)^2 \; }[/math]. Предположим, что имеет место второй вариант. Тогда можно показать, что с высокой вероятностью может быть построено разбиение (T, E) графа G', такое, что T содержит [math]\displaystyle{ O(n^{3 - \epsilon ' } ) \; }[/math] треугольников и [math]\displaystyle{ E \cap G \; }[/math] имеет размер [math]\displaystyle{ O(n^{2 - \delta } + n^{2 - \epsilon + \delta + \epsilon ' } ) \; }[/math], за [math]\displaystyle{ \tilde{O} (n^{1 + \delta + \epsilon '} ) \; }[/math] запросов (либо в процессе построения может быть найден треугольник в G). Поскольку [math]\displaystyle{ G \subseteq G' \; }[/math], любой треугольник в G либо лежит в T, либо пересекает E. В первом случае треугольник можно найти в [math]\displaystyle{ G \cap T \; }[/math] за [math]\displaystyle{ O( \sqrt{n^{3 - \epsilon ' }} ) \; }[/math] квантовых запросов посредством поиска по G при помощи алгоритма Гровера для T, известного из процедуры разбиения. Во втором случае можно найти треугольник в G с ребром из E за [math]\displaystyle{ \tilde{O} ( n + \sqrt{n^{3 - min \{ \delta, \; \epsilon - \delta - \epsilon ' \} }} ) }[/math] квантовых запросов при помощи алгоритма Бурмана и др. [6], где [math]\displaystyle{ m = | G \cap E | \; }[/math]. Таким образом:

Теорема 2 (Шегеди и коллеги [13, 14]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи [math]\displaystyle{ \tilde{O} (n^{1 + \epsilon} + n^{1 + \delta + \epsilon '} + \sqrt{n^{3 - \epsilon '}} + \sqrt{n^{3 - min \{ \delta, \; \epsilon - \delta - \epsilon ' \} }} ) }[/math] квантовых запросов.

Если положить [math]\displaystyle{ \epsilon = 3/7 \; }[/math] и [math]\displaystyle{ \epsilon ' = \delta = 1/7 \; }[/math], получим алгоритм, использующий [math]\displaystyle{ \tilde{O} (n^{10/7} ) \; }[/math] квантовых запросов.

Алгоритм с квантовым блужданием; сложность [math]\displaystyle{ \tilde{O} (n^{13/10} ) \; }[/math]

Более эффективный алгоритм поиска треугольников предложили Маньез и коллеги [13 ]; он использует процедуру квантового блуждания, введенную Амбайнисом [3] для получения оптимального алгоритма квантовых запросов для решения задачи различения элементов.

Пусть имеется обращение оракула к функции f, определяющей отношение [math]\displaystyle{ C \subseteq [n]^k \; }[/math]. Процедура поиска, предложенная Амбайнисом, решает задачу k-коллизии: найти пару [math]\displaystyle{ (a_1, ..., a_k) \in C \; }[/math], если таковая существует. Процедура поиска использует в работе три квантовых регистра [math]\displaystyle{ | A \rangle | D(A) \rangle | y \rangle \; }[/math]: регистр множеств [math]\displaystyle{ | A \rangle \; }[/math] хранит множество [math]\displaystyle{ A \subseteq [n] \; }[/math] размера |A| = r, регистр данных [math]\displaystyle{ | D(A) \rangle \; }[/math] хранит структуру данных D(A), а регистр монет [math]\displaystyle{ | y \rangle \; }[/math] хранит элемент [math]\displaystyle{ i \notin A \; }[/math]. Проверяя структуру данных D(A) при помощи процедуры квантовых запросов [math]\displaystyle{ \Phi \; }[/math] со стоимостью проверки c(r), можно определить, имеет ли место [math]\displaystyle{ A^k \cap C \ne \empty \; }[/math]. Предположим, что структура D(A) может быть построена с нуля со стоимостью построения cost s(r) либо модифицирована из D(A) в D(A'), где [math]\displaystyle{ |A \cap A'| = r - 1 \; }[/math], со стоимостью модификации u(r). Тогда процедура квантового блуждания Амбайниса решает задачу k-коллизии за [math]\displaystyle{ \tilde{O} (s(r) + (\frac{n}{r})^{k/2} \cdot (c(r) + \sqrt{r} \cdot u(r))) \; }[/math] квантовых запросов. (Более подробное изложение см. в статье «Квантовый алгоритм различения элементов»).

Рассмотрим задачу поиска коллизии в графе на примере графа [math]\displaystyle{ G \subseteq [n]^2 \; }[/math], где f определяет бинарное отношение [math]\displaystyle{ C \subseteq [n]^2 \; }[/math], удовлетворяющее [math]\displaystyle{ C(u, u') \; }[/math], если [math]\displaystyle{ f(u) = f(u') = 1 \; }[/math] и [math]\displaystyle{ (u, u') \in G \; }[/math]. Процедура поиска Амбайниса решает эту задачу за [math]\displaystyle{ \tilde{O} (n^{2/3}) \; }[/math] квантовых запросов при помощи следующих рассуждений. Зафиксируем [math]\displaystyle{ k = 2 \; }[/math] и [math]\displaystyle{ r = n^{2/3} \; }[/math] в алгоритме задачи k-коллизии и для каждого [math]\displaystyle{ U \subseteq [n] \; }[/math] определим [math]\displaystyle{ D(U) = \{ (v, f(v)) : v \in U \} \; }[/math] и [math]\displaystyle{ \Phi (D(U)) = 1 \; }[/math], если некоторые [math]\displaystyle{ u, u' \in U \; }[/math] удовлетворяют C. В таком случае для построения D(U) необходимо s(r) = r начальных запросов f(v), u(r) = 1 новый запрос f(v) необходим для обновления D(U), c(r) = 0 дополнительных запросов f(v) необходимо для проверки условия [math]\displaystyle{ \Phi(D(U)) \; }[/math]. Таким образом, всего требуется [math]\displaystyle{ \tilde{O} (r + \frac{n}{r} ( \sqrt{r} )) = \tilde{O} ( n^{2/3} ) \; }[/math] запросов.

Маньез и коллеги [13] решают задачу нахождения треугольников, сводя ее к задаче поиска коллизии в графе. Вновь зафиксируем [math]\displaystyle{ k = 2 \; }[/math] и [math]\displaystyle{ r = n^{2/3} \; }[/math]. Пусть C – множество ребер, содержащее по меньшей мере один треугольник. Определим [math]\displaystyle{ D(U) = G|_U \; }[/math] и [math]\displaystyle{ \Phi(D(U)) = 1 \; }[/math], если некоторое ребро в [math]\displaystyle{ G|_U \; }[/math] удовлетворяет С. Тогда для построения D(U) потребуется [math]\displaystyle{ s(r) = O(r^2) \; }[/math] начальных запросов, а для его обновления – u(r) = r новых запросов. Остается найти границу стоимости проверки c(r). Для любой вершины [math]\displaystyle{ v \in [n] \; }[/math] рассмотрим оракул [math]\displaystyle{ f_v \; }[/math], связанный с коллизией в графе на [math]\displaystyle{ G|_U \; }[/math] и удовлетворяющий условию: [math]\displaystyle{ f_v(u) = 1 \; }[/math], если [math]\displaystyle{ (u, v) \in G \; }[/math]. Ребро [math]\displaystyle{ G|_U \; }[/math] является треугольником в G в том и только том случае, если это ребро является решением задачи поиска коллизии в графе на [math]\displaystyle{ G|_U \; }[/math] для некоторого [math]\displaystyle{ v \in [n] \; }[/math]. Эта задача может быть решена для конкретной v за [math]\displaystyle{ \tilde{O} (r^{2/3} ) \; }[/math] запросов. Используя [math]\displaystyle{ \tilde{O} ( \sqrt{n}) \; }[/math] шагов увеличения амплитуды, можно с высокой вероятностью узнать, генерирует ли какая-либо из вершин [math]\displaystyle{ v \in [n] \; }[/math] приемлемое решение для задачи поиска коллизии в графе. Таким образом, стоимость проверки составляет [math]\displaystyle{ c(r) = \tilde{O} ( \sqrt{n} \cdot r^{2/3} ) \; }[/math] запросов, из чего следует:

Теорема 3 (Маньез и коллеги [13]). Используя процедуру квантового блуждания, задачу поиска треугольников можно решить при помощи [math]\displaystyle{ \tilde{O} (r^2 + \frac{n}{r} ( \sqrt{n} \cdot r^{2/3} + \sqrt{r} \cdot r )) \; }[/math] квантовых запросов.

Если положить [math]\displaystyle{ r = n^{3/5} \; }[/math], получим алгоритм, использующий [math]\displaystyle{ \tilde{O} (n^{13/10} ) \; }[/math] квантовых запросов.

В своей недавней работе Маньез и коллеги [12], используя разработанную Шегеди [15] технику квантового блуждания, предложили новую процедуру поиска на основе квантового блуждания, обобщая наработки Амбайниса [3]. Одним из вариантов ее применения стал алгоритм квантового блуждания для поиска треугольников за [math]\displaystyle{ O(n^{13/10}) \; }[/math] квантовых запросов.

Применение

Расширение алгоритма квантового блуждания для поиска треугольников использовалось для нахождения клик и других фиксированных подграфов, а также для определения выполнения монотонных свойств графа с малыми сертификатами при помощи меньшего числа квантовых запросов, чем у предыдущих алгоритмов.

Поиск клик, подграфов и подмножеств Алгоритм Амбайниса для поиска k-коллизии [3] может найти копию любого графа H с k > 3 вершинами за [math]\displaystyle{ \tilde{O} (n^{2 - 2/(k + 1)}) \; }[/math] квантовых запросов. Для случая, когда H является k-кликой, Чайлдз и Айзенберг [9] предложили алгоритм, требующий [math]\displaystyle{ \tilde{O} (n^{2.5 - 6/(k + 2)}) \; }[/math] запросов. Простое обобщение алгоритма поиска треугольников (Маньез и др. [13] уменьшает их число до [math]\displaystyle{ \tilde{O} (n^{2 - 2/k}) \; }[/math].

Монотонные свойства графов Вспомним, что монотонное свойство графа представляет собой булево свойство графа, значение которого инвариантно относительно перестановок меток вершин и монотонно относительно любой последовательности удалений ребер. Примерами монотонных свойств графов являются связность, планарность и отсутствие треугольников. 1-сертификатом называется минимальное подмножество запросов к ребрам, доказывающее, что свойство выполняется (например, трех ребер достаточно для доказательства наличия в графе треугольника). Маньез и коллеги [13] показали, что их алгоритм квантового блуждания для задачи поиска треугольников может быть обобщен до алгоритма с [math]\displaystyle{ \tilde{O} (n^{2 - 2/k}) \; }[/math] квантовых запросов, определяющего наличие любого монотонного свойства графов с 1-сертификатами для объектов размером k > 3 вершин. Наилучшая известная нижняя граница составляет [math]\displaystyle{ \Omega(n) \; }[/math].

Открытые вопросы

Наиболее очевидный из открытых вопросов касается решения проблемы сложности квантовых запросов при поиске треугольников; на данный момент лучшими верхней и нижней границей являются O(n13/10) и Q{n). Кроме того, остаются открытыми следующие задачи:

Сложность квантовых запросов при поиске монотонных свойств графов

Наилучшая известная нижняя граница сложности квантовых запросов для (нетривиальных) монотонных свойств графов, составляющая Q(n2/3 log 1/6n) и полученная Эндрю Яо, следует из нижней границы Q{nm log1/3 n) классического рандомизированного алгоритма Чакрабарти и Хота [ ] и техники квантового противопоставления Амбайниса [2]. Возможно ли улучшить границу Omega(n)? Если возможно, она будет достаточно близкой, поскольку для того, чтобы определить при помощи алгоритма Гровера, является ли множество ребер графа непустым, требуется O(n) квантовых запросов.

Новые алгоритмы с применением квантового блуждания

Технология квантового блуждания успешно применялась при разработке более эффективных алгоритмов квантового поиска для нескольких задач – таких как различение элементов [ ], поиск треугольников [13], верификация матричного произведения [ ] и проверка коммутативности групп [ ]. Было бы любопытно узнать, как подход на основе квантового блуждания может быть расширен для получения новых и улучшенных квантовых алгоритмов для решения различных вычислительных задач.

См. также

• Квантование цепей Маркова
• Квантовый алгоритм различения элементов

Литература

1. Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51 (4), 595-605, (2004), quant-ph/0112086

2. Ambainis, A.: Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci. 64, 750-767, (2002), quant-ph/0002066

3. Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210-239, (2007) Preliminary version in Proc. FOCS, (2004), quant-ph/0311001

4. Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510-1523, (1997), quant-ph/9701001

5. Brassard, G., Hayer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series, vol. 305. (2002) quant-ph/0005055

6. Buhrman, H., DCirr, C., Heiligman, M., P.Hayer, Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Computing 34(6), 1324-1330, (2005). Preliminary version in Proc. CCC (2001) quant-ph/0007016

7. Buhrman, H., Spalek, R.: Quantum verification of matrix products. Proc. SODA, (2006) quant-ph/0409035

8. Chakrabarti, A., Khot, S.: Improved lower bounds on the randomized complexity of graph properties. Proc. ICALP (2001)

9. Childs, A., Eisenberg, J.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5, 593 (2005), quant-ph/0311038

10. Grover, L.: A fast quantum mechanical algorithm for database search. Proc. STOC (1996) quant-ph/9605043

11. Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. Algorithmica 48(3), 221-232 (2007) Preliminary version in Proc. ICALP (2005) quant-ph/0506265

12. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. Proc. STOC (2007) quant-ph/0608026

13. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SI AM J. Comput. 37(2), 413-424, (2007). Preliminary version in Proc. SODA (2005) quant-ph/0310134

14. Szegedy, M.: On the quantum query complexity of detecting triangles in graphs. quant-ph/0310107

15. Szegedy, M.: Quantum speed-up of Markov chain based algorithms. Proc. FOCS (2004) quant-ph/0401053