Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
P_M & 0 \\ | P_M & 0 \\ | ||
P'' & I | P'' & I | ||
\end{bmatrix}</math>, где P | \end{bmatrix}</math>, где P" – матрица, полученная из P удалением столбцов, индексированных M, и строк, индексированных S \ M. P' ведет себя аналогично P, но поглощается первым помеченным состоянием, которого оно достигает. Рассмотрим квантование <math>W_{P'}</math> матрицы P' и определим ''квантовое время достижения'', H, множества M как наименьшее m, для которого <math>|W^m_{P'} \phi_0 - \phi_0| \ge 0.1</math>, где <math>\phi_0 := \sum_{x \in S} \sqrt{1/N} |x \rangle | p_x \rangle</math> (которое является стационарным для <math>W_P</math>). Заметим, что стоимость построения <math>W_{P'}</math> пропорциональна U + C. | ||
Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением P0, необходимое для заметного перекоса равномерного начального распределения. Аналогичным образом квантовое время достижения ограничивает число итераций следующего квантового алгоритма, служащего для определения того, является ли M непустым. На каждом шаге применяем оператор | Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением P0, необходимое для заметного перекоса равномерного начального распределения. Аналогичным образом квантовое время достижения ограничивает число итераций следующего квантового алгоритма, служащего для определения того, является ли M непустым. На каждом шаге применяем оператор <math>W_{P'}</math>. Если M пусто, то P0 = P и начальное состояние остается неизменным. Если M непусто, то угол между \¥р,фо и Wptpo постепенно увеличивается. Используя дополнительный регистр управления для применения либо WP0, либо <math>W_P</math> с квантовым управлением, можно определить расхождение этих двух состояний (если M непусто). Необходимое число итераций равно ровно H. | ||
Остается вычислить H. Когда P симметрично и эргодично, выражение для классического времени достижения цели имеет квантовый аналог [ ] (jMj < N/2 по техническим причинам): | Остается вычислить H. Когда P симметрично и эргодично, выражение для классического времени достижения цели имеет квантовый аналог [ ] (jMj < N/2 по техническим причинам): | ||