4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 62: | Строка 62: | ||
Маньез и коллеги [13] решают задачу нахождения треугольников, сводя ее к задаче поиска коллизии в графе. Вновь зафиксируем <math>k = 2 \;</math> и <math>r = n^{2/3} \;</math>. Пусть C – множество ребер, входящих по меньшей мере в один треугольник. Определим <math>D(U) = G|_U \;</math> и <math>\Phi(D(U)) = 1 \;</math>, если некоторое ребро в <math>G|_U \;</math> удовлетворяет С. Тогда для построения D(U) потребуется <math>s(r) = O(r^2) \;</math> начальных запросов, а для его обновления u(r) = r новых запросов. Остается найти границу стоимости проверки c(r). Для любой вершины <math>v \in [n] \;</math> рассмотрим оракул <math>f_v \;</math>, связанный с коллизией в графе на <math>G|_U \;</math> и удовлетворяющий условию: <math>f_v(u) = 1 \;</math>, если <math>(u, v) \in G \;</math>. Ребро <math>G|_U \;</math> является треугольником в G в том и только том случае, если это ребро является решением задачи поиска коллизии в графе на <math>G|_U \;</math> для | Маньез и коллеги [13] решают задачу нахождения треугольников, сводя ее к задаче поиска коллизии в графе. Вновь зафиксируем <math>k = 2 \;</math> и <math>r = n^{2/3} \;</math>. Пусть C – множество ребер, входящих по меньшей мере в один треугольник. Определим <math>D(U) = G|_U \;</math> и <math>\Phi(D(U)) = 1 \;</math>, если некоторое ребро в <math>G|_U \;</math> удовлетворяет С. Тогда для построения D(U) потребуется <math>s(r) = O(r^2) \;</math> начальных запросов, а для его обновления u(r) = r новых запросов. Остается найти границу стоимости проверки c(r). Для любой вершины <math>v \in [n] \;</math> рассмотрим оракул <math>f_v \;</math>, связанный с коллизией в графе на <math>G|_U \;</math> и удовлетворяющий условию: <math>f_v(u) = 1 \;</math>, если <math>(u, v) \in G \;</math>. Ребро <math>G|_U \;</math> является треугольником в G в том и только том случае, если это ребро является решением задачи поиска коллизии в графе на <math>G|_U \;</math> для некоторой вершины <math>v \in [n] \;</math>. Эта задача может быть решена для конкретной v за <math>\tilde{O} (r^{2/3} ) \;</math> запросов. Используя <math>\tilde{O} ( \sqrt{n}) \;</math> шагов увеличения амплитуды, можно с высокой вероятностью узнать, генерирует ли ''какая-либо'' из вершин <math>v \in [n] \;</math> приемлемое решение для задачи поиска коллизии в графе. Таким образом, стоимость проверки составляет <math>c(r) = \tilde{O} ( \sqrt{n} \cdot r^{2/3} ) \;</math> запросов, из чего следует: | ||
Строка 73: | Строка 73: | ||
== Применение == | == Применение == | ||
Расширения алгоритма квантового блуждания для поиска треугольников использовались для нахождения клик и других фиксированных подграфов, а также для определения выполнения монотонных свойств графа с малыми сертификатами при помощи меньшего числа квантовых запросов, чем у предыдущих алгоритмов. | |||
'''Поиск клик, подграфов и подмножеств''' | '''Поиск клик, подграфов и подмножеств''' | ||
Алгоритм Амбайниса для поиска k-коллизии [3] может найти копию любого графа H с k > 3 вершинами за <math>\tilde{O} (n^{2 - 2/(k + 1)}) \;</math> квантовых запросов. Для случая, когда H является k-кликой, Чайлдз и Айзенберг [9] предложили алгоритм, требующий <math>\tilde{O} (n^{2.5 - 6/(k + 2)}) \;</math> запросов. Простое обобщение алгоритма поиска треугольников (Маньез и др. [13] уменьшает их число до <math>\tilde{O} (n^{2 - 2/k}) \;</math>. | Алгоритм Амбайниса для поиска k-коллизии [3] может найти копию любого графа H с k > 3 вершинами за <math>\tilde{O} (n^{2 - 2/(k + 1)}) \;</math> квантовых запросов. Для случая, когда H является k-кликой, Чайлдз и Айзенберг [9] предложили алгоритм, требующий <math>\tilde{O} (n^{2.5 - 6/(k + 2)}) \;</math> запросов. Простое обобщение алгоритма поиска треугольников (Маньез и др. [13]) уменьшает их число до <math>\tilde{O} (n^{2 - 2/k}) \;</math>. | ||
Строка 86: | Строка 86: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Наиболее очевидный из открытых вопросов касается | Наиболее очевидный из открытых вопросов касается сложности квантовых запросов для задачи поиска треугольников; на данный момент лучшими верхней и нижней границей являются <math>O(n^{13/10}) \;</math> и <math>\Omega(n) \;</math>. Кроме того, остаются нерешенными следующие задачи: | ||
Строка 96: | Строка 96: | ||
'''Новые алгоритмы с применением квантового блуждания''' | '''Новые алгоритмы с применением квантового блуждания''' | ||
Техника квантового блуждания успешно применялась при разработке более эффективных алгоритмов квантового поиска для нескольких задач – таких как различение элементов [3], поиск треугольников [13], верификация матричного произведения [7] и проверка коммутативности групп [11]. Было бы любопытно узнать, как подход на основе квантового блуждания может быть расширен для получения новых и улучшенных квантовых алгоритмов для решения различных вычислительных задач. | |||
== См. также == | == См. также == |
правок