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

Перейти к навигации Перейти к поиску
Строка 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>


== Применение ==
== Применение ==
4501

правка

Навигация