Квантовый алгоритм различения элементов: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 116: | Строка 116: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
1. Сколько запросов необходимо для решения задачи различения элементов, если доступная алгоритму память ограничена r элементами, r < | 1. Сколько запросов необходимо для решения задачи различения элементов, если доступная алгоритму память ограничена r элементами, <math>r < N^{2/3}</math>? Алгоритм из [2] дает <math>O(N/ \sqrt{r})</math> запросов, а лучшей нижней границей является <math>\Omega(N^{2/3})</math> запросов. | ||
2. Рассмотрим следующий пример: | 2. Рассмотрим следующий пример: | ||
Коллизия в графе [ ]. Начальными условиями являются граф G (произвольный, но известный заранее) и переменные | |||
Алгоритм различения элементов может быть адаптирован для решения этой задачи с помощью O( | '''Коллизия в графе''' [12]. Начальными условиями являются граф G (произвольный, но известный заранее) и переменные <math>x_1, ..., x_N \in \{ 0, 1 \}</math>, доступные путем запросов к оракулу. Задача состоит в том, чтобы определить, содержит ли граф G ребро uv, такое, что <math>x_u = x_v = 1</math>. Сколько запросов необходимо для ее решения? | ||
Алгоритм различения элементов может быть адаптирован для решения этой задачи с помощью <math>O(N^{2/3})</math> запросов [ ], однако соответствующая нижняя граница не найдена. Существует ли лучший алгоритм? Если будет найден лучший алгоритм для задачи поиска коллизии в графе, то сразу же будет разработан лучший алгоритм для задачи о треугольнике. | |||
== См. также == | == См. также == | ||