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

Что общего между <math>W^{\sqrt{r}}</math> и <math>D</math>? Амбайнис показал, что нетривиальные собственные значения матрицы <math>W^{\sqrt{r}}</math> в подпространстве (конечной размерности), содержащем орбиту <math>\phi_0</math>, удалены от 1 на константную величину <math>\epsilon</math>. Таким образом, <math>W^{\sqrt{r}}</math> служит очень хорошим приближенным отражением вдоль оси <math>\phi_0</math> – не менее хорошим, чем у Гровера в этом приложении. Это позволяет вывести следующее заключение: существует t = O(l/a), для которого перекрытие {фё00а\(№-^ОмУ\Фо} = &(1), поэтому выходное значение, вероятно, находится в M.

Теорема 1 [2]. Пусть Р – случайное блуждание по графу Джонсона J(r; m) с r = o(m); пусть M – либо пустое множество, либо множество всех подмножеств размера r, содержащих фиксированное подмножество x1... xk при константном k < r. Тогда существует квантовый алгоритм, решающий задачу достижения (версия с поиском) со стоимостью порядка S + t(pr ■ U + C), где t = (m )k/2. Если стоимости равны S = r, U = O(1) и C = 0, то суммарная стоимость имеет оптимум O(mk/(k+1)) при r = O(mk/(k+1)).

Для цепи Маркова P (классическое) среднее время достижения относительно M может быть выражено в терминах матрицы блужданий с утечкой PM, которая получается из P путем удаления всех строк и столбцов, индексированных состояниями M. Обозначим за h(x; M) ожидаемое время достижения M из x, а за vi,.... , vN_\M\, X\,... , AN_|M| – (нормализованные) собственные векторы и соответствующие собственные значения PM. Обозначим за d : S ! R+ начальное распределение, а за d0 – его ограничение на S n M. Тогда h := Px2S d(x)h(x; M) = T,k~iMl 1(?-1^)|2- Хотя матрица блужданий с утечкой PM не является стохастической, можно рассмотреть матрицу поглощающих блужданий P0 = [ pJf, °], где P00 – матрица, полученная из P удалением столбцов, индексированных M, и строк, индексированных S n M:P0 ведет себя аналогично P, но поглощается первым помеченным состоянием, которого оно достигает. Рассмотрим квантование WP0 из P0 и определим квантовое время достижения, H, множества M как наименьшее m, для которого \W™<j)o - фо\ > 0:1, где фо := Px2S p1/Njxijpxi (которое является стационарным для WP). Заметим, что стоимость построения WP0 пропорциональна 17+ С