4551
правка
Квантовый алгоритм поиска треугольников: различия между версиями
Перейти к навигации
Перейти к поиску
м
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 22:43, 6 апреля 2016
, 6 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
'''Теорема 2 (Шегеди и коллеги [13, 14]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи <math>\tilde{O} (n^{1 + \epsilon} + n^{1 + \delta + \epsilon '} + \sqrt{n^{3 - \epsilon '}} + \sqrt{n^{3 - min \{ \delta, \; \epsilon - \delta - \epsilon ' \} }} )</math> квантовых запросов.''' | '''Теорема 2 (Шегеди и коллеги [13, 14]). Используя технику квантового увеличения амплитуды, задачу поиска треугольников можно решить при помощи <math>\tilde{O} (n^{1 + \epsilon} + n^{1 + \delta + \epsilon '} + \sqrt{n^{3 - \epsilon '}} + \sqrt{n^{3 - min \{ \delta, \; \epsilon - \delta - \epsilon ' \} }} )</math> квантовых запросов.''' | ||
Если положить | Если положить <math>\epsilon = 3/7 \;</math> и <math>\epsilon ' = \delta = 1/7 \;</math>, получим алгоритм, использующий <math>\tilde{O} (n^{10/7} ) \;</math> квантовых запросов. | ||
Алгоритм с квантовым блужданием; сложность <math>\tilde{O} (n^{13/10} ) \;</math> | '''Алгоритм с квантовым блужданием; сложность <math>\tilde{O} (n^{13/10} ) \;</math>''' | ||
Более эффективный алгоритм поиска треугольников предложили Маньез и коллеги [ ]; он использует процедуру квантового блуждания, введенную Амбайнисом [ ] для получения оптимального алгоритма квантовых запросов для решения задачи различения элементов. | Более эффективный алгоритм поиска треугольников предложили Маньез и коллеги [13 ]; он использует процедуру квантового блуждания, введенную Амбайнисом [3] для получения оптимального алгоритма квантовых запросов для решения задачи различения элементов. | ||
Пусть имеется обращение оракула к функции f, определяющей отношение C | Пусть имеется обращение оракула к функции 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))) квантовых запросов. (Более подробное изложение см. в статье «Квантовый алгоритм различения элементов»). | ||