10_Discrete_Optimization_and_Unsupervised_Learning.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T20:28:41.436161Z",
     "start_time": "2019-02-01T20:28:40.764021Z"
    }
   },
   "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": [
    "# Mapping clustering to discrete optimization\n",
    "\n",
    "We will have {*xi*}, *i=1..N* points lying in two distant regions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T20:48:40.643798Z",
     "start_time": "2019-02-01T20:48:40.594636Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.collections.PathCollection at 0x141a845b0>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXsAAAD4CAYAAAANbUbJAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAARiElEQVR4nO3dfYxl9V3H8ffH3cUu2rrYHbXsQhYTuhYjSB1pfaZpdRdqhJo2gdY+mDYbEtv4kCCQpm1M/zAVNdVI3WwQaa1CtN1QbKjrY+UPQsMgLQ/FxRUizC66Q1uqqauwy9c/7qVOh5m5Z2bOnbvb3/uVTPaec373nE9mznz2zG/OnZuqQpL0ze1bJh1AkjR+lr0kNcCyl6QGWPaS1ADLXpIasHFSB966dWvt2LFjUoeXpFPSvffe+1RVTa30eRMr+x07djAzMzOpw0vSKSnJv63meU7jSFIDLHtJaoBlL0kNsOwlqQGWvSQ1YGJ346zWbfcd5voDBzny9DHO3LKZq3ft5PILt006liSd1E6psr/tvsNct/8Bjj17AoDDTx/juv0PAFj4krSMU2oa5/oDB79e9M879uwJrj9wcEKJJOnUcEqV/ZGnj61ovSRp4JQq+zO3bF7ReknSwClV9lfv2snmTRu+Yd3mTRu4etfOCSWSpFPDKVX2AN+68f8jn3H6Jn7z53/AX85K0ginzN04C+/EAfifZ5+bYCJJOnWcMlf23okjSat3ypS9d+JI0uqNLPskNyU5muTBZcZcnOTzSR5K8o/9RhzwThxJWr0uV/Y3A7uX2phkC/AR4Oeq6vuBN/WSbAHvxJGk1Rv5C9qqujPJjmWGvBnYX1WPD8cf7SnbN3j+jhv/Lo4krVwfd+O8HNiU5LPAi4Hfq6qPLTYwyR5gD8DZZ5+94gNdfuE2y12SVqGPX9BuBH4IeD2wC3hfkpcvNrCq9lXVdFVNT02t+P1yJUmr1MeV/SzwVFV9DfhakjuBC4BHeti3JKkHfVzZfwr4iSQbk5wOvAp4uIf9SpJ6MvLKPsktwMXA1iSzwAeATQBVtbeqHk7yV8D9wHPAjVW15G2akqT11+VunCs7jLkeuL6XRJKk3p0yr6CVJK2eZS9JDbDsJakBlr0kNcCyl6QGWPaS1ADLXpIaYNlLUgMse0lqgGUvSQ2w7CWpAZa9JDXAspekBlj2ktQAy16SGmDZS1IDRpZ9kpuSHE2y7LtPJfnhJCeSvLG/eJKkPnS5sr8Z2L3cgCQbgA8BB3rIJEnq2ciyr6o7gS+PGPYe4JPA0T5CSZL6teY5+yTbgDcAezuM3ZNkJsnM3NzcWg8tSeqoj1/Qfhi4pqpOjBpYVfuqarqqpqempno4tCSpi4097GMauDUJwFbg0iTHq+q2HvYtSerBmsu+qs55/nGSm4FPW/SSdHIZWfZJbgEuBrYmmQU+AGwCqKqR8/SSpMkbWfZVdWXXnVXVO9aURpI0Fr6CVpIaYNlLUgMse0lqgGUvSQ2w7CWpAZa9JDXAspekBlj2ktQAy16SGmDZS1IDLHtJaoBlL0kNsOwlqQGWvSQ1wLKXpAZY9pLUgJFln+SmJEeTPLjE9rckuX/4cVeSC/qPKUlaiy5X9jcDu5fZ/hjwU1V1PvBBYF8PuSRJPerytoR3JtmxzPa75i3eDWzvIZckqUd9z9m/E/jMUhuT7Ekyk2Rmbm6u50NLkpbSW9kneQ2Dsr9mqTFVta+qpqtqempqqq9DS5JGGDmN00WS84EbgUuq6kt97FOS1J81X9knORvYD7y1qh5ZeyRJUt9GXtknuQW4GNiaZBb4ALAJoKr2Au8HXgp8JAnA8aqaHldgSdLKdbkb58oR298FvKu3RJKk3vkKWklqgGUvSQ2w7CWpAZa9JDXAspekBlj2ktQAy16SGmDZS1IDLHtJaoBlL0kNsOwlqQGWvSQ1wLKXpAZY9pLUAMtekhpg2UtSAyx7SWrAyLJPclOSo0keXGJ7kvx+kkNJ7k/yyv5jSpLWosuV/c3A7mW2XwKcO/zYA/zh2mNJkvo0suyr6k7gy8sMuQz4WA3cDWxJ8rK+AkqS1q6POfttwBPzlmeH614gyZ4kM0lm5ubmeji0JKmLPso+i6yrxQZW1b6qmq6q6ampqR4OLUnqoo+ynwXOmre8HTjSw34lST3po+xvB942vCvn1cBXq+rJHvYrSerJxlEDktwCXAxsTTILfADYBFBVe4E7gEuBQ8B/A784rrCSpNUZWfZVdeWI7QX8Um+JJEm98xW0ktQAy16SGmDZS1IDLHtJaoBlL0kNsOwlqQGWvSQ1wLKXpAZY9pLUAMtekhpg2UtSAyx7SWqAZS9JDbDsJakBlr0kNcCyl6QGdCr7JLuTHExyKMm1i2z/jiR/meQLSR5K4rtVSdJJZGTZJ9kA3ABcApwHXJnkvAXDfgn4YlVdwOAtDH8nyWk9Z5UkrVKXK/uLgENV9WhVPQPcCly2YEwBL04S4NuBLwPHe00qSVq1LmW/DXhi3vLscN18fwC8AjgCPAD8clU9t3BHSfYkmUkyMzc3t8rIkqSV6lL2WWRdLVjeBXweOBP4QeAPkrzkBU+q2ldV01U1PTU1tcKokqTV6lL2s8BZ85a3M7iCn+8Xgf01cAh4DPi+fiJKktaqS9nfA5yb5JzhL12vAG5fMOZx4LUASb4b2Ak82mdQSdLqbRw1oKqOJ3k3cADYANxUVQ8luWq4fS/wQeDmJA8wmPa5pqqeGmNuSdIKjCx7gKq6A7hjwbq98x4fAX6m32iSpL74ClpJaoBlL0kNsOwlqQGWvSQ1wLKXpAZY9pLUAMtekhpg2UtSAyx7SWqAZS9JDbDsJakBlr0kNcCyl6QGWPaS1ADLXpIaYNlLUgM6lX2S3UkOJjmU5Nolxlyc5PNJHkryj/3GlCStxch3qkqyAbgB+GkGbz5+T5Lbq+qL88ZsAT4C7K6qx5N815jySpJWocuV/UXAoap6tKqeAW4FLlsw5s3A/qp6HKCqjvYbU5K0Fl3KfhvwxLzl2eG6+V4OnJHks0nuTfK2xXaUZE+SmSQzc3Nzq0ssSVqxLmWfRdbVguWNwA8Brwd2Ae9L8vIXPKlqX1VNV9X01NTUisNKklZn5Jw9gyv5s+YtbweOLDLmqar6GvC1JHcCFwCP9JJSkrQmXa7s7wHOTXJOktOAK4DbF4z5FPATSTYmOR14FfBwv1ElSas18sq+qo4neTdwANgA3FRVDyW5arh9b1U9nOSvgPuB54Abq+rBcQaXJHWXqoXT7+tjenq6ZmZmJnJsSTpVJbm3qqZX+jxfQStJDbDsJakBlr0kNcCyl6QGWPaS1ADLXpIaYNlLUgMse0lqgGUvSQ2w7CWpAZa9JDXAspekBlj2ktQAy16SGmDZS1IDLHtJakCnsk+yO8nBJIeSXLvMuB9OciLJG/uLKElaq5Fln2QDcANwCXAecGWS85YY9yEGb18oSTqJdLmyvwg4VFWPVtUzwK3AZYuMew/wSeBoj/kkST3oUvbbgCfmLc8O131dkm3AG4C9y+0oyZ4kM0lm5ubmVppVkrRKXco+i6xb+C7lHwauqaoTy+2oqvZV1XRVTU9NTXWMKElaq40dxswCZ81b3g4cWTBmGrg1CcBW4NIkx6vqtj5CSpLWpkvZ3wOcm+Qc4DBwBfDm+QOq6pznHye5Gfi0RS9JJ4+RZV9Vx5O8m8FdNhuAm6rqoSRXDbcvO08vSZq8Llf2VNUdwB0L1i1a8lX1jrXHkiT1yVfQSlIDLHtJaoBlL0kNsOwlqQGWvSQ1wLKXpAZY9pLUAMtekhpg2UtSAyx7SWqAZS9JDbDsJakBlr0kNcCyl6QGWPaS1ADLXpIa0Knsk+xOcjDJoSTXLrL9LUnuH37cleSC/qNKklZrZNkn2QDcAFwCnAdcmeS8BcMeA36qqs4HPgjs6zuoJGn1ulzZXwQcqqpHq+oZ4FbgsvkDququqvrKcPFuYHu/MSVJa9Gl7LcBT8xbnh2uW8o7gc8stiHJniQzSWbm5ua6p5QkrUmXss8i62rRgclrGJT9NYttr6p9VTVdVdNTU1PdU0qS1mRjhzGzwFnzlrcDRxYOSnI+cCNwSVV9qZ94kqQ+dLmyvwc4N8k5SU4DrgBunz8gydnAfuCtVfVI/zElSWsx8sq+qo4neTdwANgA3FRVDyW5arh9L/B+4KXAR5IAHK+q6fHFliStRKoWnX4fu+np6ZqZmZnIsSVpPd1232GuP3CQI08f48wtm7l6104uv3C5+1yWluTe1VxMd5mzlySt0m33Hea6/Q9w7NkTABx++hjX7X8AYNWFvxr+uQRJGqPrDxz8etE/79izJ7j+wMF1zWHZS9IYHXn62IrWj4tlL0ljdOaWzYuu/5aE2+47vG45LHtJGqOrd+1k86YNL1h/oorr9j+wboVv2UvSGF1+4TZ+8+d/gA154R8jWM+5e8teksbs8gu38dwSt7mv19y9ZS9J62Cpuful1vfNspekdbDY3P3mTRu4etfOdTm+L6qSpHXw/Auo+nol7UpZ9pK0Ti6/cNu6vmp2PqdxJKkBlr0kNcCyl6QGWPaS1ADLXpIaMLE3L0kyB/zbRA6+tK3AU5MOsYCZujsZc5mpGzN1t7OqXrzSJ03s1suqmprUsZeSZOZkeztFM3V3MuYyUzdm6i7Jqt7iz2kcSWqAZS9JDbDsv9G+SQdYhJm6OxlzmakbM3W3qlwT+wWtJGn9eGUvSQ2w7CWpAU2XfZI3JXkoyXNJlr3FKsmGJPcl+fSkMyU5K8k/JHl4OPaXJ51pOG53koNJDiW5dsyZvjPJ3yT5l+G/Zywx7leH2R9MckuSF50kubYk+USSfx5+HX9k0pmGY9frPB+Zab3O81HnbQZ+f7j9/iSvHEeOFWZ6yzDL/UnuSnLByJ1WVbMfwCuAncBngekRY38N+DPg05POBLwMeOXw8YuBR4DzJpxpA/CvwPcCpwFfGHOm3wKuHT6+FvjQImO2AY8Bm4fLfw68Y8xfv5G5hts+Crxr+Pg0YMukMw23r9d53uXrN/bzvMt5C1wKfAYI8Grgc2P+3HTJ9KPAGcPHl3TJ1PSVfVU9XFUj3+03yXbg9cCNJ0Omqnqyqv5p+Pi/gIcZFNvEMgEXAYeq6tGqega4FbhsXJmG+/7o8PFHgcuXGLcR2JxkI3A6cGSMmTrlSvIS4CeBPwKoqmeq6ulJZhrmWrfzvEumdTrPu5y3lwEfq4G7gS1JXtZzjhVlqqq7quorw8W7ge2jdtp02a/Ah4FfB56bcI4XSLIDuBD43ISjbAOemLc8yxj/AwK+u6qehEEpAN+1cEBVHQZ+G3gceBL4alX99RgzdcrF4IptDvjj4ZTJjUm+bcKZYH3P866ZgLGe513O2/U+t1d6vHcy+MljWd/071SV5G+B71lk03ur6lMdnv+zwNGqujfJxSdDpnn7+Xbgk8CvVNV/TjhTFlm3pvt6l8vU8flnMLgiOgd4GviLJL9QVR+fZC4G33evBN5TVZ9L8nsMpjLeN6lM632er3A/vZ3ni+1+kXULz9vez+0ROh8vyWsYlP2Pj9rpN33ZV9Xr1riLHwN+LsmlwIuAlyT5eFX9wgQzkWQTg2+AP62q/WvdXw+ZZoGz5i1vZ41TJstlSvIfSV5WVU8Of6Q+usiw1wGPVdXc8Dn7Gcx1rqnse8g1C8xW1fNXqZ9gUPaTzLSu53nHTL2f54voct72fm73kIkk5zOYcrukqr40aqdO44xQVddV1faq2gFcAfz9Wr4B+pAkDOZ7H66q351klnnuAc5Nck6S0xh8rm4f4/FuB94+fPx2YLGfPh4HXp3k9OHn7LUM5n3HaWSuqvp34IkkO4erXgt8ccKZ1vs8H5lpnc7zLuft7cDbhnflvJrBdOCTY8rTKVOSs4H9wFur6pFOex3nb5VP9g/gDQz+F/1f4D+AA8P1ZwJ3LDL+YsZ/l8LITAx+ZCvgfuDzw49LJ/15YnDXwiMM7iR475g/Ty8F/g74l+G/37lEpt8A/hl4EPgT4FtPklw/CMwMv4a3MbyzYpKZ5o1fj/N8ZKb1Os8XO2+Bq4Crho8D3DDc/gAj7txbp0w3Al+Z93mZGbVP/1yCJDXAaRxJaoBlL0kNsOwlqQGWvSQ1wLKXpAZY9pLUAMtekhrwf4P8SAKGUg7GAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "np.set_printoptions(precision=3, suppress=True)\n",
    "np.random.seed(0)\n",
    "\n",
    "# Generating the data\n",
    "c1 = np.random.rand(2, 2)/5\n",
    "c2 = (-1.6, 1.5) + np.random.rand(2, 2)/5\n",
    "data = np.concatenate((c1, c2))\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "ax.scatter(data[:, 0], data[:, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1** (3 points). The unsupervised task is identify this structure. The challenge is that if we have a high number of points compared to the number of qubits and their connections, we won't be able to solve the problem. So if we blindly follow the idea of mapping the problem to max-cut using the Eucledian distance and then solve it by some quantum optimization method, we would run out of qubit connections for this problem. We can, however, choose to be clever about how we calculate the distances classically. This is a common trick: since we are doing hybrid classical-quantum algorithms anyway, we might as well do the classical parts wisely.\n",
    "\n",
    "In this case, we might rely on some form of [exploratory data analysis](https://en.wikipedia.org/wiki/Exploratory_data_analysis) to get a sense of the distances in the dataset. This is an easy case, since we just plotted the two-dimensional data, and we see that the density within a blob is high. You can make the task easier by thresholding the distances. Use any distance function you wish (even the Euclidean distance will do) and set distances to zero that are below a threshold you calculate. The threshold should be such that all of the distances within a blob will be set to zero. Store the symmetrix distance matrix in a two-dimensional numpy array called `w`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T20:27:38.349707Z",
     "start_time": "2019-02-01T20:27:38.341177Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.    0.    2.202 2.234]\n",
      " [0.    0.    2.233 2.265]\n",
      " [2.202 2.233 0.    0.   ]\n",
      " [2.234 2.265 0.    0.   ]]\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "n_instances = data.shape[0]\n",
    "###\n",
    "### YOUR CODE HERE\n",
    "###\n",
    "\n",
    "w = np.zeros((n_instances, n_instances))\n",
    "\n",
    "for i in range(n_instances):\n",
    "    for j in range(n_instances):\n",
    "        \n",
    "        distance = np.linalg.norm(data[i] - data[j])\n",
    "\n",
    "        if (distance > 0.1):\n",
    "            w[i][j] = distance\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "print(w)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T20:28:25.104088Z",
     "start_time": "2019-02-01T20:28:25.099798Z"
    },
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise1",
     "locked": true,
     "points": "3",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "labels = np.array([0, 0, 1, 1])\n",
    "assert np.alltrue(w == w.T)\n",
    "assert np.alltrue(w >= 0)\n",
    "assert (w[labels==0][:, labels==0]==0).sum() == 4\n",
    "assert (w[labels==1][:, labels==1]==0).sum() == 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the max-cut problem by QAOA\n",
    "\n",
    "**Exercise 2** (2 points). From here, it is rather formulaic to create the max-cut as an Ising Hamiltonian and solve either by annealing or by some variational circuit like QAOA. Set up the QAOA problem in your chosen framework and an optimization function. Import all necessary functions you need. Call the object `qaoa`. We set the `p` parameter of the QAOA to 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T21:29:46.241563Z",
     "start_time": "2019-02-01T21:29:46.224360Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'qiskit.aqua.operators.legacy.weighted_pauli_operator.WeightedPauliOperator'>\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/optimization/__init__.py:92: DeprecationWarning: The package qiskit.optimization is deprecated. It was moved/refactored to qiskit_optimization (pip install qiskit-optimization). For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>\n",
      "  warn_package('optimization', 'qiskit_optimization', 'qiskit-optimization')\n",
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/optimization/applications/ising/max_cut.py:54: DeprecationWarning: The package qiskit.aqua.operators is deprecated. It was moved/refactored to qiskit.opflow (pip install qiskit-terra). For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>\n",
      "  return WeightedPauliOperator(paulis=pauli_list), shift\n",
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/aqua/components/optimizers/optimizer.py:49: DeprecationWarning: The package qiskit.aqua.components.optimizers is deprecated. It was moved/refactored to qiskit.algorithms.optimizers (pip install qiskit-terra). For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>\n",
      "  warn_package('aqua.components.optimizers',\n",
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/aqua/algorithms/vq_algorithm.py:70: DeprecationWarning: The class qiskit.aqua.algorithms.VQAlgorithm is deprecated. It was moved/refactored to qiskit.algorithms.VariationalAlgorithm (pip install qiskit-terra). For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>\n",
      "  warn_class('aqua.algorithms.VQAlgorithm',\n",
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/aqua/components/variational_forms/variational_form.py:48: DeprecationWarning: The package qiskit.aqua.components.variational_forms is deprecated. For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>\n",
      "  warn_package('aqua.components.variational_forms')\n",
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/visualization/text.py:659: RuntimeWarning: The parameter \"cregbundle\" was disabled, since an instruction needs to refer to individual classical wires\n",
      "  return \"\\n\".join(self.lines()).encode(self.encoding).decode(self.encoding)\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">     ┌─────────────┐\n",
       "q_0: ┤0            ├\n",
       "     │             │\n",
       "q_1: ┤1            ├\n",
       "     │             │\n",
       "q_2: ┤2            ├\n",
       "     │             │\n",
       "q_3: ┤3            ├\n",
       "     │  Pauli IZIZ │\n",
       "c_0: ╡0            ╞\n",
       "     │             │\n",
       "c_1: ╡1            ╞\n",
       "     │             │\n",
       "c_2: ╡2            ╞\n",
       "     │             │\n",
       "c_3: ╡3            ╞\n",
       "     └─────────────┘</pre>"
      ],
      "text/plain": [
       "     ┌─────────────┐\n",
       "q_0: ┤0            ├\n",
       "     │             │\n",
       "q_1: ┤1            ├\n",
       "     │             │\n",
       "q_2: ┤2            ├\n",
       "     │             │\n",
       "q_3: ┤3            ├\n",
       "     │  Pauli IZIZ │\n",
       "c_0: ╡0            ╞\n",
       "     │             │\n",
       "c_1: ╡1            ╞\n",
       "     │             │\n",
       "c_2: ╡2            ╞\n",
       "     │             │\n",
       "c_3: ╡3            ╞\n",
       "     └─────────────┘"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = 1\n",
    "###\n",
    "### YOUR CODE HERE\n",
    "###\n",
    "\n",
    "\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.optimization.applications.ising import max_cut\n",
    "from qiskit.aqua.algorithms import QAOA\n",
    "qubit_operators, offset = max_cut.get_operator(w)\n",
    "optimizer = COBYLA()\n",
    "qaoa = QAOA(qubit_operators, optimizer, p)\n",
    "\n",
    "print(type(qubit_operators))\n",
    "circ = QuantumCircuit(4, 4)\n",
    "#circ.append(qubit_operators, [0, 1, 2, 3])\n",
    "#circ.draw('mpl')\n",
    "\n",
    "evaluation_circuits = qubit_operators.construct_evaluation_circuit(circ, False)\n",
    "\n",
    "evaluation_circuits[0].draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Setting $p=1$ in the QAOA algorithm, we can initialize it with the max-cut problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T21:17:37.687655Z",
     "start_time": "2019-02-01T21:17:37.680171Z"
    },
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise2",
     "locked": true,
     "points": "2",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "if isinstance(qaoa, qiskit.aqua.algorithms.QAOA):\n",
    "    assert qaoa._operator.num_qubits == 4\n",
    "elif isinstance(qaoa, grove.pyqaoa.qaoa.QAOA):\n",
    "    assert len(qaoa.ref_ham) == 4\n",
    "    assert all([qaoa.ref_ham[i].terms[0].compact_str() == '(1+0j)*X{}'.format(i) for i in range(4)])\n",
    "    assert len(qaoa.cost_ham) == 12\n",
    "else:\n",
    "    raise ValueError(\"Unknown type for Hamiltonian!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3** (2 points). Run the QAOA on a simulator. Store the outcome in an object called `result`. In the case of the Forest SDK, this will store the return value of the `run_and_measure` method of the QVM. In the case of Qiskit, it will be the return value of the `run` method of the `qaoa` object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T21:24:52.709677Z",
     "start_time": "2019-02-01T21:24:50.825360Z"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/aqua/quantum_instance.py:135: DeprecationWarning: The class qiskit.aqua.QuantumInstance is deprecated. It was moved/refactored to qiskit.utils.QuantumInstance (pip install qiskit-terra). For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>\n",
      "  warn_class('aqua.QuantumInstance',\n",
      "/Users/gianlucafugante/anaconda3/lib/python3.8/site-packages/qiskit/aqua/algorithms/quantum_algorithm.py:46: DeprecationWarning: The variable qiskit.aqua.aqua_globals is deprecated. It was moved/refactored to qiskit.utils.algorithm_globals (pip install qiskit-terra). For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>\n",
      "  return aqua_globals.random\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'optimal_parameters': {ParameterVectorElement(θ[0]): -1.0549067972650499, ParameterVectorElement(θ[1]): 2.748810803381066}, 'optimal_point': array([-1.055,  2.749]), 'optimal_value': -2.231691283559714, 'optimizer_evals': 37, 'optimizer_time': 0.4473717212677002, 'eigenvalue': (-2.231691283559714+0j), 'eigenstate': array([-0.125-0.j   , -0.   +0.133j, -0.   +0.117j, -0.125+0.5j  ,\n",
      "       -0.   +0.133j,  0.125+0.25j ,  0.125+0.25j , -0.   +0.117j,\n",
      "       -0.   +0.117j,  0.125+0.25j ,  0.125+0.25j , -0.   +0.133j,\n",
      "       -0.125+0.5j  , -0.   +0.117j, -0.   +0.133j, -0.125-0.j   ]), 'cost_function_evals': 37}\n"
     ]
    }
   ],
   "source": [
    "###\n",
    "### YOUR CODE HERE\n",
    "###\n",
    "\n",
    "from qiskit.aqua import QuantumInstance\n",
    "backend = Aer.get_backend('statevector_simulator')\n",
    "quantum_instance = QuantumInstance(backend, shots=100)\n",
    "\n",
    "result = qaoa.run(quantum_instance)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-02-01T21:28:58.162057Z",
     "start_time": "2019-02-01T21:28:58.157118Z"
    },
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise3",
     "locked": true,
     "points": "2",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "from qiskit.optimization.applications.ising.common import sample_most_likely\n",
    "ground_truth1 = [0, 0, 1, 1]\n",
    "ground_truth2 = [1, 1, 0, 0]\n",
    "if isinstance(result, list):\n",
    "    count = np.unique(result, return_counts=True, axis=0)\n",
    "    solution = count[0][np.argmax(count[1])]\n",
    "    assert abs(sum(solution == ground_truth1)-4) <= 1 or abs(sum(solution == ground_truth2)-4) <= 1\n",
    "else:\n",
    "    x = sample_most_likely(result['eigenstate'])\n",
    "    solution = max_cut.get_graph_solution(x)\n",
    "    assert abs(sum(solution == ground_truth1)-4) <= 1 or abs(sum(solution == ground_truth2)-4) <= 1"
   ]
  },
  {
   "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.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
}