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

Материал из WEGA
Перейти к навигации Перейти к поиску
мНет описания правки
 
(не показаны 23 промежуточные версии этого же участника)
Строка 5: Строка 5:
'''Пространственный поиск и процессы блуждания'''
'''Пространственный поиск и процессы блуждания'''


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




Строка 24: Строка 24:
'''Алгоритм квантового блуждания'''
'''Алгоритм квантового блуждания'''


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




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


Авторами первых систематических исследований квантового времени достижения на гиперкубе и d-мерном торе были Шенви и др. [17], а также Амбайнис и др. [4]. Улучшая алгоритм пространственного поиска Ааронсона и Амбайниса, основанный на алгоритме поиска Гровера, Амбайнис и др. [4] показали, что d-мерный тор (с <math>N = n^d</math> узлами) может быть исследован с помощью квантового блуждания со стоимостью порядка S + pN(U + C) и вероятностью наблюдения Q(l/\ogN) для d > 3, и со стоимостью порядка S + NlogN(U + C) и вероятностью наблюдения £?(1) для d = 2. Ключевое отличие этих результатов от результатов работы [6, 9] заключается в том, что блуждание должно начинаться из однородного состояния, а не из того, которое каким-то образом «связано» с состоянием, в которое вы хотите попасть. Только в последнем случае можно достичь экспоненциального ускорения.
Авторами первых систематических исследований квантового времени достижения на гиперкубе и 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] заключается в том, что блуждание должно начинаться из однородного состояния, а не из того, которое каким-то образом «связано» с состоянием, в которое мы хотим попасть. Только в последнем случае можно достичь экспоненциального ускорения.




Первый результат, который использовал квантовое блуждание для решения естественной алгоритмической задачи, так называемой задачи различимости элементов, принадлежит Амбайнису [ ]. Алгоритм Амбайниса использует блуждание W по графу Джонсона J(r; m), вершинами которого являются подмножества размера r из совокупности (юниверса) размера m, причем два подмножества связаны в том и только том случае, если их симметрическая разность имеет величину 2. Актуальность этого графа вытекает из нетривиальной алгоритмической идеи, согласно которой три различные стоимости (S, U и C) уравновешиваются новым способом. В отличие от этого, алгоритм Гровера – хотя он и вдохновил результат Амбайниса – не предполагает такой возможности: в его случае затраты на установку и обновление в модели запросов равны нулю.
Первый результат, который использовал квантовое блуждание для решения естественной алгоритмической задачи, так называемой ''задачи различения элементов'', принадлежит Амбайнису [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) – эффективный «угол поворота».
Главное математическое наблюдение Амбайниса о блуждании 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> – эффективный «угол поворота».




Что общего между Wpr и D? Амбайнис показал, что нетривиальные собственные значения матрицы Wr в подпространстве (конечной размерности), содержащем орбиту фо, удалены от 1 на константную величину ". Таким образом, Wr служит очень хорошим приближенным отражением вдоль оси фо – не менее хорошим, чем у Гровера в этом приложении. Это позволяет вывести следующее заключение: существует t = O(l/a), для которого перекрытие {фё00а\(№-^ОмУ\Фо} = &(1), поэтому выходное значение, вероятно, находится в M.
Что общего между <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, содержащих фиксированное подмножество 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)).
'''Теорема 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>.'''




Строка 58: Строка 58:




Для цепи Маркова 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+ С
Для цепи Маркова 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}
P_M & 0 \\
P'' & I
\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.




Почему определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением P0, необходимое для заметного перекоса равномерного начального распределения. Аналогичным образом квантовое время достижения ограничивает число итераций следующего квантового алгоритма, служащего для определения того, является ли M непустым. На каждом шаге применяем оператор WP0. Если M пусто, то P0 = P и начальное состояние остается неизменным. Если M непусто, то угол между \¥р,фо и Wptpo постепенно увеличивается. Используя дополнительный регистр управления для применения либо WP0, либо WP с квантовым управлением, можно определить расхождение этих двух состояний (если M непусто). Необходимое число итераций равно ровно H.
Почему это определение квантового времени достижения настолько интересно? Классическое время достижения измеряет количество итераций блуждания с поглощением 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.
Остается вычислить H. Когда P симметрично и эргодично, выражение для классического времени достижения цели имеет квантовый аналог [ ] (jMj < N/2 по техническим причинам):


где v^ – сумма координат vk, деленная на 1/pN. Из (1) и выражения для h можно вывести удивительную связь между классическим и квантовым временем достижения:


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


Теорема 2 [18]. Пусть P симметрично и эргодично, и пусть h – классическое время достижения для помеченного множества M и равномерного начального распределения. Тогда квантовое время достижения для M не превышает ph.
(1) <math>H \le \sum_{k = 1}^{N - |M|} \frac{\nu^2_k}{\sqrt{1 - \lambda_k}}</math>,
 
где <math>\nu_k</math> – сумма координат <math>v_k</math>, деленная на <math>1/\sqrt{N}</math>. Из (1) и выражения для h можно вывести удивительную связь между классическим и квантовым временем достижения:
 
 
'''Теорема 2 [18]. Пусть P симметрично и эргодично, и пусть h – классическое время достижения для помеченного множества M и равномерного начального распределения. Тогда квантовое время достижения для M не превышает <math>\sqrt{h}</math>.'''




Строка 73: Строка 80:




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


