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

''Пространственный поиск'' посредством ''квантового блуждания'' представляет собой поиск в базе данных с дополнительным ограничением, заключающимся в том, что перемещение по пространству поиска происходит путем квантового блуждания, подчиняющегося некоторой структуре локальности (решетка, гиперкуб и т .д.). Квантовые блуждания являются аналогами классических случайных блужданий на графах. Сложность пространственного поиска с помощью квантового блуждания определяется главным образом ''квантовым временем достижения цели'' [9] данного блуждания.

Пусть S, |S| = N, – конечное множество ''состояний'', и пусть <math>P = (p_{x, y})_{x, y \in S}</math> – ''матрица вероятностей перехода'' для ''цепи Маркова'' на S, также обозначаемая P. Предположим, что подмножество состояний <math>M \subseteq S</math> ''помечено''. Задача состоит в том, чтобы найти помеченное состояние, учитывая, что <math>M \ne \empty</math> (''версия с поиском''), или определить, является ли M непустым (''версия с принятием решений''). Если возможные перемещения <math>x \to y</math> (т. е. те, при которых <math>p_{x, y} \ne 0)</math> образуют ребра (ориентированного) графа G, то говорится, что блуждание имеет ''структуру локальности'' G.

Квантование 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> как операторы типа «черный ящик» и обеспечивает удобный способ учета ''временной сложности'' или, в модели квантовых запросов, ''сложности запроса''. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом:

Авторами первых систематических исследований квантового времени достижения на гиперкубе и 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 по графу Джонсона состоит в том, что Wr OM ведет себя примерно так же, как и DOM итерации Гровера, где D – оператор диффузии Гровера. Вспомним, что алгоритм Гровера применяет DOM многократно, переводя однородное начальное состояние ф0 в состояние $good = Px2M 1/jMjjxi после t = O(l/a) итераций, где a := 2 sin "1 (0goodl0o) – эффективный «угол поворота».

Что общего между Wpr и D? Амбайнис показал, что нетривиальные собственные значения матрицы Wr в подпространстве (конечной размерности), содержащем орбиту фо, удалены от 1 на константную величину ". Таким образом, Wr служит очень хорошим приближенным отражением вдоль оси фо – не менее хорошим, чем у Гровера в этом приложении. Это позволяет вывести следующее заключение: существует 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+ С

Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением P0, необходимое для заметного перекоса равномерного начального распределения. Аналогичным образом квантовое время достижения ограничивает число итераций следующего квантового алгоритма, служащего для определения того, является ли M непустым. На каждом шаге применяем оператор WP0. Если M пусто, то P0 = P и начальное состояние остается неизменным. Если M непусто, то угол между \¥р,фо и Wptpo постепенно увеличивается. Используя дополнительный регистр управления для применения либо WP0, либо WP с квантовым управлением, можно определить расхождение этих двух состояний (если M непусто). Необходимое число итераций равно ровно H.

Теорема 2 [18]. Пусть P симметрично и эргодично, и пусть h – классическое время достижения для помеченного множества M и равномерного начального распределения. Тогда квантовое время достижения для M не превышает ph.

Теорема 3 [18]. Если P является транзитивным по состоянию и jMj = 1, то помеченное состояние наблюдается за O(ph) шагов с вероятностью не менее N/h.

Из теорем 2 и 3 вытекает большинство результатов предыдущего раздела о квантовом времени достижения цели без вычислений, опираясь только на оценки соответствующих классических алгоритмов времени достижения. Выражение (1) основано на фундаментальной связи между собственными значениями и собственными векторами P и WP. Заметим, что R1 и R2 являются отражениями на подпространствах, порожденных f j px ® \x}\ x 2 S}и{|x) ® pxij x 2 Sg, соответственно. Следовательно, собственные значения R1R2 могут быть выражены в терминах собственных значений взаимной матрицы Грама этих систем. Эта матрица D, матрица дискриминантов P, имеет вид:

Если P симметрична, то D(P) = P, и формула остается достаточно простой даже тогда, когда P не симметрична. В частности, блуждание с поглощением P0 имеет матрицу дискриминантов [P0 ° ]. Наконец, отношение между D(P) и спектральным разложением WP задается следующим образом:

Теорема 4 [18]. Пусть P – произвольная цепь Маркова на конечном пространстве состояний S, и пусть cos 6\ 1 ■■■ > cos (9/ – сингулярные значения D(P), лежащие в открытом интервале (0;1), с соответствующими сингулярными парами векторов vj; wj для 1 < j < l. Тогда нетривиальные собственные значения WP (исключая 1 и -1) и соответствующие им собственные векторы - e~2WJ, R1wj - e~wjR2Vj; e2W) и Rjwj - ewjR2Vj для 1 < j < l.

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

Теорема 5 [ ]. Пусть P обратима и эргодична со спектральным разрывом S > 0. Пусть M имеет помеченную вероятность, равную нулю либо " > 0. Тогда существует квантовый алгоритм, решающий задачу достижения цели (версия с поиском) со стоимостью S +

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

Предположим, что даны элементы x1... xm 2 f1... ; mg и задан вопрос, существуют ли i, j такие, что xi = xj. Сложность классического подхода к выполнению этого запроса равна 0(m). Амбайнис [ ] предложил (оптимальный) квантовый алгоритм запросов со сложностью O(m2/3), использующий квантовое блуждание по графу Джонсона, состоящему из m2/3 -подмножеств f1... ; mg, в котором подмножества, которые содержат i,j с xi = xj, помечены.

Предположим, дана матрица смежности A графа с n вершинами и требуется определить, содержит ли граф треугольник (т.е. клику размером 3), используя как можно меньше запросов к записям A. Сложность классического подхода к решению этой задачи равна 0(n2). Маньез, Санта и Шегеди [13] предложили алгоритм со сложностью б(иьз), адаптировав решение из [2]. Маньез и др. улучшили ее до O(n1:3) в работе [12].

Предположим, даны три n х n матрицы A, B, C и требуется определить, является ли AB ф C (то есть, существуют ли i,j такие, что PkAikBkj ф Cij), используя как можно меньше запросов к записям A, B и C. Сложность классического подхода к решению этой задачи равна 0(n2). Бурман и Спалек [5] предложили квантовый алгоритм выполнения запросов со сложностью O(n5/3), используя результаты из [18].

Предположим, что имеется группа типа «черный ящик», заданная k генераторами, и требуется определить, коммутативна ли эта группа, используя как можно меньше запросов к операции группового произведения (т. е. запросов вида «Чему равно произведение элементов g и h?»). Сложность классического подхода к решению этой задачи составляет 0(k) групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) 6(/c2/3) квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате.

 

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

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

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

 

Требуется: найти состояние, "-близкое к ж по суммарному вариационному расстоянию.