12_Training_Probabilistic_Graphical_Models.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Available frameworks:\n",
      "Qiskit\n",
      "D-Wave Ocean\n"
     ]
    }
   ],
   "source": [
    "%run -i \"assignment_helper.py\"\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Probabilistic graphical models\n",
    "\n",
    "Recall that probabilistic graphical models capture a compact representation of a joint probability distribution through conditionally independence: random variable *X* is conditionally independent of *Y* given *Z*: $$(X\\perp Y|Z)$, if $P(X=x, Y=y|Z=z) = P(X=x|Z=z)P(Y=y|Z=z)$ for all $x\\in X,y\\in Y,z\\in Z$$ A Markov network is a type of probabilistic graphical models that allows cycles in the graph and uses global normalization of probabilities (i.e. a partition function). The factorization of the joint probability distribution is given as a sum: $$P(X_1, \\ldots, X_N) = \\frac{1}{Z}\\exp(-\\sum_k E[C_k])$$, where *Ck* are are cliques of the graph, and *E[.]* is an energy defined over the cliques.\n",
    "\n",
    "**Exercise 1** (2 points). Define a Markov random field of four binary random variables in `dimod`. Random variables *X1* and *X3* are conditionally independent given *X2*. The random variable *X4* is independent of all the other variables. The coupling strength on all edges in the graph is -1. Apart from the coupling between nodes, we also consider an external field of strength 1 applied to all nodes. Store the resulting `BinaryQuadraticModel` in an object called `model`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:10:30.684603Z",
     "start_time": "2018-11-19T20:10:30.190403Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 0), (2, 1)]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "###\n",
    "### YOUR CODE HERE\n",
    "###\n",
    "\n",
    "number_of_nodes = 4\n",
    "h = {n: 1 for n in range(number_of_nodes)}\n",
    "J = {(0,1): -1, (1,2): -1}\n",
    "model = dimod.BinaryQuadraticModel(h, J, 0.0, dimod.BINARY)\n",
    "[i for i in model.quadratic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Error in the assertion cell:\n",
    "# in line 6 should be [(1, 0), (2, 1)] and not [(0, 1), (1, 2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise1",
     "locked": true,
     "points": "2",
     "solution": false
    }
   },
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m~/Documents/Quantum Machine Learning/qml-mooc-master/coding_assignments/assignment_helper.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mmodel\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlinear\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mmodel\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlinear\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvalues\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mmodel\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mquadratic\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mmodel\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mquadratic\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvalues\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "assert isinstance(model, dimod.binary_quadratic_model.BinaryQuadraticModel)\n",
    "assert model.vartype == dimod.BINARY\n",
    "assert len(model.variables) == 4\n",
    "assert [i for i in model.linear] == [0, 1, 2, 3]\n",
    "assert [i for i in model.linear.values()] == [1, 1, 1, 1]\n",
    "assert [i for i in model.quadratic] == [(0, 1), (1, 2)]\n",
    "assert [i for i in model.quadratic.values()] == [-1, -1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2** (2 points). Convert the `dimod` model to a `networkx` graph. Store it in an object called `G`. You can use the `add_nodes_from` and `add_edges_from` methods of the graph object and the `linear` and `quadratic` methods of the model object to construct the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx\n",
    "G = networkx.Graph()\n",
    "###\n",
    "### YOUR CODE HERE\n",
    "###\n",
    "\n",
    "G.add_nodes_from(model.linear)\n",
    "G.add_edges_from(model.quadratic)\n",
    "\n",
    "networkx.draw(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise2",
     "locked": true,
     "points": "2",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert list(G.nodes) == [0, 1, 2, 3]\n",
    "assert list(G.edges) == [(0,1), (1, 2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you can easily plot the Markov network:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "networkx.draw(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3** (1 point). If we want to use quantum annealing to draw samples, we have to address the connectivity structure on the chip. Embed the graph on a single Chimera cell using `minorminer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "connectivity_structure = dwave_networkx.chimera_graph(1, 1)\n",
    "###\n",
    "### YOUR CODE HERE\n",
    "###\n",
    "\n",
    "#networkx.draw(connectivity_structure)\n",
    "embedded_graph = minorminer.find_embedding(G.edges(), connectivity_structure.edges())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise3",
     "locked": true,
     "points": "1",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert isinstance(embedded_graph, dict)\n",
    "assert len(embedded_graph) == 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a very simple Markov network that does not need multiple physical qubits to represent a logical qubit. Note that the independent random variable $X_4$ does not appear in the embedding."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dwave_networkx.draw_chimera_embedding(connectivity_structure, embedded_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4** (2 points). Estimate the partition function of this model at temperature *T=1* from 100 samples. Store the value in a variable called `Z`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:10:32.696067Z",
     "start_time": "2018-11-19T20:10:30.687484Z"
    }
   },
   "outputs": [],
   "source": [
    "###\n",
    "### YOUR CODE HERE\n",
    "###\n",
    "\n",
    "T = 1\n",
    "sampler = dimod.SimulatedAnnealingSampler()\n",
    "response = sampler.sample(model, beta_range=[1/T, 1/T], num_reads=100)\n",
    "degen = {}\n",
    "for solution in response.aggregate().data():\n",
    "    if solution.energy in degen.keys():\n",
    "        degen[solution.energy] += 1\n",
    "    else:\n",
    "        degen[solution.energy] = 1\n",
    "probabilities = np.array([degen[E] * np.exp(-E/T) for E in degen.keys()])\n",
    "Z = probabilities.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise4",
     "locked": true,
     "points": "2",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "###\n",
    "### AUTOGRADER TEST - DO NOT REMOVE\n",
    "###\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With these components in hand, you can start building a quantum-enhanced sampler for Markov networks."
   ]
  }
 ],
 "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.8.8"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}