4551
правка
Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
Квантование цепей Маркова (посмотреть исходный код)
Версия от 19:24, 15 октября 2022
, 15 октября 2022→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
'''Алгоритм квантового блуждания''' | '''Алгоритм квантового блуждания''' | ||
Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от <math>\mathbf{C}^S</math>. Здесь выбран второй путь, нотация которого соответствует изложенной в работе [18]. На <math>\mathbf{C}^{S \times S}</math> определим унитарный оператор <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>. | ||
WP – это квантование P, или оператор дискретного квантового блуждания, вытекающий из P. «Проверить», помечено ли текущее состояние, можно при помощи оператора OM = Px26M \x)(x\ ~ Px2M jxihxj. Обозначим стоимость построения WP (в единицах интересующего ресурса) как U (update cost – стоимость обновления), стоимость построения OM как C (checking cost – стоимость проверки), а стоимость подготовки начального состояния, фо, как S (setup cost – стоимость настройки). Каждый раз, когда оператор используется, его стоимость прибавляется к общим затратам. Эта абстракция, неявная в [ ] и явная в [13], позволяет рассматривать WP и OM как операторы типа «черный ящик» и обеспечивает удобный способ учета временной сложности или, в модели квантовых запросов, сложности запроса. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом: | |||