Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
this operator leads $\[a_0,a_1, ... , a_n\]$ to $\[-a_0,a_1, ... , a_n\]$. Can sketch this operator with Toffoli gate? – juaninf May 16 '13 at 15:21
I cann't get yet. Other hint please – juaninf May 16 '13 at 18:23
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. – Dan Stahlke May 16 '13 at 18:40
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? – juaninf May 16 '13 at 19:13
$\left|0,0\right> = [1,0,0,0]$ and $\left|1,1\right> = [0,0,0,1]$. – Dan Stahlke May 16 '13 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.

enter image description here

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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