6

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?

Andreas132
  • 61
  • 1

1 Answers1

2

A quantum walk can actually be defined in any graph. For each defined graph, it is only true that the operator must be local (considering the graph edges) and unitary.

So we must consider the Grover's algorithm as a walk in the complete graph. Each iteration of the algorithm applies the Grover diffusion operation that distributes the amplitude in a node for all other nodes. This is the evolution operator encoding the graph adjacency matrix (i.e., A = J-I, where J is the matrix full of 1's). The coin space is optional if we can produces an operator that already respects locality as the diffusion operator.

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.

Pedro
  • 21
  • 2