14a - Entanglement and Quantum Computing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Entanglement and Quantum Computing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "\n",
    "### Peter Onyisi\n",
    "<img src=\"images/texas_logo.png\" width=\"400\" align=\"left\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "tags": [
     "remove-cell"
    ]
   },
   "outputs": [],
   "source": [
    "# TACC: install if necessary\n",
    "try:\n",
    "    import numba\n",
    "except:\n",
    "    ! pip3 install --user numba numpy==1.19.1 scipy==1.5.2 tqdm==4.48.2\n",
    "    INSTALL_PATH='/home/jupyter/mydata/jupyter_packages/lib/python3.6/site-packages'\n",
    "    import sys, os\n",
    "    if os.access(INSTALL_PATH, os.R_OK) and INSTALL_PATH not in sys.path:\n",
    "        sys.path.insert(0, INSTALL_PATH)\n",
    "\n",
    "# generic\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib\n",
    "matplotlib.rcParams['figure.figsize'] = (8,6)\n",
    "matplotlib.rcParams['font.size'] = 16\n",
    "matplotlib.rcParams['animation.embed_limit'] = 60\n",
    "matplotlib.rcParams['xtick.top'] = True\n",
    "matplotlib.rcParams['ytick.right'] = True\n",
    "import math\n",
    "import numpy\n",
    "import scipy.integrate\n",
    "import scipy.stats\n",
    "import scipy.special\n",
    "from matplotlib import animation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Correlations\n",
    "\n",
    "Our discussion of quantum mechanics so far hasn't really touched on one of the most un-classical features of the theory: the fact that quantum states are _not_ just single particles acting independently of each other, but that in fact the proper description of the wave function of a system involves describing all particles at once.  Instead of single-particle wave functions $\\psi_A(x_A)$ and $\\psi_B(x_B)$, you really need a multi-particle wave function $\\psi(x_A, x_B)$. This means that for example that in general\n",
    "$$ \\psi(x_A, x_B) \\neq \\psi_A(x_A)\\psi_B(x_B); $$\n",
    "that is, in general there will be _correlations_ between the behavior of one particle and the behavior of the other. We can sometimes ignore these, where the correlations are very weak, but often they can be very important.\n",
    "\n",
    "The Pauli exclusion principle gives an example of such a correlation: it is not possible for two identical spin-1/2 fermions to be in the same state. The technical cause of this is an _antisymmetry_ requirement that\n",
    "$$ \\psi(x_A, s_A, x_B, s_B) = -\\psi(x_B, s_B, x_A, s_B) $$\n",
    "where $x_A$ and $x_B$ are the positions of the particles and $s_A$ and $s_B$ describe the spins of the particles. The Pauli exclusion principle itself is the observation that if $x_A = x_B = x$ and $s_A = s_B = s$, then\n",
    "$$ \\psi(x, s, x, s) = -\\psi(x, s, x, s) $$\n",
    "which can only be satisfied if $\\psi(x, s, x, s) = 0$: that is, the two particles have zero probability to be in the same place with the same spin. I may of course find a particle at _some_ position $x$ with spin $s$, but I can guarantee that I will not see a second particle in the same position and the same spin. So there is a kind of repulsion that occurs between the identical particles that has no relationship to electrical repulsion or any other such force, but only the fact that they're fermions.\n",
    "\n",
    "(You might ask, well, why can't we still have two electrons in the same state, just never in the same place at the same time? Why should this antisymmetry requirement imply the exclusion principle? Well, if we ignore the electrons' electric repulsion, then both electrons independently have to solve Schr&ouml;dinger's equation as if the other didn't exist. This means $\\psi(x_A, x_B) = \\psi(x_A)\\psi(x_B)$ - with the same wavefunction $\\psi$ for both electrons - which cannot satisfy the antisymmetry requirement. Even with the electric repulsion on, if they have the same spatial probability distribution that means they see identical electric potentials due to the other, so the solution would still have to be symmetric, not antisymmetric, under exchange of the two particles, which is forbidden.)\n",
    "\n",
    "There are opposite-behaving particles called _bosons_ (for example, photons) with integer spin quantum numbers, which have a requirement of _symmetry_ in their wave functions:\n",
    "$$ \\psi(x_A, s_A, x_B, s_B) = +\\psi(x_B, s_B, x_A, s_B) $$\n",
    "This symmetry causes identical bosons to _prefer_ to be in the same state, and leads to phenomena such as [lasers](https://en.wikipedia.org/wiki/Laser) and [Bose-Einstein condensation](https://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_condensate).\n",
    "\n",
    "There are other correlations that are possible. To explore these let's discuss the quantum mechanics of spin angular momentum a little bit more.\n",
    "\n",
    "## Spin and Spin Entanglement\n",
    "\n",
    "The angular momentum of a single spin-1/2 particle along any axis (conventionally called $z$) can be measured and the result will be either $+\\hbar/2$ or $-\\hbar/2$. These are referred to as \"spin up\" and \"spin down\". We can designate the quantum mechanical states (\"wave functions\") of the particle that always give spin up or spin down results as $|\\uparrow\\rangle$ and $|\\downarrow\\rangle$, respectively. \n",
    "\n",
    "If the spin along $z$ is definite in this way, then the spin angular momentum measured along $x$ will be random! Since Schr&ouml;dinger's equation is linear, we can get an acceptable particle state by taking any linear combination of $|\\uparrow\\rangle$ and $|\\downarrow\\rangle$, and it turns out that $\\frac{1}{\\sqrt{2}}(|\\uparrow\\rangle + |\\downarrow\\rangle)$ is the combination that gives a state that always be measured to have spin angular momentum $+\\hbar/2$ along $x$. This actually tells us that we can manipulate the wave function if we are able to rotate the spin direction, e.g. by causing the corresponding magnetic moment to precess in an external magnetic field: if we rotate from a state of $+\\hbar/2$ along $z$ to $+\\hbar/2$ along $x$, then we have shifted the wave function from $|\\uparrow\\rangle$ to $\\frac{1}{\\sqrt{2}}(|\\uparrow\\rangle + |\\downarrow\\rangle)$.\n",
    "\n",
    "Now, some physical processes may result in the creation of states where the total spin angular momentum of the two particles may be zero, but where there's no preferred direction for the spins of the individual particles. That means we must observe one particle with spin up and one particle with spin down, but which is which is equal probability by the wave function. This can be represented by the wave function $\\frac{1}{\\sqrt{2}}(|\\uparrow\\downarrow\\rangle - |\\downarrow\\uparrow\\rangle)$: there is no probability to find the states $|\\uparrow\\uparrow\\rangle$ or $|\\downarrow\\downarrow\\rangle$ - which would have total spin angular momentum $\\hbar$, instead of zero, because the spins would be aligned - and there is equal probability to see $|\\uparrow\\downarrow\\rangle$ and $|\\downarrow\\uparrow\\rangle$. \n",
    "\n",
    "The thing that's weird about this state is that if we know the particles are _entangled_ in this way, then measurement of the spin of one of the particles immediately tells us about the spin of the other. In principle the two particles could have been physically moved apart from each other while remaining in this entangled state - one could be on Earth, the other on Mars, while maintaining the entanglement - and the measurement of the particle on Earth immediately tells us the spin state of the particle on Mars. \n",
    "\n",
    "### The Einstein-Podolsky-Rosen \"Paradox\"\n",
    "\n",
    "In the Copenhagen interpretation, measuring the spin of one particle \"collapses the wave function\" for the two, regardless of how far apart they are. This phenomenon was called \"spooky action at a distance\" by Einstein, because he really wasn't comfortable with the idea that the wave function contains _all_ the information there is to know about the two-particle system; he really wanted the \"true\" spin to somehow be associated with the particles themselves, which meant that the two particles in this case would somehow have to communicate their states instantaneously to each other, transmitting information faster than light (which is forbidden by the special theory of relativity). A [famous paper](https://doi.org/10.1103%2FPhysRev.47.777) by Einstein, Podolsky, and Rosen claimed that that this constituted a paradox, which mandated that in fact there must be \"local hidden variables\" not in the quantum theory that would determine, during the creation of the entangled pair, which was eventually going to be spin up and which was going to be spin down, and which are carried along with the particles.\n",
    "\n",
    "### Bell Inequalities\n",
    "\n",
    "There's a fundamental problem with \"local hidden variable\" theories, though, which is that the correlation between the particles is set up at the time of their creation and cannot be changed at one during the wave function collapse of the other (at least, not without faster-than-light communication, which is what Einstein wanted to avoid in the first place). Now, consider a measurement of the particle spin along an axis $z'$ that is, say, 1 degree offset from $z$. A particle in state $|\\uparrow\\rangle$ will usually be measured to have spin up along this new axis, but _sometimes_ it will be spin down, because $z'$ and $z$ are not the same axis. We can ask how often one particle will be measured as spin down along the original axis $z$ and how often one will be measured up along the new axis $z'$. It was [proved by John Bell](https://journals.aps.org/ppf/abstract/10.1103/PhysicsPhysiqueFizika.1.195) that local hidden variable theories predicted a different (and smaller) maximal correlation rate than the Copenhagen interpretation (hence the term _Bell inequality_). Variations of these have been tested experimentally, and in fact experimental observations agree with Copenhagen and _not_ with local hidden variable theories. The spooky action-at-a-distance is real, and two particles can share an entangled wave function that in principle could span the entire universe.\n",
    "\n",
    "![EPR image](images/epr.png)\n",
    "\n",
    "### The resolution of the EPR paradox\n",
    "The EPR paradox isn't really a paradox as long as you accept that there are certain questions you can't ask coherently (as often comes up in quantum mechanics). In the Copenhagen interpretation, for the state $\\frac{1}{\\sqrt{2}}(|\\uparrow\\downarrow\\rangle + |\\downarrow\\uparrow\\rangle)$, the first particle you measure is spin up or spin down, but you have no control over that whatsoever - you get 50% probabilities for the two options. You immediately know what the other particle's wave function is, at that point, but _you cannot communicate any information this way_: since you didn't get to choose which state you observed - quantum mechanics did - you cannot send an instantaneous signal from the Earth to Mars.\n",
    "\n",
    "This still leaves the question of how exactly the \"wavefunction collapse\" happens. Is it instantaneous everywhere in the universe? What about relativity's statement that \"simultaneity\" doesn't make sense, that different reference frames can see such events in different order, thus reversing which measurement collapsed the wave function? Post-Copenhagen interpretations answer this by punting on the \"collapse\" question, instead just saying that the observations are such that everything is _consistent_. In this sense \"which measurement caused the collapse\" is not a relevant question, since the important (and measurable) thing is that both particles have opposite spins and will always be measured to have such.\n",
    "\n",
    "### Quantum Key Distribution\n",
    "\n",
    "Now, even though we can't transmit information through EPR effects, we _can_ use it to establish a common information base between two distant observers. This turns out to potentially be very useful for cryptography.\n",
    "\n",
    "One of the main challenges in keeping communications secure is establishing a common _secret key_ between two people without the possibility of interception. This secret key is used to encrypt a message, and once encrypted you need to know the same key to decrypt it. Once the key is established, you can encrypt your messages, but how do you get a key that only the two of you share? You can't just send the key over an open channel, since anyone could be listening in. The standard solution is _public key cryptography_, which uses clever algorithms to allow your browser to generate a random number for the key and encrypt it in such a way that only the server finds it easy to decrypt it. However these algorithms rely on the fact that certain mathematical problems are difficult to solve without extra information (e.g. factoring large numbers is much easier if people give you some of the factors). Sufficient computing effort by interested parties, or possible future developments in quantum computing, may make it much easier to solve these problems without the secrets, which would _break_ those algorithms and make it impossible to exchange the secret keys.\n",
    "\n",
    "![Diagram of SSL/TLS](images/tls.png)\n",
    "\n",
    "Entanglement can be used for _quantum key distribution_, which generates a random key from entangled particles shared between parties (generally photons, not spin-1/2 particles, but the idea is the same). The key isn't created until the photon spins are measured. The neat thing is that anyone trying to intercept the entangled particles collapses the wave function, _but cannot generate a new photon with the same entanglement_, which means that interception causes random disagreements in what the two people trying to generate a shared key think the key should be. By comparing randomly-chosen bits, they can look for a high error rate and either detect a problem or reassure themselves that they are fine. As this method doesn't involve any math problems, faster computers do not affect this method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Computation\n",
    "\n",
    "Quantum computation is a very hot area of research right now. We won't try to go into it in any great detail, but hopefully give a flavor of what people are hoping to achieve in this field.\n",
    "\n",
    "Any computer logic is, at the hardware level, abstractable into what we call _gates_, which act on information. In normal computers this information is binary numbers, and each 0 or 1 is a _bit_. A gate could, for example, reverse a single one of these numbers (a _bit_): if you input a 0, the output is a 1, and vice versa. This gate is called a NOT gate. In classical computation we can have gates like the AND gate, whose output is 1 if and only if all inputs are 1, or an XOR (exclusive OR) gate, which takes two inputs and returns 1 if and only if exactly one of the inputs is 1. A computation can be expressed as a series of gates acting on input bits.\n",
    "\n",
    "Quantum computation takes advantage of several facts of the quantum regime: \n",
    "* we can create _superpositions_ of states: so the basic unit of information is now a \"_qubit_\" instead of a bit, and instead of just being 1 or 0, a qubit could be, say, $\\frac{1}{\\sqrt{2}}(|1\\rangle + i|0\\rangle)$;\n",
    "* we can _entangle_ multiple qubits, creating states like $\\frac{1}{\\sqrt{2}}(|10\\rangle + |01\\rangle)$ (each position in $|10\\rangle$ corresponds to a different qubit). \n",
    "* we can define _quantum gates_ which evolve the qubits using Schr&ouml;dinger's equation: quantum gates preserve the superpositions and entanglements. It can be shown that we can define quantum gates to carry out any desired logic.\n",
    "The term \"qubit\" is used to refer both to the abstract quantum analog of a bit and to the physical hardware that stores such a state and the ability to manipulate it.\n",
    "\n",
    "Suppose we have two qubits and create the superposition $\\frac{1}{2}(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle)$. Because quantum gates preserve superpositions and entanglements, any computation defined by a set of quantum gates _will operate on all possible classical inputs at once_. Now the problem is that we will wind up with a superposition of _all the answers_, so getting the information you actually want could be tricky. In the end we can only read out the probability that the qubits are found in some states - we need to collapse the wave function - so what you actually do is run the quantum algorithm many times and look at the observed probabilities of the collapsed qubit states at the end. You also need to engineer a method to interpret what those probabilities mean.\n",
    "\n",
    "In practice quantum computers are very sensitive devices and qubit operations are not as precise as digital logic, so there is some \"error\" introduced in every step of the calculation. For example, a rotation by 90 degrees usually requires application of a signal for a very specific length of time, and any error in the timing will result in a rotation by slightly too large or too small an angle, which means the resulting state is not exactly what the algorithm requires.  (There is a separate problem that it's impossible to fully separate the qubits from the surrounding environment, and so random changes to the state can creep in that way.) \n",
    "\n",
    "One interesting wrinkle in quantum gate design is that for a quantum computer to be useful it cannot _destroy information_. Most simple classical gates do, in fact, destroy information: with an AND gate, for example, if the output is zero, we cannot know if all the inputs were 0, or if some (but not all) of the inputs were 1. There is a class of gates preserve information (and are therefore their computations are _reversible_), and these can be given quantum gate analogs. So instead of XOR or AND gates, which may be familiar to you, we have CNOT and Toffoli gates. There are also quantum gates that are used to prepare superpositions (such as the _Hadamard gate_).\n",
    "\n",
    "The most famous quantum algorithm is probably _Shor's algorithm_, which finds the prime factors of large numbers (though so far it's only gotten up to two-digit numbers). With enough qubits, a quantum computer would factor large numbers much faster than a classical computer; since the difficulty of this problem lies behind a lot of public key cryptography, large-scale quantum computers would threaten the security of current cryptosystems. (However there are proposed public key cryptography methods that are resistant to quantum computing, as far as we know.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running on a Quantum Computer\n",
    "\n",
    "You too can give quantum computing a try. [IBM provides access and tutorials](https://quantum-computing.ibm.com/) for some small-scale systems. As an example of what you can do, I've provided an example of a [Bell inequality experiment](https://quantum-computing.ibm.com/composer/files/new?initial=N4IgdghgtgpiBcIBCMA2qAEBJMMCOArhKgJYAuAniADQh4QDOUCIA8gAoCiAcgIoCCAZQCyGAEwA6AAwBuADpgSYAMaoCAExgY5dNCQBGARglLlO%2BWAV4ATjADmGPAG0xAXQvLbD5S-cKFtgwwZI5OUn5ggcGhhhEAHqHhFgnOsRYAFokRyilhrtSpEdYUABQADiQA9AAsAJQxEbCMBLZZGAC0AHwYPkkKTQwtWoUd3T5pNCCaDJ4kZWQkAPZgLCAAvkA).\n",
    "\n",
    "![Bell inequality quantum circuit](images/bell_circuit_explanation.png)\n",
    "\n",
    "The image above shows a series of quantum gates acting on two qubits. They prepare the correlated state $\\frac{1}{\\sqrt{2}}(|10\\rangle - |01\\rangle)$ and perform a Bell-like test where the state of the two qubits is measured, with one measurement axis offset from the other by 45 degrees. We can define the value\n",
    "$$ C = \\frac{N_\\mathrm{same} - N_\\mathrm{different}}{N_\\mathrm{same} + N_\\mathrm{different}} $$\n",
    "as a measure of the correlation of the measurements of the two detectors over a series of trials; if the detectors read the same value then we count the attempt as $N_\\mathrm{same}$, else we count it as $N_\\mathrm{different}$. $C$ can vary from $-1$ (perfectly anticorrelated) to $1$ (perfectly correlated) - if the two detectors are set to measure in the same direction, for the special entangled state above, we expect them to always read opposite values (i.e. $C=-1$) and for the 45 degree offset quantum mechanics predicts $C = -1/\\sqrt{2} = -0.707$, while a hidden variable theory can only predict $C$ of $-0.5$ or higher.\n",
    "\n",
    "An actual run of 2048 \"shots\" of the circuit gives the following results:\n",
    "\n",
    "![Bell inquality run result](images/bell_circuit_result.png)\n",
    "\n",
    "This gives\n",
    "$$ C = \\frac{208+195-873-772}{208+195+873+772} = -0.606$$\n",
    "which is much more negative than the hidden variable result allows (though it is not quite the perfect theoretical prediction of quantum mechanics, due to quantum computation errors of a few percent in this circuit).\n",
    "\n",
    "To illustrate quantum error, we can look at 1024 shots where the two detectors should actually be reading out in the same direction. In this case we should always get either $01$ or $10$, never $00$ or $11$, and yet we do get those states sometimes:\n",
    "\n",
    "![Bell inquality run result](images/bell_circuit_errors.png)\n",
    "\n",
    "Controlling quantum errors is one of the key technological challenges to be overcome on the way to realistic quantum computation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}