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

Перейти к навигации Перейти к поиску
Строка 74: Строка 74:




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




Строка 80: Строка 80:




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




Из теорем 2 и 3 вытекает большинство результатов предыдущего раздела о квантовом времени достижения цели без вычислений, опираясь только на оценки соответствующих классических алгоритмов времени достижения. Выражение (1) основано на фундаментальной связи между собственными значениями и собственными векторами P и WP. Заметим, что R1 и R2 являются отражениями на подпространствах, порожденных f j px ® \x}\ x 2 S}и{|x) ® pxij x 2 Sg, соответственно. Следовательно, собственные значения R1R2 могут быть выражены в терминах собственных значений взаимной матрицы Грама этих систем. Эта матрица D, матрица дискриминантов P, имеет вид:
Из теорем 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, имеет вид:
 
(2) <math> D(P) = \sqrt{P \circ P_T} = (\sqrt{p_{x, y} p_{y, x}})_{x, y \in S}.</math>




4551

правка

Навигация