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

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

Алгоритм Амбайниса для поиска k-коллизии [ ] может найти копию любого графа H с k > 3 вершинами за 6(n2 2/(k+1)) квантовых запросов. Для случая, когда H является k-кликой, Чайлдз и Айзенберг [9] предложили алгоритм, требующий О(и2'5~6/^+2-)) запросов. Простое обобщение алгоритма поиска треугольников (Маньез и др. [ ] уменьшает их число до 6{n2-2lk).

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

Вспомним, что монотонное свойство графа представляет собой булево свойство графа, значение которого инвариантно относительно перестановок меток вершин и монотонно относительно любой последовательности удалений ребер. Примерами монотонных свойств графов являются связность, планарность и отсутствие треугольников. 1-сертификатом называется минимальное подмножество запросов к ребрам, доказывающее, что свойство выполняется (например, трех ребер достаточно для доказательства наличия в графе треугольника). Маньез и коллеги [13] показали, что их алгоритм квантового блуждания для задачи поиска треугольников может быть обобщен до алгоритма с 6(n2~2lk) квантовых запросов, определяющего наличие любого монотонного свойства графов с 1-сертификатами для объектов размером k > 3 вершин. Наилучшая известная нижняя граница составляет Q{n).