awards/teach_me_quantum_2018/basic_intro2qc/QuantumComputingIntroduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/cat.png\" width=\"200 px\" align=\"right\"><img src=\"images/qiskit.png\" width=\"140 px\" align=\"right\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Quantum Computing with QISKit - a pratical guide\n",
    "#### How to use www.qiskit.org :: An open source quantum computing framework for the development of quantum experiments and applications.\n",
    "\n",
    "### Download the [slides](Slides4Lecture.pdf) that go with this course!\n",
    "--- "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Contributors:\n",
    "Carla Silva, Vanda Azevedo, Diogo Fernandes, and Inês Dutra from Department of Computer Science, University of Porto, Portugal.\n",
    "\n",
    "### *Abstract*\n",
    "\n",
    "*Quantum computing is computing using quantum-mechanical phenomena, unlike binary digital electronic computers based on transistors. This notebook, provides an introduction to the fundamental notions of quantum mechanics and computer science techniques of the field of quantum computation and quantum information. We detail concepts of quantum mechanics on a computational basis and showcase examples using QISKit.*\n",
    "\n",
    "*Note: this notebook was run on 11/15/2018 at 23:15 p.m. (WET)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Concepts\n",
    "- What is a qubit\n",
    "- What is bra-ket notation\n",
    "- What is a superposition\n",
    "- What is a entanglement\n",
    "- What is a bloch sphere\n",
    "- Measurement\n",
    "- Classical vs quantum\n",
    "- How do quantum algorithms work\n",
    "- Quantum gates\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a qubit?\n",
    "In quantum computing, a qbit or qubit or quantum bit is a unit of quantum information. In a quantum computer the basic memory units are qubits, analogously to the bits on a classical computer. A classical bit can take two distinct values, 0 or 1 at a given time. In contrast, a qubit state can be a combination of 0 and 1, called superposition where the qubit is in both basic states (0 and 1) at the same time. A qubit is a quantum system in which the Boolean states 0 and 1 are represented by a pair of normalised and mutually orthogonal quantum states. The two states form a computational basis and any other (pure) state of the qubit can be written as a linear combination,\n",
    "$$|\\psi\\rangle = \\alpha|0\\rangle + \\beta |1\\rangle$$\n",
    "\n",
    "where $\\alpha$ and $\\beta$ are probability amplitudes and can be complex numbers. In a measurement the probability of the bit being in $|0\\rangle$ is $|\\alpha|^2$ and $|1\\rangle$ is $|\\beta|^2$,\n",
    "$$\n",
    "|\\psi\\rangle =  \n",
    "\\begin{pmatrix}\n",
    "\\alpha \\\\\n",
    "\\beta\n",
    "\\end{pmatrix}.\n",
    "$$\n",
    "\n",
    "Two real numbers can describe a single qubit quantum state, since global phase is undetectable and conservation probability $|\\alpha|^2+ |\\beta|^2 = 1$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is bra-ket notation?\n",
    "In quantum mechanics, bra-ket notation is a standard notation for representing quantum states. In order to calculate the scalar product of vectors, the notation uses angle brackets $\\langle$ $\\rangle$, and a vertical bar |. The scalar product is then $\\langle\\phi|\\psi\\rangle$ where the right part is the \"psi ket\" (a column vector) and the left part is the bra - the Hermitian transpose of the ket (a row vector). Bra-ket notation was introduced in 1939 by Paul Dirac and is also known as the Dirac notation.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a superposition?\n",
    "Superposition allows the qubit to be in both states at the same time, and it can be defined as a weighted combination between the basic states 0 and 1. Superposition occurs when any two (or more) quantum states are added, becoming superposed, resulting in a new quantum state - i.e. in 0 and 1 simultaneously, a linear combination of the two classical states.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a entanglement?\n",
    "An important difference between a qubit and a classical bit is that multiple qubits can exhibit quantum entanglement. It occurs when pairs or more than two particles are generated or interact in a way that the quantum state of each particle can't be described independently of the state of the other(s).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a bloch sphere?\n",
    "We can describe the states of the qubit by $|\\psi\\rangle = \\cos(\\theta/2)|0\\rangle + \\sin(\\theta/2)e^{i\\phi}|1\\rangle$\n",
    "where $0\\leq \\phi < 2\\pi$, and $0\\leq \\theta \\leq \\pi$. Qubit states ($\\mathbb{C}^2$) corresponde to the points on the surface of a unit sphere ($\\mathbb{R}^3$).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/bloch_sphere.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Measurement\n",
    "The system is deterministic until measurement. Afterwards, measurement provide only one state of the superposed states. The only one state become the new state and interferes with computational procedures. This state, is determined with some probability <= 1, implying  uncertainty in the result states and cannot be copied (\"cloned\"). Also, environmental interference may cause a measurement-like state collapse (decoherence).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classical vs quantum\n",
    "- Classical Logic Circuits, are governed by classical physics, where signal states are simple bit vectors, e.g. 11000101, operations are based in Boolean algebra, we can copy and measure signals freely, and we have the universal gate types, e.g. NAND, (AND, OR, NOT), (AND, NOT), etc.\n",
    "- Quantum Logic Circuits, are governed by quantum mechanics, where signal states are vectors interpreted as a superposition of binary \"qubit\" vectors, operations are defined by linear algebra in the Hilbert space, represented by unitary matrices with complex elements, there are restrictions on copying and measuring signals, and we have many unitary operations and gates.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How do quantum algorithms work?\n",
    "Quantum algorithms work by applying quantum operations, called quantum logical gates, on qubits. Similar to instructions in a classical program. A quantum algorithm using gates is then a quantum circuit.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quantum gates\n",
    "Quantum gates/operations are represented as matrices which act on a qubit represented by a $2\\times 2$ unitary matrix $U$, in case of single qubit gates. The operation is by multiplying the matrix representing the gate with the vector that represents the quantum state.\n",
    "\n",
    "$$|\\psi'\\rangle = U|\\psi\\rangle$$\n",
    "\n",
    "Here are the 1-qubit gates:\n",
    "$$\\sigma_x=\\left(\\begin{array}{cc}0\\quad1\\\\1\\quad0\\end{array}\\right)$$\n",
    "\n",
    "$$\\sigma_y=\\left(\\begin{array}{cc}0\\quad-i\\\\i\\quad0\\end{array}\\right)$$\n",
    "\n",
    "$$\\sigma_h=\\left(\\begin{array}{cc}1\\quad0\\\\0\\quad-1\\end{array}\\right)$$\n",
    "\n",
    "$$H=\\left(\\begin{array}{cc}\\frac{1}{\\sqrt{2}}\\quad\\frac{1}{\\sqrt{2}}\\\\\\frac{1}{\\sqrt{2}}\\quad-\\frac{1}{\\sqrt{2}}\\end{array}\\right)$$\n",
    "\n",
    "The 2-qubit gates are $4\\times 4$, and 3-qubit gates $8\\times 8$ matrices. An overview of the single and multiple qubit gates is described below, along with the matrix and circuit representation of each gate.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preliminaries\n",
    "- IBM Q Experience device information\n",
    "- What is QISKit\n",
    "- Install QISKit using PIP Install Command\n",
    "- Single-Qubit Gates\n",
    "- Two-Qubit Gates\n",
    "- Three-Qubit Gates\n",
    "- Hello Quantum World program\n",
    "- Quantum (not)Smiley program\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### IBM Q Experience device information\n",
    "IBM Q devices are named after IBM office locations around the globe.\n",
    "- Client: IBM Q 20 Tokyo (20 qubits)\n",
    "- Public devices: IBM Q 14 Melbourne (14 qubits), IBM Q 5 Tenerife (5 qubits) and IBM Q 5 Yorktown (5 qubits)\n",
    "- Simulators: IBM Q QASM 32 Q Simulator (32 qubits)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- display_name: IBM Q 5 Yorktown | backend_name: ibmqx2 | description: the connectivity is provided by two coplanar waveguide (CPW) resonators with resonances around 6.6 GHz (coupling Q2, Q3 and Q4) and 7.0 GHz (coupling Q0, Q1 and Q2). Each qubit has a dedicated CPW for control and readout (labeled as R). Chip layout and connections:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/yorktown.png\" width=\"300 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/yorktown-connections.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- display_name: IBM Q 16 Melbourne | backend_name: ibmq_16_melbourne | description: the connectivity on the device is provided by total 22 coplanar waveguide (CPW) \"bus\" resonators, each of which connects two qubits. Three different resonant frequencies are used for the bus resonators: 6.25 GHz, 6.45 GHz, and 6.65 GHz. Chip layout and connections:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/melbourne.png\" width=\"300 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/melbourne-connections.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To take full advantage of the connections of each different type of chip, research is being done in order to find the best coupling map using techniques and algorithms such as the Quantum Tabu Search to obtain a quantum combinatorial optimisation, suggesting that an entanglement-metaheurisc can display optimal solutions.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/tabuSearch.png\" width=\"450 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm main steps can be briefly described by, a) generating the neighbors, b) evaluating each neighbor and c) getting the neighbor with maximum evaluation. The algorithm stops at any iteration where there are no feasible moves into the local neighborhood of the current solution.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is QISKit?\n",
    "QISKit is a software development kit (SDK) comprising of Python-based software libraries used to create quantum computing programs, compile, and execute them on one of the real quantum processors backends and simulators available in the IBM cloud.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/qiskit.org.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### What is Terra?\n",
    "Qiskit Terra provides the foundational roots for our software stack. Within Terra is a set of tools for composing quantum programs at the level of circuits and pulses, optimizing them for the constraints of a particular physical quantum processor, and managing the batched execution of experiments on remote-access backends.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/terra.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### What is Aqua?\n",
    "Qiskit Aqua contains a library of cross-domain quantum algorithms upon which applications for near-term quantum computing can be built. Aqua is designed to be extensible, and employs a pluggable framework where quantum algorithms can easily be added. It currently allows the user to experiment on chemistry, AI, optimization and finance applications for near-term quantum computers.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/aqua.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Install Python PIP\n",
    "Execute the following command to install QISKit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pip install qiskit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Useful packages for the next gates experiments\n",
    "import numpy as np\n",
    "from qiskit import QuantumCircuit, QuantumRegister\n",
    "from qiskit import execute\n",
    "from qiskit.tools.visualization import circuit_drawer\n",
    "from qiskit import Aer\n",
    "backend = Aer.get_backend('unitary_simulator')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Single-Qubit Gates\n",
    "\n",
    "- u gates\n",
    "- Identity gate\n",
    "- Pauli gates\n",
    "- Cliffords gates\n",
    "- $C3$ gates\n",
    "- Standard rotation gates \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[ 0.+0.j  1.-0.j]\n",
       " [ 1.+0.j -0.+0.j]]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Pauli X : bit-flip gate\n",
    "q = QuantumRegister(1)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.x(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateX.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateX.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[ 0.+0.j -0.-1.j]\n",
       " [ 0.+1.j -0.+0.j]]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Pauli Y : bit and phase-flip gate\n",
    "q = QuantumRegister(1)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.y(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateY.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateY.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[ 1.+0.j  0.+0.j]\n",
       " [ 0.+0.j -1.+0.j]]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Pauli Z : phase-flip gate\n",
    "q = QuantumRegister(1)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.z(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateZ.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateZ.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[ 0.707+0.j  0.707-0.j]\n",
       " [ 0.707+0.j -0.707+0.j]]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Clifford Hadamard gate\n",
    "q = QuantumRegister(1)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.h(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateH.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateH.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1.+0.j 0.+0.j]\n",
       " [0.+0.j 0.+1.j]]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Clifford S gate\n",
    "q = QuantumRegister(1)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.s(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateS.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateS.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1.   +0.j    0.   +0.j   ]\n",
       " [0.   +0.j    0.707+0.707j]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Clifford T gate\n",
    "q = QuantumRegister(1)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.t(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateT.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateT.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Two-Qubit Gates\n",
    "\n",
    "- controlled Pauli gates\n",
    "- controlled Hadamard gate\n",
    "- controlled rotation gates\n",
    "- controlled phase gate\n",
    "- controlled u3 gate\n",
    "- swap gate\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1.+0.j 0.+0.j 0.+0.j 0.+0.j]\n",
       " [0.+0.j 0.+0.j 0.+0.j 1.+0.j]\n",
       " [0.+0.j 0.+0.j 1.+0.j 0.+0.j]\n",
       " [0.+0.j 1.+0.j 0.+0.j 0.+0.j]]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Pauli Controlled-X (or, controlled-NOT) gate\n",
    "q = QuantumRegister(2)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.cx(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateCX.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateCX.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[ 1.-0.j  0.+0.j  0.+0.j  0.+0.j]\n",
       " [ 0.+0.j  1.-0.j  0.+0.j -0.-0.j]\n",
       " [ 0.+0.j  0.+0.j  1.-0.j  0.+0.j]\n",
       " [ 0.+0.j -0.+0.j  0.+0.j -1.+0.j]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Pauli Controlled Z (or, controlled Phase) gate\n",
    "q = QuantumRegister(2)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.cz(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateCZ.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateCZ.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1.+0.j 0.+0.j 0.+0.j 0.+0.j]\n",
       " [0.+0.j 0.+0.j 1.+0.j 0.+0.j]\n",
       " [0.+0.j 1.+0.j 0.+0.j 0.+0.j]\n",
       " [0.+0.j 0.+0.j 0.+0.j 1.+0.j]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# SWAP gate\n",
    "q = QuantumRegister(2)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.swap(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateSWAP.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateSWAP.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Three-Qubit Gates\n",
    "\n",
    "- Toffoli gate \n",
    "- Fredkin gate\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[ 1.-0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j]\n",
       " [ 0.+0.j  1.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j]\n",
       " [ 0.+0.j  0.+0.j  1.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j]\n",
       " [ 0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  1.-0.j]\n",
       " [ 0.+0.j  0.+0.j  0.+0.j  0.+0.j  1.-0.j  0.+0.j  0.+0.j  0.+0.j]\n",
       " [ 0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  1.-0.j  0.+0.j  0.+0.j]\n",
       " [ 0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  0.+0.j  1.-0.j  0.+0.j]\n",
       " [ 0.+0.j  0.+0.j  0.+0.j  1.-0.j  0.+0.j  0.+0.j  0.+0.j -0.+0.j]]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Toffoli gate (ccx gate)\n",
    "q = QuantumRegister(3)\n",
    "qc = QuantumCircuit(q)\n",
    "qc.ccx(q)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"GateCCX.png\", \"PNG\")\n",
    "job = execute(qc, backend)\n",
    "print(np.round(job.result().get_data(qc)['unitary'], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/GateCCX.png\" width=\"200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hello Quantum World program\n",
    "Create and save a \"Hello Quantum World\" with the following code in a file such as quantumWorld.py:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import ClassicalRegister, QuantumRegister\n",
    "from qiskit import QuantumCircuit, execute\n",
    "from qiskit.tools.visualization import plot_histogram, circuit_drawer\n",
    "# Create a Quantum Register called \"qr\" with 2 qubits.\n",
    "qr = QuantumRegister(2)\n",
    "# Create a Classical Register called \"cr\" with 2 bits.\n",
    "cr = ClassicalRegister(2)\n",
    "# Create a Quantum Circuit called \"qc\" with qr and cr.\n",
    "qc = QuantumCircuit(qr, cr)\n",
    "# Add the H gate in the Qubit 1, putting this qubit in superposition.\n",
    "qc.h(qr[1])\n",
    "# Add the CX gate on control qubit 1 and target qubit 0, putting the qubits in a Bell state i.e entanglement.\n",
    "qc.cx(qr[1], qr[0])\n",
    "# Add a Measure gate to see the state.\n",
    "qc.measure(qr, cr)\n",
    "# Compile and execute the quantum program in the local simulator.\n",
    "job_sim = execute(qc, \"qasm_simulator\")\n",
    "stats_sim = job_sim.result().get_counts()\n",
    "# Plot and print results.\n",
    "plot_histogram(stats_sim)\n",
    "print(stats_sim)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"circuit.png\", \"PNG\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/qwhist.png\" width=\"500 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "{'00': 512, '11': 512}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/qwcircuit.png\" width=\"300 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quantum (not)Smiley program\n",
    "Create and save a file such as quantumSmiley.py:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import ClassicalRegister, QuantumRegister\n",
    "from qiskit import QuantumCircuit, execute\n",
    "from qiskit.tools.visualization import plot_histogram\n",
    "import matplotlib.pyplot as plt\n",
    "# 3 bitStrings, one for each symbol : )( \n",
    "#\":\" 00111010 \"(\" 00101000 \")\" 00101001\n",
    "# Create a Quantum Register called \"qr\" with 16 qubits.\n",
    "qr = QuantumRegister(16)\n",
    "# Create a Classical Register called \"cr\" with 16 bits.\n",
    "cr = ClassicalRegister(16)\n",
    "# Create a Quantum Circuit called \"qc\" with qr and cr.\n",
    "qc = QuantumCircuit(qr, cr)\n",
    "# Add the H gate in the 0 Qubit, putting the qubit in superposition.\n",
    "qc.h(qr[0])\n",
    "qc.x(qr[3])\n",
    "qc.x(qr[5])\n",
    "qc.x(qr[9])\n",
    "qc.x(qr[11])\n",
    "qc.x(qr[12])\n",
    "qc.x(qr[13])\n",
    "for j in range(16):\n",
    "    qc.measure(qr[j], cr[j])\n",
    "# Compile and execute the quantum program in the local simulator.\n",
    "shots_sim = 128\n",
    "job_sim = execute(qc, \"qasm_simulator\", shots=shots_sim)\n",
    "stats_sim = job_sim.result().get_counts()\n",
    "# Plot and print results.\n",
    "plot_histogram(stats_sim)\n",
    "print(stats_sim)\n",
    "def plotSmiley (stats, shots):\n",
    "    for bitString in stats:\n",
    "        char = chr(int(bitString[0:8],2)) # 8 bits (left), convert to an ASCII character.\n",
    "        char += chr(int(bitString[8:16],2)) # 8 bits (right), add it to the previous character.\n",
    "        prob = stats[bitString]/shots # Fraction of shots the result occurred\n",
    "        plt.annotate(char, (0.5,0.5), va=\"center\", ha=\"center\", color = (0,0,0,prob), size = 300) # Create plot.\n",
    "    plt.axis(\"off\")\n",
    "    plt.show()\n",
    "plotSmiley(stats_sim, shots_sim)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/Figure_2.png\" width=\"500 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "{'0011101000101000': 64, '0011101000101001': 64}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/Figure_3.png\" width=\"500 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arithmetics\n",
    "- Assignment\n",
    "- Sum (Binary)\n",
    "- Sum (Ripple-carry adder)\n",
    "- Sum (Quantum Fourier Transform)\n",
    "- Average\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Assignment\n",
    "The registers are made of qubits, therefore we cannot directly assign values from the bit strings to a quantum register. As such, when we create a new quantum register, all of its qubits start in the $|0\\rangle$ state. By using the quantum X gate, we can flip the qubits that give us the $|1\\rangle$ state.\n",
    "Create a file such as assignment.py:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import ClassicalRegister, QuantumRegister\n",
    "from qiskit import QuantumCircuit, execute\n",
    "# E.g. number 21 in binary.\n",
    "number = \"10101\"\n",
    "# Initializing the registers.\n",
    "# Create a Quantum Register called \"qr\" with length number qubits.\n",
    "qr = QuantumRegister(len(str(number)))\n",
    "# Create a Classical Register called \"cr\" with length number bits.\n",
    "cr = ClassicalRegister(len(str(number)))\n",
    "# Create a Quantum Circuit called \"qc\" with qr and cr.\n",
    "qc = QuantumCircuit(qr, cr)\n",
    "# Setting up the registers using the value inputted.\n",
    "for i in range(len(str(number))):\n",
    "    if number[i] == \"1\":\n",
    "       qc.x(qr[len(str(number)) - (i+1)]) #Flip the qubit from 0 to 1.\n",
    "#Measure qubits and store results in classical register cr.\n",
    "for i in range(len(str(number))):\n",
    "    qc.measure(qr[i], cr[i])\n",
    "# Compile and execute the quantum program in the local simulator.\n",
    "job_sim = execute(qc, \"qasm_simulator\")\n",
    "stats_sim = job_sim.result().get_counts()\n",
    "# Print number.\n",
    "print(stats_sim)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "{'10101': 1024} #21"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sum (Binary)\n",
    "Create a file such as sumBinary.py:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Boolean binary string adder.\n",
    "def rjust_lenght(s1, s2, fill='0'):\n",
    "    l1, l2 = len(s1), len(s2)\n",
    "    if l1 > l2:\n",
    "        s2 = s2.rjust(l1, fill)\n",
    "    elif l2 > l1:\n",
    "        s1 = s1.rjust(l2, fill)\n",
    "    return (s1, s2)\n",
    "def get_input():\n",
    "    bits_a = input('input your first binary string ')\n",
    "    bits_b = input('input your second binary string ')\n",
    "    return rjust_lenght(bits_a, bits_b)\n",
    "def xor(bit_a, bit_b):\n",
    "    A1 = bit_a and (not bit_b)\n",
    "    A2 = (not bit_a) and bit_b\n",
    "    return int(A1 or A2)\n",
    "def half_adder(bit_a, bit_b):\n",
    "    return (xor(bit_a, bit_b), bit_a and bit_b)\n",
    "def full_adder(bit_a, bit_b, carry=0):\n",
    "    sum1, carry1 = half_adder(bit_a, bit_b)\n",
    "    sum2, carry2 = half_adder(sum1, carry)\n",
    "    return (sum2, carry1 or carry2)\n",
    "def binary_string_adder(bits_a, bits_b):\n",
    "    carry = 0\n",
    "    result = ''\n",
    "    for i in range(len(bits_a)-1 , -1, -1):\n",
    "        summ, carry = full_adder(int(bits_a[i]), int(bits_b[i]), carry)\n",
    "        result += str(summ)\n",
    "    result += str(carry)\n",
    "    return result[::-1]\n",
    "def main():\n",
    "    bits_a, bits_b = get_input()\n",
    "    print('1st string of bits is : {}, ({})'.format(bits_a, int(bits_a, 2)))\n",
    "    print('2nd string of bits is : {}, ({})'.format(bits_b, int(bits_b, 2)))\n",
    "    result = binary_string_adder(bits_a, bits_b)\n",
    "    print('summarized is         : {}, ({})'.format(result, int(result, 2)))\n",
    "if __name__ == '__main__':\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "input your first binary string 101<br>\n",
    "input your second binary string 1011<br>\n",
    "1st string of bits is : 0101, (5)<br>\n",
    "2nd string of bits is : 1011, (11)<br>\n",
    "summarized is         : 10000, (16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sum (Ripple-carry adder)\n",
    "This implementation prepares a = 1, b = 15 and computes the sum into b with an output carry cout[0] by using a quantum ripple-carry adder approach.\n",
    "Create a file such as sum.py:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import ClassicalRegister, QuantumRegister\n",
    "from qiskit import QuantumCircuit, execute\n",
    "from qiskit.tools.visualization import circuit_drawer\n",
    "# Initializing the registers.\n",
    "# Create a Quantum Registers.\n",
    "cin = QuantumRegister(1)\n",
    "a = QuantumRegister(4)\n",
    "b = QuantumRegister(4)\n",
    "cout = QuantumRegister(1)\n",
    "# Create a Classical Registers.\n",
    "ans = ClassicalRegister(5)\n",
    "# Create a Quantum Circuit called \"qc\".\n",
    "qc = QuantumCircuit(cin, a, b, cout, ans)\n",
    "# Set input states.\n",
    "x = \"0001\" #1\n",
    "y = \"1111\" #15\n",
    "# Setting up the registers using the value inputted.\n",
    "for i in range(len(str(x))):\n",
    "    if x[i] == \"1\":\n",
    "       qc.x(a[len(str(x)) - (i+1)]) #Flip the qubit from 0 to 1.\n",
    "for i in range(len(str(y))):\n",
    "    if y[i] == \"1\":\n",
    "       qc.x(b[len(str(y)) - (i+1)]) #Flip the qubit from 0 to 1.\n",
    "def majority(circ, a, b, c):\n",
    "  circ.cx(c,b)\n",
    "  circ.cx(c,a)\n",
    "  circ.ccx(a,b,c)\n",
    "def unmaj(circ, a, b, c):\n",
    "  circ.ccx(a,b,c)\n",
    "  circ.cx(c,a)\n",
    "  circ.cx(a,b)\n",
    "# Add a to b, storing result in b\n",
    "majority(qc,cin[0],b[0],a[0])\n",
    "majority(qc,a[0],b[1],a[1])\n",
    "majority(qc,a[1],b[2],a[2])\n",
    "majority(qc,a[2],b[3],a[3])\n",
    "qc.cx(a[3],cout[0])\n",
    "unmaj(qc,a[2],b[3],a[3])\n",
    "unmaj(qc,a[1],b[2],a[2])\n",
    "unmaj(qc,a[0],b[1],a[1])\n",
    "unmaj(qc,cin[0],b[0],a[0])\n",
    "# Measure qubits and store results.\n",
    "for i in range(0, 4):\n",
    "  qc.measure(b[i], ans[i])\n",
    "qc.measure(cout[0], ans[4])\n",
    "# Compile and execute the quantum program in the local simulator.\n",
    "num_shots = 2 # Number of times to repeat measurement.\n",
    "job = execute(qc, \"qasm_simulator\", shots=num_shots)\n",
    "job_stats = job.result().get_counts()\n",
    "# Print result number and circuit.\n",
    "print(job_stats)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"circuitSum.png\", \"PNG\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "{'10000': 2} #16"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/circuitSum.png\" width=\"800 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sum (Quantum Fourier Transform)\n",
    "Method to calculate sum on a quantum computer using the quantum Fourier Transform by applying repeated controlled-U gates.\n",
    "Create a file such as sumQFT.py:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import ClassicalRegister, QuantumRegister\n",
    "from qiskit import QuantumCircuit, execute\n",
    "from qiskit.tools.visualization import circuit_drawer\n",
    "import numpy as np\n",
    "n1 = '10011'\n",
    "# E.g. number 19\n",
    "n2 = '0011101'\n",
    "# E.g. number 29\n",
    "if len(str(n1)) > len(str(n2)):\n",
    "     n = len(str(n1))\n",
    "else:\n",
    "     n = len(str(n2))\n",
    "# Initializing the registers.\n",
    "# Create a Quantum Registers called \"qr1\" and \"qr2\".\n",
    "qr1 = QuantumRegister(n+1)\n",
    "qr2 = QuantumRegister(n+1)\n",
    "# The classical register.\n",
    "cr = ClassicalRegister(n+1)\n",
    "# Create a Quantum Circuit called \"qc\".\n",
    "qc = QuantumCircuit(qr1, qr2, cr)\n",
    "length1 = len(n1)\n",
    "length2 = len(n2)\n",
    "# Set same length.\n",
    "if length2 > length1:\n",
    "    n1,n2 = n2, n1\n",
    "    length2, length1 = length1, length2\n",
    "n2 = (\"0\")*(length1-length2) + n2\n",
    "# Set registers qr1 and qr2 to hold the two numbers.\n",
    "for i in range(len(str(n1))):\n",
    "    if n1[i] == \"1\":\n",
    "      qc.x(qr1[len(str(n1)) - (i+1)])\n",
    "for i in range(len(str(n2))):\n",
    "    if n2[i] == \"1\":\n",
    "       qc.x(qr2[len(str(n2)) - (i+1)])\n",
    "def qft(circ, q1, q2, n):\n",
    "  # n-qubit QFT on q in circ.\n",
    "  for i in range(0, n+1):\n",
    "          qc.cu1(np.math.pi/float(2**(i)), q2[n-i], q1[n])\n",
    "def invqft(circ, q, n):\n",
    "    # Performs the inverse quantum Fourier transform.\n",
    "    for i in range(0, n):\n",
    "        qc.cu1(-np.math.pi/float(2**(n-i)), q[i], q[n])\n",
    "    qc.h(q[n])\n",
    "def input_state(circ, q, n):\n",
    "    # n-qubit input state for QFT.\n",
    "    qc.h(q[n])\n",
    "    for i in range(0, n):\n",
    "        qc.cu1(np.math.pi/float(2**(i+1)), q[n-(i+1)], q[n])\n",
    "for i in range(0, n+1):\n",
    "  input_state(qc, qr1, n-i)\n",
    "qc.barrier()\n",
    "for i in range(0, n+1):\n",
    "  qft(qc, qr1, qr2, n-i)\n",
    "qc.barrier()\n",
    "for i in range(0, n+1):\n",
    "  invqft(qc, qr1, i)\n",
    "qc.barrier()\n",
    "for i in range(0, n+1):\n",
    "  qc.cx(qr1[i],qr2[i])\n",
    "for i in range(0, n+1):\n",
    "  qc.measure(qr1[i], cr[i])\n",
    "# Compile and execute the quantum program in the local simulator.\n",
    "num_shots = 2 # Number of times to repeat measurement.\n",
    "job = execute(qc, \"qasm_simulator\", shots=num_shots)\n",
    "job_stats = job.result().get_counts()\n",
    "print(job_stats)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"circuitAdderQFT.png\", \"PNG\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "{'00110000': 2} #48"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Average\n",
    "Show that the average value of the observable $$X_1Z_2$$ for a two-qubit system measured in the state $$(|00\\rangle+|11\\rangle)/\\sqrt{2}$$ is zero.\n",
    "In a two-qubit system we represent the kets as vectors, the Pauli matrices and perform the tensor products, and conduct the multiplication.\n",
    "\n",
    "$$|0\\rangle\\equiv\\left(\\begin{array}{c}1\\\\0\\end{array}\\right)\\qquad|1\\rangle\\equiv\\left(\\begin{array}{c}0\\\\1\\end{array}\\right)$$We calculate the tensor product, such as $|01\\rangle$,$$|01\\rangle=|0\\rangle\\otimes|1\\rangle\\equiv\\left(\\begin{array}{c}1\\times\\left(\\begin{array}{c} 0 \\\\ 1 \\end{array}\\right)\\\\ 0\\times \\left(\\begin{array}{c} 0 \\\\ 1 \\end{array}\\right) \\end{array}\\right)=\\left(\\begin{array}{c} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{array}\\right)$$Where $\\langle 01|$ is the Hermitian conjugate of,$$\\langle 01|=\\left(\\begin{array}{cccc} 0 & 1 & 0 & 0 \\end{array}\\right)$$Then similar reasoning for the operators. For example,$$X_1X_2=\\sigma_1\\otimes\\sigma_1=\\left(\\begin{array}{cc} 0\\times \\left(\\begin{array}{cc} 0 & 1 \\\\ 1 & 0 \\end{array}\\right) & 1\\times \\left(\\begin{array}{cc} 0 & 1 \\\\ 1 & 0 \\end{array}\\right) \\\\ 1\\times \\left(\\begin{array}{cc} 0 & 1 \\\\ 1 & 0 \\end{array}\\right) & 0\\times \\left(\\begin{array}{cc} 0 & 1 \\\\ 1 & 0 \\end{array}\\right) \\end{array}\\right)=\\left(\\begin{array}{cccc} 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \\end{array}\\right).$$Finally, we simply multiply it out:$$\\langle 01|X_1X_2|01\\rangle=\\left(\\begin{array}{cccc} 0 & 1 & 0 & 0 \\end{array}\\right)\\left(\\begin{array}{cccc} 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \\end{array}\\right)\\left(\\begin{array}{c} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{array}\\right)=0.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import ClassicalRegister, QuantumRegister\n",
    "from qiskit import QuantumCircuit, execute\n",
    "from qiskit.tools.visualization import circuit_drawer\n",
    "# Initializing the registers.\n",
    "# Create a Quantum Registers.\n",
    "cin = QuantumRegister(1)\n",
    "a = QuantumRegister(2)\n",
    "b = QuantumRegister(2)\n",
    "cout = QuantumRegister(1)\n",
    "# Create a Classical Registers.\n",
    "ans = ClassicalRegister(3)\n",
    "# Create a Quantum Circuit called \"qc\".\n",
    "qc = QuantumCircuit(cin, a, b, cout, ans)\n",
    "# Set input states.\n",
    "x = \"00\" #0\n",
    "y = \"11\" #3\n",
    "# Setting up the registers using the value inputted.\n",
    "for i in range(len(str(x))):\n",
    "    if x[i] == \"1\":\n",
    "       qc.x(a[len(str(x)) - (i+1)]) #Flip the qubit from 0 to 1.\n",
    "for i in range(len(str(y))):\n",
    "    if y[i] == \"1\":\n",
    "       qc.x(b[len(str(y)) - (i+1)]) #Flip the qubit from 0 to 1.\n",
    "# Add a to b, storing result in b\n",
    "majority(qc,cin[0],b[0],a[0])\n",
    "majority(qc,a[0],b[1],a[1])\n",
    "qc.cx(a[1],cout[0])\n",
    "unmaj(qc,a[0],b[1],a[1])\n",
    "unmaj(qc,cin[0],b[0],a[0])\n",
    "qc.cx(b[1],b[0])\n",
    "qc.x(b[1])\n",
    "# Measure qubits and store results.\n",
    "for i in range(0, 1):\n",
    "  qc.measure(b[i], ans[i])\n",
    "qc.measure(cout[0], ans[1])\n",
    "# Compile and execute the quantum program in the local simulator.\n",
    "num_shots = 2 # Number of times to repeat measurement.\n",
    "job = execute(qc, \"qasm_simulator\", shots=num_shots)\n",
    "job_stats = job.result().get_counts()\n",
    "# Print result number and circuit.\n",
    "print(job_stats)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"circuitAverage.png\", \"PNG\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "{'000': 2} #0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/circuitAverage.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Algorithms\n",
    "- Shor's\n",
    "- Grover's\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shor's\n",
    "Any integer number has a unique decomposition into a product of prime numbers.\n",
    "In 1995 Peter Shor proposed a polynomial-time quantum algorithm for the factoring problem.\n",
    "\n",
    "-> Runs partially on quantum computer. Fourier Transform and Period-finding algorithm.<br>\n",
    "-> Pre- and post-processing on a classical computer: greatest common divisor (quadratic in number of digits of a, b), test of primality (polynomial), prime power test (O(log n)) and continued fraction expansion (polynomial)<br>\n",
    "\n",
    "Worst Case in Quantum : polynomial in log(N)<br>\n",
    "Worst Case in Classical: polynomial in N<br>\n",
    "\n",
    "- Period Finding\n",
    "Given integers N and a, find the smallest positive integer r such that a^r-1 is a multiple of N,\n",
    "where r is the period of a modulo N (smallest positive integer r such that a^r=1 mod N)\n",
    "\n",
    "Example: N=15 and a=7\n",
    "    We want to find the smallest positive integer r such that a^r = 1 mod N\n",
    "    <=> 7^r = 1 mod 15\n",
    "\n",
    "    r=2: 7^2 = 4 mod 15\n",
    "    r=3: 7^3 = 4 * 7 mod 15 = 13 mod 15\n",
    "    r=4: 7^4 = 13 * 7 mod 15 = 1 mod 15\n",
    "    -> r=4 is the period of a modulo N\n",
    "\n",
    "- From factoring to period finding<br>\n",
    "Assume that N has only two distinct prime factors: N = p1 * p2.<br>\n",
    "1) pick an integer a between [2,N-1] and compute greatest common divisor gcd(N,a) using Euclid's Algorithm.<br>\n",
    "2) If gcd(N,a)=p1 or p2 we are done.<br>\n",
    "3) Else repeat the above steps with different random choices of a until r is even.\n",
    "    If r is even and is the smallest integer such that a^r-1 is a multiple of N:<br>\n",
    "    a^r-1=(a^(r/2)-1)*(a^(r/2)+1).<br>\n",
    "    where neither (a^(r/2)-1) nor (a^(r/2)+1) is a multiple of N, but their product is.<br>\n",
    "    We can find p1 and p2 by computing gcd(N, (a^(r/2)-1)) and gcd(N, (a^(r/2)+1)).<br>\n",
    "    If (a^(r/2)+1) is multiple of N we try with a different a.<br><br>\n",
    "At the heart of Shor's Algorithm, Quantum Fourier Transform (QFT), a linear transformation on quantum bits, and the quantum analogue of the discrete Fourier transform.<br>\n",
    "Formally, the QFT is expected to be useful in determining the period r of a function i.e. when f(x)=f(x+r) for all x.<br>\n",
    "The input register for QFT contains n-qubit basis state $|x\\rangle$ which is rewritten as the tensor product of the individual qubits in its binary expansion.<br>\n",
    "In fact, each of those single-qubit operations can be implemented efficiently using a Hadamard gate and controlled phase gates.<br>\n",
    "The first term requires one Hadamard gate and (n-1) controlled phase gates, the next one requires a Hadamard gate and (n-2) controlled phase gate, and each following term requires one fewer controlled phase gate.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/1QFT.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/2QFT.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/3QFT.png\" width=\"600 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Shor's Algorithm<br>\n",
    "Shor's algorithm exploits interference to measure periodicity of arithmetic objects.<br>\n",
    "Suppose we a,N are co-primes, gcd(a,N)=1.<br>\n",
    "Our goal is to compute the smallest positive integer r such that a^r=1 mod N.<br><br>\n",
    "Steps:<br>\n",
    "1. Determine if n is even, prime or a prime power. If so, exit.<br>\n",
    "2. Pick a random integer x < n and calculate gcd(x, n). If this is not 1, then we have obtained a factor of n.<br>\n",
    "3. Quantum algorithm:<br>\n",
    "    Pick q as the smallest power of 2 with n^2 $\\leq$ q < 2 * n^2.<br>\n",
    "    Find period r of x^a mod n.<br>\n",
    "    Measurement gives us a variable c which has the property c $\\approx$ d where d $\\in$ |N.<br>\n",
    "4. Determine d, r via continued fraction expansion algorithm. d, r only determined if gcd(d, r) = 1 (reduced fraction).<br>\n",
    "5. If r is odd, go back to 2.<br>\n",
    "    If x^(r/2) $\\equiv$ −1 mod n go back to 2.<br>\n",
    "    Otherwise the factors p, q = gcd(x^(r/2) $\\pm$ 1, n).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grover's<br>\n",
    "-  Quantum algorithms<br>\n",
    "The current state of quantum algorithms can be divided in two main types of algorithms. On one side we have the algorithms based on \"Shor's quantum Fourier transform\", on which were built some of the most popular known algorithms with a exponencial speedup over their classical counterparts.<br>\n",
    "For example the classic Fast Fourier transform on a runs on O(nlog n) time and the Quantum Fourier transform runs on O(log^2 n).<br>\n",
    "On the other side we have Groover's, which is mainly used on quantum search. This method gives a quadratic speedup to some of the best classical algorithms.<br>\n",
    "Since it is used to search a database if the classical algorithm runs on the worst case O(N), on a groover's search algorithm it can e improved to run on O(sqrt(N))<br>\n",
    "- Quantum Complexity<br>\n",
    "Regarding computational complexity theory, when it comes to quantum computing we have two big correlations that we can compare to the classical computing complexities know as P and NP. One of them is BQP which stands for bounded-error quantum polynomial time which as the name implies belongs to the class of decision problems that can be solved by a quantum computer in polynomial time. We then have QMA, which stands for Quantum Merlin Arthur, and this one is, in an informal way, the set of decision problems for which when the answer is YES, there is a polynomial-size quantum proof (a quantum state) which convinces a polynomial-time quantum verifier of the fact with high probability. Moreover, when the answer is NO, every polynomial-size quantum state is rejected by the verifier with high probability. Both of these can be compared to P and NP because QMA is to BQP as NP is to P.<br>\n",
    "- Groover's Algorithm<br>\n",
    "This algorithm is mainly used to search databases, as told before the time it runs improves quadratically compared to the classical counterparts.<br>\n",
    "What does that mean? Given an array of N elements, and on that array we want to locate a specific and unique element. Given this typical example we can relate to a normal problem we would face on a classical computer, but it would take on average N/2 or in the worst case O(N). This is not how it will work on a quantum computer, because using groover algorithm it is possible to reduce the time to O(sqrt(N)). How does it work?<br>\n",
    " - The Oracle<br>\n",
    "  Firstly we have to encode a list in terms of a function f, this function returns f(x)=0 for all unwanted positions and f(u)=1 for the element we want to locate.<br>\n",
    "  The we define the Oracle to act on the state |x$\\rangle$, this done by the following function: U f|x$\\rangle$ =(-1)^f(x) |x$\\rangle$.<br>\n",
    "  This works because the state of the qbit only changes when we find f(u)=1 resulting in U f|u$\\rangle$ = -|w$\\rangle$ while the rest remains the same.<br>\n",
    " - Amplitude amplification<br>\n",
    "  So far so good but it is still very similar to a normal algorithm, and we cannot guess because it would still take O(N) and if we were to guess, the measure would destroy the super position. Amplitude representation in the image below.<br>\n",
    " So how to initialize the algorithm?<br>\n",
    " 1. Start a uniform superposition |s$\\rangle$ by doing the following |s$\\rangle$=H$\\otimes$n|0$\\rangle$n.<br>\n",
    " 2. We then have to apply the oracle function to Uf|$\\psi$t$\\rangle$=|$\\psi$t'$\\rangle$. This results on the amplitude of the element we are searching for turning negative.<br>\n",
    " 3. We now apply an additional reflection Us about the state |s$\\rangle$.<br>\n",
    " We have then to repeat this process O($\\sqrt{N}$).<br>\n",
    " In this code we have a grover implementation.<br>\n",
    " This code represents a deterministic solution for a SAT problem with 3 clauses and 3 literals that has exactly one true output, the formula has to be on conjunctive normal form(CNF) in order for it to work.<br>\n",
    " This works the following way, imagine all the results the expression could give are in an array, since the expression only has one output that is true, being that the one we want to find, it is possible to apply the algorithm to this problem.<br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/charts.png\" width=\"400 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SAT program\n",
    "Create and save a program with the following code in a file such as sat.py:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from qiskit import ClassicalRegister, QuantumRegister\n",
    "from qiskit import QuantumCircuit, execute\n",
    "from qiskit.tools.visualization import plot_histogram, circuit_drawer\n",
    "n = 3\n",
    "sat_formula = [[1,2,-3],[-1,-2,-3],[1,-2,3]]\n",
    "f_in = QuantumRegister(n)\n",
    "f_out = QuantumRegister(1)\n",
    "aux = QuantumRegister(len(sat_formula)+1)\n",
    "ans = ClassicalRegister(n)\n",
    "qc = QuantumCircuit(f_in, f_out, aux, ans)\n",
    "# Initializes all of the qbits.\n",
    "def input_state(circuit, f_in, f_out, n):\n",
    "  for j in range(n):\n",
    "    circuit.h(f_in[j])\n",
    "  circuit.x(f_out)\n",
    "  circuit.h(f_out)\n",
    "# The back box U function (Oracle).\n",
    "def black_box_u_f(circuit, f_in, f_out, aux, n, sat_formula):\n",
    "  num_claus = len(sat_formula)\n",
    "  for(k,claus) in enumerate(sat_formula):\n",
    "    for literal in claus:\n",
    "      if literal > 0:\n",
    "        circuit.cx(f_in[literal-1],aux[k])\n",
    "      else:\n",
    "        circuit.x(f_in[-literal-1])\n",
    "        circuit.cx(f_in[-literal-1],aux[k])\n",
    "    circuit.ccx(f_in[0],f_in[1],aux[num_claus])\n",
    "    circuit.ccx(f_in[2],aux[num_claus],aux[k])\n",
    "    circuit.ccx(f_in[0],f_in[1],aux[num_claus])\n",
    "    for literal in claus:\n",
    "      if literal < 0:\n",
    "        circuit.x(f_in[-literal-1])\n",
    "  if(num_claus == 1):\n",
    "    circuit.cx(aux[0], f_out[0])\n",
    "  elif(num_claus == 2):\n",
    "    circuit.ccx(aux[0],aux[1],f_out[0])\n",
    "  elif(num_claus == 3):\n",
    "    circuit.ccx(aux[0], aux[1], aux[num_claus])\n",
    "    circuit.ccx(aux[2], aux[num_claus], f_out[0])\n",
    "    circuit.ccx(aux[0], aux[1], aux[num_claus])\n",
    "  else:\n",
    "    raise ValueError('Apenas 3 clausulas pf :)')\n",
    "  for(k,claus) in enumerate(sat_formula):\n",
    "    for literal in claus:\n",
    "      if literal > 0:\n",
    "        circuit.cx(f_in[literal-1],aux[k])\n",
    "      else:\n",
    "        circuit.x(f_in[-literal-1])\n",
    "        circuit.cx(f_in[-literal-1],aux[k])\n",
    "    circuit.ccx(f_in[0], f_in[1], aux[num_claus])\n",
    "    circuit.ccx(f_in[2], aux[num_claus], aux[k])\n",
    "    circuit.ccx(f_in[0], f_in[1], aux[num_claus])\n",
    "    for literal in claus:\n",
    "      if literal < 0:\n",
    "        circuit.x(f_in[-literal-1])\n",
    "# iInverts the qbit that was affected by the Oracle function.\n",
    "def inversion_about_average(circuit,f_in,n):\n",
    "  for j in range(n):\n",
    "    circuit.h(f_in[j])\n",
    "  for j in range(n):\n",
    "    circuit.x(f_in[j])\n",
    "  n_controlled_z(circuit, [f_in[j] for j in range(n-1)], f_in[n-1])\n",
    "  for j in range(n):\n",
    "    circuit.x(f_in[j])\n",
    "  for j in range(n):\n",
    "    circuit.h(f_in[j])\n",
    "def n_controlled_z(circuit,controls,target):\n",
    "  if(len(controls) > 2):\n",
    "    raise ValueError('erro de control')\n",
    "  elif(len(controls) == 1):\n",
    "    circuit.h(target)\n",
    "    circuit.cx(controls[0],target)\n",
    "    circuit.h(target)\n",
    "  elif(len(controls) == 2):\n",
    "    circuit.h(target)\n",
    "    circuit.ccx(controls[0],controls[1],target)\n",
    "    circuit.h(target)\n",
    "input_state(qc,f_in,f_out,n)\n",
    "black_box_u_f(qc,f_in,f_out,aux,n,sat_formula)\n",
    "inversion_about_average(qc,f_in,n)\n",
    "black_box_u_f(qc,f_in,f_out,aux,n,sat_formula)\n",
    "inversion_about_average(qc,f_in,n)\n",
    "for j in range(n):\n",
    "  qc.measure(f_out[0],ans[j])\n",
    "# Compile and execute the quantum program in the local simulator.\n",
    "job_sim = execute(qc, \"qasm_simulator\")\n",
    "stats_sim = job_sim.result().get_counts()\n",
    "# Plot and print results.\n",
    "print(stats_sim)\n",
    "plot_histogram(stats_sim)\n",
    "im = circuit_drawer(qc)\n",
    "im.save(\"circuitGrover.pdf\", \"PDF\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/grover.png\" width=\"400 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/circuitGrover.png\" width=\"1200 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Final notes\n",
    "- Check 'from qiskit import available_backends', useful to know which real backends are available.\n",
    "- Check 'from qiskit.tools.qi.qi import state_fidelity', tool to verify if two states are same or not.\n",
    "- Check 'from qiskit.tools.visualization import...', tools for exceptional visualization charts!\n",
    "- Happy Quantum Coding! And, any help, check the IBM Q Graphical composer :) Compose quantum circuits using drag and drop interface. Save circuits online or as QASM text, and import later. Run circuits on real hardware and simulator."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/qasmeditor.png\" width=\"800 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/Help.png\" width=\"700 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Acknowledgments\n",
    "We acknowledge use of the IBM Q for this work. The views expressed are those of the authors and do not reflect the official policy or position of IBM or the IBM Q team."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "### *References*\n",
    "\n",
    "[1] M. Nielsen, and I. Chuang (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511976667.<br>\n",
    "[2] IBM Research and the IBM QX team (2017). User guide. IBM Q Experience Documentation https://quantumexperience.ng.bluemix.net/qx/tutorial<br>\n",
    "[3] S. Cuccaro, T. Draper, S. Kutin, and D. Moulton. A new quantum ripple-carry addition circuit. arXiv:quant-ph/0410184, 2004.<br>\n",
    "[4] Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. Open quantum assembly language. arXiv:1707.03429, 2017.<br>\n",
    "[5] 5-qubit backend: IBM Q team, \"IBM Q 5 Yorktown backend specification V1.1.0,\" (2018). Retrieved from https://ibm.biz/qiskit-yorktown.<br>\n",
    "[6] 14-qubit backend: IBM Q team, \"IBM Q 14 Melbourne backend specification V1.x.x,\" (2018). Retrieved from https://ibm.biz/qiskit-melbourne.<br>\n",
    "[7] C. Silva, I. Dutra, and M.S. Dahlem (2018). Driven tabu search: a quantum inherent optimisation. arXiv preprint arXiv:1808.08429.<br>\n",
    "[8] L. Ruiz-Perez and J. C. Garcia-Escartin (2014). Quantum arithmetic with the Quantum Fourier Transform. arXiv preprint arXiv:1411.5949.<br>[9] P. Kaye, R. Laflamme, and M. Mosca (2007). An Introduction to Quantum Computing. Oxford Univ. Press.<br>"
   ]
  }
 ],
 "metadata": {
  "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.6.3"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}