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

'''Теорема 4 [18]. Пусть P – произвольная цепь Маркова на конечном пространстве состояний S, и пусть <math>cos \; \theta_1 \ge ... \ge cos \; \theta_l</math> – сингулярные значения D(P), лежащие в открытом интервале (0, 1), с соответствующими парами сингулярных векторов <math>v_j, w_j</math> для <math>1 \le j \le l</math>. Тогда нетривиальные собственные значения <math>W_P</math> (исключая 1 и -1) и соответствующие им собственные векторы имеют вид - e~2WJ, R1wj - e~wjR2Vj; e2W) и Rjwj - ewjR2Vj для 1 < j < l.'''

Маньез и коллеги [ ] использовали выполненное Шегеди квантование WP эргодического блуждания P (а не его версии с поглощением P0) для получения эффективной и общей реализации алгоритма абстрактного поиска Амбайниса и др. [4].

Теорема 5 [ ]. Пусть P обратима и эргодична со спектральным разрывом S > 0. Пусть M имеет помеченную вероятность, равную нулю либо " > 0. Тогда существует квантовый алгоритм, решающий задачу достижения цели (версия с поиском) со стоимостью S +