Tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Discrete Time Quantum Walks\n",
    "\n",
    "### MIT iQuHACK 2020 | Team \"Quantum Waddle\"\n",
    "\n",
    "This work explores the implementation of discrete-time quantum walks on a 1D and 2D chain as described in [1] using IBM's quantum computing platform. A useful tutorial referenced here can be found at [2].\n",
    "\n",
    "### Contributors\n",
    "Biswaroop Mukherjee, Carsten Robens, Maya Reese, Lamia Ateshian, Yiqi Ni, Enrique Mendez"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Introduction\n",
    "Classical random walks are used widely in graph searching and optimization, with many important applications in route planning, game playing, physics, and finance. This motivates researchers to look at the quantum analogue of a random walk, a quantum walk. \n",
    "\n",
    "A simple random walk example consists of a 1D chain whose nodes are enumerated by integer values and connected to its two adjacent neighbors. A random walker in position $i$ steps to either $i+1$ or $i-1$ depending on the outcome of a coin flip. \n",
    "\n",
    "In the quantum mechanical analogue, we consider evolution of position on a lattice conditioned on the spin state of a spin-1/2 system.\n",
    "\n",
    "<img src=\"figures/random_walk.png\" width=700px>\n",
    "\n",
    "### Motivation\n",
    "One primary motivation is to determine whether quantum computers are faster at solving problems than classical computers.\n",
    "\n",
    "Prior to 2003, exponential speedup was only demonstrated on algorithms that depended on the quantum Fourier transform. It's an interesting question to determine whether there is algorithmic variety in exponential speed up. It turns out that quantum walks can exhibit an exponential speed up[3].\n",
    "\n",
    "In the paper[3] by Childs, *et al.*, they define the graph traversal problem. The idea is that if they implement graphs encoded via *so called* black box functions, they demonstrate that for certain complicated graphs, quantum walks can traverse the graph exponentially faster than any classical algorithm.\n",
    "Our desire was to implement a quantum walk in IBM's quantum computer, starting in particularly simple cases and then work our way up to the full fledged case. As determining actual circuit configurations in a real quantum computer is a non-trivial problem we followed the work given in [1].\n",
    "\n",
    "### Quantum Walk on a Lattice\n",
    "\n",
    "The state of the system evolves with the application of two unitary operators:\n",
    "\n",
    "1. A coin flip operator\n",
    "2. A conditional shift operator\n",
    "\n",
    "The state of our system $\\vert \\Psi \\rangle$ is the product state of the coin and the position on the lattice\n",
    "$\\vert \\Psi \\rangle = \\vert s \\rangle \\otimes \\vert \\psi \\rangle$.\n",
    "\n",
    "Coin space: $\\vert s \\rangle \\in \\mathcal{H}_C = \\{ \\vert \\uparrow \\rangle, \\vert \\downarrow \\rangle \\}$\n",
    "\n",
    "Position space: $ \\vert \\psi \\rangle = \\mathcal{H}_P = \\{ \\sum_{i \\in Z} \\alpha_i \\vert i \\rangle \\} $\n",
    "\n",
    "#### Hadamard coin\n",
    "\n",
    "For a walk on a chain, the coin flip operator is a $2 \\times 2$ unitary matrix. A typical choice would be the Hadamard coin,\n",
    "\n",
    "$H = \\frac{1}{\\sqrt 2} \\begin{bmatrix} 1 & 1\\\\ 1 & -1 \\end{bmatrix}$\n",
    "\n",
    "#### Shift operator\n",
    "\n",
    "The shift operator S is a position translating operator conditioned on the coin as the control qubit. It increments the position by one if the particle is in the spin up state, and decrements by one if the particle is in the spin down state:\n",
    "\n",
    "$ S = \\sum_{i \\in Z} \\mid i + 1 \\rangle \\langle i \\mid \\otimes \\vert \\uparrow \\rangle \\langle \\uparrow \\vert + \\vert i - 1 \\rangle \\langle i \\vert \\otimes \\vert \\downarrow \\rangle \\langle \\downarrow \\vert $\n",
    "\n",
    "#### Single time step\n",
    "If the system is initialized in the state $\\vert \\Psi \\rangle = \\vert \\uparrow \\rangle \\otimes \\vert 0 \\rangle$,\n",
    "\n",
    "a single time step involves the application of a Hadamard coin flip\n",
    "\n",
    "$\\vert \\uparrow \\rangle \\otimes \\vert 0 \\rangle \\xrightarrow{H} \\frac{1}{\\sqrt 2} \\big( \\vert \\uparrow \\rangle + \\vert \\downarrow \\rangle \\big) \\otimes \\vert 0 \\rangle $\n",
    "\n",
    "followed by a conditional shift\n",
    "\n",
    "$ \\xrightarrow{S} \\frac{1}{\\sqrt 2} \\big( \\vert \\uparrow \\rangle \\otimes \\vert 1 \\rangle  + \\vert \\downarrow \\rangle \\otimes \\vert -1 \\rangle \\big) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quantum Cycle Graph\n",
    "\n",
    "A 1D cycle chain of 8 nodes is represented by the following figure:\n",
    "<img src=\"figures/cycle_graph.png\" width=400px>\n",
    "\n",
    "A quantum walk on the cycle can be efficiently and straightforwardly implemented with a set of quantum gates consisting of Hadamard gates followed by conditional increment and decrement gates, described below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1D Quantum Walk Circuit\n",
    "This shows the quantum circuit for a 1D walk along a circular lattice [1]. A $2^n$-node circuit requires n qubits to encode the position and one coin.\n",
    "<img src=\"figures/1d_circuit.png\" width=\"600px\">\n",
    "\n",
    "### 2D Quantum Walk Circuit\n",
    "The equivalent 2D circuit has n qubits each to encode the x and y positions, and two coins. At any given time step, the position can shift up, down, left, or right. [1]\n",
    "<img src=\"figures/2d_circuit.png\" width=\"600px\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Increment and Decrement Gates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import time\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "from qiskit import (QuantumCircuit, QuantumRegister, ClassicalRegister, execute, Aer)\n",
    "from ipywidgets import interact, interactive, fixed, interact_manual\n",
    "import ipywidgets as widgets\n",
    "import tkinter as tk\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=3\n",
    "def counts_to_prob_1d(counts):\n",
    "    # Convert histogram counts to probability vector of size 1 x 2^n\n",
    "    states = list(counts.keys())\n",
    "    state_counts = list(counts.values())\n",
    "    nshots = sum(state_counts)\n",
    "    # Convert binary to integer index, reversing order as consistent w qiskit convention\n",
    "    states_x = [int(s[::-1],2) for s in states]\n",
    "    # Create array of probability values\n",
    "    probabilities = np.zeros(2**n)\n",
    "    probabilities[states_x] = state_counts\n",
    "    probabilities /= nshots\n",
    "    return probabilities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def increment_gate(circuit, qpos):\n",
    "    n = len(qpos)\n",
    "    for i in range(n):\n",
    "        circuit.mct(qpos[i+1:], qpos[i], None, mode='noancilla')\n",
    "def decrement_gate(circuit, qpos):\n",
    "    n = len(qpos)\n",
    "    for i in range(n):\n",
    "        if i+1 < n: circuit.x(qpos[i+1:])\n",
    "        circuit.mct(qpos[i+1:], qpos[i], None, mode='noancilla')\n",
    "        if i+1 < n: circuit.x(qpos[i+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "seed = 12\n",
    "random.seed(seed)\n",
    "np.random.seed(seed)\n",
    "def plotCircleGraph(propabilities):\n",
    "    G = nx.Graph()\n",
    "    colorarray = []\n",
    "    # generate array of colors\n",
    "    numProp = len(propabilities)\n",
    "    for idx in range(numProp):\n",
    "        colorarray.append([1-propabilities[idx],1-propabilities[idx],1])\n",
    "    # generate graph\n",
    "    for idx in range(numProp-1):\n",
    "        G.add_edge(idx, idx+1)\n",
    "    # add last edge\n",
    "    G.add_edge(0,numProp-1)\n",
    "    nx.draw(G,pos=nx.circular_layout(G),node_color = colorarray,cmap=plt.cm.Blues)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    simulator = Aer.get_backend('qasm_simulator')\n",
    "    qpos = QuantumRegister(n,'qc')\n",
    "    cpos = ClassicalRegister(n,'cr')\n",
    "    circuit = QuantumCircuit(qpos, cpos)\n",
    "    if x<0:\n",
    "        for i in range(-x):\n",
    "            decrement_gate(circuit, qpos)\n",
    "    for i in range(x):\n",
    "        increment_gate(circuit, qpos)\n",
    "    # # Map the quantum measurement to the classical bits\n",
    "    circuit.measure(qpos,cpos)\n",
    "    # # Execute the circuit on the qasm simulator\n",
    "    job = execute(circuit, simulator, shots=1000)\n",
    "    # # Grab results from the job\n",
    "    result = job.result()\n",
    "    # # Returns counts\n",
    "    counts = result.get_counts(circuit)\n",
    "    prob = counts_to_prob_1d(counts)\n",
    "    plotCircleGraph(prob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Circuit Representation\n",
    "\n",
    "#### Increment Gate\n",
    "<img src=\"figures/inc_only.png\" width=\"auto\">\n",
    "\n",
    "#### Decrement Gate\n",
    "<img src=\"figures/dec_only.png\" width=\"auto\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "3f3ffe2f71364bcc85094d81ffb6f5d6",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='x', max=10, min=-10), Output()), _dom_classes=('widget-i…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "interact(f, x=widgets.IntSlider(min=-10, max=10, step=1, value=0));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### One time step of a Hadamard Walk\n",
    "A single time step of a Hadamard quantum walk combines the components into the circuit represented below:\n",
    "<img src=\"figures/1step.png\" width=\"auto\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1D and 2D Quantum Walk Simulation\n",
    "The 1D and 2D quantum walks were implemented in the notebooks <a href=\"1D Walk on IBM.ipynb\">1D Walk on IBM.ipynb</a> and <a href=\"2D Walk on IBM.ipynb\">2D Walk on IBM.ipynb</a>. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Outlook\n",
    "\n",
    "Having demonstrated the 1-D and 2-D case, we are ready to move on to more complicated quantum walks that actually exhibit a quantum speed up. Fortunately [3], has a circuit for implementing a transformed quantum walk problem, but the actual walking for the graph of interest needs to be implemented by a black box function. The paper doesn't illustrate how to implement the actual black box function, so we came up with an algorithmic way to implement any black box function.\n",
    "\n",
    "Once that's done, it's straightforward to include the rest of the quantum gates necessary to implement exponentially sped up quantum walks on arbitrary quantum graphs. One more hack-a-thon should be enough to implement arbitrary quantum walks on a quantum computer!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "[1]: Douglas, B. L., & Wang, J. B. (2009). Efficient quantum circuit implementation of quantum walks. Physical Review A, 79(5), 052335.\n",
    "\n",
    "[2]: Reitzner, D., Nagaj, D., & Buzek, V. (2012). Quantum walks. arXiv preprint arXiv:1207.7283.\n",
    "\n",
    "[3]: Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003, June). Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (pp. 59-68)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}