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

Авторами первых систематических исследований квантового времени достижения на гиперкубе и d-мерном торе были Шенви и др. [17], а также Амбайнис и др. [4]. Улучшая алгоритм пространственного поиска Ааронсона и Амбайниса, основанный на алгоритме поиска Гровера, Амбайнис и др. [4] показали, что d-мерный тор (с <math>N = n^d</math> узлами) может быть исследован с помощью квантового блуждания со стоимостью порядка <math>S + \sqrt{N}(U + C)</math> и вероятностью наблюдения <math>\Omega(1 / log N)</math> для <math>d \ge 3</math>, и со стоимостью порядка <math>S + \sqrt{N log N}(U + C)</math> и вероятностью наблюдения <math>\Omega(1)</math> для <math>d = 2</math>. Ключевое отличие этих результатов от результатов работы [6, 9] заключается в том, что блуждание должно начинаться из однородного состояния, а не из того, которое каким-то образом «связано» с состоянием, в которое вы хотите попасть. Только в последнем случае можно достичь экспоненциального ускорения.

Первый результат, который использовал квантовое блуждание для решения естественной алгоритмической задачи, так называемой ''задачи различимости элементов'', принадлежит Амбайнису [2]. Алгоритм Амбайниса использует блуждание W по ''графу Джонсона'' J(r, m), вершинами которого являются подмножества размера r из совокупности размера m, причем два подмножества связаны в том и только том случае, если их симметрическая разность имеет величину 2. Актуальность этого графа вытекает из нетривиальной алгоритмической идеи, согласно которой три различные стоимости (S, U и C) уравновешиваются новым способом. В отличие от этого, алгоритм Гровера – хотя он и вдохновил результат Амбайниса – не предполагает такой возможности: в его случае затраты на установку и обновление в модели запросов равны нулю.

Что общего между <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.

\end{bmatrix}</math>, где P" – матрица, полученная из P удалением столбцов, индексированных M, и строк, индексированных S \ M. P' ведет себя аналогично P, но поглощается первым помеченным состоянием, которого оно достигает. Рассмотрим квантование <math>W_{P'}</math> матрицы P' и определим ''квантовое время достижения'', H, множества M как наименьшее m, для которого <math>|W^m_{P'} \phi_0 - \phi_0| \ge 0.1</math>, где <math>\phi_0 := \sum_{x \in S} \sqrt{1/N} |x \rangle | p_x \rangle</math> (которое является стационарным для <math>W_P</math>). Заметим, что стоимость построения <math>W_{P'}</math> пропорциональна U + C.  

Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением P', необходимое для заметного перекоса равномерного начального распределения. Аналогичным образом квантовое время достижения ограничивает число итераций следующего квантового алгоритма, служащего для определения того, является ли M непустым. На каждом шаге применяем оператор <math>W_{P'}</math>. Если M пусто, то P' = P и начальное состояние остается неизменным. Если M непусто, то угол между <math>W^t_{P'} \phi_0</math> и <math>W^t_P \phi_0</math> постепенно увеличивается. Используя дополнительный ''регистр управления'' для применения либо <math>W_{P'}</math>, либо <math>W_P</math> с квантовым управлением, можно определить расхождение этих двух состояний (если M непусто). Необходимое число итераций равно ровно H.

'''Теорема 4 [18]. Пусть P – произвольная цепь Маркова на конечном пространстве состояний S, и пусть <math>cos \; \theta_1 \ge ... \ge cos \; \theta_l</math> – сингулярные значения D(P), лежащие в открытом интервале (0, 1), с соответствующими парами сингулярных векторов <math>v_j, w_j</math> для <math>1 \le j \le l</math>. Тогда нетривиальные собственные значения <math>W_P</math> (исключая 1 и -1) и соответствующие им собственные векторы имеют вид <math>e^{- 2i \theta_j}, R_1 w_j - e^{-i \theta_j} R_2 v_j; e^{2i \theta_j}, R_j w_j - e^{i \theta_j} R_2 v_j</math> для <math>1 \le j \le l</math>.'''

'''Различимость элементов'''

Предположим, дана матрица смежности A графа с n вершинами и требуется определить, содержит ли граф треугольник (т.е. клику размером 3), используя как можно меньше запросов к записям A. Сложность классического подхода к решению этой задачи равна <math>\Theta(n^2)</math>. Маньез, Санта и Шегеди [13] предложили алгоритм со сложностью <math>\tilde{O}(n^{1,3})</math>, адаптировав решение из [2]. Маньез и др. улучшили ее до <math>O(n^{1,3})</math> в работе [12].

Предположим, даны три матрицы A, B, C размера <math>n \times n</math> и требуется определить, верно ли соотношение <math>AB \ne C</math> (то есть, существуют ли i,j такие, что <math>\sum_k A_{ik} B_{kj} \ne C_{ij}</math>), используя как можно меньше запросов к записям A, B и C. Сложность классического подхода к решению этой задачи равна <math>\Theta(n^2)</math>. Бурман и Спалек [5] предложили квантовый алгоритм выполнения запросов со сложностью <math>O(n^{5/3})</math>, используя результаты из [18].

Предположим, что имеется группа типа «черный ящик», заданная k генераторами, и требуется определить, коммутативна ли эта группа, используя как можно меньше запросов к операции группового произведения (т. е. запросов вида «Чему равно произведение элементов g и h?»). Сложность классического подхода к решению этой задачи составляет <math>\Theta(n^2)</math> групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) <math>\tilde{O}(k^{2/3})</math> квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате.

Можно ли распространить квадратичное ускорение квантового времени достижения со всех симметричных цепей Маркова на все обратимые? Можно ли распространить нижнюю границу вероятности наблюдения из [18] за пределы класса транзитивных по состоянию цепей Маркова с единственным помеченным состоянием? Какие еще алгоритмические приложения квантового времени достижения можно найти?

Еще одной сферой широкого применения цепей Маркова в классических алгоритмах является ''перемешивание''. В частности, алгоритмы ''Марковской цепи в методе Монте-Карло'' работают путем запуска эргодической цепи Маркова с тщательно выбранным стационарным распределением <math>\pi</math> до достижения времени перемешивания; в этот момент распределение текущего состояния гарантированно <math>\varepsilon</math>-близко к равномерному. Такие алгоритмы лежат в основе большинства рандомизированных алгоритмов для аппроксимации #P-полных задач. Таким образом, задача выглядит следующим образом:

Понятия квантового времени смешивания на линии, цикле и гиперкубе впервые предложили и проанализировали Наяк и др. [3, 15], Ахаронов и др. [ ], а также Мур и Расселл [14]. В работах Кендон и Трегенны [10] и Рихтера [16] исследовалось использование декогеренции для улучшения перемешивания квантовых блужданий [10]. Остаются открытыми два фундаментальных вопроса о времени квантового перемешивания: как выглядит «наиболее естественное» определение и когда имеет место квантовое ускорение по сравнению с временем перемешивания в классических подходах?