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

Перейти к навигации Перейти к поиску
Строка 24: Строка 24:
'''Алгоритм квантового блуждания'''
'''Алгоритм квантового блуждания'''


Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от <math>\mathbf{C}^S</math>. Здесь выбран второй путь, нотация которого соответствует изложенной в работе [18]. На <math>\mathbf{C}^{S \times S}</math> определим унитарный оператор <math>WP := R_1 R_2</math>, где
Квантование 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>.
(px\ --0 <8> \x}(x\,R2 = J2X€S \x)(x\ ® (2\px)(px\ - I), и jpxi := Py2S ppy;xjyi. WP – это квантование P, или оператор дискретного квантового блуждания, вытекающий из P. «Проверить», помечено ли текущее состояние, можно при помощи оператора OM = Px26M \x)(x\ ~ Px2M jxihxj. Обозначим стоимость построения WP (в единицах интересующего ресурса) как U (update cost – стоимость обновления), стоимость построения OM как C (checking cost – стоимость проверки), а стоимость подготовки начального состояния, фо, как S (setup cost – стоимость настройки). Каждый раз, когда оператор используется, его стоимость прибавляется к общим затратам. Эта абстракция, неявная в [ ] и явная в [13], позволяет рассматривать WP и OM как операторы типа «черный ящик» и обеспечивает удобный способ учета временной сложности или, в модели квантовых запросов, сложности запроса. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом:
 
WP – это квантование P, или оператор дискретного квантового блуждания, вытекающий из P. «Проверить», помечено ли текущее состояние, можно при помощи оператора OM = Px26M \x)(x\ ~ Px2M jxihxj. Обозначим стоимость построения WP (в единицах интересующего ресурса) как U (update cost – стоимость обновления), стоимость построения OM как C (checking cost – стоимость проверки), а стоимость подготовки начального состояния, фо, как S (setup cost – стоимость настройки). Каждый раз, когда оператор используется, его стоимость прибавляется к общим затратам. Эта абстракция, неявная в [ ] и явная в [13], позволяет рассматривать WP и OM как операторы типа «черный ящик» и обеспечивает удобный способ учета временной сложности или, в модели квантовых запросов, сложности запроса. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом:




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