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

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

Треугольник представляет собой клику размера 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{ c \; }[/math] треугольника [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{ v_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. В таком случае необходимо s(r) = r начальных запросов f(v) для построения D(U), 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].

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

Наиболее очевидный из открытых вопросов касается сложности квантовых запросов для задачи поиска треугольников; на данный момент лучшими верхней и нижней границей являются [math]\displaystyle{ O(n^{13/10}) \; }[/math] и [math]\displaystyle{ \Omega(n) \; }[/math]. Кроме того, остаются нерешенными следующие задачи:

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

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

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

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

См. также

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

Литература

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