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

Пусть имеется обращение оракула к функции f, определяющей отношение <math>C \subseteq [n]^k \;</math>. Процедура поиска, предложенная Амбайнисом, решает задачу ''k-коллизии'': найти пару <math>(a_1, ..., a_k) \in C \;</math>, если таковая существует. Процедура поиска использует в работе три квантовых регистра <math>| A \rangle | D(A) \rangle | y \rangle \;</math>: ''регистр множеств'' <math>| A \rangle \;</math> хранит множество <math>A \subseteq [n] \;</math> размера |A| = r, ''регистр данных'' <math>| D(A) \rangle \;</math> хранит структуру данных D(A), а ''регистр монет'' <math>| y \rangle \;</math> хранит элемент <math>i \notin A \;</math>. Проверяя структуру данных D(A) при помощи процедуры квантовых запросов <math>\Phi \;</math> со ''стоимостью проверки'' c(r), можно определить, имеет ли место <math>A^k \cap C \ne \empty \;</math>. Предположим, что структура D(A) может быть построена с нуля со ''стоимостью построения'' cost s(r) либо модифицирована из D(A) в D(A'), где <math>|A \cap A'| = r - 1 \;</math>, со ''стоимостью модификации'' u(r). Тогда процедура квантового блуждания Амбайниса решает задачу k-коллизии за <math>\tilde{O} (s(r) + \frac{n}{r}^{k/2} \cdot (c(r) + \sqrt{r} \cdot u(r))) \;</math> квантовых запросов. (Более подробное изложение см. в статье «[[Квантовый алгоритм различения элементов]]»).

Рассмотрим задачу поиска коллизии в графе на примере графа G С [n]2, где f определяет бинарное отношение C С [n]2, удовлетворяющее C(u; u0) iff(u) = f(u0) = 1 и (u; U0) 2 G. Процедура поиска Амбайниса решает эту задачу за 6(и2/3) квантовых запросов при помощи следующих рассуждений. Зафиксируем k = 2 и r = n2/3 в алгоритме задачи k-коллизии и для каждого U С [n] определим D(U) = f(v;f(v)) : v 2 Ug и Ф(О([7)) = 1, если некоторые u, u0 2 U удовлетворяют C. В таком случае для построения D(U) необходимо s(r) = r начальных запросов f(v), u(r) = 1 новый запрос f(v) необходим для обновления D(U), c(r) = 0 дополнительных запросов f(v) необходимо для проверки условия Ф(О(С7)). Таким образом, всего требуется O(r + nr(pr)) = б(и2/3) запросов.