4510
правок
Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
Квантование цепей Маркова (посмотреть исходный код)
Версия от 00:36, 21 октября 2022
, 21 октября 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 64: | Строка 64: | ||
Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением | Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением P', необходимое для заметного перекоса равномерного начального распределения. Аналогичным образом квантовое время достижения ограничивает число итераций следующего квантового алгоритма, служащего для определения того, является ли M непустым. На каждом шаге применяем оператор <math>W_{P'}</math>. Если M пусто, то P' = P и начальное состояние остается неизменным. Если M непусто, то угол между <math>W^t_{P'} \phi_0</math> и <math>W^t_P \phi_0</math> постепенно увеличивается. Используя дополнительный ''регистр управления'' для применения либо <math>W_{P'}</math>, либо <math>W_P</math> с квантовым управлением, можно определить расхождение этих двух состояний (если M непусто). Необходимое число итераций равно ровно H. | ||
где | |||
Остается вычислить H. Когда P симметрично и ''эргодично'', выражение для классического времени достижения цели имеет квантовый аналог [8] (|M| <math>\le</math>N/2 по техническим причинам): | |||
(1) <math>H \le \sum_{k = 1}^{N - |M|} \frac{\nu^2_k}{\sqrt{1 - \lambda_k}}</math>, | |||
где <math>\nu_k</math> – сумма координат <math>v_k</math>, деленная на <math>1/\sqrt{N}</math>. Из (1) и выражения для h можно вывести удивительную связь между классическим и квантовым временем достижения: | |||