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

Пусть имеется обращение оракула к функции 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) при помощи процедуры квантовых запросов Ф со стоимостью проверки c(r), можно определить, имеет ли место Ak \ C ф ;. Предположим, что структура D(A) может быть построена с нуля со стоимостью построения cost s(r) либо модифицирована из D(A) в D(A0), где jA \ A0j = r — 1, со стоимостью модификации u(r). Тогда процедура квантового блуждания Амбайниса решает задачу k-коллизии за 6(s(r) + (nr)k/2 ■ (c(r) + pr ■ u(r))) квантовых запросов. (Более подробное изложение см. в статье «Квантовый алгоритм различения элементов»).