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

Пространственный поиск сочетает алгоритм поиска Гровера [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] заключается в том, что блуждание должно начинаться из однородного состояния, а не из того, которое каким-то образом «связано» с состоянием, в которое вы хотите попасть. Только в последнем случае можно достичь экспоненциального ускорения.