4551
правка
Квантовый алгоритм различения элементов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Квантовый алгоритм различения элементов (посмотреть исходный код)
Версия от 23:08, 7 марта 2023
, 7 марта 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
== Основные результаты == | == Основные результаты == | ||
Различение элементов: краткое изложение результатов | '''Различение элементов: краткое изложение результатов''' | ||
В классическом (неквантовом) контексте естественное решение задачи различения элементов осуществляется путем сортировки, как описано в предыдущем разделе. При этом используется O(N) запросов о значениях (или O(N log N) запросов о сравнении) и O(N log N) времени. Любому классическому алгоритму требуется <math>\Omega</math>(N) запросов о значениях или <math>\Omega</math>(N log N) запросов о сравнении. Для алгоритмов, ограниченных пространством o(N), известны более сильные нижние границы [15]. | |||
В квантовом контексте Бурман и коллеги [5] предложили первый нетривиальный квантовый алгоритм, использующий <math>O(N^{3/4})</math> запросов. Затем Амбайнис [2] разработал новый алгоритм, основанный на новаторской идее использования квантовых блужданий. Алгоритм Амбайниса использует <math>O(N^{2/3})</math> запросов и, как известно, является оптимальным: Ааронсон и Ши [1,3,10] показали, что любой квантовый алгоритм для задачи различения элементов должен использовать <math>\Omega(N^{2/3})</math> запросов. | |||
Для квантовых алгоритмов, которые ограничены хранением r значений <math>x_i</math> (где <math>r < N^{2/3}</math>), время работы лучшего алгоритма составляет <math>O(N / \sqrt{r})</math>. | |||
Все эти результаты получены для запросов о значениях. Они могут быть адаптированы к модели запросов о сравнениях, при этом сложность увеличится в | |||
Все эти результаты получены для запросов о значениях. Они могут быть адаптированы к модели запросов о сравнениях, при этом сложность увеличится в log N раз. Временная сложность с точностью до полилогарифмического коэффициента <math>O(log^c \; N)</math> соответствует сложности в запросах, если только вычислительная модель имеет достаточно общий характер [2]. (Для реализации любого из двух известных квантовых алгоритмов необходима квантовая память с произвольным доступом). | |||