Квантование цепей Маркова: различия между версиями

Перейти к навигации Перейти к поиску
Строка 107: Строка 107:
'''Различимость элементов'''
'''Различимость элементов'''


Предположим, что даны элементы x1... xm 2 f1... ; mg и задан вопрос, существуют ли i, j такие, что xi = xj. Сложность классического подхода к выполнению этого запроса равна 0(m). Амбайнис [ ] предложил (оптимальный) квантовый алгоритм запросов со сложностью O(m2/3), использующий квантовое блуждание по графу Джонсона, состоящему из m2/3 -подмножеств f1... ; mg, в котором подмножества, которые содержат i,j с xi = xj, помечены.
Предположим, что даны элементы <math>x_1, ..., x_m \in \{ 1, ..., m \}</math> и нужно узнать, существуют ли i, j такие, что <math>x_i = x_j</math>. Сложность классического подхода к выполнению этого запроса равна <math>\Theta(m)</math>. Амбайнис [2] предложил (оптимальный) квантовый алгоритм запросов со сложностью <math>O(m^{2/3})</math>, использующий квантовое блуждание по графу Джонсона, состоящему из <math>m^{2/3}</math>-подмножеств <math>\{ 1, ..., m \}</math>, в котором подмножества, которые содержат i, j с <math>x_i = x_j</math>, помечены.




'''Поиск треугольника'''
'''Поиск треугольника'''


Предположим, дана матрица смежности A графа с n вершинами и требуется определить, содержит ли граф треугольник (т.е. клику размером 3), используя как можно меньше запросов к записям A. Сложность классического подхода к решению этой задачи равна 0(n2). Маньез, Санта и Шегеди [13] предложили алгоритм со сложностью б(иьз), адаптировав решение из [2]. Маньез и др. улучшили ее до O(n1:3) в работе [12].
Предположим, дана матрица смежности A графа с n вершинами и требуется определить, содержит ли граф треугольник (т.е. клику размером 3), используя как можно меньше запросов к записям A. Сложность классического подхода к решению этой задачи равна <math>\Theta(n^2)</math>. Маньез, Санта и Шегеди [13] предложили алгоритм со сложностью <math>\tilde{O}(n^{1,3})</math>, адаптировав решение из [2]. Маньез и др. улучшили ее до <math>O(n^{1,3})</math> в работе [12].




Строка 145: Строка 145:


Понятия квантового времени смешивания на линии, цикле и гиперкубе впервые предложили и проанализировали Наяк и др. [3, 15], Ахаронов и др. [ ], а также Мур и Расселл [14]. В работах Кендон и Трегенны [10] и Рихтера [16] исследовалось использование декогеренции для улучшения перемешивания квантовых блужданий [10]. Остаются открытыми два фундаментальных вопроса о времени квантового перемешивания: как выглядит «наиболее естественное» определение и когда имеет место квантовое ускорение по сравнению с временем перемешивания в классических подходах?
Понятия квантового времени смешивания на линии, цикле и гиперкубе впервые предложили и проанализировали Наяк и др. [3, 15], Ахаронов и др. [ ], а также Мур и Расселл [14]. В работах Кендон и Трегенны [10] и Рихтера [16] исследовалось использование декогеренции для улучшения перемешивания квантовых блужданий [10]. Остаются открытыми два фундаментальных вопроса о времени квантового перемешивания: как выглядит «наиболее естественное» определение и когда имеет место квантовое ускорение по сравнению с временем перемешивания в классических подходах?


== См. также ==
== См. также ==
4551

правка

Навигация