1
$\begingroup$

I am trying to understand the Reflection Gate - Us explained for 2 qubits in the qiskit textbook. In the explanation it is mentioned that first Hadamard gate is applied to change the state $|s\rangle$ to $|0\rangle$ then a circuit adds negative phase to all the states orthogonal to $|s\rangle$ and this is done by applying 2 $Z$ (one each on both the qubits) gates followed by a controlled $Z$. I am confused about this because once $|s\rangle$ goes to $|0\rangle$ there won't be any superposition so $Z$ gates won't do anything at all because the effect of $Z$ gates on computational basis is to change $|1\rangle$ to $-|1\rangle$. Can someone please explain. This question is different from other questions asked so please do not link it to other questions.

$\endgroup$
1
2
$\begingroup$

In a nutshell: The key fact to remember is that what you called the reflection gate is only applied after the oracle. Therefore the state is not $|s\rangle$ anymore.


Detailed answer:

To show in more detail what's going on we can calculate a concrete example. In general, Grover's algorithm apply the Grover operator $Q$ defined as $$ Q = H^{\otimes n}S_0 H^{\otimes 2} S_f $$ where $H$ is the Hadamard gate, $S_0 = 2|0\rangle^{\otimes n}\langle 0|^{\otimes n} - \mathbb I$ is a reflection about the $|0\rangle^{\otimes n}$ state and $S_f$ is the oracle. Sometimes we group the first three operations and call it "diffusion" because it equals a reflection about the maximally superposed state: $$ Q = S_{+} S_f $$ with the diffusion operator $S_+ = 2|+\rangle^{\otimes n}\langle +|^{\otimes n} - \mathbb I$.

Now, in the standard formulation of Grover's algorithm we initialize a maximally superposed state and apply $Q$ a specific number of times $p$ to amplify the amplitude of the solution bitstring: $$ Q^p H^{\otimes n} |0\rangle^{\otimes n}. $$ If you know the number of solutions you can calculate $p$, otherwise we usually apply different powers of $Q$, measure, and check if the output is a solution.

Let's look at your particular example to see that the diffusion operator really amplifies the solution state. I've attached that as notes, since the math takes a bit long to TeX

enter image description here

Sidenote: you can also use different operations than $H^{\otimes n}$ to for the general amplitude amplification algorithm.

$\endgroup$
2
  • $\begingroup$ Texed version of the decomposition of Grover's diffusion operator $\endgroup$ Jun 25 at 10:17
  • $\begingroup$ Thanks for explaining $\endgroup$ Jun 25 at 15:04

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.