Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 107: | Строка 107: | ||
'''Различимость элементов''' | '''Различимость элементов''' | ||
Предположим, что даны элементы | Предположим, что даны элементы <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. Сложность классического подхода к решению этой задачи равна | Предположим, дана матрица смежности 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]. Остаются открытыми два фундаментальных вопроса о времени квантового перемешивания: как выглядит «наиболее естественное» определение и когда имеет место квантовое ускорение по сравнению с временем перемешивания в классических подходах? | ||
== См. также == | == См. также == | ||