4551
правка
Квантовый алгоритм различения элементов: различия между версиями
Материал из WEGA
Квантовый алгоритм различения элементов (посмотреть исходный код)
Версия от 13:17, 8 марта 2023
, 8 марта 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
Задача о различении k элементов (и нахождении k-подмножества) может быть решена с помощью O( | Задача о различении k элементов (и нахождении k-подмножества) может быть решена с помощью <math>O(N^{k/(k+1)})</math> запросов о значениях с использованием <math>O(N^{k/(k+1)})</math> памяти. Для случая, когда память ограничена <math>r < N^{k/(k+1)}</math> значениями <math>x_i</math>, достаточно использовать <math>O(r + (N^{k/2})/(r^{(k - 1)/2)})</math> запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов). | ||
Различение элементов: методы | '''Различение элементов: методы''' | ||
Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями | Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями <math>|T \rangle</math> для всех наборов индексов <math>T \subseteq \{ 1, ..., N \}</math>, |T| = r. Алгоритм начинает с равномерной суперпозиции всех <math>|T \rangle</math> и многократно применяет последовательность из двух преобразований: | ||
1. Условный переворот фазы: | |||
2. Квантовое блуждание: выполнить O( | 1. Условный переворот фазы: <math>|T \rangle \to - |T \rangle</math> для всех T, таких, что в нем содержатся i, j, <math>x_i = x_j</math>, и <math>|T \rangle \to |T \rangle</math> для всех остальных T; | ||
2. Квантовое блуждание: выполнить <math>O(\sqrt{r})</math> шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое jTi на комбинацию базисных состояний jT0i для T, которые отличаются от T на один элемент. | |||
