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

Перейти к навигации Перейти к поиску
Строка 117: Строка 117:
'''Верификация матричного произведения'''
'''Верификация матричного произведения'''


Предположим, даны три n х n матрицы A, B, C и требуется определить, является ли AB ф C (то есть, существуют ли i,j такие, что PkAikBkj ф Cij), используя как можно меньше запросов к записям A, B и C. Сложность классического подхода к решению этой задачи равна 0(n2). Бурман и Спалек [5] предложили квантовый алгоритм выполнения запросов со сложностью O(n5/3), используя результаты из [18].
Предположим, даны три матрицы 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?»). Сложность классического подхода к решению этой задачи составляет 0(k) групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) 6(/c2/3) квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате.
Предположим, что имеется группа типа «черный ящик», заданная k генераторами, и требуется определить, коммутативна ли эта группа, используя как можно меньше запросов к операции группового произведения (т. е. запросов вида «Чему равно произведение элементов g и h?»). Сложность классического подхода к решению этой задачи составляет <math>\Theta(n^2)</math> групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) <math>\tilde{O}(k^{2/3})</math> квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате.


 
== Открытые вопросы ==
'''Открытые вопросы'''
Многие вопросы квантования цепей Маркова остаются нерешенными – как для задачи достижения цели, так и для тесно связанной с ней задачи перемешивания.
Многие вопросы квантования цепей Маркова остаются нерешенными – как для задачи достижения цели, так и для тесно связанной с ней задачи перемешивания.


Строка 131: Строка 130:
'''Достижение цели'''
'''Достижение цели'''


Можно ли распространить квадратичное ускорение квантового времени достижения со всех симметричных цепей Маркова на все обратимые? Можно ли распространить нижнюю границу вероятности наблюдения из [ ] за пределы класса транзитивных по состоянию цепей Маркова с единственным помеченным состоянием? Какие еще алгоритмические приложения квантового времени достижения можно найти?
Можно ли распространить квадратичное ускорение квантового времени достижения со всех симметричных цепей Маркова на все обратимые? Можно ли распространить нижнюю границу вероятности наблюдения из [18] за пределы класса транзитивных по состоянию цепей Маркова с единственным помеченным состоянием? Какие еще алгоритмические приложения квантового времени достижения можно найти?




'''Перемешивание'''
'''Перемешивание'''


Еще одной сферой широкого применения цепей Маркова в классических алгоритмах является перемешивание. В частности, алгоритмы Марковской цепи в методе Монте-Карло работают путем запуска эргодической цепи Маркова с тщательно выбранным стационарным распределением ж до достижения времени перемешивания; в этот момент распределение текущего состояния гарантированно "-близко к равномерному. Такие алгоритмы лежат в основе большинства рандомизированных алгоритмов для аппроксимации #P-полных задач. Таким образом, задача выглядит следующим образом:
Еще одной сферой широкого применения цепей Маркова в классических алгоритмах является ''перемешивание''. В частности, алгоритмы ''Марковской цепи в методе Монте-Карло'' работают путем запуска эргодической цепи Маркова с тщательно выбранным стационарным распределением <math>\pi</math> до достижения времени перемешивания; в этот момент распределение текущего состояния гарантированно <math>\varepsilon</math>-близко к равномерному. Такие алгоритмы лежат в основе большинства рандомизированных алгоритмов для аппроксимации #P-полных задач. Таким образом, задача выглядит следующим образом:




Дано: цепь Маркова P на множестве S, допуск ">0.
'''Дано:''' цепь Маркова P на множестве S, допуск <math>\varepsilon > 0</math>.


Требуется: найти состояние, "-близкое к ж по суммарному вариационному расстоянию.
'''Требуется''': найти состояние, <math>\varepsilon</math>-близкое к <math>\pi</math> по суммарному вариационному расстоянию.




Источник — http://pco.iis.nsk.su/wega/index.php/Квантование_цепей_Маркова