# Chapter 5 Quantum entanglement

About the fundamental tool of quantum computing:

entanglement, via the formalism oftensor products, which was the missing ingredient from our previous formalism of quantum theory. Also about variouscontrolled gates, including the always usefulcontrolled-.\texttt{NOT}

We now know everything we need to know about a single qubit and its quantum behaviour. But if we want to understand quantum computation — a complicated quantum interference of many interacting qubits — then we will need few more mathematical tools. Stepping up from one qubit to two or more is a bigger leap than you might expect. Already, with just two qubits, we will encounter the remarkable phenomenon of quantum entanglement and have a chance to discuss some of the most puzzling features of quantum theory that took people decades to understand.

## 5.1 A small history

The notion of **quantum entanglement** was the subject of many early debates that focused on the meaning of quantum theory.
Back in the 1930s, Albert Einstein, Niels Bohr, Werner Heisenberg, and Erwin Schrödinger (to mention just the usual suspects) were trying hard to understand its conceptual consequences.^{68}
Einstein, the most sceptical of them all, claimed that it was pointing toward the fatal flaw in quantum theory, and referred to it as “*spooky action-at-a-distance*”.
In contrast, Schrödinger was much more prepared to accept quantum theory exactly as it was formulated, along with all its predictions, no matter how weird they might be.
In his 1935 paper, which introduced quantum entanglement, he wrote “I would not call it *one* but rather *the* characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought”.
Today we still talk a lot about quantum entanglement, but more often it is viewed as a physical resource which enables us to communicate with perfect security, build very precise atomic clocks, and even teleport small quantum objects!
But what exactly is quantum entanglement?

## 5.2 One, two, many…

In classical physics, the transition from a single object to a composite system of many objects is trivial: in order to describe the state of, say, 42 objects at any given moment of time, it is sufficient to describe the state of each of the objects separately. Indeed, the classical state of 42 point-like particles is described by specifying the position and the momentum of each particle.

In the *classical* world, “the whole is the sum of its parts”, but the *quantum* world is very different.

Consider, for example, a pair of qubits.
Suppose that each one is described by a state vector: the first one by *cannot* be expressed in this form.
In order to write down the most general state of two qubits we first focus on the basis states.

For a single qubit we have been using the standard basis ^{69}

For example, compare the two states of two qubits,
**separable**, i.e. we can view it as a pair of state vectors where each one pertains to one of the two qubits:
*not* admit such a decomposition: there do *not* exist any **entangled** state.
Informally, any bipartite state that cannot be viewed as a pair of two states pertaining to the constituent subsystems is said to be entangled.

With this discussion in our minds, we can now give more formal account of the states of composite quantum systems.

## 5.3 Quantum theory, formally (continued)

Recalling Chapter 4, where we said that we were missing a key part of the formalism of quantum theory, we can now fill in this hole.
Our mathematical formalism of choice behind the quantum theory of composite systems is based on the **tensor product** of Hilbert spaces.

### 5.3.1 Tensor products

Let the states of some system **tensor product space** ^{70}

The tensor product operation ^{71}, to any number of subsystems.
Note that the bra corresponding to the tensor product state

Some joint states of **separable** (or just **product states**).
States that are not separable are said to be **entangled**.

A useful fact about tensor products is that

We will also need the concept of the tensor product of two operators.
If

## 5.4 Back to qubits

Let’s see how this formalism works for qubits.
The ^{72}
*classical* register composed of three bits can store *only one* of these two binary strings at any time; a *quantum* register composed of three qubits can store *both of them* in a superposition.

Indeed, if we start with the state ^{73}

The resulting state is exactly a superposition of all binary string of length 3, and can also be written as

In general, the tensor product operation **Hadamard transform**, and it maps product states to product states.
Like the Hadamard gate in the typical quantum interference circuit, the Hadamard transform opens and closes a multi-qubit interference.

## 5.5 Separable or entangled?

*Most* vectors in *cannot* be written as product states

