4501
правка
Квантовый алгоритм различения элементов: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм различения элементов (посмотреть исходный код)
Версия от 15:41, 8 марта 2023
, 8 марта 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 107: | Строка 107: | ||
Для этой цепи Маркова можно показать, что разрыв собственных значений составляет <math>\delta = O(1/r)</math>, а доля помеченных состояний равна <math>\epsilon = O((r^2)/(N^2))</math>. Таким образом, квантовый алгоритм выполняется за время | Для этой цепи Маркова можно показать, что разрыв собственных значений составляет <math>\delta = O(1/r)</math>, а доля помеченных состояний равна <math>\epsilon = O((r^2)/(N^2))</math>. Таким образом, квантовый алгоритм выполняется за время <math>O \bigg( S' + \frac{1}{\sqrt{\epsilon}} \bigg( \frac{1}{\sqrt{\delta}} U' + C' \bigg) \bigg) = O \bigg( S' + \sqrt{r} \bigg( \frac{N}{r} U' + C' \bigg) \bigg) = O \bigg( r + \frac{N}{\sqrt{r}} \bigg) .</math> | ||
== Применение == | == Применение == | ||