Quantum walks on directed graphs
Ashley Montanaro · Quantum Information and Computation · 2007
We consider the definition of quantum walks on directed graphs. Call a directed graph reversible if, for each pair of vertices $(v_i, v_j)$, if $v_i$ is connected to $v_j$ then there is a path from $v_j$ to $v_i$. We show that reversibility is a necessary and sufficient condition for a directed graph to allow the notion of a discrete-time quantum walk, and discuss some implications of this condition. We present a method for defining a "partially quantum'' walk on directed graphs that are not reversible.