4551
правка
Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
м
Квантование цепей Маркова (посмотреть исходный код)
Версия от 23:42, 20 ноября 2022
, 20 ноября 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
Квантовые блуждания были впервые введены Дэвидом Мейером и Джоном Уотроусом для изучения квантовых клеточных автоматов и квантового логарифмического пространства, соответственно. Квантовые блуждания в дискретном времени исследовали Наяк и др. [3, 15], а также Ахаронов и др. [1] на бесконечной линии и N-цикле, соответственно. Центральными темами в первые годы развития концепции квантовых блужданий были определение оператора блуждания, понятия времени перемешивания и времени достижения цели, а также достижимое ускорение по сравнению с классической постановкой задачи. Экспоненциальное квантовое ускорение времени достижения между антиподами гиперкуба было показано Кемпе [9], а Чайлдс и коллеги [6] представили первую задачу с оракулом, решаемую экспоненциально быстрее алгоритмом, основанным на квантовых блужданиях, чем любым (не обязательно основанным на блужданиях) классическим алгоритмом. | Квантовые блуждания были впервые введены Дэвидом Мейером и Джоном Уотроусом для изучения квантовых клеточных автоматов и квантового логарифмического пространства, соответственно. Квантовые блуждания в дискретном времени исследовали Наяк и др. [3, 15], а также Ахаронов и др. [1] на бесконечной линии и N-цикле, соответственно. Центральными темами в первые годы развития концепции квантовых блужданий были определение оператора блуждания, понятия времени перемешивания и времени достижения цели, а также достижимое ускорение по сравнению с классической постановкой задачи. Экспоненциальное квантовое ускорение времени достижения между антиподами гиперкуба было показано Кемпе [9], а Чайлдс и коллеги [6] представили первую задачу с оракулом, решаемую экспоненциально быстрее алгоритмом, основанным на квантовых блужданиях, чем любым (не обязательно основанным на блужданиях) классическим алгоритмом. | ||
Авторами первых систематических исследований квантового времени достижения на гиперкубе и 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>. Ключевое отличие этих результатов от результатов | Авторами первых систематических исследований квантового времени достижения на гиперкубе и d-мерном торе были Шенви и др. [17], а также Амбайнис и др. [4]. Улучшая алгоритм пространственного поиска Ааронсона и Амбайниса, основанный на алгоритме поиска Гровера, Амбайнис и др. [4] показали, что d-мерный тор (с <math>N = n^d</math> узлами) может быть исследован с помощью квантового блуждания со стоимостью порядка <math>S + \sqrt{N}(U + C)</math> и вероятностью наблюдения <math>\Omega(1 / log N)</math> для <math>d \ge 3</math>, и со стоимостью порядка <math>S + \sqrt{N log N}(U + C)</math> и вероятностью наблюдения <math>\Omega(1)</math> для <math>d = 2</math>. Ключевое отличие этих результатов от результатов работ [6, 9] заключается в том, что блуждание должно начинаться из однородного состояния, а не из того, которое каким-то образом «связано» с состоянием, в которое мы хотим попасть. Только в последнем случае можно достичь экспоненциального ускорения. | ||
Первый результат, который использовал квантовое блуждание для решения естественной алгоритмической задачи, так называемой ''задачи | Первый результат, который использовал квантовое блуждание для решения естественной алгоритмической задачи, так называемой ''задачи различения элементов'', принадлежит Амбайнису [2]. Алгоритм Амбайниса использует блуждание W по ''графу Джонсона'' J(r, m), вершинами которого являются подмножества размера r из совокупности размера m, причем два подмножества связаны в том и только том случае, если их симметрическая разность имеет величину 2. Актуальность этого графа вытекает из нетривиальной алгоритмической идеи, согласно которой три различные стоимости (S, U и C) уравновешиваются новым способом. В отличие от этого, алгоритм Гровера – хотя он и вдохновил результат Амбайниса – не предполагает такой возможности: в его случае затраты на установку и обновление в модели запросов равны нулю. | ||
| Строка 47: | Строка 47: | ||
Что общего между <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>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. | ||