4551
правка
Квантование цепей Маркова: различия между версиями
Материал из WEGA
Квантование цепей Маркова (посмотреть исходный код)
Версия от 22:57, 23 октября 2022
, 23 октября 2022→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 117: | Строка 117: | ||
'''Верификация матричного произведения''' | '''Верификация матричного произведения''' | ||
Предположим, даны три | Предположим, даны три матрицы 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?»). Сложность классического подхода к решению этой задачи составляет | Предположим, что имеется группа типа «черный ящик», заданная k генераторами, и требуется определить, коммутативна ли эта группа, используя как можно меньше запросов к операции группового произведения (т. е. запросов вида «Чему равно произведение элементов g и h?»). Сложность классического подхода к решению этой задачи составляет <math>\Theta(n^2)</math> групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) <math>\tilde{O}(k^{2/3})</math> квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате. | ||
== Открытые вопросы == | |||
Многие вопросы квантования цепей Маркова остаются нерешенными – как для задачи достижения цели, так и для тесно связанной с ней задачи перемешивания. | Многие вопросы квантования цепей Маркова остаются нерешенными – как для задачи достижения цели, так и для тесно связанной с ней задачи перемешивания. | ||
| Строка 131: | Строка 130: | ||
'''Достижение цели''' | '''Достижение цели''' | ||
Можно ли распространить квадратичное ускорение квантового времени достижения со всех симметричных цепей Маркова на все обратимые? Можно ли распространить нижнюю границу вероятности наблюдения из [ ] за пределы класса транзитивных по состоянию цепей Маркова с единственным помеченным состоянием? Какие еще алгоритмические приложения квантового времени достижения можно найти? | Можно ли распространить квадратичное ускорение квантового времени достижения со всех симметричных цепей Маркова на все обратимые? Можно ли распространить нижнюю границу вероятности наблюдения из [18] за пределы класса транзитивных по состоянию цепей Маркова с единственным помеченным состоянием? Какие еще алгоритмические приложения квантового времени достижения можно найти? | ||
'''Перемешивание''' | '''Перемешивание''' | ||
Еще одной сферой широкого применения цепей Маркова в классических алгоритмах является перемешивание. В частности, алгоритмы Марковской цепи в методе Монте-Карло работают путем запуска эргодической цепи Маркова с тщательно выбранным стационарным распределением | Еще одной сферой широкого применения цепей Маркова в классических алгоритмах является ''перемешивание''. В частности, алгоритмы ''Марковской цепи в методе Монте-Карло'' работают путем запуска эргодической цепи Маркова с тщательно выбранным стационарным распределением <math>\pi</math> до достижения времени перемешивания; в этот момент распределение текущего состояния гарантированно <math>\varepsilon</math>-близко к равномерному. Такие алгоритмы лежат в основе большинства рандомизированных алгоритмов для аппроксимации #P-полных задач. Таким образом, задача выглядит следующим образом: | ||
Дано: цепь Маркова P на множестве S, допуск | '''Дано:''' цепь Маркова P на множестве S, допуск <math>\varepsilon > 0</math>. | ||
Требуется: найти состояние, | '''Требуется''': найти состояние, <math>\varepsilon</math>-близкое к <math>\pi</math> по суммарному вариационному расстоянию. | ||
