4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 74: | Строка 74: | ||
Теорема 2 [18]. Пусть P симметрично и эргодично, и пусть h – классическое время достижения для помеченного множества M и равномерного начального распределения. Тогда квантовое время достижения для M не превышает | '''Теорема 2 [18]. Пусть P симметрично и эргодично, и пусть h – классическое время достижения для помеченного множества M и равномерного начального распределения. Тогда квантовое время достижения для M не превышает <math>\sqrt{h}</math>.''' | ||
Строка 80: | Строка 80: | ||
Теорема 3 [18]. Если P является транзитивным по состоянию и | '''Теорема 3 [18]. Если P является транзитивным по состоянию и |M| = 1, то помеченное состояние наблюдается за <math>O(\sqrt{h})</math> шагов с вероятностью не менее N/h.''' | ||
Из теорем 2 и 3 вытекает большинство результатов предыдущего раздела о квантовом времени достижения цели без вычислений, опираясь только на оценки соответствующих классических алгоритмов времени достижения. Выражение (1) основано на фундаментальной связи между собственными значениями и собственными векторами 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> | |||
правка