4551
правка
Квантовый алгоритм различения элементов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Квантовый алгоритм различения элементов (посмотреть исходный код)
Версия от 18:14, 9 марта 2023
, 9 марта 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
Задача о различении 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> запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов). | Задача о различении 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> запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов). | ||
| Строка 40: | Строка 40: | ||
Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями <math>|T \rangle</math> для всех наборов индексов <math>T \subseteq \{ 1, ..., N \}</math>, |T| = r. Алгоритм начинает с равномерной суперпозиции всех <math>|T \rangle</math> и многократно применяет последовательность из двух преобразований: | Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями <math>|T \rangle</math> для всех наборов индексов <math>T \subseteq \{ 1, ..., N \}</math>, |T| = r. Алгоритм начинает с равномерной суперпозиции всех <math>|T \rangle</math> и многократно применяет последовательность из двух преобразований: | ||
1. Условный переворот фазы: <math>|T \rangle \to - |T \rangle</math> для всех T, | 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]. Каждый шаг представляет собой преобразование, которое отображает каждое <math>|T \rangle</math> на комбинацию базисных состояний <math>|T' \rangle</math> для T', которые отличаются от T на один элемент. | 2. Квантовое блуждание: выполнить <math>O(\sqrt{r})</math> шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое <math>|T \rangle</math> на комбинацию базисных состояний <math>|T' \rangle</math> для T', которые отличаются от T на один элемент. | ||