4551
правка
Квантовый алгоритм поиска треугольников: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 22:01, 6 апреля 2016
, 6 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
Алгоритм с увеличением амплитуды; сложность O(n + | '''Алгоритм с увеличением амплитуды; сложность <math>O(n + \sqrt{nm} ) \;</math>''' | ||
Поскольку в графе G имеется | Поскольку в графе G имеется <math>\tbinom{n}{3} \;</math> потенциальных треугольников (a, b, c), тривиальное применение алгоритма квантового поиска Гровера [10] решает задачу поиска треугольников при помощи <math>O(n^{3/2}) \;</math> квантовых запросов. Бурман и коллеги [6] улучшили эту верхнюю границу для специального случая, когда граф G является [[разреженные графы|разреженным]] (т.е. <math>m = o (n^2)) \;</math>, при помощи следующего рассуждения. | ||
| Строка 69: | Строка 69: | ||
В своей недавней работе Маньез и коллеги [ ], используя разработанную Шегеди [15] технику квантового блуждания, предложили новую процедуру поиска на основе квантового блуждания, обобщая наработки Амбайниса [ ]. Одним из вариантов ее применения стал алгоритм квантового блуждания для поиска треугольников за O(n13/10) квантовых запросов. | В своей недавней работе Маньез и коллеги [ ], используя разработанную Шегеди [15] технику квантового блуждания, предложили новую процедуру поиска на основе квантового блуждания, обобщая наработки Амбайниса [ ]. Одним из вариантов ее применения стал алгоритм квантового блуждания для поиска треугольников за O(n13/10) квантовых запросов. | ||
== Применение == | == Применение == | ||