4446
правок
Квантование цепей Маркова: различия между версиями
Материал из WEGA
Квантование цепей Маркова (посмотреть исходный код)
Версия от 21:07, 20 октября 2022
, 20 октября 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
Что общего между <math>W^{\sqrt{r}}</math> и <math>D</math>? Амбайнис показал, что нетривиальные собственные значения матрицы <math>W^{\sqrt{r}}</math> в подпространстве (конечной размерности), содержащем орбиту <math>\phi_0</math>, удалены от 1 на константную величину <math>\ | Что общего между <math>W^{\sqrt{r}}</math> и <math>D</math>? Амбайнис показал, что нетривиальные собственные значения матрицы <math>W^{\sqrt{r}}</math> в подпространстве (конечной размерности), содержащем орбиту <math>\phi_0</math>, удалены от 1 на константную величину <math>\varepsilon</math>. Таким образом, <math>W^{\sqrt{r}}</math> служит очень хорошим приближенным отражением вдоль оси <math>\phi_0</math> – не менее хорошим, чем у Гровера в этом приложении. Это позволяет вывести следующее заключение: существует <math>t = O(1/ \alpha)</math>, для которого перекрытие <math>\langle \phi_{good} | (W^{\sqrt{r}} O_M)^t | \phi_0 \rangle = \Omega(1)</math>, поэтому выходное значение, вероятно, находится в M. | ||
Теорема 1 [2]. Пусть Р – случайное блуждание по графу Джонсона J(r | '''Теорема 1 [2]. Пусть Р – случайное блуждание по графу Джонсона J(r, m), r = o(m); пусть M – либо пустое множество, либо множество всех подмножеств размера r, содержащих фиксированное подмножество <math>x_1, ..., x_k</math> при константном <math>k \le r</math>. Тогда существует квантовый алгоритм, решающий задачу достижения (версия с поиском) со стоимостью порядка <math>S + t(\sqrt{r} \cdot U + C)</math>, где <math>t = (\frac{m}{r})^{k/2}</math>. Если стоимости равны S = r, U = O(1) и C = 0, то суммарная стоимость имеет оптимум <math>O(m^{k/(k+1)})</math> при <math>r = O(m^{k/(k+1)})</math>.''' | ||
| Строка 58: | Строка 58: | ||
Для цепи Маркова 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+ С | Для цепи Маркова 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+ С | ||
