Квантовый алгоритм поиска треугольников: различия между версиями

'''Поиск клик, подграфов и подмножеств'''

Алгоритм Амбайниса для поиска 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>.

'''Монотонные свойства графов'''

Вспомним, что ''монотонное свойство графа'' представляет собой булево свойство графа, значение которого инвариантно относительно перестановок меток вершин и монотонно относительно любой последовательности удалений ребер. Примерами монотонных свойств графов являются связность, планарность и отсутствие треугольников. ''1-сертификатом'' называется минимальное подмножество запросов к ребрам, доказывающее, что свойство выполняется (например, трех ребер достаточно для доказательства наличия в графе треугольника). Маньез и коллеги [13] показали, что их алгоритм квантового блуждания для задачи поиска треугольников может быть обобщен до алгоритма с <math>\tilde{O} (n^{2 - 2/k}) \;</math> квантовых запросов, определяющего наличие любого монотонного свойства графов с 1-сертификатами для объектов размером k > 3 вершин. Наилучшая известная нижняя граница составляет <math>\Omega(n) \;</math>.