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

Пусть имеется обращение оракула к функции f, определяющей отношение <math>C \subseteq [n]^k \;</math>. Процедура поиска, предложенная Амбайнисом, решает задачу ''k-коллизии'': найти пару <math>(a_1, ..., a_k) \in C \;</math>, если таковая существует. Процедура поиска использует в работе три квантовых регистра jAijD(A)ijyi: регистр множеств jAi хранит множество A С [n] размера jAj = r, регистр данных jD(A)i хранит структуру данных D(A), а регистр монет jyi хранит элемент i <£ A. Проверяя структуру данных 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))) квантовых запросов. (Более подробное изложение см. в статье «Квантовый алгоритм различения элементов»).