Significance of the term "diffusion" in Grover's diffusion operator

Question

In the context of Grover's algorithm, the diffusion operator is defined as $U_s = 2|s\rangle \langle s| - I$ with $|s\rangle\equiv |+\rangle^{\otimes n}$. What is the significance of the term "diffusion"? Does it refer to some physical phenomena?

Answer 1

I had forwarded this question to Dr. Lov Grover and received the following response.

I guess inversion about average is a better name for the $\mathrm{W}\mathbb I_0\mathrm{W}$ transformation. When I initially did the algorithm, I called this the diffusion transform because I was familiar with classical diffusion and this is what this transform accomplished - it drove an equal probability from any state to every other state (at least initially).

Later on, I realized this was the same as the Householder transformation in Linear Algebra. There probably exist more applications in that direction (e.g. using quantum computing to implement given rotations in optimization) but I have not pursued them.

Best wishes,
Lov

I think he means classical diffusion in this (random walk) sense. It's still not exactly clear what he means by "drove an equal probability from any state to every other state"; if anyone can decipher it, let me know in a comment!

---

Updates:

Ahh! You computer scientists don't understand much of that language, unfortunately.

The physical idea is to scatter the particle rapidly, then apply a potential function, that attracts the particle to the T state - a potential function is just a phase rotation & the IAA is the diffusion transform.

---

IAA = Inversion about average

For the relation between rotation and accumulation see any QM text under Schrödinger equation. I wrote a paper on that - From Schrödinger’s equation to the quantum search algorithm.

The cited paper actually addresses the physical motivation for the diffusion transform! You may access a preprint version of the paper here. It looks like a phenomenal paper that gives us glimpses into how Grover thought of and designed his flagship algorithm. It's interesting to note that the motivation for the search algorithm was mostly from physics (Grover wasn't a computer scientist), and by the same token it's unfortunate that none of the quantum computing textbooks, as far as I know, mention this aspect of the algorithm.

Answer 2

The operator was named "diffusion transform" in the original Grover's paper (see second column of pag. 3) but no explanation is given for the terminology there (and I don't know whether it was "common" at the time).

You can think of Grover's algorithm as a repeated application of an operator $\mathcal U=-\mathcal S_i\mathcal S_t$ that is the product of two reflections, the first with respect to the target state, and the second one with respect to the initial state: $$\mathcal S_t\equiv 2|t\rangle\!\langle t| - I, \qquad \mathcal S_i\equiv 2|i\rangle\!\langle i| - I,$$ if $|i\rangle$ and $|t\rangle$ are initial and target states. These operators satisfy by construction $\mathcal S_t|t\rangle=|t\rangle$ and $\mathcal S_t|t_\perp\rangle=-|t_\perp\rangle$ for all $\langle t_\perp|t\rangle=0$, and similarly for $|i\rangle$.

To connect this with the more common notation used in expositions of Grover's algorithm, just use $|i\rangle=|+\rangle^{\otimes n}$ as the initial state. Then, $\mathcal S_t$ is what is often (e.g. in the Wikipedia page) written as $U_\omega$ and $\mathcal S_i$ is the diffusion operator.

One possible rationale for naming $\mathcal S_i$ a "diffusion operator" is that, of the two operators, it is the one that changes the probability of measuring the target. Indeed, for any state $|\psi\rangle$, you have $$|\langle t|\mathcal S_t|\psi\rangle|^2=|\langle t|\psi\rangle|^2.$$ You can, therefore, picture the action of $\mathcal U$ as being comprised of one operation ($\mathcal S_t$) that only changes the phases of $|\psi\rangle$ without really moving it closer to the target, and another diffusion operation ($\mathcal S_i$) that moves the state towards $|t\rangle$.

To be fair though, this interpretation only makes sense if you are just looking at the probability of finding the evolving state to be $|t\rangle$ at every step. One could make the same exact argument but looking at the probability of finding $|\psi\rangle$ on the initial state, and then we would conclude that $\mathcal S_t$ should be called "diffusion operator" rather than $\mathcal S_i$. Ultimately, the algorithm is entirely symmetric in the way the two reflections act, so I wouldn't read too much into the way the terminology "diffusion operator" is used in this context.