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