# Quantum CNot algorithm problem

I have a very simple quantum algorithm:

Let's start with two qubits in the state $|00\rangle$. I apply a Hadamard gate to the first one. Then I apply a CNot gate, with the first one as a control. Then I apply a Hadamard gate to both of them.

I think I should end up with with two qubits 100% in the $|00\rangle$ state. However, I tested this algorithm on two different simulators (QuantumPlayground and Davy Wybiral's), and the output of both was:

$$0.707\,|00\rangle ;\ 0.707\,|11\rangle\,.$$

Where did I go wrong?

• In case it helps you, 0.707 is $\sqrt{2}/2$. – David Richerby May 13 '16 at 18:48

(For convenience I'm omitting the normalization factors like $1/\sqrt2$ and $1/\sqrt4$.)

The state after applying CNOT is $$\left|E\right\rangle=\left|00\right\rangle + \left|11\right\rangle.$$ This is not the same as $$\left|S\right\rangle=(\left|0\right\rangle+\left|1\right\rangle)(\left|0\right\rangle+\left|1\right\rangle)=\left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle+\left|11\right\rangle.$$ Only $(H\otimes H)\left|S\right\rangle=\left|00\right\rangle$, but $(H\otimes H)\left|E\right\rangle$ is something else.

Physically we say $\left|E\right\rangle$ is an entangled state and $\left|S\right\rangle$ is a separable state. Being entangled means you cannot consider each qubit independently.

Instead, to compute $(H\otimes H)\left|E\right\rangle$ you need to consider each possibility (linear component) separately:

\begin{align} (H\otimes H)\left|00\right\rangle &= (\left|0\right\rangle+\left|1\right\rangle)(\left|0\right\rangle+\left|1\right\rangle) &&= \left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle+\left|11\right\rangle \\ (H\otimes H)\left|11\right\rangle &= (\left|0\right\rangle-\left|1\right\rangle)(\left|0\right\rangle-\left|1\right\rangle) &&= \left|00\right\rangle-\left|01\right\rangle-\left|10\right\rangle+\left|11\right\rangle \\ \hline \therefore\;(H\otimes H)\left|E\right\rangle &&&= \left|00\right\rangle \phantom{\,-\left|01\right\rangle-\left|10\right\rangle} + \left|11\right\rangle. \end{align}

• Thanks! You explained a lot to me. Next time I will read some proper math before trying to deal with the problem :) – MichalO May 13 '16 at 18:08

The other answers explain how the circuit behaves. This answer will explain how to directly manipulate the circuit into a simpler form.

Here's a surprising fact: surrounding a CNOT with Hadamards flips the CNOT.

(I get that checking this on paper requires already understanding the solution to your question. You can confirm it for yourself in a circuit simulator such as Quirk at least.)

Your CNOT circuit is surrounded by 3 Hadamards. By flipping the CNOT, and using the fact that H is its own inverse, we can turn that into a single Hadamard:

Leaving us with the standard make-an-entangled-bell-pair circuit. So, when the input is $|00\rangle$, the output is $\frac{1}{\sqrt 2}|00\rangle + \frac{1}{\sqrt 2}|11\rangle$.

Your circuit is equivalent to first applying a Hadamard gate on the second qubit followed by a CNOT gate where the control is the second qubit. This cannot result in state $|00>$ after execution.

To help you further, why do you think it should end up in state $|00>$?

• Thanks for response. My reasoning was: I apply Hadamard gate at first qubit, so it is now in sqrt(2)|0> sqrt(2)|1> state. Then I apply CNot gate, so second qubit is in the same state as first (because if first is |1>, second is negated, so it's becomes |1>). So after applying Hadamard at first one, it should became |0> again (because it is unchanged after first Hadamard), and after applying Hadamard at the second, it should became |0> , because it has the same state as the first. – MichalO May 13 '16 at 16:25