Из теорем 2 и 3 вытекает большинство результатов предыдущего раздела о квантовом времени достижения цели без вычислений, опираясь только на оценки соответствующих классических алгоритмов времени достижения. Выражение (1) основано на фундаментальной связи между собственными значениями и собственными векторами P и WP. Заметим, что R1 и R2 являются отражениями на подпространствах, порожденных f j px ® \x}\ x 2 S}и{|x) ® pxij x 2 Sg, соответственно. Следовательно, собственные значения R1R2 могут быть выражены в терминах собственных значений взаимной матрицы Грама этих систем. Эта матрица D, матрица дискриминантов P, имеет вид:
(2) <math> 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 не симметрична. В частности, блуждание с поглощением P0 имеет матрицу дискриминантов [P0 ° ]. Наконец, отношение между D(P) и спектральным разложением WP задается следующим образом:
Если P симметрична, то D(P) = P, и формула остается достаточно простой даже тогда, когда P не симметрична. В частности, блуждание с поглощением P' имеет матрицу дискриминантов <math>\begin{bmatrix}
P_M & 0 \\
0 & I
\end{bmatrix}</math>. Наконец, отношение между D(P) и спектральным разложением <math>W_P</math> задается следующим образом:




Теорема 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.
'''Теорема 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>.'''




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


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




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


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


Предположим, что даны элементы x1... xm 2 f1... ; mg и задан вопрос, существуют ли i, j такие, что xi = xj. Сложность классического подхода к выполнению этого запроса равна 0(m). Амбайнис [ ] предложил (оптимальный) квантовый алгоритм запросов со сложностью O(m2/3), использующий квантовое блуждание по графу Джонсона, состоящему из m2/3 -подмножеств f1... ; mg, в котором подмножества, которые содержат i,j с xi = xj, помечены.
Предположим, что даны элементы <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. Сложность классического подхода к решению этой задачи равна 0(n2). Маньез, Санта и Шегеди [13] предложили алгоритм со сложностью б(иьз), адаптировав решение из [2]. Маньез и др. улучшили ее до O(n1:3) в работе [12].
Предположим, что дана матрица смежности 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].




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


Предположим, даны три n х n матрицы A, B, C и требуется определить, является ли AB ф C (то есть, существуют ли i,j такие, что PkAikBkj ф Cij), используя как можно меньше запросов к записям A, B и C. Сложность классического подхода к решению этой задачи равна 0(n2). Бурман и Спалек [5] предложили квантовый алгоритм выполнения запросов со сложностью O(n5/3), используя результаты из [18].
Предположим, что даны три матрицы 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?»). Сложность классического подхода к решению этой задачи составляет 0(k) групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) 6(/c2/3) квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате.
Предположим, что имеется группа типа «черный ящик», заданная k генераторами, и требуется определить, коммутативна ли эта группа, используя как можно меньше запросов к операции группового произведения (т. е. запросов вида «Чему равно произведение элементов g и h?»). Сложность классического подхода к решению этой задачи составляет <math>\Theta(k)</math> групповых операций. Маньез и Наяк [11] предложили (практически оптимальный) <math>\tilde{O}(k^{2/3})</math> квантовый алгоритм выполнения запросов путем блуждания по произведению двух графов, вершины которых являются (упорядоченными) l-кортежами различных генераторов, у которого вероятности перехода являются ненулевыми только там, где l-кортежи в двух конечных точках отличаются не более чем по одной координате.


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


Строка 119: Строка 130:
'''Достижение цели'''
'''Достижение цели'''


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




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


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


Дано: цепь Маркова P на множестве S, допуск ">0.


Требуется: найти состояние, "-близкое к ж по суммарному вариационному расстоянию.
'''Дано:''' цепь Маркова P на множестве S, допуск <math>\varepsilon > 0</math>.


'''Требуется''': найти состояние, <math>\varepsilon</math>-близкое к <math>\pi</math> по суммарному вариационному расстоянию.


Понятия квантового времени смешивания на линии, цикле и гиперкубе впервые предложили и проанализировали Наяк и др. [3, 15], Ахаронов и др. [ ], а также Мур и Расселл [14]. В работах Кендон и Трегенны [10] и Рихтера [16] исследовалось использование декогеренции для улучшения перемешивания квантовых блужданий [10]. Остаются открытыми два фундаментальных вопроса о времени квантового перемешивания: как выглядит «наиболее естественное» определение и когда имеет место квантовое ускорение по сравнению с временем перемешивания в классических подходах?


Понятия квантового времени перемешивания на линии, цикле и гиперкубе впервые предложили и проанализировали Наяк и др. [3, 15], Ахаронов и др. [1], а также Мур и Расселл [14]. В работах Кендон и Трегенны [10] и Рихтера [16] исследовалось использование декогеренции для улучшения перемешивания квантовых блужданий [10]. Остаются открытыми два фундаментальных вопроса о времени квантового перемешивания: как выглядит «наиболее естественное» определение и когда имеет место квантовое ускорение по сравнению с временем перемешивания в классических подходах?


== См. также ==
== См. также ==

Текущая версия от 17:56, 21 ноября 2022

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

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

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

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

Пространственный поиск посредством квантового блуждания представляет собой поиск в базе данных с дополнительным ограничением, заключающимся в том, что перемещение по пространству поиска происходит путем квантового блуждания, подчиняющегося некоторой структуре локальности (решетка, гиперкуб и т .д.). Квантовые блуждания являются аналогами классических случайных блужданий на графах. Сложность пространственного поиска с помощью квантового блуждания определяется главным образом квантовым временем достижения цели [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)