Квантование цепей Маркова
Ключевые слова и синонимы
Квантовые блуждания
Постановка задачи
Пространственный поиск и процессы блуждания
Пространственный поиск посредством квантового блуждания представляет собой поиск в базе данных с дополнительным ограничением, заключающимся в том, что перемещение по пространству поиска происходит путем квантового блуждания, подчиняющегося некоторой структуре локальности (решетка, гиперкуб и т .д.). Квантовые блуждания являются аналогами классических случайных блужданий на графах. Сложность пространственного поиска с помощью квантового блуждания определяется главным образом квантовым временем достижения цели [9] данного блуждания.
Пусть S, |S| = N, – конечное множество состояний, и пусть [math]\displaystyle{ P = (p_{x, y})_{x, y \in S} }[/math] – матрица вероятностей перехода для цепи Маркова на S, также обозначаемая P. Предположим, что подмножество состояний [math]\displaystyle{ M \subseteq S }[/math] помечено. Задача состоит в том, чтобы найти помеченное состояние, учитывая, что [math]\displaystyle{ M \ne \empty }[/math] (версия с поиском), или определить, является ли M непустым (версия с принятием решений). Если возможные перемещения [math]\displaystyle{ x \to y }[/math] (т. е. те, при которых [math]\displaystyle{ p_{x, y} \ne 0) }[/math] образуют ребра (ориентированного) графа G, то говорится, что блуждание имеет структуру локальности G.
Дано: Марковская цепь P на множестве S, помеченное подмножество [math]\displaystyle{ M \subseteq S }[/math].
Требуется: найти помеченное состояние с вероятностью 0.1, если оно существует (версия с поиском), или булево возвращаемое значение с односторонней ошибкой, обнаруживающее [math]\displaystyle{ M \ne \empty }[/math] с вероятностью 0.1 (версия с принятием решений).
Если P несводима (т. е. если лежащий в ее основе орграф является сильно связным), то помеченное состояние может быть найдено с высокой вероятностью за конечное время путем имитации классического случайного блуждания с использованием коэффициентов P. В квантовом случае этот процесс случайного блуждания может быть заменен квантовым блужданием с использованием коэффициентов P (в частности, с соблюдением локальности).
Фундаментальный вопрос заключается в том, находит ли процесс квантового блуждания помеченное состояние быстрее, чем классический процесс случайного блуждания.
Алгоритм квантового блуждания
Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от [math]\displaystyle{ \mathbf{C}^S }[/math]. Здесь выбран второй путь, нотация которого соответствует изложенной в работе [18]. На [math]\displaystyle{ \mathbf{C}^{S \times S} }[/math] определим унитарный оператор [math]\displaystyle{ W_P := R_1 R_2 }[/math], где [math]\displaystyle{ R_1 = \sum_{x \in S} (2 | p_x \rangle \langle p_x | - I) \otimes | x \rangle \langle x | }[/math], [math]\displaystyle{ R_2 = \sum_{x \in S} | x \rangle \langle x | \otimes (2 | p_x \rangle \langle p_x | - I) }[/math], [math]\displaystyle{ | p_x \rangle := \sum_{y \in S} \sqrt{p_{y, x}} | y \rangle }[/math]. [math]\displaystyle{ W_P }[/math] – это квантование P, или оператор квантового блуждания в дискретном времени, вытекающий из P. «Проверить», помечено ли текущее состояние, можно при помощи оператора [math]\displaystyle{ O_M = \sum_{x \notin M} | x \rangle \langle x | - \sum_{x \in M} | x \rangle \langle x | }[/math]. Обозначим стоимость построения [math]\displaystyle{ W_P }[/math] (в единицах интересующего ресурса) как U (update cost – стоимость обновления), стоимость построения [math]\displaystyle{ O_M }[/math] как C (checking cost – стоимость проверки), а стоимость подготовки начального состояния, [math]\displaystyle{ \phi_0 }[/math], как S (setup cost – стоимость настройки). Каждый раз, когда оператор используется, его стоимость прибавляется к общим затратам. Эта абстракция, неявная в [2] и явная в [13], позволяет рассматривать [math]\displaystyle{ W_P }[/math] и [math]\displaystyle{ O_M }[/math] как операторы типа «черный ящик» и обеспечивает удобный способ учета временной сложности или, в модели квантовых запросов, сложности запроса. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом:
АЛГОРИТМ: Квантовая схема [math]\displaystyle{ X = X_m X_{m - 1} ... X_1 }[/math], с «проводами» (обычно их два), которые переносят [math]\displaystyle{ \mathbf{C}^S }[/math] и управляющие биты. Каждый элемент [math]\displaystyle{ X_i }[/math] является либо [math]\displaystyle{ W_P }[/math]-вентилем, либо [math]\displaystyle{ O_M }[/math]-вентилем, либо управляемой версией одного из них. X применяется к начальному состоянию [math]\displaystyle{ \phi_0 }[/math]. Стоимость последовательности равна сумме стоимостей отдельных операторов. Вероятность наблюдения – это вероятность того, что после измерения конечного состояния, [math]\displaystyle{ \phi_m }[/math], в стандартном базисе, один из проводов выводит элемент из М. Если вероятность наблюдения равна q, необходимо повторить процедуру 1/[math]\displaystyle{ \sqrt q }[/math] раз, используя усиление по амплитуде (версия с поиском). В версии с принятием решений можно отличить М от М', если [math]\displaystyle{ | X \phi_0 - X' \phi_0 | \ge 0.1 }[/math], где Х выводится из [math]\displaystyle{ O_M }[/math], а Х' из [math]\displaystyle{ O_{M'} }[/math].
Основные результаты
Первоначальные результаты
Пространственный поиск сочетает алгоритм поиска Гровера [8], который находит помеченный элемент в базе данных размера N за [math]\displaystyle{ \sqrt{N / |M|} }[/math] шагов, с квантовыми блужданиями.
Квантовые блуждания были впервые введены Дэвидом Мейером и Джоном Уотроусом для изучения квантовых клеточных автоматов и квантового логарифмического пространства, соответственно. Квантовые блуждания в дискретном времени исследовали Наяк и др. [3, 15], а также Ахаронов и др. [1] на бесконечной линии и N-цикле, соответственно. Центральными темами в первые годы развития концепции квантовых блужданий были определение оператора блуждания, понятия времени перемешивания и времени достижения цели, а также достижимое ускорение по сравнению с классической постановкой задачи. Экспоненциальное квантовое ускорение времени достижения между антиподами гиперкуба было показано Кемпе [9], а Чайлдс и коллеги [6] представили первую задачу с оракулом, решаемую экспоненциально быстрее алгоритмом, основанным на квантовых блужданиях, чем любым (не обязательно основанным на блужданиях) классическим алгоритмом.
Авторами первых систематических исследований квантового времени достижения на гиперкубе и d-мерном торе были Шенви и др. [17], а также Амбайнис и др. [4]. Улучшая алгоритм пространственного поиска Ааронсона и Амбайниса, основанный на алгоритме поиска Гровера, Амбайнис и др. [4] показали, что d-мерный тор (с [math]\displaystyle{ N = n^d }[/math] узлами) может быть исследован с помощью квантового блуждания со стоимостью порядка [math]\displaystyle{ S + \sqrt{N}(U + C) }[/math] и вероятностью наблюдения [math]\displaystyle{ \Omega(1 / log N) }[/math] для [math]\displaystyle{ d \ge 3 }[/math], и со стоимостью порядка [math]\displaystyle{ S + \sqrt{N log N}(U + C) }[/math] и вероятностью наблюдения [math]\displaystyle{ \Omega(1) }[/math] для [math]\displaystyle{ d = 2 }[/math]. Ключевое отличие этих результатов от результатов работы [6, 9] заключается в том, что блуждание должно начинаться из однородного состояния, а не из того, которое каким-то образом «связано» с состоянием, в которое вы хотите попасть. Только в последнем случае можно достичь экспоненциального ускорения.
Первый результат, который использовал квантовое блуждание для решения естественной алгоритмической задачи, так называемой задачи различимости элементов, принадлежит Амбайнису [2]. Алгоритм Амбайниса использует блуждание W по графу Джонсона J(r, m), вершинами которого являются подмножества размера r из совокупности размера m, причем два подмножества связаны в том и только том случае, если их симметрическая разность имеет величину 2. Актуальность этого графа вытекает из нетривиальной алгоритмической идеи, согласно которой три различные стоимости (S, U и C) уравновешиваются новым способом. В отличие от этого, алгоритм Гровера – хотя он и вдохновил результат Амбайниса – не предполагает такой возможности: в его случае затраты на установку и обновление в модели запросов равны нулю.
Главное математическое наблюдение Амбайниса о блуждании W по графу Джонсона состоит в том, что [math]\displaystyle{ W^{\sqrt{r}} O_M }[/math] ведет себя примерно так же, как и [math]\displaystyle{ DO_M }[/math] итерации Гровера, где D – оператор диффузии Гровера. Вспомним, что алгоритм Гровера применяет [math]\displaystyle{ DO_M }[/math] многократно, переводя однородное начальное состояние [math]\displaystyle{ \phi_0 }[/math] в состояние [math]\displaystyle{ \phi_{good} = \sum_{x \in M} \sqrt{1 / |M| | x \rangle } }[/math] после [math]\displaystyle{ t = O(1/ \alpha) }[/math] итераций, где [math]\displaystyle{ \alpha := 2 sin^{-1} \langle \phi_{good} | \phi_0 \rangle }[/math] – эффективный «угол поворота».
Что общего между [math]\displaystyle{ W^{\sqrt{r}} }[/math] и [math]\displaystyle{ D }[/math]? Амбайнис показал, что нетривиальные собственные значения матрицы [math]\displaystyle{ W^{\sqrt{r}} }[/math] в подпространстве (конечной размерности), содержащем орбиту [math]\displaystyle{ \phi_0 }[/math], удалены от 1 на константную величину [math]\displaystyle{ \varepsilon }[/math]. Таким образом, [math]\displaystyle{ W^{\sqrt{r}} }[/math] служит очень хорошим приближенным отражением вдоль оси [math]\displaystyle{ \phi_0 }[/math] – не менее хорошим, чем у Гровера в этом приложении. Это позволяет вывести следующее заключение: существует [math]\displaystyle{ t = O(1/ \alpha) }[/math], для которого перекрытие [math]\displaystyle{ \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]\displaystyle{ x_1, ..., x_k }[/math] при константном [math]\displaystyle{ k \le r }[/math]. Тогда существует квантовый алгоритм, решающий задачу достижения (версия с поиском) со стоимостью порядка [math]\displaystyle{ S + t(\sqrt{r} \cdot U + C) }[/math], где [math]\displaystyle{ t = \bigg( \frac{m}{r} \bigg)^{k/2} }[/math]. Если стоимости равны S = r, U = O(1) и C = 0, то суммарная стоимость имеет оптимум [math]\displaystyle{ O(m^{k/(k+1)}) }[/math] при [math]\displaystyle{ r = O(m^{k/(k+1)}) }[/math].
Цепи Маркова общего вида
В работе [18] Шегеди исследует время достижения для квантовых блужданий, порождаемых цепями Маркова общего вида. Его определения (оператор блуждания, время достижения) непосредственно выводятся из [2] и согласуются с предыдущими исследованиями, хотя их представление несколько отличается.
Для цепи Маркова P (классическое) среднее время достижения относительно M может быть выражено в терминах матрицы блужданий с утечкой [math]\displaystyle{ P_M }[/math], которая получается из P путем удаления всех строк и столбцов, индексированных состояниями M. Обозначим за h(x, M) ожидаемое время достижения M из x, а за [math]\displaystyle{ v_i, ...., v_{N - |M|}, \lambda_1, ..., \lambda_{N - |M|} }[/math] – (нормализованные) собственные векторы и соответствующие собственные значения [math]\displaystyle{ P_M }[/math]. Обозначим за [math]\displaystyle{ d : S \to \mathbf{R}^+ }[/math] начальное распределение, а за d' – его ограничение на S \ M. Тогда [math]\displaystyle{ 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]\displaystyle{ P_M }[/math] не является стохастической, можно рассмотреть матрицу поглощающих блужданий 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.
Остается вычислить H. Когда P симметрично и эргодично, выражение для классического времени достижения цели имеет квантовый аналог [ ] (jMj < N/2 по техническим причинам):
где v^ – сумма координат vk, деленная на 1/pN. Из (1) и выражения для 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-полных задач. Таким образом, задача выглядит следующим образом:
Дано: цепь Маркова P на множестве S, допуск ">0.
Требуется: найти состояние, "-близкое к ж по суммарному вариационному расстоянию.
Понятия квантового времени смешивания на линии, цикле и гиперкубе впервые предложили и проанализировали Наяк и др. [3, 15], Ахаронов и др. [ ], а также Мур и Расселл [14]. В работах Кендон и Трегенны [10] и Рихтера [16] исследовалось использование декогеренции для улучшения перемешивания квантовых блужданий [10]. Остаются открытыми два фундаментальных вопроса о времени квантового перемешивания: как выглядит «наиболее естественное» определение и когда имеет место квантовое ускорение по сравнению с временем перемешивания в классических подходах?
См. также
Литература
1. Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proc. STOC (2001)
2. Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210-239 (2007). Preliminary version in Proc. FOCS 2004
3. Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proc. STOC (2001)
4. Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proc. SODA (2005)
5. Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proc. SODA (2006)
6. Childs, A., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.: Exponential algorithmic speedup by a quantum walk. In: Proc. STOC (2003)
7. Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58 (1998)
8. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. STOC (1996)
9. Kempe, J.: Discrete quantum walks hit exponentially faster. In: Proc. RANDOM (2003)
10. Kendon, V., Tregenna, B.: Decoherence can be useful in quantum walks. Phys. Rev. A. 67,42-315 (2003)
11. Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. Algorithmica 48(3), 221-232 (2007) Preliminary version in Proc. ICALP 2005
12. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proc. STOC (2007)
13. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413-424 (2007) Preliminary version in Proc. SODA 2005
14. Moore, C., Russell, A.: Quantum walks on the hypercube. In: Proc. RANDOM (2002)
15. Nayak, A., Vishwanath, A.: Quantum walk on the line. quant-ph/0010117
16. Richter, P.C.: Quantum speedup of classical mixing processes. Phys. Rev. A 76,042306 (2007)
17. Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A 67, 52-307 (2003)
18. Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proc. FOCS (2004)
