  Szegedy's quantum walk is a quantization of a classical random walk or Markov
chain, where the walk occurs on the edges of the bipartite double cover of the
original graph. To search, one can simply quantize a Markov chain with
absorbing vertices. Recently, Santos proposed two alternative search algorithms
that instead utilize the sign-flip oracle in Grover's algorithm rather than
absorbing vertices. In this paper, we show that these two algorithms are
exactly equivalent to two algorithms involving coined quantum walks, which are
walks on the vertices of the original graph with an internal degree of freedom.
The first scheme is equivalent to a coined quantum walk with one walk-step per
query of Grover's oracle, and the second is equivalent to a coined quantum walk
with two walk-steps per query of Grover's oracle. These equivalences lie
outside the previously known equivalence of Szegedy's quantum walk with
absorbing vertices and the coined quantum walk with the negative identity
operator as the coin for marked vertices, whose precise relationships we also
investigate.

Quantum Physics