4551
правка
Квантовый алгоритм поиска треугольников: различия между версиями
Материал из WEGA
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 17:37, 7 апреля 2016
, 7 апреля 2016→Применение
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 78: | Строка 78: | ||
'''Поиск клик, подграфов и подмножеств''' | '''Поиск клик, подграфов и подмножеств''' | ||
Алгоритм Амбайниса для поиска 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>. | ||
