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

\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.  

Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением 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.