0
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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".

$\endgroup$
10
  • $\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$
    – juaninf
    May 16, 2013 at 15:21
  • $\begingroup$ I cann't get yet. Other hint please $\endgroup$
    – juaninf
    May 16, 2013 at 18:23
  • $\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$
    – juaninf
    May 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
0
$\begingroup$

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.

enter image description here

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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