In order to see this, let us write any joint state *product* state, these vectors have a special form.
Indeed, if ^{74}
So if we want to identify which joint states are product states and which are not, we simply write the joint state according to Equation (5.5.1) and check if all the vectors

Quantum entanglement is one of the most fascinating aspects of quantum theory. We will now explore some of its implications.

## 5.6 Controlled-NOT

How do entangled states arise in real physical situations?
The short answer is that *entanglement is the result of interactions*.
It is easy to see that tensor product operations

and so any collection of separable qubits remains separable.

As soon as qubits start interacting with one another, however, they become entangled, and things start to get really interesting.
We will describe interactions that cannot be written as tensor products of unitary operations on individual qubits.
The most popular two-qubit entangling gate is the **controlled- \texttt{NOT}** (or

**controlled-**X gate.

^{75}The gate acts on two qubits: it flips the second qubit (referred to as the

**target**) if the first qubit (referred to as the

**control**) is

controlled- |
---|

We can also represent the

Note that this gate does not admit any tensor product decomposition, but can be written as a sum of tensor products:^{76}

The

### 5.6.1 The Bell states, and the Bell measurement

We start with the generation of entanglement.
Here is a simple circuit that demonstrates the entangling power of ^{77}

(Generating entanglement).

In this circuit, the separable input **Bell states**.

The **Bell states**,

The Bell states form an orthonormal basis in the Hilbert space ^{78}
Indeed, if we reverse the circuit, then we get a circuit which maps the Bell state

### 5.6.2 Quantum teleportation

A wonderful fact, that sounds more like science fiction than actual science, is the following: *an unknown quantum state can be teleported from one location to another.*
Consider the following circuit:^{79}

(Quantum teleportation).

The first input qubit (counting from the top) is in some arbitrary state.
After the action of the part of the circuit in the first dashed box (counting from the left), the state of the three qubits reads^{80}

If you understand how this circuit works then you are ready for quantum teleportation. Here is a dramatic version.

Suppose three qubits, which look very similar, are initially in the possession of an absent-minded Oxford student, Alice. The first qubit is in a precious quantum state and this state is needed urgently for an experiment in Cambridge. The other two qubits are entangled, in the

|\psi_{00}\rangle state. Alice’s colleague, Bob, pops in to collect the qubit. Once he is gone, Alice realises that, by mistake, she gave him not the first but the third qubit: the one which is entangled with the second qubit.The situation seems to be hopeless — Alice does not know the quantum state of the first qubit, and Bob is now miles away and her communication with him is limited to few bits. However, Alice and Bob are both very clever and they both diligently attended their “Introduction to Quantum Information Science” classes. Can Alice rectify her mistake and save Cambridge science?

Hmmm… (pause for thought)…

Of course: Alice can teleport the state of the first qubit! She performs the Bell measurement on the first two qubits, which gives her two binary digits,

x andy . She then broadcastsx andy to Bob, who chooses the corresponding transformation, as in Equation (5.6.2), performs it, and recovers the original state.

This raises a natural “philosophical” question: what do we really *mean* by teleportation?
A key part of this question is understanding what happens to our original qubit when we teleport it.
As it turns out, it must necessarily be *destroyed*, as we now explain.

### 5.6.3 Thou shalt not clone

Let us now look at something that controlled-*seems* to be doing but, in fact, *isn’t*.
It is easy to see that the

**This is not so!**

The unitarity of the *entanglement* of the control and the target: if the control qubit is in the a superposition state *impossible* to clone an unknown quantum state, and we can prove this!

To prove this via contradiction, let’s assume that we *could* build a universal quantum cloner, and then take any two normalised states *non-identical* (i.e. *non-orthogonal* (i.e.

Thus, states of qubits, unlike states of classical bits, cannot be faithfully cloned.
Note that, in quantum teleportation, the original state must therefore be *destroyed*, since otherwise we would be producing a clone of an unknown quantum state.
The no-cloning property of quantum states leads to interesting applications, of which quantum cryptography is one.

Universal quantum cloners are *impossible*.

## 5.7 Other controlled gates

### 5.7.1 Controlled-phase

Needless to say, not everything is about the controlled-**controlled-phase** gate

controlled-phase |
---|

We can also represent the

Again, the matrix is written in the computational basis **controlled- Z gate**, which acts as

In order to see the entangling power of the controlled-phase shift gate, consider the following circuit.

(Generating entanglement, again).

In this circuit, first the two Hadamard gates prepare the equally-weighted superposition of all states from the computational basis

and then the controlled-

which results in the entangled state.

### 5.7.2 Controlled-U

Both the above two-qubit controlled gates (i.e. **controlled- U gate**:

controlled- |
---|

We can also represent the

We can go even further and consider a more general unitary operation: the two-qubit ** x-controlled-U gate**:

### 5.7.3 Phase kick-back

Before moving on to the next section, we first describe a simple “trick” — an unusual way of introducing phase shifts that will be essential for our analysis of quantum algorithms. Consider the following circuit.

(Controlled-

where *eigenstate* of

This should look familiar: it is the usual interference circuit, but with the phase gate replaced by a controlled-*required to be an eigenstate of U*.
The circuit effects the following sequence of transformations (omitting the normalisation factors):

*not*get entangled with the first one: it remains in its original state

Consider the following

Now, prepare the qubit in the second register in state *the phase kick-back mechanism introduced a relative phase in the equally-weighted superposition of all binary strings of length two*.

Phase kick-back is how we control quantum interference in quantum computation.

We will return to this topic later on, when we discuss quantum evaluation of Boolean functions and quantum algorithms.

### 5.7.4 Universality, revisited

We will come across few more gates in this course, but at this stage you already know all the elementary unitary operations that are needed to construct any unitary operation on any number of qubits:

- the Hadamard gate,
- all phase gates, and
- the
\texttt{c-NOT}

These gates form a **universal set of gates**: with ^{81}
We should mention that there are many universal sets of gates.
In fact, almost any gate that can entangle two qubits can be used as a universal gate.

We are particularly interested in any *finite* universal set of gates (such as the one containing the Hadamard,

### 5.7.5 Density operators and the like

The existence of entangled states leads to an obvious question: if we cannot attribute a state vector to an individual qubit, then how can we describe its quantum state? In the next few chapters we will see that, when we limit our attentions to a part of a larger system, states are not represented by vectors, measurements are not described by orthogonal projections, and evolution is not unitary. As a spoiler, here is a dictionary of some of the new concepts that will soon be introduced:

state vectors | density operators | |

unitary evolutions | completely-positive trace-preserving maps | |

orthogonal projectors | positive operator-valued measures |

## 5.8 Why qubits, subsystems, and entanglement?

One question that is rather natural to ask at this point is the following:

If entanglement is so fragile and difficult to control, then why bother? Why not perform the whole computation in one physical system that has as many quantum states as we normally have labels for the states of qubits, so that we can label these quantum states in the same way as we normally label the qubits, and give

themcomputational meaning?

This suggestion, although possible, gives a very inefficient way of representing data (it is describing the **unary encoding**).
For serious computations *we need subsystems*.
Here is why.

Suppose you have *separately* and put it into any of the **physical bit**.
We label the two states of a physical bit as

Suppose the two states in the physical bit are separated by the energy difference

In contrast, if we choose to encode

One can, of course, try to switch from harmonic oscillators to quantum systems which have a finite spread in the energy spectrum.
For example, by operating on the energy states of the hydrogen atom one can encode any number from

That is, we have to trade energy for time.

It turns out that whichever way we try to represent the number

## 5.9 *Remarks and exercises*

### 5.9.1 Entangled or not?

Let a joint state of

Show that, if

|\psi\rangle is a product state, then\det (c_{ij}) = 0 .Show that the converse (

\det(c_{ij})=0 implies that|\psi\rangle is a product state) holds only for qubits. Explain why.Deduce that the state

\frac12\big(|00\rangle + |01\rangle + |10\rangle + (-1)^k|11\rangle\big) is entangled fork=1 and unentangled fork=0 . Express the latter case explicitly as a product state.

There is a lot of interesting physics behind the previous innocuous-looking mathematical statement.
For example, think again about the state ^{82}
But can you actually use this effect to send a message faster than light?
What would happen if you tried?

Hopefully you can see that it would not work, since the result of the measurement is random — you cannot choose the bit value you want to send. We shall return to this, and other related phenomena, later on.

### 5.9.2 SWAP circuit

Show that, for any states

(Swapping).

### 5.9.3 Controlled-NOT circuit

Show that the circuit below implements the controlled-

(Controlled-

### 5.9.4 Measuring with controlled-NOT

The controlled-

Take a look at the circuit below, where

(?).

Now assume that the top two qubits are in the state

### 5.9.5 Arbitrary controlled-U on two qubits

Any unitary operation

### 5.9.6 Entangled qubits

Two entangled qubits in the state

What is the probability that Alice and Bob will register identical results? Can any correlations they observe be used for instantaneous communication?

Prior to the measurements in the computational basis, Alice and Bob apply unitary operations

R_\alpha andR_\beta (respectively) to their respective qubits:The gate

R_\theta is defined by its action on the basis states:\begin{aligned} |0\rangle &\longmapsto \cos\theta|0\rangle + \sin\theta|1\rangle \\|1\rangle &\longmapsto -\sin\theta|0\rangle + \cos\theta|1\rangle. \end{aligned} Show that the state of the two qubits prior to the measurements is\begin{aligned} &\frac{1}{\sqrt2}\cos(\alpha-\beta)\big( |00\rangle + |11\rangle \big) \\- &\frac{1}{\sqrt2}\sin(\alpha-\beta)\big( |01\rangle - |10\rangle \big). \end{aligned} What is the probability that Alice and Bob’s outcomes are identical?

### 5.9.7 Quantum dense coding

**!!!TO-DO!!!**

### 5.9.8 Playing with conditional unitaries

The swap gate

Show that the four Bell states

\frac{1}{\sqrt2}(|00\rangle\pm|11\rangle) and\frac{1}{\sqrt2}(|01\rangle\pm|10\rangle) are eigenvectors ofS that form an orthonormal basis in the Hilbert space associated to two qubits. Which Bell states span the*symmetric subspace*(i.e. the space spanned by all eigenvectors with eigenvalue1 ), and which the*antisymmetric*one (i.e. that spanned by eigenvectors with eigenvalue-1 )? CanS have any eigenvalues apart from\pm1 ?Show that

P_\pm = \frac12(\mathbf{1}\pm S) are two orthogonal projectors which form the decomposition of the identity and project on the symmetric and antisymmetric subspaces. Decompose the state vector|a\rangle|b\rangle of two qubits into symmetric and antisymmetric components.Consider the quantum circuit below, composed of two Hadamard gates, one controlled-

S operation (also known as the**controlled-swap**, or**Fredkin**gate), and the measurementM in the computational basis. Suppose that the state vectors|a\rangle and|b\rangle are normalised but*not*orthogonal to one another. Step through the execution of this network, writing down the quantum states of the three qubits after each computational step. What are the probabilities of observing0 or1 when the measurementM is performed?

(Symmetric and antisymmetric projection).

Explain why this quantum network implements projections on the symmetric and antisymmetric subspaces of the two qubits.

Two qubits are transmitted through a quantum channel which applies the same, randomly chosen, unitary operation

U to each of them. Show that the symmetric and antisymmetric subspaces are invariant underU\otimes U .Polarised photons are transmitted through an optical fibre. Due to the variation of the refractive index along the fibre, the polarisation of each photon is rotated by the same unknown angle. This makes communication based on polarisation encoding unreliable. However, if you can prepare any polarisation state of the two photons then you can still use the channel to communicate without any errors. How can this be achieved?

## 5.10 *Appendices*

### 5.10.1 Tensor products in components

In our discussion of tensor products we have so far taken a rather abstract approach.
There are, however, situations in which we have to put numbers in, and write tensor products of vectors and matrices explicitly.
For example, here is the standard basis of two qubits written explicitly as column vectors:

The matrix elements of the tensor product operation

are given by
^{83}

The tensor product induces a natural partition of matrices into blocks. Multiplication of block matrices works pretty much the same as regular matrix multiplication (assuming the dimensions of the sub-matrices are appropriate), except that the entries are now matrices rather than numbers, and so may not commute.

Evaluate the following matrix product of

(4\times 4) block matrices:\left[ \, \begin{array}{c|c} \mathbf{1}& X \\\hline Y & Z \end{array} \, \right] \left[ \, \begin{array}{c|c} \mathbf{1}& Y \\\hline X & Z \end{array} \, \right] (whereX ,Y , andZ are the Pauli matrices).Using the block matrix form of

A\otimes B expressed in terms ofA_{ij} andB_{ij} (as described above), explain how the following operations are performed on the block matrix:- transposition
(A\otimes B)^T ; partial transpositionsA^T\otimes B andA\otimes B^T ; - trace
\operatorname{tr}(A\otimes B) ; partial traces(\operatorname{tr}A )\otimes B andA\otimes (\operatorname{tr}B) .

Consider the Hadamard transform

H\otimes H\otimes H on three qubits, which is described by a(2^3\times2^3) matrix. We know thatH = \frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix} and so we can calculate thatH\otimes H = \frac12 \left[ \, \begin{array}{c|c} \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}1&1\\1&-1\end{matrix} \\\hline \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}-1&-1\\-1&1\end{matrix} \end{array} \, \right] and thus thatH\otimes H\otimes H = \frac12 \left[ \, \begin{array}{c|c|c|c} \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}1&1\\1&-1\end{matrix} \\\hline \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}-1&-1\\-1&1\end{matrix} & \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}-1&-1\\-1&1\end{matrix} \\\hline \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}-1&-1\\-1&1\end{matrix} & \begin{matrix}-1&-1\\-1&1\end{matrix} \\\hline \begin{matrix}1&1\\1&-1\end{matrix} & \begin{matrix}-1&-1\\-1&1\end{matrix} & \begin{matrix}-1&-1\\-1&1\end{matrix} & \begin{matrix}1&1\\1&-1\end{matrix} \end{array} \, \right]. The rows and columns ofH\otimes H\otimes H are labelled by the triples000,001,\ldots,111 . Now, suppose we applyH\otimes H\otimes H to the state|110\rangle :- transposition

