4446
правок
Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
Квантование цепей Маркова (посмотреть исходный код)
Версия от 21:00, 20 октября 2022
, 20 октября 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 44: | Строка 44: | ||
Главное математическое наблюдение Амбайниса о блуждании W по графу Джонсона состоит в том, что <math>W^{\sqrt{r}} O_M</math> ведет себя примерно так же, как и <math>DO_M</math> итерации Гровера, где D – оператор диффузии Гровера. Вспомним, что алгоритм Гровера применяет <math>DO_M</math> многократно, переводя однородное начальное состояние | Главное математическое наблюдение Амбайниса о блуждании W по графу Джонсона состоит в том, что <math>W^{\sqrt{r}} O_M</math> ведет себя примерно так же, как и <math>DO_M</math> итерации Гровера, где D – оператор диффузии Гровера. Вспомним, что алгоритм Гровера применяет <math>DO_M</math> многократно, переводя однородное начальное состояние <math>\phi_0</math> в состояние <math>\phi_{good} = \sum_{x \in M} \sqrt{1 / |M| | x \rangle }</math> после <math>t = O(1/ \alpha)</math> итераций, где <math>\alpha := 2 sin^{-1} \langle \phi_{good} | \phi_0 \rangle </math> – эффективный «угол поворота». | ||
Что общего между | Что общего между <math>W^{\sqrt{r}}</math> и <math>D</math>? Амбайнис показал, что нетривиальные собственные значения матрицы <math>W^{\sqrt{r}}</math> в подпространстве (конечной размерности), содержащем орбиту <math>\phi_0</math>, удалены от 1 на константную величину <math>\epsilon</math>. Таким образом, <math>W^{\sqrt{r}}</math> служит очень хорошим приближенным отражением вдоль оси <math>\phi_0</math> – не менее хорошим, чем у Гровера в этом приложении. Это позволяет вывести следующее заключение: существует t = O(l/a), для которого перекрытие {фё00а\(№-^ОмУ\Фо} = &(1), поэтому выходное значение, вероятно, находится в M. | ||