4551
правка
Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
Квантование цепей Маркова (посмотреть исходный код)
Версия от 15:19, 21 ноября 2022
, 21 ноября 2022→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 105: | Строка 105: | ||
== Применение == | == Применение == | ||
''' | '''Различение элементов''' | ||
Предположим, что даны элементы <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>, помечены. | Предположим, что даны элементы <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>, помечены. | ||
| Строка 112: | Строка 112: | ||
'''Поиск треугольника''' | '''Поиск треугольника''' | ||
Предположим, дана матрица смежности A графа с n вершинами и требуется определить, содержит ли граф треугольник (т.е. клику | Предположим, что дана матрица смежности 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]. | ||
'''Верификация матричного произведения''' | '''Верификация матричного произведения''' | ||
Предположим, даны три матрицы A, B, C размера <math>n \times n</math> и требуется определить, верно ли соотношение <math>AB \ne C</math> (то есть, существуют ли i,j такие, что <math>\sum_k A_{ik} B_{kj} \ne C_{ij}</math>), используя как можно меньше запросов к | Предположим, что даны три матрицы A, B, C размера <math>n \times n</math> и требуется определить, верно ли соотношение <math>AB \ne C</math> (то есть, существуют ли i,j такие, что <math>\sum_k A_{ik} B_{kj} \ne C_{ij}</math>), используя как можно меньше запросов к элементам A, B и C. Сложность классического подхода к решению этой задачи равна <math>\Theta(n^2)</math>. Бурман и Спалек [5] предложили квантовый алгоритм выполнения запросов со сложностью <math>O(n^{5/3})</math>, используя результаты из [18]. | ||
'''Проверка коммутативности группы''' | '''Проверка коммутативности группы''' | ||
Предположим, что имеется группа типа «черный ящик», заданная k генераторами, и требуется определить, коммутативна ли эта группа, используя как можно меньше запросов к операции группового произведения (т. е. запросов вида «Чему равно произведение элементов g и h?»). Сложность классического подхода к решению этой задачи составляет <math>\Theta( | Предположим, что имеется группа типа «черный ящик», заданная k генераторами, и требуется определить, коммутативна ли эта группа, используя как можно меньше запросов к операции группового произведения (т. е. запросов вида «Чему равно произведение элементов g и h?»). Сложность классического подхода к решению этой задачи составляет <math>\Theta(k)</math> групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) <math>\tilde{O}(k^{2/3})</math> квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате. | ||
== Открытые вопросы == | == Открытые вопросы == | ||