# Implementing Deutsch's problem on IBM Q composer

I tried to implement the Deutsch's problem on IBM Q but didn't get the results as expected.

So here is the circuit for the Deutsch algorithm

and this is my implementation on the composer:

so let me explain to you what I did/thought:

$$|x\rangle$$ is qubit q(1)

$$|y\rangle$$ is q(2)

with qubit q(0) I wanted to realize the oracle function $$f(x)$$, which has - as implemented - the properties that $$f(0) = 0$$ and $$f(1) = 1$$. As I used the cnot gate on the initial $$|0\rangle$$ state of q(0) -> so $$f$$ is balanced on q(0) I should have f(x) after the first CNOT gate. q(0) (which is $$f(|x\rangle)$$ now determines what happens with q(2) using a flipped CNOT, as it is technically not possible to use the normal CNOT gate.

Then I measure $$|x\rangle$$ i.e. q(1) which should be in a pure state (here $$|0\rangle$$ as $$f$$ is balanced) - but it is not:

so any ideas what went wrong here? Maybe (probably) my implementation of $$U_{f}$$ is wrong, but how can this be realized then?

## 1 Answer

TL;DR: There are 8 possible outcomes, each with equal probability of being read. The final state has q[1] read as 0 in 4 of the outcomes, and read as 1 in the other 4 outcomes. Since you are only measuring q[1], you only see the two results, one with q[1] as 0 and one with q[1] as 1. They are both around 50% because each outcome had an equal probability of being read.

Let's go through your circuit and what the state should be at each step.

X-Gate on q[2]

The state will now be |100$$\rangle$$

Just a simple bit flip on q[2], from 0 to 1.

H-Gate on q[2] and H-Gate on q[1]

After these gates, the state will be $$\frac{1}{\sqrt4}$$|000$$\rangle$$ + $$\frac{1}{\sqrt4}$$|010$$\rangle$$ + $$\frac{1}{\sqrt4}$$|100$$\rangle$$ + $$\frac{1}{\sqrt4}$$|110$$\rangle$$

q[2] and q[1] both get put into superposition. They both can be either 0 or 1, leading to 4 possible outcomes.

CNOT from q[1] to q[0]

After this gate, the state will be $$\frac{1}{\sqrt4}$$|000$$\rangle$$ + $$\frac{1}{\sqrt4}$$|011$$\rangle$$ + $$\frac{1}{\sqrt4}$$|100$$\rangle$$ + $$\frac{1}{\sqrt4}$$|111$$\rangle$$

q[1] and q[0] become entangled. q[0]'s outcome depends on q[1]. The two will either be 00 or 11, and since q[2] is still in superposition, there are still 4 possible outcomes.

H-Gate on q[2] and H-Gate on q[0]

After these gates, the state will be $$\frac{1}{\sqrt4}$$|100$$\rangle$$ + $$\frac{1}{\sqrt4}$$|101$$\rangle$$ + $$\frac{1}{\sqrt4}$$|110$$\rangle$$ + $$\frac{1}{\sqrt4}$$|111$$\rangle$$

The H-Gate on q[2] cancels the first one out, leaving q[2]'s outcome as 1. The H-Gate on q[0] puts it in superposition, meaning it can be either 0 or 1. There are still 4 outcomes, because although we lost two possible outcomes with q[2] going back to just being 1, we gained two possible outcomes since q[0] can be either 0 or 1.

CNOT from q[2] to q[0]

After this gate, the state will still be $$\frac{1}{\sqrt4}$$|100$$\rangle$$ + $$\frac{1}{\sqrt4}$$|101$$\rangle$$ + $$\frac{1}{\sqrt4}$$|110$$\rangle$$ + $$\frac{1}{\sqrt4}$$|111$$\rangle$$

This gate essentially does not change the state. What ends up happening is when q[2] is 1, a bit flip will be applied to q[0]. However, at the moment q[2] is always 1, so each possible outcome will have q[0]'s bit flipped. Since each outcome has an equal probability of being read, the bit flip just provides us with the state possible outcomes, each with the same probabilities.

H-Gate on q[2] and H-Gate on q[0]

After these gates, the state will be $$\frac{1}{\sqrt4}$$|000$$\rangle$$ + $$\frac{1}{\sqrt4}$$|011$$\rangle$$ + $$\frac{1}{\sqrt4}$$|100$$\rangle$$ + $$\frac{1}{\sqrt4}$$|111$$\rangle$$

The H-Gate on q[2] puts it back in superposition, meaning it can be either 0 or 1. The H-Gate on q[0] cancels out the first one, meaning it is either 0 or 1 depending on q[1]. q[0] and q[1] will either be 00 or 11, and q[2] will either be 0 or 1, providing us with 4 possible outcomes.

H-Gate on q[1]

After this gate, the state will be $$\frac{1}{\sqrt8}$$|000$$\rangle$$ + $$\frac{1}{\sqrt8}$$|001$$\rangle$$ + $$\frac{1}{\sqrt8}$$|010$$\rangle$$ + $$\frac{1}{\sqrt8}$$|011$$\rangle$$ + $$\frac{1}{\sqrt8}$$|100$$\rangle$$ + $$\frac{1}{\sqrt8}$$|101$$\rangle$$ + $$\frac{1}{\sqrt8}$$|110$$\rangle$$ + $$\frac{1}{\sqrt8}$$|111$$\rangle$$

This final H-gate sets q[1]'s outcome as either 0 or 1, and this change won't affect q[0]'s outcome. q[0]'s outcome is still either 0 or 1 depending on what q[1] at the CNOT gate. q[2] is still in superposition, so it is either 0 or 1 as well. Since all 3 of the qubits can be either 0 or 1, there are $$2^3$$, or 8, possible outcomes.

The last H-Gate on q[1] does not cancel out the first H-Gate (which would end up setting q[1] to only be 0) because of the entanglement between q[0] and q[1].

Unfortunately, I do not know exactly how to fix your circuit to have it do what you want it to, as I am not very knowledgable on the algorithm itself. However, this article may provide some more information on the topic.