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

Общая сложность классического алгоритма составляет <math>S + t_2(t_1 U + C)</math>. Необходимые <math>t_1</math> и <math>t_2</math> могут быть вычислены из характеристик цепи Маркова P, а именно:

Предложение 1 [13]. Пусть P – эргодическая, но симметричная цепь Маркова. Пусть <math>\delta > 0</math> – зазор собственных значений P, и предположим, что всякий раз, когда множество помеченных состояний M непусто, мы имеем <math>|M| / |X| \ge \epsilon</math>. Тогда существуют <math>t_1 = O(1 / \delta)</math> и <math>t_2 = O(1 / \epsilon)</math>, такие, что алгоритм 1 находит помеченный элемент с высокой вероятностью.

Таким образом, стоимость нахождения помеченного элемента классическим способом составляет <math>O(S + 1 / \epsilon (1 / \delta U + C))</math>. Маньез и коллеги [13] построили квантовый алгоритм, который находит помеченный элемент за <math>O(S' + 1 / \epsilon (1 / \sqrt{\delta} U' + C'))</math> шагов, где S', U', С' – это квантовые версии затрат на установку, обновление и проверку (в большинстве вариантов применения они того же порядка, что и S, U и C). Это позволяет добиться квадратичного улучшения зависимости как от <math>\epsilon</math>, так и от <math>\delta</math>.