Квантовый алгоритм различения элементов: различия между версиями

Перейти к навигации Перейти к поиску
Строка 33: Строка 33:




Задача о различении k элементов (и нахождении k-подмножества) может быть решена с помощью O(Nk/(k+1)) запросов о значениях и использования O(Nk/(k+1)) памяти. Для случая, когда память ограничена r < Nk/(k+1) значениями xi, достаточно использовать O(r + (Nkl2)/(r(k~1)l2)) запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов).
Задача о различении 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> запросов о значениях. Эти результаты можно обобщить на запросы о сравнениях и временную сложность, причем временная сложность увеличивается с полилогарифмическим коэффициентом (аналогично задаче о различении элементов).




Различение элементов: методы
'''Различение элементов: методы'''


Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями jTi для всех наборов индексов T С {1,... ; Ng с jTj = r. Алгоритм начинает с равномерной суперпозиции всех j Ti и многократно применяет последовательность из двух преобразований:
Алгоритм Амбайниса имеет следующую структуру. Его пространство состояний охватывается базовыми состояниями <math>|T \rangle</math> для всех наборов индексов <math>T \subseteq \{ 1, ..., N \}</math>, |T| = r. Алгоритм начинает с равномерной суперпозиции всех <math>|T \rangle</math> и многократно применяет последовательность из двух преобразований:
1. Условный переворот фазы: j T -> - T i для всех T, таких, что Г содержит i, j с xi = xj, и j Ti !j T i для всех остальных T;
 
2. Квантовое блуждание: выполнить O(pr) шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое jTi на комбинацию базисных состояний jT0i для T, которые отличаются от 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]. Каждый шаг представляет собой преобразование, которое отображает каждое jTi на комбинацию базисных состояний jT0i для T, которые отличаются от T на один элемент.




4501

правка

Навигация