## Introduction to quantum computing with Q# – Part 5, Entanglement

In the last post in this series we dove deep into the mathematics and usage examples of multi-qubit gates, with special attention paid to one of the most critical gates in quantum computing, the CNOT gate.

In today’s post we are going to explore the wonders of entanglement – a core concept of quantum mechanics and a critical idea for quantum computing, where it is obtained via the application of the CNOT gate.

### EPR paper

In 1935, three physicists – Albert Einstein, Boris Podolsky, and Nathan Rosen, in a paper Can Quantum-Mechanical Description of Physical Reality be Considered Complete? described an apparent problem, or a paradox, in quantum mechanics. Through a thought experiment around two quantum systems (particles forming the so called “EPR pair”) that interact with each other, they pointed out that through measuring a certain physical property (say a position $x$ or a momentum $p$) of the first one (let’s call it $x_1$), the measurement result of the same physical property of the second particle (let’s call it $x_2$) can be predicted with probability equal to one. Repeating this process again, with the measured properties swapped (now measuring the second property $p_1$), we can predict with probability equal to one the value of $p_2$. Those were the so-called EPR “correlations”. What follows, according to EPR argument, is that we can simultaneously ascribe two incompatible conjugate properties to a quantum object, thus violating the uncertainty principle around which the new quantum theory was built. In this way, they argued, quantum mechanics was incomplete as a description of physical reality.

It has been widely reported that Einstein was not particularly content with some of the argumentation and the general direction (for example by Blanchard and Fröhlich) taken by Podolsky, who was the main author of the paper. Podolsky focused more on criticizing the completeness – or rather lack thereof – of quantum mechanics and its ability to describe reality. Einstein followed the EPR paper with a famous lengthy exchange with Niels Bohr, who provided an initial response to the paper. In that exchange, Bohr pointed out that the EPR reasoning is generally incorrect due to the irreducible role of the measuring instruments in quantum theory and the fact that the logic followed by EPR paper requires two separate experimental arrangements, thus rendering the argument as invalid. This point is emphasised by Arkady Plotnitsky in Epistemology and Probability:

This, however, is at least an implication of his argument, given his insistence (apparently lost on Einstein) in his reply and elsewhere that “in the problem in question we are not dealing with a single specified experimental arrangement, but are referring to two different, mutually exclusive arrangements”. (…) In the EPR case, we can predict with probability equal to unity the first quantity in question—say, the value of the position variable—for the second object, $S_{12}$, of a given EPR pair ($S_{11}$, $S_{12}$).We can then predict the second quantity—the value of the momentum variable—for the second object, $S_{22}$, of, unavoidably, another, “identically prepared” EPR pair ($S_{21}$, $S_{22}$). However, we cannot coordinate these predictions in such a way that they could be considered as pertaining to two identically prepared objects in the way this could be done in classical physics. This is not possible since the necessary intermediate measurements would, in general, give us different data.

### Nonlocality in EPR

Einstein then shifted the focus of the argument to the apparent nonlocality of quantum mechanics – violation of special relativity theory, since the EPR correlations appeared to be communication between the two particles appeared that was superluminal – faster than the speed of light. At this point it is worth adding that it is clear to observe, at least implicitly, that in his work Einstein would always take locality as an axiom. Any possible violation of local realism was unacceptable to Einstein, who famously proceeded to calling the EPR correlations “spooky action at a distance” (“spukhafte Fernwirkung” in German). To him, the quantum mechanical “restriction to laws of a statistical nature will turn out to be transitory”, which in turn led to him on a search for the so-called “hidden variables” theories, which aimed at (re)introducing determinism into the nature of quantum processes. The goal of such hidden variables was to show that the correlated information was present in the particles all along, just beyond the reach of the quantum mechanical mathematical scheme, thus restoring locality.

A simplified variant of the EPR thought experiment, focusing on the non-locality aspect, rather then the completenes of the theory and its description of reality, was proposed by David Bohm in 1951 in his Quantum Theory. The variant we will discuss here is based on this Bohm model, further refined in a very digestible and approachable explanation by David Griffiths in his Introduction to Qunatum Mechanics. Bohm defined a source emitting an entangle positron-electron pair (e.g. a decaying neutral pion), where both emitted particles fly off towards separate observers – unsurprisingly for theoretical physics – Alice and Bob. Due to the fact the pion had 0 spin and that angular moment conservation applies, we know that when Alice measures her particle along the Z-axis, and gets a result of spin being up, then Bob will certainly get spin down in his measurements. It is equally possible that Alice would get a spin down though, in which case Bob is guaranteed to get a spin up result. These correlations are guaranteed provided they both measure along the same axis – not necessarily Z, but it has to be the same.

