I need sketch two circuits to understand Grover algorithm. The first is the operator $R_f$ and another is the operator $R_D = H^{\otimes n}(2|0\rangle\langle0|-I)H^{\otimes n}$. I get the first operator. How I will be able to sketch the operator $R_D$ using Toffoli and Hadamard gates? I need a hint to solve this exercise please
2 Answers
You are halfway there, because you already wrote down the Hadamard gates. The remaining part, $I-2\left|0\right>\left<0\right|$ (I negated it from what you have, since this gives a simpler solution), is diagonal in the computational basis. Write down these diagonal entries and say out loud to yourself what this operator "does".
-
$\begingroup$ this operator leads $\[a_0,a_1, ... , a_n\]$ to $\[-a_0,a_1, ... , a_n\]$. Can sketch this operator with Toffoli gate? $\endgroup$– juaninfMay 16, 2013 at 15:21
-
-
$\begingroup$ This operator flips the phase if the input is $\left|0,0,...,0\right>$, otherwise it has no effect. In other words, it flips the phase if the first bit is 0 AND the second bit is zero AND the third bit is zero, etc. So, your first task is to make a circuit that checks if all of the input qubits are zero. You will need to introduce ancilla bits to store the working memory for this part of the computation. Then flip the phase if all inputs were zero. Then clean up (uncompute) the ancilla bits. $\endgroup$ May 16, 2013 at 18:40
-
$\begingroup$ I cann't understand when you say: flips the phase if the input is $\left|0,0,...,0\right>$ otherwise it has no effect. For example if the input is $a|0,0\rangle$ the phase is $a$ and $(I-2\left|0\right>\left<0\right|)(a|0,0\rangle) = -a|0,0\rangle$ but the same happens if the input is $a|1,1\rangle$, because the output is $-a|1,1\rangle$. Am I wrong? $\endgroup$– juaninfMay 16, 2013 at 19:13
-
1$\begingroup$ $\left|0,0\right> = [1,0,0,0]$ and $\left|1,1\right> = [0,0,0,1]$. $\endgroup$ May 16, 2013 at 20:13
Dear Dan with your suggestions I trying a one answer. Can you verify this please? . (I build to $R_D = H^{\otimes n}(2|0\rangle\langle0|-I)H^{\otimes n}$.). The first and the last column represented $H^{\otimes n}$. For the expression $(2|0\rangle\langle0|-I)$ while the input has form $|000\cdots00\rangle$ tha phase is the same, otherwise the phase change. I make this using your hint $Z=H^{+}XH$ in the last row in the circuit.