[Belovs] and [Montanaro1] define quantum walk search in the electric network framework, that share common property: A single step of the quantum walk is defined, such that its the identity on marked nodes. [ACRSZ] uses a similar quantum walker(, and [Belovs] also points to this paper).
Lets recalls the definition (incomplete, but hopefully sufficient) of the quantum walk operator of [Belovs] (Section 3):
Let $G = (V, E)$ be an undirected graph, and $M \subseteq V$ a set of marked vertices. G is bipartite, with parts A,B. Each edge $uv \in E$ is associated with weight $w_{uv}$.
A step of the quantum walk is defined by $R_B R_A$ where
- $R_A = \oplus_{u \in A} D_u$
- $R_B = \oplus_{u \in B} D_u$
and $D_u$ is defined as
- If $u$ is marked: identity
- If $u$ is nor marked: Reflection about $|\phi_u \rangle$, $I - 2|{\phi_u}\rangle \langle{\phi_u}|$, with $|{\phi_u}\rangle = \sqrt{\frac{\sigma_u}{C_1 R}} |{u}\rangle + \sum_{uv \in E} \sqrt{w_{uv}} |{uv}\rangle$
where $C_1 > 0$ some constant, and $R$ is the effective resistance.
This means, that if the quantum walker steps into a marked node, then the the walker does not leave the marked node anymore. To me, this fits the definition of a absorbing quantum walk (rather than an interpolated walk, that leaves the state with a certain probabilty).
Question: Why is this a valid quantum walk operator?
Remark: To my understanding the graph traversed by [Belovs] and [Montanaro1] walker
is not reversible [Montanaro2], which is a necessary condition to allow a discrete-time quantum walk
describes an absorbing random walk (rather than an interpolated walk), which means that Markov chain is not ergodic anymore, and thus the nice eigenvalue properties may not hold anymore. This may not be so relevant, as they prove properties, and the use QPE to decide if a marked node exists, rather than "walk" until a marked node can be measured with high probability.
