4430
правок
Квантование цепей Маркова: различия между версиями
Материал из WEGA
Квантование цепей Маркова (посмотреть исходный код)
Версия от 18:50, 15 октября 2022
, 15 октября 2022→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Дано: Марковская цепь P на множестве S, помеченное подмножество M | '''Дано''': Марковская цепь P на множестве S, помеченное подмножество <math>M \subseteq S</math>. | ||
Требуется: найти помеченное состояние с вероятностью 0 | '''Требуется''': найти помеченное состояние с вероятностью 0.1, если оно существует (версия с поиском), или булево возвращаемое значение с односторонней ошибкой, обнаруживающее <math>M \ne \empty</math> с вероятностью 0.1 (версия с принятием решений). | ||
Если P несводима (т. е. если лежащий в ее основе орграф является сильно связным), то помеченное состояние может быть найдено с высокой вероятностью за конечное время путем имитации классического случайного блуждания с использованием коэффициентов P. В квантовом случае этот процесс случайного блуждания может быть заменен квантовым блужданием с использованием коэффициентов P (в частности, с соблюдением локальности). | Если P ''несводима'' (т. е. если лежащий в ее основе орграф является сильно связным), то помеченное состояние может быть найдено с высокой вероятностью за конечное время путем имитации ''классического'' случайного блуждания с использованием коэффициентов P. В ''квантовом'' случае этот процесс случайного блуждания может быть заменен квантовым блужданием с использованием коэффициентов P (в частности, с соблюдением локальности). | ||
Фундаментальный вопрос заключается в том, находит ли процесс квантового блуждания помеченное состояние быстрее, чем классический процесс случайного блуждания. | Фундаментальный вопрос заключается в том, находит ли процесс квантового блуждания помеченное состояние ''быстрее'', чем классический процесс случайного блуждания. | ||
'''Алгоритм квантового блуждания''' | '''Алгоритм квантового блуждания''' | ||
Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от | Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от <math>\mathbf{C}^S</math>. Здесь выбран второй путь, нотация которого соответствует изложенной в работе [18]. На <math>\mathbf{C}^{S \times S}</math> определим унитарный оператор <math>WP := R_1 R_2</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 как операторы типа «черный ящик» и обеспечивает удобный способ учета временной сложности или, в модели квантовых запросов, сложности запроса. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом: | (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 как операторы типа «черный ящик» и обеспечивает удобный способ учета временной сложности или, в модели квантовых запросов, сложности запроса. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом: | ||
