4430
правок
Квантовый алгоритм поиска треугольников: различия между версиями
Материал из WEGA
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 19:43, 6 апреля 2016
, 6 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Треугольник представляет собой клику размера 3 в неориентированно…») |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Треугольник представляет собой клику размера 3 в неориентированном графе. Поиск треугольников является фундаментальной вычислительной проблемой, временная сложность которой тесно связана со сложностью умножения матриц. В последние годы она широко исследовалась как задача базового поиска, сложность квантовых запросов для которой все еще неясна – в противоположность задаче неструктурированного поиска [4, 10] и задаче различения элементов [1, 3]. Данный обзор рассматривает алгоритмы квантового поиска для нахождения треугольников. | [[Треугольник]] представляет собой [[клика|клику]] размера 3 в [[неориентированный граф|неориентированном графе]]. Поиск треугольников является фундаментальной вычислительной проблемой, временная сложность которой тесно связана со сложностью умножения матриц. В последние годы она широко исследовалась как задача базового поиска, сложность квантовых запросов для которой все еще неясна – в противоположность задаче неструктурированного поиска [4, 10] и задаче различения элементов [1, 3]. Данный обзор рассматривает алгоритмы квантового поиска для нахождения треугольников. | ||
== Нотация и ограничения == | == Нотация и ограничения == | ||
