Marked sets, stationary mass, and walk-search tasks

Let $(X,P,\pi )$ be a finite reversible Markov chain with positive stationary law, as in Finite reversible Markov chain with positive stationary law, and let $\mathcal{M}\subseteq X$ be a set of marked states. Its stationary marked mass is

$\epsilon :=\pi (\mathcal{M})={\sum }_{x\in \mathcal{M}}{\pi }_x\mathrm{.}$

For a specified threshold ${\epsilon }_0\in (0,1]$, the marked-set detection promise problem has yes-instances with $\mathcal{M}\mathrm{\ne }\mathrm{\varnothing }$ and $\epsilon \ge {\epsilon }_0$, and no-instances with $\mathcal{M}=\mathrm{\varnothing }$. The required classical output is one bit distinguishing these two cases; its permitted failure probability is a separate algorithm input. In the uniform-chain case, ${\pi }_x=1\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$, so $\epsilon =\mathrm{\mid }\mathcal{M}\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$.

The marked-state finding promise problem has inputs with $\epsilon \ge {\epsilon }_0$ and requires a classical output $x\in \mathcal{M}$. It is a different output relation from detection. A claimed output is checked by the declared finite projective measurement and marked predicate; the corresponding outcome law is Finite projective measurements and Finite POVMs and their outcome law. The encoding of $X$, the coherent marked predicate, and all state-preparation and transition circuits are supplied input data, not consequences of the finite chain matrix.