4551
правка
Квантовый алгоритм поиска треугольников: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 22:09, 6 апреля 2016
, 6 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
Алгоритм с увеличением амплитуды; сложность | '''Алгоритм с увеличением амплитуды; сложность <math>\tilde{O} (n^{10/7} ) \;</math>''' | ||
Пусть [)} – полный граф с вершинами [i С [n], VQ(V) – множество вершин, смежных с вершиной v, а degG(v) – степень вершины v. Отметим, что для любой вершины v 2 [n] можно либо найти треугольник в G, содержащий v, либо удостовериться в том, что G С [n]2 n VG(V)2, при помощи 6(и) квантовых запросов с вероятностью успеха 1 — 1/n3. Для этого вначале необходимо вычислить VQ{V) классическим способом, а затем применить механизм поиска Гровера логарифмическое количество раз, чтобы найти ребро графа G в VG(V)2 с высокой вероятностью, если таковое существует. Шегеди и коллеги [13, 14] использовали это наблюдение для разработки алгоритма поиска треугольников, не использующего других квантовых процедур, кроме увеличения амплитуды (как и алгоритм Бурмана и др. [6]), но требующего только | Пусть [)} – полный граф с вершинами [i С [n], VQ(V) – множество вершин, смежных с вершиной v, а degG(v) – степень вершины v. Отметим, что для любой вершины v 2 [n] можно либо найти треугольник в G, содержащий v, либо удостовериться в том, что G С [n]2 n VG(V)2, при помощи 6(и) квантовых запросов с вероятностью успеха 1 — 1/n3. Для этого вначале необходимо вычислить VQ{V) классическим способом, а затем применить механизм поиска Гровера логарифмическое количество раз, чтобы найти ребро графа G в VG(V)2 с высокой вероятностью, если таковое существует. Шегеди и коллеги [13, 14] использовали это наблюдение для разработки алгоритма поиска треугольников, не использующего других квантовых процедур, кроме увеличения амплитуды (как и алгоритм Бурмана и др. [6]), но требующего только <math>\tilde{O} (n^{10/7} ) \;</math> квантовых запросов. | ||
| Строка 46: | Строка 46: | ||
Теорема 2 (Шегеди и коллеги [13, 14]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи O(n1+€ + n1+s+€' + Vn3"e' + ^/n^-^m{S,€-S-€'}) квантовых запросов. | Теорема 2 (Шегеди и коллеги [13, 14]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи O(n1+€ + n1+s+€' + Vn3"e' + ^/n^-^m{S,€-S-€'}) квантовых запросов. | ||
Если положить e = 3/7 и e' = 8 = 1/7, получим алгоритм, использующий | Если положить e = 3/7 и e' = 8 = 1/7, получим алгоритм, использующий <math>\tilde{O} (n^{10/7} ) \;</math> квантовых запросов. | ||
Алгоритм с квантовым блужданием; сложность | Алгоритм с квантовым блужданием; сложность <math>\tilde{O} (n^{13/10} ) \;</math> | ||
Более эффективный алгоритм поиска треугольников предложили Маньез и коллеги [ ]; он использует процедуру квантового блуждания, введенную Амбайнисом [ ] для получения оптимального алгоритма квантовых запросов для решения задачи различения элементов. | Более эффективный алгоритм поиска треугольников предложили Маньез и коллеги [ ]; он использует процедуру квантового блуждания, введенную Амбайнисом [ ] для получения оптимального алгоритма квантовых запросов для решения задачи различения элементов. | ||