4511
правок
Квантовый алгоритм поиска треугольников: различия между версиями
Материал из WEGA
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 23:13, 6 апреля 2016
, 6 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 60: | Строка 60: | ||
Маньез и коллеги [ ] решают задачу нахождения треугольников, сводя ее к задаче поиска коллизии в графе. Вновь зафиксируем | Маньез и коллеги [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> запросов, из чего следует: | ||
Теорема 3 (Маньез и коллеги [ ]). Используя процедуру квантового блуждания, задачу поиска треугольников можно решить при помощи O{ | '''Теорема 3 (Маньез и коллеги [13]). Используя процедуру квантового блуждания, задачу поиска треугольников можно решить при помощи <math>\tilde{O} (r^2 + \frac{n}{r} ( \sqrt{n} \cdot r^{2/3} + \sqrt{r} \cdot r )) \;</math> квантовых запросов.''' | ||
Если положить r = | Если положить <math>r = n^{3/5} \;</math>, получим алгоритм, использующий <math>\tilde{O} (n^{13/10} ) \;</math> квантовых запросов. | ||
В своей недавней работе Маньез и коллеги [ ], используя разработанную Шегеди [15] технику квантового блуждания, предложили новую процедуру поиска на основе квантового блуждания, обобщая наработки Амбайниса [ ]. Одним из вариантов ее применения стал алгоритм квантового блуждания для поиска треугольников за O( | |||
В своей недавней работе Маньез и коллеги [12], используя разработанную Шегеди [15] технику квантового блуждания, предложили новую процедуру поиска на основе квантового блуждания, обобщая наработки Амбайниса [3]. Одним из вариантов ее применения стал алгоритм квантового блуждания для поиска треугольников за <math>O(n^{13/10}) \;</math> квантовых запросов. | |||
== Применение == | == Применение == | ||
