Ever wondered what is so special about applying the Hadamard gate H and the CNOT gate together in a quantum circuit? Well, obviously it is used extensively to produce entangled qubits.

But how does this actually happen?

And more importantly: how was this discovered?

Like most exercises in quantum information theory you can either work forward or backward. Working forward through a problem is nice as it allows you to follow logical steps that lead from one proposition to the next. But often this hides the true motivation, and the result, which is usually remarkable, just happens to appear out of thin air.

As a researcher in this field, I find that working forward through a problem is not as useful as working backward through a problem. In this article we are also going to work backward through this problem because it is very easy to describe up front what we want.

We Want Entangled Qubits

It’s clear we want entangled qubits. One definition of an entangled system of qubits is that the state which describes the system cannot be factored as a product of states. But this definition is not very useful to us. Another definition is of the measurement of entangled qubits: that they are maximally correlated.

This is the definition we will use.

Two qubits are entangled when they are maximally correlated.

And this means that when we measure qubit one to be, say, 0 then qubit two is also 0. When we measure qubit one to be 1 then the second qubit is also 1, no matter what – they are maximally correlated. Even though a sequence of measurements may produce a random list of 0’s and 1’s, both lists from each qubit will be in the same order.

Only 4 Combinations to Think About

OK, so we want maximally correlated qubits. Let’s think about this in terms of two qubits, which we will label q_0 and q_1. In the usual notation, the quantum state vector of this system is |q_0q_1\rangle.

With just 2 qubits like this there are only 4 combinations possible:

\displaystyle |00\rangle\quad|01\rangle\quad|10\rangle\quad|11\rangle

and only two of these are correlated:

\displaystyle |00\rangle\quad|11\rangle

So, somehow, we must get rid of the states |10\rangle and 01\rangle but do so in a quantumly way, i.e. use only the tools that quantum mechanics allow, obviously this will by way of quantum logic gates.

Writing Out States In Full

To give us an idea of where to go next, let us write out these quantum states in full.

The |00\rangle state is shorthand for

\displaystyle |00\rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}

and the |11\rangle state is shorthand for:

\displaystyle |11\rangle = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}

This is because the composite state |00\rangle is actually a tensor product of two states: |0\rangle\otimes|0\rangle, but we just write |00\rangle to save ink! And each of these little guys are

\displaystyle |0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}

and so the full calculation of their tensor product is

\displaystyle |00\rangle = |0\rangle\otimes|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\otimes\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \times 1 \\ 1 \times 0 \\ 0 \times 1 \\ 0 \times 0\end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}

and a similar calculation for the other correlated state:

\displaystyle |11\rangle = |1\rangle\otimes|1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\otimes\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \times 0 \\ 0 \times 1 \\ 1 \times 0 \\ 1 \times 1\end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}

It is very easy to see what happens when we add these two states together:

\displaystyle |00\rangle + |11\rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

And now, what if we multiply this by \frac{1}{\sqrt{2}}?

\displaystyle \frac{1}{\sqrt{2}}\left(|00\rangle + |11\rangle\right) = \frac{1}{\sqrt{2}}\left(\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}\right) = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

Why have I done this?

Well, because the state \frac{1}{\sqrt{2}}\left(|00\rangle + |11\rangle\right) is the first Bell state.

This is of no use to us because this is just a label we give to something we already know is maximally correlated, and hence entangled. But we do know how to get Bell states from other states.

This means that once we do a bunch of stuff (which we don’t know how to do yet!) and arrive at this Bell state, then we know immediately that the two qubits are maximally correlated.

So how do we get a Bell state?

Creating Bell States

There are many ways to create Bell states using quantum logic gates. But let’s say that we are researching this for the very first time and we don’t know any of these methods and we have to do it ourselves.

We know where we are starting from, because that is a register of two qubits |q_1 q_2 \rangle, and we know where we have to get to:

\displaystyle \frac{1}{\sqrt{2}}\left(|00\rangle + |11\rangle\right) = \frac{1}{\sqrt{2}}\left(\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}\right) = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

and we know that we are only able to get there using quantum mechanics. This means we are only allowed to use unitary (density) matrices denoted by U. Since we have two qubits, these things are 2^2 \times 2^2-square matrices that satisfy unitarity.

Therefore our problem becomes a matrix multiplication problem: Find a U such that,

\displaystyle U |q_1 q_2 \rangle = \frac{1}{\sqrt{2}}\left(|00\rangle + |11\rangle\right) = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

There are so Many Unitaries!

The above system of linear equations must hold for every combination of qubit state placed in the q_1,\, q_2 placeholders. I.e. it has to work for:

\displaystyle U |00 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

\displaystyle U |01 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

\displaystyle U |10 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

\displaystyle U |11 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}

