I am trying to understand and implement the Deutsch algorithm. I follow the logic from Nielsen book and I started to implement it in Qiskit. For implementing the oracle, I use a CNOT gate and now I have this circuit:

enter image description here

Every time I ran it, the first qubit is always in state $|1\rangle$. I am not sure if this is what I expect. Shouldn't it be sometimes $|1\rangle$ and sometimes $|0\rangle$?


CNOT gate is an example that implements a balanced function for which $f(0) = 0$ and $f(1) = 1$:

\begin{equation} CNOT \frac{1}{2}\left(|0\rangle + |1\rangle \right) \left(|0\rangle - |1\rangle \right) = \\ = \frac{1}{2}|0\rangle \left(|0 \oplus f(0)\rangle - |1 \oplus f(0)\rangle \right) + \frac{1}{2}|1\rangle \left(|0 \oplus f(1)\rangle - |1 \oplus f(1)\rangle \right) = \\ = \frac{1}{2} \left(|0\rangle - |1\rangle \right) \left(|0\rangle - |1\rangle \right) \end{equation}

$$H \otimes I \frac{1}{2}\left(|0\rangle - |1\rangle \right) \left(|0\rangle - |1\rangle \right)= \frac{1}{\sqrt{2}}|1\rangle \left(|0\rangle - |1\rangle \right)$$

It means that if we will do everything right we always should obtain (for balanced functions $f(0) \ne f(1)$) $|1\rangle$ outcome in the Deutsch algorithm.

For more look at 1.44 equation (page 33) in the M. Nielsen and I. Chuang textbook, where one can find the final state before the measurement. In the 1.44 system, one can see that if $f(0) = f(1)$ then the first qubit will be in $|0\rangle$ state and if $f(0) \ne f(1)$ (like the case with CNOT) then the first qubit will be in $|1\rangle$ state before the measurement.

| improve this answer | |

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.