The output state is a superposition of all binary strings:

\sum_x c_x|x\rangle , withx\in\{0,1\}^3 . Where in theH^{\otimes 3} matrix will you find the coefficientsc_x ?Now, do you want to write down

H\otimes H\otimes H\otimes H ? I don’t think so. This is an exponentially growing monster and you may soon run out of space if you actually do try to write it down. Instead, let’s spot the pattern of the entries\pm1 in these matrices.Consider the Hadamard gate matrix

H_{ab} , wherea,b=0,1 are the labels for the rows and the columns. Observe thatH_{ab}=(-1)^{ab}/\sqrt{2} . (This may look like a fancy way of writing the entries of the Hadamard matrix but it will pay off in a moment). Using the fact that(A\otimes B)_{ik,jl} = A_{ij}B_{kl} , or any other method, analyse the pattern of the\pm1 in the tensor product of Hadamard matrices. What is the entryH^{\otimes 4}_{0101,1110} ?For any two binary strings

a=(a_1,\ldots, a_n) andb =(b_1,\ldots , b_n) of the same length we can define their “scalar” product asa\cdot b = (a_1b_1\oplus \ldots \oplus a_n b_n) . Show that, up to the constant(1/\sqrt{2})^n , the entryH^{\otimes n}_{a,b} , for anyn and for any binary stringsa andb of lengthn , is(-1)^{a\cdot b} .Show that

