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

'''Теорема 1 [2]. Пусть Р – случайное блуждание по графу Джонсона J(r, m), r = o(m); пусть M – либо пустое множество, либо множество всех подмножеств размера r, содержащих фиксированное подмножество <math>x_1, ..., x_k</math> при константном <math>k \le r</math>. Тогда существует квантовый алгоритм, решающий задачу достижения (версия с поиском) со стоимостью порядка <math>S + t(\sqrt{r} \cdot U + C)</math>, где <math>t = (\frac{m}{r})^{k/2}</math>. Если стоимости равны S = r, U = O(1) и C = 0, то суммарная стоимость имеет оптимум <math>O(m^{k/(k+1)})</math> при <math>r = O(m^{k/(k+1)})</math>.'''

Для цепи Маркова P (классическое) ''среднее время достижения'' относительно M может быть выражено в терминах матрицы блужданий с утечкой PM, которая получается из P путем удаления всех строк и столбцов, индексированных состояниями M. Обозначим за h(x; M) ожидаемое время достижения M из x, а за vi,.... , vN_\M\, X\,... , AN_|M| – (нормализованные) собственные векторы и соответствующие собственные значения PM. Обозначим за d : S ! R+ начальное распределение, а за d0 – его ограничение на S n M. Тогда h := Px2S d(x)h(x; M) = T,k~iMl 1(?-1^)|2- Хотя матрица блужданий с утечкой PM не является стохастической, можно рассмотреть матрицу поглощающих блужданий P0 = [ pJf, °], где P00 – матрица, полученная из P удалением столбцов, индексированных M, и строк, индексированных S n M:P0 ведет себя аналогично P, но поглощается первым помеченным состоянием, которого оно достигает. Рассмотрим квантование WP0 из P0 и определим квантовое время достижения, H, множества M как наименьшее m, для которого \W™<j)o - фо\ > 0:1, где фо := Px2S p1/Njxijpxi (которое является стационарным для WP). Заметим, что стоимость построения WP0 пропорциональна 17+ С