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

Рассмотрим задачу поиска ''коллизии в графе'' на примере графа <math>G \subseteq [n]^2 \;</math>, где f определяет бинарное отношение <math>C \subseteq [n]^2 \;</math>, удовлетворяющее <math>C(u, u') \;</math>, если <math>f(u) = f(u') = 1 \;</math> и <math>(u, u') \in G \;</math>. Процедура поиска Амбайниса решает эту задачу за <math>\tilde{O} (n^{2/3}) \;</math> квантовых запросов при помощи следующих рассуждений. Зафиксируем <math>k = 2 \;</math> и <math>r = n^{2/3} \;</math> в алгоритме задачи k-коллизии и для каждого <math>U \subseteq [n] \;</math> определим <math>D(U) = \{ (v, f(v)) : v \in U \} \;</math> и <math>\Phi (D(U)) = 1 \;</math>, если некоторые <math>u, u' \in U \;</math> удовлетворяют C. В таком случае для построения D(U) необходимо s(r) = r начальных запросов f(v), u(r) = 1 новый запрос f(v) необходим для обновления D(U), c(r) = 0 дополнительных запросов f(v) необходимо для проверки условия <math>\Phi(D(U)) \;</math>. Таким образом, всего требуется <math>\tilde{O} (r + \frac{n}{r} ( \sqrt{r} )) = \tilde{O} ( n^{2/3} ) \;</math> запросов.