There are two things that are particularly troubling in this. Firstly, as Einstein was quick to realize, the particles could be spatially separated by light years – and the correlations would still apply, forming what seems to be a completely nonlocal, special relativity violating phenomenon. Secondly, the choice of the basis seems to mysteriously affect the result too. Imagine Alice and Bob agreed on measuring along the X-axis, however, this time Alice decides to cheat, and without telling Bob, she measures across the Z-axis. This way, instead of getting the spin result $+$ or $-$, which would be the result for the X-axis (Hadamard basis) measurement, she gets a result $up$ or $down$. Bob, unaware of this plot twist, still measures along the X-axis. What he will experience, is that he will get $+$ 50% of time, and $-$ 50% of time. If you recall our discussion from part 2 of this series about superposition and measurement badis impacting the result, this is exactly what Bob is experiencing here. The measurement that Alice performed, possibly even lights year away, has forced Bob’s qubit to assume a definite spin opposite to Alice’s result ($up$ or $down$), and therefore also assume a superposition with respect to the X basis, leaving poor Bob getting random results when measuring that way. This is of course what really bother Einstein here when he referred to “spooky action at a distance”.

It wasn’t until 1964, when Irish physicist, John S. Bell, in his now legendary paper “On The Einstein Podolsky Rosen Paradox” (you can read the original here), disproved the “hidden variable” program for quantum mechanics using an ingenious method of analyzing correlation between entangled quantum objects, when measured in different bases. It became known as the Bell’s theorem and we shall revisit it in more detail in future posts.

The EPR paper, while conceptually describing the phenomenon of entanglement, did not use that term – it was introduced in the same year (1935) by Erwin Schrödinger, in his famous “cat-paradox” paper “Die gegenwärtige Situation in der Quantenmechanik” (English translation is available here). The original term he used was Verschränkung, which later became translated to English as “entanglement”. Schrödinger defined entanglement in the following way:

When two systems, of which we know the states by their respective representatives, enter into temporary physical interaction due to known forces between them, and when after a time of mutual influence the systems separate again, then they can no longer be described in the same way as before, viz. by endowing each of them with a representative of its own.

Schrödinger also proceeded to describe entanglement as the essence of quantum theory. As we already defined, a compound quantum system can be represented by a tensor product:

$$\ket{\psi} = \ket{\psi_1}\otimes\ket{\psi_2} … \otimes\ket{\psi_n}$$

According to Schrödinger, with entangled states, we can no longer use the tensor products of the subsystem state vectors to describe the overall system state. In fact, for all intents and purposes, we can say that the individual states do not exist anymore as independent entities. Blanchard and Fröhlich describe this particularly troubling observation in their in-depth study of weird and counter-intuitive concepts of quantum mechanics:

If a quantum system consists of various parts, it is the total state that is primary. Two entangled electrons may have a definite total spin value in each direction, but no one of the two electrons has a definite spin value in itself in any direction. The components stand in a certain relation, but the total state of the composite system cannot be derived from the non-relational properties of these components. In contrast to classical objects, quantum objects are not characterized by intrinsic properties but by being part of more comprehensive systems.

The phenomenon of entanglement contributes dramatically to the massive divide between quantum and classical theoretical thinking, up to a point where, as it was the case with Einstein, it drifts so far away from our acceptable rational boundaries that it becomes difficult, or even impossible to accept it as being the true nature of reality. This ultimately lead Bohr onto his well documented path to develop interpretative framework for quantum phenomena revolving around nonrealism, something we already touched upon in this series.

### Mathematics of entanglement

As we mentioned above, at purely theoretical level, we can speak of a system being in an entangled state, when it cannot be described by the individual states of its subsystems. As defined in the last post, given two separate qubit states $\ket{\psi_1}$ and $\ket{\psi_2}$:

$$\ket{\psi_1} = \alpha_1\ket{0} + \beta_1\ket{1}$$
$$\ket{\psi_2} = \alpha_2\ket{0} + \beta_2\ket{1}$$

