6
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ +1. I always thought it was meant to imply similarity to the one-dimensional heat equation, wherein you have a uniform distribution of heat but for spike in heat at various locations. The heat equation shows that spikes of heat gets transferred everywhere else. Here the uniform distribution is over the Hilbert space, and the spikes of heat correspond to the states that are rotated. The Diffusion operator "transfers" the amplitude of the rotated states all around to others. $\endgroup$ – Mark S Oct 26 '19 at 12:07
  • $\begingroup$ Would not be reflection operator be a better name? It looks like a Householder reflection? $\endgroup$ – stephanmg Sep 20 '20 at 14:33
  • 1
    $\begingroup$ @stephanmg Indeed. You are right. Grover told me in an email that he was not aware that the mathematicians had a name for this reflection operation until after he had written the paper. $\endgroup$ – Sanchayan Dutta Oct 29 '20 at 19:02
6
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Maybe "equal probability" means an eigenstate having a uniform distribution. For example, an eigenstate of a one-dimensional heat equation with walls of equal temperature is the uniform distribution, and (an instantaneous) spike of heat within the one-dimensional line will be driven to this distribution. As @gIS showed, an eigenstate of Grover's operator is also a uniform distribution over the corresponding Hilbert space (with $\lambda=\pm 1$). $\endgroup$ – Mark S Oct 29 '19 at 14:48
  • $\begingroup$ @MarkS What does it mean when you say "an eigenstate of Grover's operator is also a uniform distribution over the corresponding Hilbert space"? I understand that the eigenvectors $|t\rangle$ and $|t_\perp\rangle$ have eigenvalues +1 and -1 respectively (as per glS' answer). However, can't relate it to any uniform "distribution" on the Hilbert space. Distribution of what? I'd suggest writing an answer! $\endgroup$ – Sanchayan Dutta Oct 29 '19 at 15:03
  • $\begingroup$ Well, if all of the probability amplitudes are the same (e.g. uniform), then inversion about the mean doesn't do anything... $\endgroup$ – Mark S Oct 29 '19 at 17:48
  • $\begingroup$ @MarkS Sure, but what does that have to do with eigenstates of Grover's operator? I guess you're trying to say something along these lines, but it's not exactly clear. If I understand correctly, the aim of Grover's algorithm is to amplify the "spike" rather than drive it to a uniform distribution. $\endgroup$ – Sanchayan Dutta Oct 29 '19 at 18:08
  • $\begingroup$ I don't know... your questions are good, and your intuition is running against my lack of formalism. I might offer more but with @gIS's and Dr. Grover's answers themselves I'd probably just add noise... $\endgroup$ – Mark S Oct 29 '19 at 18:45
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This paper along with Dr. Grover's responses to my follow up questions more or less clarifies the physical motivation for the diffusion operator. $\endgroup$ – Sanchayan Dutta Oct 29 '19 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.