# Why is Grover's Algorithm considered to be a Quantum Walk?

I have heard it said that Grover's algorithm is (can be modeled as?) a Quantum Walk. In fact, one reason for their popularity is that QW are used in certain Quantum algorithms. I am trying to understand the connection between this algorithm and a Quantum Walk:

So using the setup from Wikipedia, for Grover's algorithm we have a function $$f: \{0,1,...,N-1\} \to \{0,1\}$$ such that there exists a unique index $$\omega \in \{0,1,...,N-1\}$$ where $$f(\omega)=1$$. In every step of the algorithm we apply the unitary operator $$U_\omega$$, where \begin{align*} U_\omega |x \rangle = (-1)^{f(x)} |x\rangle \end{align*} From what I know, a Quantum Walk is a local, unitary and translation invariant operator that acts on a Hilbert space $$l^2(\mathbb{Z}^d; \mathbb{C}^s)$$ and models the movement of a Quantum particle on the grid $$\mathbb{Z}^d$$. The movement of the particle in each step depends on the state of the coin space $$\mathbb{C}^s$$.

In Grover's algorithm, I'd say that the "grid" corresponds to the search space $$\{0,1,...,N-1\}$$, so is kind of a one-dimensional grid $$\mathbb{Z}$$. The coin space would then correspond to the minus sign, which may be introduced by $$U_\omega$$. Thus, we should have $$d=1$$ and $$s=1$$. $$U_\omega$$ is unitary and local, but not translation invariant. So if I drop the requirement for a Quantum Walk to be translation invariant, is that then already all the connection between a QW and Grover's algorithm? That it is basically a unitary operator acting on a grid? Or is there a deeper connection? Furthermore, if I think of a Quantum Walk as a quantum particle moving on a grid, is there a more figurative interpretation?

The operator $$U_\omega$$ is a local modification that "marks" the vertex $$\omega$$, disturbing the evolution operator and making the probability of being in $$\omega$$ to oscillate in each step even though we started in the uniform distribution. The translation invariant property cited in your question is more specific to the grid and is not a requirement for general quantum walks.