The overall state of such composite system, when it is in an unentangled state, can be decomposed and expressed by the tensor product of the subsystems:

$$\ket{\psi} = \ket{\psi_1}\otimes\ket{\psi_2} = \alpha_1\alpha_2\ket{00} \\ + \alpha_1\beta_2\ket{01} + \ \beta_1\alpha_2\ket{10} + \beta_1\beta_2\ket{11}$$

This is algebraically understandable and in itself doesn’t necessarily seem indicative of anything suspicious yet. It is, however, a good place to set off on the quest of searching for entanglement. Therefore, let’s consider the following quantum circuit, consisting of two gates are already familiar with, $CNOT$ and $H$, called the Bell circuit: It is a two qubit circuit, and in the example above both input qubits start in $\ket{0}$ state (which we could write using the shorthand Dirac notation $\ket{00}$). The circuit uses a regular $CNOT$ gate, except the control qubit passes through the Hadamard gate first. As we already know, the $H$ gate will force the qubit state into a uniform linear superposition. We can now calculate the output of this gate:

$$CNOT(H\ket{0} \otimes \ket{0}) = \\ CNOT((\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})) \otimes \ket{0}) = \\ CNOT(\frac{1}{\sqrt{2}}\ket{00} + \frac{1}{\sqrt{2}}\ket{10}) = \\ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}(\frac{1}{\sqrt{2}}\ket{00} + \frac{1}{\sqrt{2}}\ket{10}) = \\ \frac{1}{\sqrt{2}}\ket{00} + \frac{1}{\sqrt{2}}\ket{11} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$$

Next thing to do would be to compare the output of the Bell circuit to the generalized description of a two-qubit system:

$$\alpha_1\alpha_2\ket{00} + \alpha_1\beta_2\ket{01} + \beta_1\alpha_2\ket{10} + \beta_1\beta_2\ket{11} = \\ \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$$

This is starting to get a little more problematic. Notice that in the resulting state, the amplitude, and thus, per Born rule, the probability of receiving the states $\ket{01}$ or $\ket{10}$ are both $0$ for us. Given this information, we know that $\alpha_1\beta_2 = 0$ and $\beta_1\alpha_2 = 0$. This naturally implies that either $\alpha_1\alpha_2 = 0$ or $\beta_1\beta_2 = 0$ is also true, which is not the case – since both of these are explicitly non-zero. And this is the mathematical gist of entanglement – we cannot decompose an entangled qubit state into a tensor product of the individual qubit states. Moreover, upon measurement, we can only ever end up with $\ket{00}$ and $\ket{11}$, which implies that if we receive $\ket{0}$ when measuring the first qubit, the second is guaranteed to be $\ket{0}$ too, while if the first one produces $\ket{1}$ on measurement, we will certainly get $\ket{1}$ on the other one – provided the measurements are always done in the same basis, in this case in the computational basis, Pauli Z.

The state $\frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$ is the so called Bell state, or to be more precise, one of the four Bell states, describing maximally entangled particles. In quantum mechanics their role, just like the role of entanglement in general, has historically been seen as more of a curiosity, relevant mainly for theorists. It is also worth noting that such pure simple biparticle states are rather an exception in nature – much complex systems emerge quickly. The role of entanglement, however, grew dramatically via the advent of quantum information theory, and the Bell states are fundamentally important in quantum computing, as they form the core concept around the possible quantum-over-classical computational advantage. This way they are often a key component for various quantum computing algorithms. The particular Bell state above is normally described by a symbol $\ket{\Phi^+}$ and we obtain it when the input states (also known as the input register) is $\ket{00}$.

All four of the Bell states are listed below, and they can be produced depending on the input to the Bell circuit. Together, they form an orthonormal basis for a two-qubit system:

$$\ket{00} \rightarrow \frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) = \ket{\Phi^+}$$
$$\ket{10} \rightarrow \frac{1}{\sqrt{2}}(\ket{00} – \ket{11}) = \ket{\Phi^-}$$
$$\ket{01} \rightarrow \frac{1}{\sqrt{2}}(\ket{01} + \ket{10}) = \ket{\Psi^+}$$
$$\ket{11} \rightarrow \frac{1}{\sqrt{2}}(\ket{01} – \ket{10}) = \ket{\Psi^-}$$