H^{\otimes n} acts as|a\rangle \longmapsto \left(\frac{1}{\sqrt 2}\right)^n \sum_{b\in\{0,1\}^n} (-1)^{a\cdot b}|b\rangle A quantum register of

10 qubits holds the binary string0110101001 . The Hadamard Transform is then applied to this register yielding a superposition of all binary strings of length10 . What is the sign in front of the|0101010101\rangle term?

### 5.10.2 The Schmidt decomposition

An arbitrary vector in the Hilbert space **Schmidt decomposition** of *the bases used depend on the state being expanded*.
Indeed, given two bipartite states *cannot* perform the Schmidt decomposition using the *same* orthonormal bases in

The Schmidt decomposition follows from the **singular value decomposition** or **SVD**): *any* **singular values** of

You can visualize the SVD by thinking of

Using the index notation **rank** of **Schmidt number**.
Clearly, all bipartite states of rank one are separable.

The Schmidt decomposition is *almost* unique.
The ambiguity arises when we have two or more identical singular values, as, for example, in the case of the Bell states.
Then any unitary transformation of the basis vectors corresponding to a degenerate singular value, both in

E. Schrödinger, Discussion of probability relations between separated system,

*Mathematical Proceedings of the Cambridge Philosophical Society***31**(1935), pp. 555–563.↩︎It looks like we are defining some sort of “multiplication rule” for kets here, saying that

