Квантование цепей Маркова

Ключевые слова и синонимы

Квантовые блуждания

Постановка задачи

Пространственный поиск и процессы блуждания

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

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

Остается вычислить H. Когда P симметрично и эргодично, выражение для классического времени достижения цели имеет квантовый аналог [8] (|M| [math]\displaystyle{ \le }[/math]N/2 по техническим причинам):

(1) [math]\displaystyle{ H \le \sum_{k = 1}^{N - |M|} \frac{\nu^2_k}{\sqrt{1 - \lambda_k}} }[/math],

где [math]\displaystyle{ \nu_k }[/math] – сумма координат [math]\displaystyle{ v_k }[/math], деленная на [math]\displaystyle{ 1/\sqrt{N} }[/math]. Из (1) и выражения для h можно вывести удивительную связь между классическим и квантовым временем достижения:

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

Далее можно показать следующие результаты:

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

Из теорем 2 и 3 вытекает большинство результатов предыдущего раздела о квантовом времени достижения цели без вычислений, опираясь только на оценки соответствующих классических алгоритмов времени достижения. Выражение (1) основано на фундаментальной связи между собственными значениями и собственными векторами P и [math]\displaystyle{ W_P }[/math]. Заметим, что [math]\displaystyle{ R_1 }[/math] и [math]\displaystyle{ R_2 }[/math] являются отражениями на подпространствах, порожденных [math]\displaystyle{ \{ |p_x \rangle \otimes | x \rangle | x \in S \} }[/math] и [math]\displaystyle{ \{ |x \rangle \otimes | p_x \rangle | x \in S \} }[/math], соответственно. Следовательно, собственные значения [math]\displaystyle{ R_1 R_2 }[/math] могут быть выражены в терминах собственных значений взаимной матрицы Грама этих систем. Эта матрица D, матрица дискриминантов P, имеет вид:

(2) [math]\displaystyle{ D(P) = \sqrt{P \circ P_T} \; \stackrel{\mathrm{def}}{=} \; (\sqrt{p_{x, y} p_{y, x}})_{x, y \in S}. }[/math]

Если P симметрична, то D(P) = P, и формула остается достаточно простой даже тогда, когда P не симметрична. В частности, блуждание с поглощением P' имеет матрицу дискриминантов [math]\displaystyle{ \begin{bmatrix} P_M & 0 \\ 0 & I \end{bmatrix} }[/math]. Наконец, отношение между D(P) и спектральным разложением [math]\displaystyle{ W_P }[/math] задается следующим образом:

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

Недавние разработки

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

Теорема 5 [12]. Пусть P обратима и эргодична со спектральным разрывом [math]\displaystyle{ \delta \gt 0 }[/math]. Пусть M имеет помеченную вероятность, равную нулю либо [math]\displaystyle{ \varepsilon \gt 0 }[/math]. Тогда существует квантовый алгоритм, решающий задачу достижения цели (версия с поиском) со стоимостью [math]\displaystyle{ S + \frac{1}{\sqrt{\varepsilon}} \bigg( \frac{1}{\sqrt{\delta}} U + C \bigg) }[/math].

Применение

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

Предположим, что даны элементы [math]\displaystyle{ x_1, ..., x_m \in \{ 1, ..., m \} }[/math] и нужно узнать, существуют ли i, j такие, что [math]\displaystyle{ x_i = x_j }[/math]. Сложность классического подхода к выполнению этого запроса равна [math]\displaystyle{ \Theta(m) }[/math]. Амбайнис [2] предложил (оптимальный) квантовый алгоритм запросов со сложностью [math]\displaystyle{ O(m^{2/3}) }[/math], использующий квантовое блуждание по графу Джонсона, состоящему из [math]\displaystyle{ m^{2/3} }[/math]-подмножеств [math]\displaystyle{ \{ 1, ..., m \} }[/math], в котором подмножества, которые содержат i, j с [math]\displaystyle{ x_i = x_j }[/math], помечены.

Поиск треугольника

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

Верификация матричного произведения

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

Проверка коммутативности группы

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

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

Многие вопросы квантования цепей Маркова остаются нерешенными – как для задачи достижения цели, так и для тесно связанной с ней задачи перемешивания.

Достижение цели

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

Перемешивание

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

Дано: цепь Маркова P на множестве S, допуск [math]\displaystyle{ \varepsilon \gt 0 }[/math].

Требуется: найти состояние, [math]\displaystyle{ \varepsilon }[/math]-близкое к [math]\displaystyle{ \pi }[/math] по суммарному вариационному расстоянию.

Понятия квантового времени перемешивания на линии, цикле и гиперкубе впервые предложили и проанализировали Наяк и др. [3, 15], Ахаронов и др. [1], а также Мур и Расселл [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)