4
$\begingroup$

According to the tutorial https://qiskit.org/textbook/ch-algorithms/grover.html I understand the mathematical principle of diffusion operator:

$$ \begin{equation} \begin{split} U_s&=2\left|s\right\rangle\left\langle s\right|-I \\ &=H^{\otimes n}U_0H^{\otimes n} \\ &=H^{\otimes n}\left(2\left|0\right\rangle\left\langle 0\right|-I\right)H^{\otimes n} \\ &=H^{\otimes n}\begin{bmatrix}1 & & & \\ & -1 & & \\ & & \ddots & \\ & & & -1\end{bmatrix}H^{\otimes n} \end{split} \end{equation} $$

For example, for two qubits

$$\left|s\right\rangle=\frac{1}{2}\left(\left|00\right\rangle+\left|01\right\rangle-\left|10\right\rangle+\left|11\right\rangle\right)=\frac{1}{2} \begin{pmatrix}1 \\ 1 \\ -1 \\ 1 \end{pmatrix}$$

applying the diffusion operator and we got

$$H^{\otimes 2}U_0H^{\otimes 2}\frac{1}{2} \begin{pmatrix}1 \\ 1 \\ -1 \\ 1 \end{pmatrix}=\begin{pmatrix}0 \\ 0 \\ 1 \\ 0 \end{pmatrix}$$

where $$H^{\otimes 2}=\begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\1 & -1 & -1 & 1 \end{bmatrix}$$

So far this transformation is working well, it reflected the states of $s$ as expected. But it is difficult for me to understand the role played by the Hadamard gate here. How to prove or explain the following equation?

$$2\left|s\right\rangle\left\langle s\right|-I=H^{\otimes n}\left(2\left|0\right\rangle\left\langle 0\right|-I\right)H^{\otimes n}$$

or

$$ \left|s\right\rangle\left\langle s\right|=H^{\otimes n}\left|0\right\rangle\left\langle 0\right|H^{\otimes n} $$

$\endgroup$
1
  • $\begingroup$ personally, I find the most intuitive way to understand Grover's algorithm is to realise it amounts to a simple rotation in the space spanned by input and target space. See e.g. quantumcomputing.stackexchange.com/a/8623/55 and quantumcomputing.stackexchange.com/a/5306/55 (I'm referring to how to intuitively understand the action of the whole diffusion operator; proving the last relation is just a matter of algebra) $\endgroup$
    – glS
    Dec 3 '20 at 9:53
2
$\begingroup$

It is often described as flipping the number around the mean. Lets take example with real numbers (normally these are complex numbers). For example, we have an array of 4 elements and we want to find element 3. We will start in an equal superposition. We have : $$|\psi\rangle = [\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}]$$ When we apply $U_\omega$ we will flip ("add a minus") to the 3rd number : $$|\psi\rangle = [\frac{1}{2}, \frac{1}{2}, -\frac{1}{2}, \frac{1}{2}]$$ When we apply Grover's diffusion operator, we take the mean/average : $$a = \frac{3*\frac{1}{2}-\frac{1}{2}}{4}=\frac{1}{4}$$ When we do the inversion around the mean of a number $v$, we do $-v+2*a$ which gives us : $$-\frac{1}{2}+(2*\frac{1}{4})=0$$ and $$-(-\frac{1}{2})+(2*\frac{1}{4})=1$$. If we do this for every element, this gives us : $$|\psi\rangle = [0, 0, 1, 0]$$ As you can see, we just increased the probability to measure the correct element and decreased the probability of the incorrect elements. This of course is a very simple example, but it demonstrates the effect really well. This is the same example as in the section 6.4 of quantum computing for computer scientists. If you have any more questions, please write a coment !

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. Can you give a proof or explanation that HUHs=2a-v? This is where I am confused. $\endgroup$
    – Devymex
    Dec 2 '20 at 21:36
  • $\begingroup$ Aditya answered already, here is another decomposition in basic gates. This is the one used is many different cases. $\endgroup$ Dec 3 '20 at 9:52
1
$\begingroup$

Like @Jonathcraft mentioned, the diffusion operator inverts the probability amplitudes about their mean. What is equally important to note is that the inversion about the mean is the same as a reflection of the state-vector about the state $|u\rangle = \frac{1}{2^{n/2}}\sum_x\lvert x\rangle$, which is the equal superposition of all the basis states for an n-qubit system.

To understand this, consider the general state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$:

  • Flipping the amplitudes about the mean ($\mu = \frac{\alpha+\beta}{2}$) would yield the state $|\psi\prime\rangle = \beta|0\rangle + \alpha|1\rangle$.
  • To reflect about the state $|u\rangle = \frac{1}{\sqrt{2}}{|0\rangle}+\frac{1}{\sqrt{2}}{|1\rangle}$, you would first have to find the angle between $|\psi\rangle$ and $|u\rangle$, and then rotate $|\psi\rangle$ by twice that angle. You can verify using the general $2\times 2$ rotation matrix that this yields $|\psi\prime\rangle$.

Now, to answer your question about the presence of the Hadamard Gate -

When you want to reflect a given state about the equal superposition over all basis states $|u\rangle$, the easy way to think about it is using these 3 steps:

  1. Transform $|u\rangle$ into $|0\rangle^n$ - This is achieved by applying the Hadamard Transform to all $n$ qubits.
  2. Reflect your vector (which would also have been transformed by the application of the Hadamard transform) about $|0\rangle^n$. The matrix for this is $diag_n(1, -1, -1, ..., -1)$.
  3. Transform $|0\rangle ^n$ back to $|u\rangle$ to reverse what you did in the first step. Since the Hadamard gate is its own inverse, this is equivalent to repeating Step 1.

Putting it all together, the diffusion operator is given by:

$$ H^{\otimes n} \begin{bmatrix}1 & & & \\ & -1 & & \\ & & \ddots & \\ & & & -1\end{bmatrix} H^{\otimes n} $$

$\endgroup$

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.