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

'''Теорема 2 [18]. Пусть P симметрично и эргодично, и пусть h – классическое время достижения для помеченного множества M и равномерного начального распределения. Тогда квантовое время достижения для M не превышает <math>\sqrt{h}</math>.'''

'''Теорема 3 [18]. Если P является транзитивным по состоянию и |M| = 1, то помеченное состояние наблюдается за <math>O(\sqrt{h})</math> шагов с вероятностью не менее N/h.'''

Из теорем 2 и 3 вытекает большинство результатов предыдущего раздела о квантовом времени достижения цели ''без вычислений'', опираясь только на оценки соответствующих классических алгоритмов времени достижения. Выражение (1) основано на фундаментальной связи между собственными значениями и собственными векторами P и <math>W_P</math>. Заметим, что <math>R_1</math> и <math>R_2</math> являются отражениями на подпространствах, порожденных <math> \{ |p_x \rangle \otimes | x \rangle | x \in S \}</math> и <math> \{ |x \rangle \otimes | p_x \rangle | x \in S \}</math>, соответственно. Следовательно, собственные значения <math>R_1 R_2</math> могут быть выражены в терминах собственных значений взаимной матрицы Грама этих систем. Эта матрица D, ''матрица дискриминантов'' P, имеет вид: