Quantum-walk conjecture for reversible Markov chains

Let $\mathcal{P}$ be a reversible, ergodic Markov chain with stationary distribution $\uppi$, and let $M$ be a set of marked states. Define

$$p_M=\sum_{x\in M}\uppi_x.$$

Assume that $p_M<0.5$, and consider Algorithm

with interpolation parameter $s\in[0,1)$ and positive integer running time $t$. **Quantum-walk conjecture.** There \exists a value $s\in[0,1)$ and a positive integer

t=\mathcal{O}\big(\sqrt{HT}\big)

$$such that Algorithm$$

succeeds with probability $\Omega(1)$. This is the paper's algorithm-specific formulation of the proposed quadratic-speedup claim; the available text gives no resolution beyond the conjecture, while a more complicated algorithm is proved to achieve a logarithmically weaker bound.