Квантование цепей Маркова: различия между версиями

'''Теорема 5 [12]. Пусть P обратима и эргодична со спектральным разрывом <math>\delta > 0</math>. Пусть M имеет помеченную вероятность, равную нулю либо <math> \varepsilon > 0</math>. Тогда существует квантовый алгоритм, решающий задачу достижения цели (версия с поиском) со стоимостью <math>S + \frac{1}{\sqrt{\varepsilon}} \bigg( \frac{1}{\sqrt{\delta}} U + C \bigg)</math>.