4551
правка
Квантовый алгоритм различения элементов: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм различения элементов (посмотреть исходный код)
Версия от 13:24, 8 марта 2023
, 8 марта 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
1. Условный переворот фазы: <math>|T \rangle \to - |T \rangle</math> для всех T, таких, что в нем содержатся i, j, <math>x_i = x_j</math>, и <math>|T \rangle \to |T \rangle</math> для всех остальных T; | 1. Условный переворот фазы: <math>|T \rangle \to - |T \rangle</math> для всех T, таких, что в нем содержатся i, j, <math>x_i = x_j</math>, и <math>|T \rangle \to |T \rangle</math> для всех остальных T; | ||
2. Квантовое блуждание: выполнить <math>O(\sqrt{r})</math> шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое | 2. Квантовое блуждание: выполнить <math>O(\sqrt{r})</math> шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое <math>|T \rangle</math> на комбинацию базисных состояний <math>|T' \rangle</math> для T', которые отличаются от T на один элемент. | ||
Алгоритм ведет еще один квантовый регистр, в котором хранятся все значения | Алгоритм ведет еще один квантовый регистр, в котором хранятся все значения <math>x_i, i \in T</math>. Этот регистр обновляется с каждым шагом квантового блуждания. | ||
Если имеются два элемента i,j такие, что | Если имеются два элемента i, j такие, что <math>x_i = x_j</math>, то повторение этих двух преобразований O(N/r) раз увеличивает амплитуды <math>|T \rangle</math>, содержащих i, j. Измерение состояния алгоритма в этот момент с высокой вероятностью дает множество T, содержащее i, j. Затем из множества T мы можем найти i и j. | ||
Основная структура алгоритма из [ ] похожа на квантовый поиск Гровера, но с одним существенным отличием. В алгоритме Гровера вместо квантового блуждания применяется диффузионное преобразование Гровера. Реализация алгоритма диффузии Гровера требует | Основная структура алгоритма из [2] похожа на квантовый поиск Гровера, но с одним существенным отличием. В алгоритме Гровера вместо квантового блуждания применяется ''диффузионное преобразование'' Гровера. Реализация алгоритма диффузии Гровера требует <math>\Omega(r)</math> обновлений регистра, хранящего <math>x_i, i \in T</math>. В отличие от алгоритма диффузии Гровера, каждый шаг квантового блуждания изменяет T на один элемент, требуя только одного обновления списка <math>x_i, i \in T</math>. Таким образом, <math>O(\sqrt{r})</math> шагов квантового блуждания могут быть выполнены с <math>O(\sqrt{r})</math> обновлениями, что квадратично быстрее, чем при преобразовании диффузии Гровера. И, как показано в [2], квантовое блуждание обеспечивает достаточно хорошую аппроксимацию диффузии, чтобы алгоритм работал правильно. | ||
| Строка 58: | Строка 58: | ||
1. Инициализировать x состоянием, выбранным из некоторого начального распределения по состояниям P. | 1. Инициализировать x состоянием, выбранным из некоторого начального распределения по состояниям P. | ||
2. | 2. <math>t_2</math> раз повторить: | ||
(а) Если текущее состояние y помечено, вывести y и остановить работу алгоритма; | (а) Если текущее состояние y помечено, вывести y и остановить работу алгоритма; | ||
(б) Смоделировать | (б) Смоделировать <math>t_1</math> шагов случайного блуждания, начиная с текущего состояния y. | ||
3. Если алгоритм не завершил выполнение, вывести «Нет помеченного состояния». | 3. Если алгоритм не завершил выполнение, вывести «Нет помеченного состояния». | ||
| Строка 66: | Строка 66: | ||
Обобщение на произвольные цепи Маркова | '''Обобщение на произвольные цепи Маркова''' | ||
Шегеди [14] и Маньез и др. [ ] обобщили алгоритмы из [ ] и [ ], соответственно, для ускорения поиска по произвольной цепи Маркова. Основной результат работы [13] состоит в следующем. | Шегеди [14] и Маньез и др. [13] обобщили алгоритмы из [4] и [2], соответственно, для ускорения поиска по произвольной цепи Маркова. Основной результат работы [13] состоит в следующем. | ||
Пусть P – несводимая цепь Маркова с пространством состояний X. Предположим, что некоторые состояния в пространстве состояний P помечены. Наша цель – найти помеченное состояние. Это можно сделать с помощью классического алгоритма, который обрабатывает цепь Маркова P до тех пор, пока она не достигнет помеченного состояния (алгоритм 1). | Пусть P – несводимая цепь Маркова с пространством состояний X. Предположим, что некоторые состояния в пространстве состояний P ''помечены''. Наша цель – найти помеченное состояние. Это можно сделать с помощью классического алгоритма, который обрабатывает цепь Маркова P до тех пор, пока она не достигнет помеченного состояния (алгоритм 1). | ||
В сложность алгоритма 1 вносят вклад три типа стоимости: | В сложность алгоритма 1 вносят вклад три типа стоимости: | ||
1. Стоимость настройки S: стоимость выборки начального состояния x из начального распределения. | 1. '''Стоимость настройки''' S: стоимость выборки начального состояния x из начального распределения. | ||
2. Стоимость обновления U: стоимость моделирования одного шага случайного блуждания. | 2. '''Стоимость обновления''' U: стоимость моделирования одного шага случайного блуждания. | ||
3. Стоимость проверки C: затраты на проверку помеченности текущего состояния x. | 3. '''Стоимость проверки''' C: затраты на проверку помеченности текущего состояния x. | ||