It is also worth noting, that while the notion of superposition is basis-dependent – a qubit might be in superposition with respect to some bases, but not to other, something we covered in part 2 of this series – and that the basis choice would naturally impact measurement results of entanglement qubit, the notion of basis choice doesn’t impact entanglement itself. The measurement of both qubits using the same basis – any basis, no necessarily the Pauli Z – is however mandatory to observe the correlated results. This characteristic of entanglement is critical in the study and research of quantum cryptography.

### Entanglement in Q

We can of course use Q# to further explore and verify the properties of entangled quantum states. In principle such exercise would not be much different from the earlier work done in this series – as we only need the $H$ and $CNOT$ to produce a Bell state. This could be done by the following sequence of gate operations, where $control$ and $target$ represent two borrowed qubits.

Q#, being a higher level language than a bare bones implementation of gate semantics, also offers a shortcut convenience operation to prepare a Bell state. This operation, $PrepareEntangledState$, is available in the $Microsoft.Quantum.Preparation$ namespace and allows us to entangle an arbitrary number of qubits. We could replace the above sequence of $H$ and $CNOT$ calls with a simple:

Please pay attention to the array syntax – even though in our case we use just a single control and target qubits – to produce a classic singlet Bell state – it is possible to create more sophisticated entangled states too.

And example of a program initializing and measuring a Bell state is shown below. The operation is repeated a thousand times to help us develop a statistical understanding of what is going on. To do so, we will track how many times the resulting measurements on both the control and target qubit produce the four possible outcomes – $\ket{00}$, $\ket{01}$, $\ket{10}$ and $\ket{11}$. Additionally, we want to check how many times the measurement along the Z-axis of control qubit and target qubit agree with each other – to verify whether we really encounter the entanglement phenomenon and whether we can spot any statistical patterns in our results. The code below uses $PrepareQubitState$ operation that we defined in the last post, to flip $\ket{0}$ to $\ket{1}$, should out input register require so – this allows us to arbitrarily prepare qubits with $\ket{0}$ or $\ket{1}$ initial states. Since in a moment we shall try different Pauli bases for measurement, those are also exposed as input into the operation.

We can now execute this code above and produce the Bell state $\Phi^+$. To do so, we shall initialize the input register to system state $\ket{00}$ and we will then follow with coordinated but independent measurements along the Z-axis ($PauliZ$ basis), using the following $EntryPoint$ operation:

The result should be the following, or approximately similar, since we are dealing with statistically varying results, output in the terminal:

The result confirms that just as predicted by quantum mechanics in the $\ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$ Bell state, the two qubits became maximally entangled. The measurements never result in $\ket{01}$ or $\ket{10}$, but, with equal probability only $\ket{00}$ or $\ket{11}$. It follows that the measurements of the two qubits always agree with each other. Let’s now run the code for the other opposite Bell state $\Phi^-$. As we already algebraically determined, we can obtain the state $\ket{\Phi^-} = \frac{1}{\sqrt{2}}(\ket{00} – \ket{11})$ when starting with the input register of $\ket{10}$. Since the only difference between $\ket{\Phi^+}$ and $\ket{\Phi^-}$ is the amplitude sign, the probabilities will be identical. In Q#, this corresponds to executing our code using the following input parameters:

We should receive the output similar to the one below:

which agrees with our predictions and corresponds statistically to the results for $\Phi^+$.

For $\Psi^+$ and $\Psi^-$, the invocation code looks like this:

And the output shows us:

This is again as expected. When starting with input register of $\ket{01}$, the resulting entangled Bell state is described by the equation $\ket{\Psi^+} = \frac{1}{\sqrt{2}}(\ket{01} + \ket{10})$ which tells us that the only possibilities upon measurement along the Z-axis are – with equal probability – $\ket{01}$ or $\ket{10}$. This means that we should never encounter a situation when the first qubit has the same measured bit value as the second one – they should be opposite. This is exactly what we see in our Q# program, and the same conclusions can be drawn for $\ket{\Psi^-} = \frac{1}{\sqrt{2}}(\ket{01} – \ket{10})$.

