Квантовый алгоритм различения элементов: различия между версиями

2. Квантовое блуждание: выполнить <math>O(\sqrt{r})</math> шагов квантового блуждания согласно определению в работе [2]. Каждый шаг представляет собой преобразование, которое отображает каждое <math>|T \rangle</math> на комбинацию базисных состояний <math>|T' \rangle</math> для T', которые отличаются от T на один элемент.

Алгоритм ведет еще один квантовый регистр, в котором хранятся все значения <math>x_i, i \in T</math>. Этот регистр обновляется с каждым шагом квантового блуждания.

Это было одно из первых применений квантовых блужданий для построения квантовых алгоритмов. Затем Амбайнис, Кемпе и Ривош [4] обобщили его для поиска на решетках (см. ссылку). Их алгоритм основан на тех же математических идеях, но имеет несколько иную структуру. Вместо чередования шагов квантового блуждания с переворотами фаз, он выполняет квантовое блуждание с двумя различными правилами – «нормальным» и «возмущенным». («Нормальное» правило соответствует блужданию без переворота фазы, а «возмущенное» – комбинации блуждания с переворотом фазы).

Пусть P – несводимая цепь Маркова с пространством состояний X. Предположим, что некоторые состояния в пространстве состояний P ''помечены''. Наша цель – найти помеченное состояние. Это можно сделать с помощью классического алгоритма, который обрабатывает цепь Маркова P до тех пор, пока она не достигнет помеченного состояния (алгоритм 1).