Квантование цепей Маркова
Ключевые слова и синонимы
Квантовые блуждания
Постановка задачи
Пространственный поиск и процессы блуждания
Пространственный поиск посредством квантового блуждания представляет собой поиск в базе данных с дополнительным ограничением, заключающимся в том, что по пространству поиска необходимо перемещаться с помощью квантового блуждания, подчиняющегося некоторой структуре локальности (решетка, гиперкуб и т .д.). Квантовые блуждания являются аналогами классических случайных блужданий на графах. Сложность пространственного поиска с помощью квантового блуждания определяется главным образом квантовым временем достижения цели [ ] данного блуждания.
Пусть S, |S| = N, – конечное множество состояний, и пусть P = (px;y)x;y2S – матрица вероятностей перехода цепи Маркова на S, также обозначаемая P. Предположим, что подмножество состояний M С S помечено. Задача состоит в том, чтобы найти помеченное состояние, учитывая, что M ф (версия с поиском), или определить, является ли M непустым (версия с принятием решений). Если возможные перемещения x ! y (т. е. те, при которых px;y ф 0) образуют ребра (ориентированного) графа G, то говорится, что блуждание имеет структуру локальности G.
Дано: Марковская цепь P на множестве S, помеченное подмножество M С S.
Требуется: найти помеченное состояние с вероятностью 0:1, если оно существует (версия с поиском) или булево возвращаемое значение с односторонней ошибкой, обнаруживающей M ф ; с вероятностью 0:1 (версия с принятием решений).
Если P несводима (т. е. если лежащий в ее основе орграф является сильно связным), то помеченное состояние может быть найдено с высокой вероятностью за конечное время путем имитации классического случайного блуждания с использованием коэффициентов P. В квантовом случае этот процесс случайного блуждания может быть заменен квантовым блужданием с использованием коэффициентов P (в частности, с соблюдением локальности).
Фундаментальный вопрос заключается в том, находит ли процесс квантового блуждания помеченное состояние быстрее, чем классический процесс случайного блуждания.
Алгоритм квантового блуждания
Квантование P является нетривиальной задачей, поскольку стохастические матрицы не имеют непосредственных унитарных эквивалентов. Оказывается, что нужно либо отказаться от дискретно-временной природы блуждания [7], либо определить оператор блуждания на пространстве, отличном от CS. Здесь выбран второй путь, нотация которого соответствует изложенной в работе [18]. На CSxS определим унитарный WP := R1R2, где (px\ --0 <8> \x}(x\,R2 = J2X€S \x)(x\ ® (2\px)(px\ - I), и jpxi := Py2S ppy;xjyi. WP – это квантование P, или оператор дискретного квантового блуждания, вытекающий из P. «Проверить», помечено ли текущее состояние, можно при помощи оператора OM = Px26M \x)(x\ ~ Px2M jxihxj. Обозначим стоимость построения WP (в единицах интересующего ресурса) как U (update cost – стоимость обновления), стоимость построения OM как C (checking cost – стоимость проверки), а стоимость подготовки начального состояния, фо, как S (setup cost – стоимость настройки). Каждый раз, когда оператор используется, его стоимость прибавляется к общим затратам. Эта абстракция, неявная в [ ] и явная в [13], позволяет рассматривать WP и OM как операторы типа «черный ящик» и обеспечивает удобный способ учета временной сложности или, в модели квантовых запросов, сложности запроса. Алгоритм пространственного поиска с помощью квантового блуждания описывается следующим образом:
Квантовая схема X = XmXm-\ 1.. X1, с «проводами» (обычно их два), которые переносят CS и управляющие биты. Каждый элемент Xi является либо WP-вентилем, либо OM- вентилем, либо управляемой версией одного из них. X применяется к начальному состоянию фо. Стоимость последовательности равна сумме стоимостей отдельных операторов. Вероятность наблюдения – это вероятность того, что после измерения конечного состояния, фт, в стандартном базисе, один из проводов выводит элемент из М. Если вероятность наблюдения равна q, необходимо повторить процедуру 1/pq раз, используя усиление по амплитуде (версия с поиском). В версии с принятием решений можно отличить М от М0, если \Хфо - Х'фо\ > 0:1, где Х возникает из ОМ, а Х0 из ОМ0.
Основные результаты
Первоначальные результаты
Пространственный поиск сочетает алгоритм поиска Гровера [8], который находит помеченный элемент в базе данных размера N за N/jMj шагов, с квантовыми блужданиями.
Квантовые блуждания были впервые введены Дэвидом Мейером и Джоном Уотроусом для изучения квантовых клеточных автоматов и квантового логарифмического пространства, соответственно. Квантовые блуждания в дискретном времени исследовали Наяк и др. [3, 15], а также Ахаронов и др. [ ] на бесконечной линии и N-цикле, соответственно. Центральными темами в первые годы развития концепции квантовых блужданий были определение оператора блуждания, понятия времени перемешивания и времени достижения цели, а также достижимое ускорение по сравнению с классической постановкой задачи. Экспоненциальное квантовое ускорение времени достижения между антиподами гиперкуба было показано Кемпе [ ], а Чайлдс и коллеги [6] представили первую задачу с оракулом, решаемую экспоненциально быстрее алгоритмом, основанным на квантовых блужданиях, чем любым (не обязательно основанным на блужданиях) классическим алгоритмом.
Авторами первых систематических исследований квантового времени достижения на гиперкубе и d-мерном торе были Шенви и др. [17], а также Амбайнис и др. [4]. Улучшая алгоритм пространственного поиска Ааронсона и Амбайниса, основанный на алгоритме поиска Гровера, Амбайнис и др. [ ] показали, что d-мерный тор (с N = nd узлами) может быть исследован с помощью квантового блуждания со стоимостью порядка S + pN(U + C) и вероятностью наблюдения Q(l/\ogN) для d > 3, и со стоимостью порядка S + NlogN(U + C) и вероятностью наблюдения £?(1) для d = 2. Ключевое отличие этих результатов от результатов работы [6, 9] заключается в том, что блуждание должно начинаться из однородного состояния, а не из того, которое каким-то образом «связано» с состоянием, в которое вы хотите попасть. Только в последнем случае можно достичь экспоненциального ускорения.
Первый результат, который использовал квантовое блуждание для решения естественной алгоритмической задачи, так называемой задачи различимости элементов, принадлежит Амбайнису [ ]. Алгоритм Амбайниса использует блуждание 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)).
Цепи Маркова общего вида
В работе [18] Шегеди исследует время достижения для квантовых блужданий, порождаемых цепями Маркова общего вида. Его определения (оператор блуждания, время достижения) непосредственно выводятся из [2] и согласуются с предыдущими исследованиями, хотя их представление несколько отличается.
Для цепи Маркова 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.
Остается вычислить 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)