An interesting question to ask at this point is what can we observe in Q# for the situation where the target qubit is not measured in the Pauli Z base, but in the Pauli X base, while the control qubit is still using the Pauli Z. This corresponds to the situation we described earlier where Alice “cheated” and measured her particle along the Z-axis, and Bob, unaware of that, still measured his particle along the X-axis like they agreed to earlier. This is shown in the Q# snippet below, covering all four Bell states.

The output of this code should resemble the following:

With the obvious limitation of our 1000 runs sample size, what we can observe is an almost perfect probabilistic distribution of the four obtained final states – $\ket{00}$, $\ket{01}$, $\ket{10}$ and $\ket{11}$ – each of which occurs 25% of time. Additionally, and this follows naturally due to the usage of computational basis with two orthogonal states $\ket{0}$ and $\ket{1}$, the measurements of the two qubits only agree 50% of the time. These experimental Q# results align perfectly with our earlier description of the EPR pair behavior.

Finally, we can use Q# to verify one other claim that we made – entanglement should not be basis dependent, as long as both qubits (particles) are measured using the same basis, any basis, we should be able to observe the phenomenon of entanglement. We shall therefore execute our sample code, forcing both control and target qubits to be measured using the Pauli X basis instead of the typical computational basis Z.

The output of this code upon execution would be similar what we see in the snippet below. In this particular case we are yet again able to see (statistically speaking) perfect distribution and correlation of the measured results. Since we are now measuring in the X basis, rather than the Z basis, the positive correlation occurs for the initial input states $\ket{00}$ and $\ket{01}$, while the inverse correlation can be spotted for the initial reigster $\ket{10}$ and $\ket{11}$.

### What does entanglement even mean?

We shall close off this post on a more philosophical note. It is clear that quantum entanglement occupies space right at the very heart of the confusing landscape of quantum theory. The problem is amplified by the term ‘entanglement’ itself – the quantum behavior is named after a known, relatable, visualizable and inherently local classical concept. Unfortunately, quantum entanglement with its nonlocal correlations is nothing like the classical, macro-scale term, leading to a sudden and violent breakdown of our intuition. These deceptive linguistic traps are characteristic for quantum theory and have often been studied in quantum theoretical literature over the years. Edward MacKinnon makes the following observation about entanglement in his study of the language of the quantum-classical divide, Interpreting Physics:

‘Entanglement’ when used in a classical sense presupposes locality. Two strings are entangled when one is wound around the other. When ‘entanglement’ is used in quantum contexts it refers to a non-local, or holistic, property. (…) One is using language beyond the limits of normal usage by suppressing presuppositions and using mathematics as a vehicle for moving usage beyond normal limits. This supports an idiontology, a specification of the distinctive properties of quantum systems. It does not yield an ontology, either in the sense of a specification of basic entities or a categorial system for the quantum realm.

In the last post, we mentioned that the sophisticated mathematical scheme used to perform quantum calculations doesn’t lend itself to be used as description or representation of the underlying reality. We are now able to also extend this reasoning onto the language used to theorize about quantum phenomena. We are not only unable to represent the reality using the mathematical framework we use to reason about it, when dealing with quantum phenomena we are also having troubles to find applicable language constructs that are free of the classical burden. The result of that is that the cognitive barriers around quantum mechanics are high, if not insurmountable. The entire situation is somewhat unfortunate, but also, for the most part, inescapable. Already back in 1930, in the transcription of his famous Chicago lectures Heisenberg warned about this exact problem when reasoning about the quantum theory:

It is not surprising that our language should be incapable of describing the processes occurring within the atoms, for, as has been remarked, it was invented to describe the experiences of daily life, and these consist only of processes involving exceedingly large number of atoms. Furthermore, it is very difficult to modify our language so that it will be able to describe atomic processes, for words can only describe things of which we can form mental pictures.

Overall, this discussion leads us back to the interpretative framework that we already touched upon, something that Bohr fathered, reality without realism. While, in principle, we cannot preclude the existence of quantum objects themselves, we are not even able to provide any realistic (or, as in classical physics, idealized) representation of them.

### Summary

In this part 5 of the series, we explored the deep concept of entanglement and tried to give it some historical background. We were able to use Q# to create entangled qubits and confirm some of the fundamental quantum mechanical behaviors related to entanglement.

In the next posts we shall continue building upon that and we will see why there is no way to copy qubits, and ultimately work our way towards some real practical use cases for entanglement such as quantum teleportation or superdense coding.