|a\rangle|b\rangle:=|ab\rangle . This is indeed the case, but to talk about this properly we need to introduce the idea of**tensor products**(which we do very soon).↩︎If the bases

\{|a_i\rangle\} and\{|b_j\rangle\} are orthonormal then so too is the tensor product basis\{|a_i\rangle\otimes|b_j\rangle\} .↩︎({\mathcal{H}}_a \otimes {\mathcal{H}}_b)\otimes {\mathcal{H}}_c = {\mathcal{H}}_a \otimes ({\mathcal{H}}_b\otimes {\mathcal{H}}_c) .↩︎We often drop the

\otimes symbol, especially when we deal with the standard tensor product basis. For example, a state of a quantum register composed of four qubits holding the binary string1001 may be written as|1\rangle\otimes|0\rangle\otimes|0\rangle\otimes|1\rangle , as|1\rangle|0\rangle|0\rangle|1\rangle , or even simply as|1001\rangle .↩︎We often simply write

H\otimes H\otimes H asH^{\otimes 3} .↩︎Even though an entangled state cannot be written as a tensor product, it can always be written as a linear combination of vectors from the tensor product basis. In fact, any state of

n qubits|\psi\rangle can be expressed in the standard*product*basis. In general, givenn qubits, we need2(2^n-1) real parameters to describe their state vector, but only2n to describe separable states.↩︎Here the