We can solve this equation using methods from linear algebra. This is too verbose for this blog, you can use your favourite mathematical software to solve it. But there does exist a U, and it is:

\displaystyle U = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0\end{pmatrix}

Before we check where this beast came from, let’s check that it works.

Checking the 00 State

Let’s begin by substituting all the necessary ingredients:

\displaystyle U|00\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}

This calculation is very simple because of all the zeroes in the \left(1,0,0,0\right)^{\top} state vector. The 1 in the first entry is literally just going to pick out the 1 in entry U_{11} and the 1 in entry U_{41}. So this matrix does indeed give the desired result:

\displaystyle U|00\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}}\left(|00\rangle + |11\rangle\right)

Those qubits are maximally correlated and we have successfully killed off the unwanted states.

Checking the 10 State

What about the state |10\rangle?

\displaystyle U|01\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ -1 \end{pmatrix} = \frac{1}{\sqrt{2}}\left(|00\rangle - |11\rangle\right)

Success again! The only states left after this matrix multiplication by U is just the desired |00\rangle and |11\rangle states.

Checking the 01 State

Let’s keep going! What about the state |01\rangle?

\displaystyle U|01\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\left(|01\rangle + |10\rangle\right)

Whoa! Wait a minute.

That is NOT a correlated state there! What happened?

Well, technically they are maximally correlated…they’re just anti-correlated!  Whenever the first qubit is a 1 the second is a 0, and vice versa. So technically, this is still something we desire! We just didn’t realise it. This is also a Bell state.

A Quick Note on the Basis

Interestingly, if we were calculating all of this stuff in the \{|+\rangle,|-\rangle\} basis instead of the standard computational basis \{|0\rangle,|1\rangle\}, the calculation we just did would end up being correlated, and the other two anti-correlated. 

Checking the 11 State

OK, let’s keep going. What about the state |11\rangle?

\displaystyle U|11\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 0 \\ 1 \\ -1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\left(|01\rangle - |10\rangle\right)

and again, this is anti-correlated and the 4th Bell state.

Deconstructing the Unitary

OK, so we successfully found a unitary matrix

\displaystyle U = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0\end{pmatrix}

that when applied to every single combination of input qubit states |00\rangle\,|10\rangle\,|01\rangle\,|11\rangle it output a maximally correlated or anti-correlated state.

The question is now: How do we implement the unitary U on a quantum circuit? Is it even possible?

Well, straight up, no – it’s not possible. 

The trick is to note that U can be factored in to two smaller unitaries, i.e. U = U_C \cdot U_H, like so:

\displaystyle U = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{pmatrix}\cdot\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1\end{pmatrix}

where

\displaystyle U_C := \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{pmatrix}

\displaystyle U_H := \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1\end{pmatrix}

What is so special about this factorisation?

Well, both of these smaller matrices are both unitary as well, but they are also irreducible – they can’t be factored in to smaller unitaries. This means that they are implementable as quantum logic gates on a circuit.

In fact, these two matrices are already well-known as the CNOT gate U_C and the Hadamard gate U_H.

Summary

So now we know that we can run any register of 2 qubits (no matter what state) through a Hadamard gate and then a CNOT gate will always result in a maximally correlated (or anti-correlated) pair of qubits.

By starting with what we wanted, we worked backward and expanded all the quantum states as vectors, solved a system of linear equations subject to the some constraints about unitary-ness, then factored that unitary matrix and found that the factors are the Hadamard and the CNOT gate. 

We proved that this worked by working through the matrix multiplications of every single possible arrangement; and proved to ourselves that no matter which combination we put in to the Hadamard and CNOT gate arrangement we always ended up with what we wanted.

Doesn’t the CNOT Constitute a Measurement?

It make look like the CNOT gate must actually measure the first qubit to determine what to change the second gate to (or leave it). You might think therefore that the CNOT gate collapses the wavefunction or something like that – you know, like what a measurement does.

The CNOT gate never physically returns a result. It does not output a number or provide some status of the state of the system. Instead, it modifies the underlying probability distribution in a non-collapsing way. Very similar to quantum oracles, which act in the same way.

After a CNOT gate, the control qubit is kept while the target now holds the logical XOR of control-and-target so that

\displaystyle\textsf{CNOT}|x\rangle|y\rangle = |x\rangle|x\oplus y\rangle

As you can see, this is difficult to do in practice as coherence must be ensured for as long as possible.

An example of a matrix which is not reversible and not unitary and which does collapse wavefunctions is the measurement matrix. An example of one acting on one qubit looks like this:

\displaystyle M_x :=|x\rangle\langle x| = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 1\times 1 & 1 \times 0 \\ 0 \times 1 & 0 \times 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}

Very different kind of matrix when compared to the CNOT matrix.