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

''Пространственный поиск'' посредством ''квантового блуждания'' представляет собой поиск в базе данных с дополнительным ограничением, заключающимся в том, что перемещение по пространству поиска происходит путем квантового блуждания, подчиняющегося некоторой структуре локальности (решетка, гиперкуб и т .д.). Квантовые блуждания являются аналогами классических случайных блужданий на графах. Сложность пространственного поиска с помощью квантового блуждания определяется главным образом ''квантовым временем достижения цели'' [9] данного блуждания.

Пусть S, |S| = N, – конечное множество ''состояний'', и пусть <math>P = (p_{x, y})_{x, y \in S}</math> – ''матрица вероятностей перехода'' для ''цепи Маркова'' на S, также обозначаемая P. Предположим, что подмножество состояний <math>M \subseteq S</math> ''помечено''. Задача состоит в том, чтобы найти помеченное состояние, учитывая, что <math>M \ne \empty</math> (''версия с поиском''), или определить, является ли M непустым (''версия с принятием решений''). Если возможные перемещения <math>x \to y</math> (т. е. те, при которых <math>p_{x, y} \ne 0)</math> образуют ребра (ориентированного) графа G, то говорится, что блуждание имеет ''структуру локальности'' G.