X refers to the Pauli operator\sigma_x\equiv X that implements the bit-flip.↩︎Make sure that you understand how the Dirac notation is used here. More generally, think why

|0\rangle\langle 0|\otimes A + |1\rangle\langle 1|\otimes B means “*if the first qubit is in state*”. What happens if the first qubit is in a superposition of|0\rangle then applyA to the second one, and if the first qubit is in state|1\rangle then applyB to the second one|0\rangle and|1\rangle ?↩︎John Stewart Bell (1928–1990) was a Northern Irish physicist.↩︎

For any state

|\psi\rangle of two qubits, the amplitude\langle\psi_{xy}|\psi\rangle can be written as\langle xy|U^\dagger|\psi\rangle , whereU^\dagger is such that|\psi_{xy}\rangle = U|xy\rangle .↩︎*Divide et impera*, or “divide and conquer”: a good approach to solving problems in mathematics (and in life). Start with the smaller circuits in the dashed boxes.↩︎We neglect to write the normalisation factors.↩︎

Recall the big-

O asymptotic notation: given a*positive*functionf(n) , we writeO(f(n)) to mean “bounded above byc\,f(n) for some constantc > 0 (for sufficiently largen )”. For example,15n^2+4n+7 isO(n^2) .↩︎“Spooky action at a distance” is a loose translation of the German “spukhafte Fernwirkung”, which is the phrase that Albert Einstein used in his 1947 letter to Max Born.↩︎

We always use the lexicographic order

00<01<10<11 .↩︎