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

Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от <math>\mathbf{C}^S</math>. Здесь выбран второй путь, нотация которого соответствует изложенной в работе [18]. На <math>\mathbf{C}^{S \times S}</math> определим унитарный оператор <math>W_P := R_1 R_2</math>, где <math>R_1 = \sum_{x \in S} (2 | p_x \rangle \langle p_x | - I) \otimes | x \rangle \langle x |</math>, <math>R_2 = \sum_{x \in S} | x \rangle \langle x | \otimes (2 | p_x \rangle \langle p_x | - I)</math>, <math> | p_x \rangle := \sum_{y \in S} \sqrt{p_{y, x}} | y \rangle</math>. <math>W_P</math> – это ''квантование'' P, или оператор ''квантового блуждания в дискретном времени'', вытекающий из P. «Проверить», помечено ли текущее состояние, можно при помощи оператора <math>O_M = \sum_{x \notin M} | x \rangle \langle x | - \sum_{x \in M} | x \rangle \langle x |</math>. Обозначим стоимость построения <math>W_P</math> (в единицах интересующего ресурса) как U (''update cost'' – стоимость обновления), стоимость построения <math>O_M</math> как C (''checking cost'' – стоимость проверки), а стоимость подготовки начального состояния, <math>\phi_0</math>, как S (''setup cost'' – стоимость настройки). Каждый раз, когда оператор используется, его стоимость прибавляется к общим затратам. Эта абстракция, неявная в [2] и явная в [13], позволяет рассматривать <math>W_P</math> и <math>O_M</math> как операторы типа «черный ящик» и обеспечивает удобный способ учета ''временной сложности'' или, в модели квантовых запросов, ''сложности запроса''. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом: