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

'''Требуется''': найти помеченное состояние с вероятностью 0.1, если оно существует (версия с поиском), или булево возвращаемое значение с односторонней ошибкой, обнаруживающее <math>M \ne \empty</math> с вероятностью 0.1 (версия с принятием решений).

Если P ''несводима'' (т. е. если лежащий в ее основе орграф является сильно связным), то помеченное состояние может быть найдено с высокой вероятностью за конечное время путем имитации ''классического'' случайного блуждания с использованием коэффициентов P. В ''квантовом'' случае этот процесс случайного блуждания может быть заменен квантовым блужданием с использованием коэффициентов P (в частности, с соблюдением локальности).

Фундаментальный вопрос заключается в том, находит ли процесс квантового блуждания помеченное состояние ''быстрее'', чем классический процесс случайного блуждания.

Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от <math>\mathbf{C}^S</math>. Здесь выбран второй путь, нотация которого соответствует изложенной в работе [18]. На <math>\mathbf{C}^{S \times S}</math> определим унитарный оператор <math>W_P := R_1 R_2</math>, где <math>R_1 = \sum_{x \in S} (2 | p_x \rangle \langle p_x | - I) \otimes | x \rangle \langle x |</math>, <math>R_2 = \sum_{x \in S} | x \rangle \langle x | \otimes (2 | p_x \rangle \langle p_x | - I)</math>, <math> | p_x \rangle := \sum_{y \in S} \sqrt{p_{y, x}} | y \rangle</math>. <math>W_P</math> – это ''квантование'' P, или оператор ''квантового блуждания в дискретном времени'', вытекающий из P. «Проверить», помечено ли текущее состояние, можно при помощи оператора <math>O_M = \sum_{x \notin M} | x \rangle \langle x | - \sum_{x \in M} | x \rangle \langle x |</math>. Обозначим стоимость построения <math>W_P</math> (в единицах интересующего ресурса) как U (''update cost'' – стоимость обновления), стоимость построения <math>O_M</math> как C (''checking cost'' – стоимость проверки), а стоимость подготовки начального состояния, <math>\phi_0</math>, как S (''setup cost'' – стоимость настройки). Каждый раз, когда оператор используется, его стоимость прибавляется к общим затратам. Эта абстракция, неявная в [2] и явная в [13], позволяет рассматривать <math>W_P</math> и <math>O_M</math> как операторы типа «черный ящик» и обеспечивает удобный способ учета ''временной сложности'' или, в модели квантовых запросов, ''сложности в виде числа запросов''. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом:

АЛГОРИТМ: Квантовая схема <math>X = X_m X_{m - 1} ... X_1</math>, с «проводами» (обычно их два), которые переносят <math>\mathbf{C}^S</math> и управляющие биты. Каждый элемент <math>X_i</math> является либо <math>W_P</math>-вентилем, либо <math>O_M</math>-вентилем, либо управляемой версией одного из них. X применяется к начальному состоянию <math>\phi_0</math>. Стоимость последовательности равна сумме стоимостей отдельных операторов. ''Вероятность наблюдения'' – это вероятность того, что после измерения конечного состояния, <math>\phi_m</math>, в стандартном базисе, один из проводов выводит элемент из М. Если вероятность наблюдения равна q, необходимо повторить процедуру 1/<math>\sqrt q</math> раз, используя усиление по амплитуде (версия с поиском). В версии с принятием решений можно отличить М от М', если <math>| X \phi_0 - X' \phi_0 | \ge 0.1</math>, где Х выводится из <math>O_M</math>, а Х' из <math>O_{M'}</math>.

Пространственный поиск сочетает алгоритм поиска Гровера [8], который находит помеченный элемент в базе данных размера N за <math> \sqrt{N / |M|}</math> шагов, с квантовыми блужданиями.

Квантовые блуждания были впервые введены Дэвидом Мейером и Джоном Уотроусом для изучения квантовых клеточных автоматов и квантового логарифмического пространства, соответственно. Квантовые блуждания в дискретном времени исследовали Наяк и др. [3, 15], а также Ахаронов и др. [1] на бесконечной линии и N-цикле, соответственно. Центральными темами в первые годы развития концепции квантовых блужданий были определение оператора блуждания, понятия времени перемешивания и времени достижения цели, а также достижимое ускорение по сравнению с классической постановкой задачи. Экспоненциальное квантовое ускорение времени достижения между антиподами гиперкуба было показано Кемпе [9], а Чайлдс и коллеги [6] представили первую задачу с оракулом, решаемую экспоненциально быстрее алгоритмом, основанным на квантовых блужданиях, чем любым (не обязательно основанным на блужданиях) классическим алгоритмом.

Авторами первых систематических исследований квантового времени достижения на гиперкубе и 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) уравновешиваются новым способом. В отличие от этого, алгоритм Гровера – хотя он и вдохновил результат Амбайниса – не предполагает такой возможности: в его случае затраты на установку и обновление в модели запросов равны нулю.

Главное математическое наблюдение Амбайниса о блуждании W по графу Джонсона состоит в том, что <math>W^{\sqrt{r}} O_M</math> ведет себя примерно так же, как и <math>DO_M</math> итерации Гровера, где D – оператор диффузии Гровера. Вспомним, что алгоритм Гровера применяет <math>DO_M</math> многократно, переводя однородное начальное состояние <math>\phi_0</math> в состояние <math>\phi_{good} = \sum_{x \in M} \sqrt{1 / |M| | x \rangle }</math> после <math>t = O(1/ \alpha)</math> итераций, где <math>\alpha := 2 sin^{-1} \langle \phi_{good} | \phi_0 \rangle </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, 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 = \bigg( \frac{m}{r} \bigg)^{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>.'''

Для цепи Маркова P (классическое) ''среднее время достижения'' относительно M может быть выражено в терминах ''матрицы блужданий с утечкой'' <math>P_M</math>, которая получается из P путем удаления всех строк и столбцов, индексированных состояниями M. Обозначим за h(x, M) ожидаемое время достижения M из x, а за <math>v_i, ...., v_{N - |M|}, \lambda_1, ..., \lambda_{N - |M|}</math> – (нормализованные) собственные векторы и соответствующие собственные значения <math>P_M</math>. Обозначим за <math>d : S \to \mathbf{R}^+</math> начальное распределение, а за d' – его ограничение на S \ M. Тогда <math>h := \sum_{x \in S} d(x) h(x, M) = \sum_{k = 1}^{N - |M|} \frac{|v_k, d'|^2}{1 - \lambda_k}</math>. Хотя матрица блужданий с утечкой <math>P_M</math> не является стохастической, можно рассмотреть матрицу ''поглощающих блужданий'' <math>P' = \begin{bmatrix}

\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.

 

 

 

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

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

Из теорем 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, имеет вид:

 

'''Теорема 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_1 w_j - e^{i \theta_j} R_2 v_j</math> для <math>1 \le j \le l</math>.'''

Маньез и коллеги [12] использовали выполненное Шегеди квантование <math>W_P</math> эргодического блуждания P (а не его версии с поглощением P') для получения эффективной и общей реализации алгоритма абстрактного поиска Амбайниса и др. [4].

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

Предположим, что даны элементы <math>x_1, ..., x_m \in \{ 1, ..., m \}</math> и нужно узнать, существуют ли i, j такие, что <math>x_i = x_j</math>. Сложность классического подхода к выполнению этого запроса равна <math>\Theta(m)</math>. Амбайнис [2] предложил (оптимальный) квантовый алгоритм запросов со сложностью <math>O(m^{2/3})</math>, использующий квантовое блуждание по графу Джонсона, состоящему из <math>m^{2/3}</math>-подмножеств <math>\{ 1, ..., m \}</math>, в котором подмножества, которые содержат i, j с <math>x_i = x_j</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(k)</math> групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) <math>\tilde{O}(k^{2/3})</math> квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате.

== Открытые вопросы ==

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

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

'''Дано:''' цепь Маркова P на множестве S, допуск <math>\varepsilon > 0</math>.