06 - qaoa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum Approximate Optimization Algorithm \n",
    "\n",
    "Qiskit has an implementation of the Quantum Approximate Optimization Algorithm [QAOA](https://qiskit.org/documentation/stubs/qiskit.algorithms.QAOA.html) and this notebook demonstrates using it for a graph partition problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import networkx as nx\n",
    "\n",
    "from qiskit import Aer\n",
    "from qiskit.algorithms import NumPyMinimumEigensolver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we create a graph and draw it so it can be seen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_nodes = 4\n",
    "w = np.array([[0., 1., 1., 0.],\n",
    "              [1., 0., 1., 1.],\n",
    "              [1., 1., 0., 1.],\n",
    "              [0., 1., 1., 0.]])\n",
    "G = nx.from_numpy_matrix(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true,
    "tags": [
     "nbsphinx-thumbnail"
    ]
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dZ0BU57oF4DUNRETsUSlREBvEbmIBO6CoGMUuEAVjojkxUY9GvdHkXNMUe2/YW9QEW1ABNQgegzEq1qiJFWwoHpQOM3N/cPBasAAz8+2ZvZ4/JjKzZ8Uga7+7fQq9Xq8HERGRTChFByAiIjIlFh8REckKi4+IiGSFxUdERLLC4iMiIllh8RERkayw+IiISFZYfEREJCssPiIikhUWHxERyQqLj4iIZIXFR0REssLiIyIiWWHxERGRrLD4iIhIVlh8REQkKyw+IiKSFRYfERHJCouPiIhkhcVHRESywuIjIiJZUYsO8Kays5OQkZGI/Pw0KJVlYG3tCDu7llAoFKKjERGRGZF08en1Ojx8eAA3b85AWlo8FAprADoACgA6qNUV4eT0T1Sv/gHUanvBaYmIyBwo9Hq9XnSIouTm3kNiojeys69Aq01/6euUyrIAFHB334bKlbuZLiAREZklSRZfbu5dHD/eHLm59wDkvdF7lEob1K+/BtWq9TduOCIiMmuSKz6dLg/HjzdBZuYlAPnFeq9SWRZNmhxE+fLvGSccEZkVvV6P32/9jsjLkbiTfgcAUNOuJvzr+aNJ9SaC05Eokiu+e/e24eLFkFce3nwVe/v2aNr0V8OGIiKzkpOfg41nNmL6kelIfpSMrLws6KADAKgUKlirreFa0RVftP0C/d37Q6PSCE5MpiS54jt+vAXS0/8o8fuVyjJo2fI8bGxqGzAVEZmLB5kP0GV9F1x+cBkZeRmvfK2txhZNqjdB5JBIlLcub6KEJJqk7uPLyDiPzMzzpdqGXq9DUtJ8AyUiKfruu+/g6OgIV1dXpKWlFfma+fPno2XLlmjRogXOnDlj4oQkSlp2Gt5b+R7O3Tv32tIDgIy8DBy/dRxeq72QlZdlgoQkBZIqvrS0Iyi4VaHk9PpcPHwYY5hAJEne3t7Yv38/ypYtC61W+8LXT548iV27dmHNmjX47rvvMGHCBKSnl+zQOZmX/tv7I+lREvJ0b3ZRHADkaHNw6cElDNs5zIjJSEokdR9ffv5/oNe/+Tfsy6SkXMWnn34KtVoNlUr1zK9F/V5xXmPo9/MG/OJr2bIlUlNToVQqoVKpXvj6li1b0KtXL7i7u8Pd3R2jR4/G3bt3Ua5cOQFpyVQu3r+IuOtxyNHmFPu92fnZ2HlxJ249voWadjWNkI6kRFLFp1RawRBDqEZjAzc3N2i1WuTn5z/za25u7gu/9/Svr/ram7ymOO/XarVPfnhLuZxFfcardgx0Oh30en2Rxff333+jc+fO0Ol0UCqVcHJywp07d+Dq6lrq7y2SrnkJ85CvK96V4E/T6/VYenwp/rfj/xowFUmRpIrPyqoGlEoraEuwx/a0KlXqYfTo0QZKZTx6vR46nc6o5Vrcr+Xm5iIzM9OkOwAv+5pOp4OTkxMuXLgAW1vbZ/7sdLr/XqFXRPHl5eVBpVJBqSzYibKysnry+qfdvHkTEyZMMNsdCB4x+H85+TlYm7i2WIc4X9iGNgcLjy3E1x2+hlIhqbNAZGCSKr5Klfyg15d8jw0AVKpyqFnzYwMlMi6FQvHkBxi9SK/XQ6vVFvnnUzjxFZbb09566y08fPgQ+fn5UKvVSEpKQvXq1V94nZ2dHfz9/YtVzjk5OS/sGIjaSdHpdE++f0RP56KPINzOvA0Y4Pr0jLwMPM55DPsyfASiJZNU8anV5fDWW0Nw+/YaFPfm9adVrdrXYJlIHIVCAbW66G9RhUIBpVIJa2vrF77m5+eHNWvWoG/fvkhOTkZubi6cnZ1feF2FChUwaNAgg+c2lcIdAylM54X/nJ2dLeQUQo59DjL7ZwIvfjsUi1qpxqOcRyw+Cyep4gMAR8cxuHt3I3QlOFavUFijRo0PoVKVMUIykoqhQ4ciOjoad+7cgZOTE/71r39Bq9VCr9djxIgR6NmzJyIiItCoUSMoFArMmDGjyII0d4U7Bi/bOZCTKw+voNGSRm90C8Or5OvyYWtl+/oXklmT3A3sAHDt2jTcuPEDdLrMN36PVgukp9uja9frsLbm3pqlK5x2Cg+FFp4vLSy49PR0pKamQqFQwNHRkefCLFxmXiYqTa9Uois6n2arsUXaxDSolDz9YMkkeQb37be/RM2aI/+78sLrKRRlULZsHaxZ0xiDBg1Ddna2kROSaIXTjrW1NdRqNTQazTNTXbly5eDs7AwnJyeWngyU1ZRFnwZ9SnVRikapwbCmw1h6MiDJ4lMoFKhTZybq1l0MK6uaUKmKvv9KqSwLpbIMqlUbhJYtT2DLliio1Wr4+fnh0aNHJk5NRCKNaz0OZdQlP82hUqrw2XufGTARSZUkD3U+rWAx2oO4eXMG0tNPQqvNgEJhBSurt+Dg8A9Urx6Mpxeh1Wq1+OSTT3D8+HHs3bsXVatWFZieiEyp2bJmOHPvTLHv59MoNfB09sTBDw4aKRlJieSLryT0ej2mTp2KrVu3Ijo6usgr+ojI8tx6fAuNlzZGalYqdPoX790sikqhQo1yNXDq41OoXLaykROSFEjyUGdpKRQKTJs2DSNHjoSnpyfOny/dg6+JyDzUtKuJ30J/Q41yNWCltHrt661V1ni7wts4OvwoS09GLLL4Cn3++ef49ttv0alTJyQkJIiOQ0Qm4FrJFYkfJ6JxVmNY6axgZ2X3wmvUWjXKKspioudEnPzoJBzLOwpISqJY5KHO5+3ZswchISHYuHEjvL29RcchIiO7c+cOGjZsiBOJJ3Ds0TFsO7cN9zLuQaFQoHq56nDNdsXBJQdx9MhR0VFJAFkUHwDExcWhb9++WLhwIfr16yc6DhEZ0bhx45Cfn4958+YV+fW8vDw4OjoiPj4ebm5uJk5Hosmm+AAgMTERfn5+mDJlCj7+2Dye50lExVM47Z09exY1a758iaHPP/8c9vb2+Ne//mXCdCQFsio+oGDJGm9vb4SGhmLy5Mm8uZnIwowbNw55eXmYP3/+K1934sQJBAQE4O+//y7yYedkuWRXfABw+/Zt+Pr6onPnzpg1axa/6YksxN27d9GgQQOcOXMGDg4Or3ytXq+Hh4cHli5dCi8vLxMlJCmQ5U/8GjVqIDY2FseOHcPQoUORl1f6Vd+JSLywsDAEBga+tvSAgtuegoODsX79ehMkIymR5cRXKDMzE3379oVKpcLWrVthY2MjOhIRlVBxpr1CSUlJaNSoEZKTk/n3X0ZkOfEVKlu2LHbu3Al7e3v4+vriP//5j+hIRFRCYWFhGDJkyBuXHgA4OjqiWbNm2L17txGTkdTIuvgAQKPRYN26dWjSpAk6dOiAO3fuiI5ERMV09+5drFq1ChMnTiz2e4ODg7Fu3TojpCKpkvWhzqfp9Xp88803WLt2LaKiouDi4iI6EhG9ofHjxyM7OxsLFiwo9nvT09Ph6OiIS5cuoVq1akZIR1LD4nvOkiVL8O233yIyMhKNGjUSHYeIXuPevXuoX79+sc7tPS8oKAgtWrTAZ59xWSI5kP2hzueNHDkSs2bNgre3N44cOSI6DhG9RknO7T2PhzvlhRPfS+zfvx+BgYFYu3Yt/Pz8RMchoiIUTnunT5+Go2PJHzSt1Wrh7OyMqKgouLu7GzAhSREnvpfw9fXF7t27MWzYMGzcuFF0HCIqQlhYGAYPHlyq0gMAlUqFwMBA3tMnE5z4XuPcuXPo2rUrxo8fj9GjR4uOQ0T/Zahpr9DZs2fRtWtXXL9+HSqVygAJSao48b2Gu7s74uLisHDhQnz11VfgfgKRNMycOdMg014hDw8PVKtWDb/++qtBtkfSxYnvDd29exfdunVD69atsWDBAj7fk0ggQ097hebOnYuTJ09i7dq1BtsmSQ+LrxjS0tLQq1cv1KhRA2vXroWVlZXoSESyNGHCBGRkZGDRokUG3e7du3dRr149JCUloVy5cgbdNkkHx5ZisLe3x759+5CVlQV/f39kZGSIjkQkO/fu3cPKlStL9JSW13nrrbfQtm1bREREGHzbJB0svmIqU6YMtm/fjho1aqBLly5ITU0VHYlIVmbOnIlBgwbBycnJKNvnig2Wj4c6S0iv12PChAnYu3cv9u/fX6qbZ4nozaSkpKB+/fo4deqU0YovKysLDg4OpXoSDEkbJ74SUigUCAsLQ3BwMDw9PXH58mXRkYgs3syZMzFw4ECjlR4A2NjYoE+fPrx/14Jx4jOAlStXYurUqfjll1/QtGlT0XGILFJKSgrq1auHxMREoxYfABw+fBijRo3CmTNnoFAojPpZZHqc+Axg+PDhWLhwIXx9fXkPEJGRmGLaK+Tp6YmMjAycOnXK6J9FpseJz4AOHjyIgQMHYsWKFejVq5foOEQWw5TTXqEpU6YgPT0dc+bMMcnnkemw+Azs+PHj6NmzJ7777jsMGzZMdBwiizBx4kQ8evQIixcvNtlnXrp0CV5eXkhOToZarTbZ55Lx8f+mgbVo0QKHDh2Cr68vUlNTMW7cONGRiMxaSkoKVqxYYfLDjnXr1oWLiwuioqK4QouF4Tk+I6hfvz7i4+OxcuVKTJo0ic/3JCqFWbNmoX///iY7xPm0oKAgrtNngXio04ju378PPz8/NG7cGEuXLuUT34mKqfDc3qlTp+Ds7Gzyz3/w4AFcXFxw48YN2Nvbm/zzyTg48RlRlSpVcODAAVy7dg39+/dHdna26EhEZmXWrFkYMGCAkNIDgMqVK6Nz587Yvn27kM8n4+DEZwI5OTkIDAxEamoqduzYATs7O9GRiCTv/v37qFevHk6ePCms+ABgx44dmDNnDmJjY4VlIMPixGcC1tbW2LJlC9zc3NCpUyekpKSIjkQkeYXn9kSWHgD4+fnh3LlzuHbtmtAcZDgsPhNRqVRYsmQJfH194eXlhRs3boiORCRZ9+/fx/LlyzFp0iTRUWBlZYUBAwZgw4YNoqOQgbD4TEihUOCbb77BRx99BE9PT1y4cEF0JCJJmjVrFvr16yd82isUHByMdevW8QptC8H7+AQYM2YMKleujI4dO2LXrl149913RUcikoz79+9j2bJlOHnypOgoTxT+HU1ISECrVq0Ep6HS4sQnSHBwMFasWIEePXogJiZGdBwiyZg9ezb69++Pt99+W3SUJxQKxZOpj8wfr+oU7PDhw+jbty8WL16Mvn37io5DJFThlZwnTpyQVPEBwLVr19CiRQskJyfD2tpadBwqBU58grVr1w5RUVEYPXo0li9fLjoOkVCzZ89G3759JVd6AFCrVi14eHggMjJSdBQqJU58EvHXX3/Bx8cHH374ISZOnMg1wEh2pDztFQoPD8eePXsQEREhOgqVAotPQm7dugVfX194e3tj5syZUCo5kJN8TJ48GQ8ePMCyZctER3mptLQ0ODs748qVK6hcubLoOFRCLD6JefjwIXr06IE6depg5cqV0Gg0oiMRGd2DBw9Qt25dSU97hQYNGgQvLy+MGjVKdBQqIY4UElOxYkVERUUhJSUFAQEByMrKEh2JyOikfG7veVyxwfxx4pOovLw8DB06FDdv3sTu3bv5ZHiyWIXT3h9//IFatWqJjvNa+fn5cHR0RGxsLOrVqyc6DpUAJz6J0mg0WL9+PRo3boz27dvjzp07oiMRGcXs2bMREBBgFqUHAGq1GoMHD+YjzMwYJz6J0+v1mDZtGtatW4fo6GjUrl1bdCQigzG3aa/QyZMn0bt3b1y5coUXoZkh/h+TOIVCgalTp2Ls2LHw8vLCmTNnREciMpg5c+aY1bRXqEmTJrCzs0NcXJzoKFQCnPjMyObNm/H5558jIiICbdq0ER2HqFTMddorFBYWhosXL2LlypWio1AxsfjMzL59+55cVdatWzfRcYhK7Msvv8Tdu3exYsUK0VFK5NatW/Dw8EBycjJsbGxEx6FiYPGZoaNHj+L999/H3LlzMWjQINFxiIqtcNo7fvy4WZ+39vHxQUhICAYOHCg6ChUDz/GZodatW+PAgQMYP348Fi5cKDoOUbHNmTMHffr0MevSA8AVG8wUJz4zdvXqVfj4+GDIkCH46quv+HxPMgupqalwc3Mz+2kPADIyMuDg4IA///wT1atXFx2H3hAnPjNWu3ZtxMfHY+fOnfj000+h0+lERyJ6LUuZ9gDA1tYWvXr1wubNm0VHoWLgxGcB0tLS4O/vDwcHB6xZswZWVlaiIxEVyZKmvUIHDhzAP//5T0mtGE+vxonPAtjb22Pfvn3IyMhAr169kJGRIToSUZHmzJmD3r17W0zpAUCHDh1w//593mNrRjjxWZD8/HwMHz4cly5dwp49e1CpUiXRkYieKJz2fv/9d7i4uIiOY1CTJk2CVqvFjBkzREehN8CJz4Ko1WqsWrUKbdq0Qbt27ZCcnCw6EtETc+fORe/evS2u9ICCFRs2btwIrVYrOgq9AbXoAGRYSqUSYWFhqFq1Kjw9PREVFQU3NzfRsUjmUlNTsXjxYhw7dkx0FKNo2LAhatSogYMHD8Lb21t0HHoNTnwWSKFQ4IsvvsDkyZPRvn17nnQn4ebOnYv333/fIqe9Qrynz3zwHJ+F++mnnzBy5Ehs374d7dq1Ex2HZMiSz+097d69e6hbty5u3rwJOzs70XHoFTjxWbiAgABs3rwZffv2xa5du0THIRmSw7QHANWqVYOXlxd+/vln0VHoNTjxycTvv/+Onj17Yvr06fjggw9ExyGZePjwIdzc3HDs2DGLLz4A2LZtG5YtW4aYmBjRUegVWHwy8ueff8LX1xefffYZxo4dKzoOycBXX32FpKQkhIeHi45iEtnZ2ahZsyYSExPh5OQkOg69BItPZm7evAkfHx/07t0b3377LZ/vSUYjt2mv0IgRI+Di4oKJEyeKjkIvwXN8MuPk5IS4uDjExMTgo48+4n1HZDRz586Fv7+/rEoPKLi6c/369eBMIV2c+GTq8ePH6N27NypUqICNGzfC2tpadCSyIIXTXkJCAlxdXUXHMSm9Xg9XV1ds27YNzZs3Fx2HisCJT6bs7Ozwyy+/AAC6d++OnJycl75Wp9Ph4sWLpopGFiA5ORnDhw+XXekBBffRBgUF8Z4+CePEJ3NarRbbt2+Hv78/bGxsinzN3r17MX78eIwbNw7Dhg0zcUIyR3l5eVCpVFAq5blv/ddff6FNmzZITk6GRqMRHYeeI8/vSnpCpVKhf//+Ly09AOjWrRv69u2LqVOn4v79+yZMR+ZKo9HItvQAoE6dOnBzc8P+/ftFR6EiyPc7k5543ZWdMTEx2LNnDxYsWIAqVaqYKBWReePhTunioU56pd9//x0fffQRPv30Ux7mpJfS6XSynvCKkpqaitq1a+P69euoUKGC6Dj0FH6n0gtu3boFALhw4QI+/fRTBAUFPSk97ifR0x4/fgwALL0iVKpUCd7e3ti2bZvoKPQcTnz0jKysLHTv3h0tWrTA2bNn0apVK0ydOhXA/5fe04dG79+/z8OfMjV16lRcvnwZ169fR0hICNq3b/9kCSytVguVSiU4oXi7du1CWFgY4uLiREehp7D46AU3btyAr68vsrOzcfXqVQAFq7urVKonpbdr1y6cPHkSR48eRdmyZbFp0yaUKVNGZGwyoW3btuGHH35AVFQUYmJi8NNPPyE3Nxe9evXiIfGn5ObmwsHBAQkJCbK7kV/KeHyCXuDs7Ix///vfcHJywr59+wAUrO5eWHrLly/Hpk2bUKVKFSxZsgSOjo4YNWqUyMhkYmfPnkXXrl1RuXJlDBgwAFu3bsWIESOwZMkSBAYGIi8vT3RESbCyssLAgQOxYcMG0VHoKSw+KlLFihXx66+/QqFQPLPMys8//4zdu3cjJCQEQ4YMQe3atTFw4EDY29sLTEumNnDgQFy4cAF79+5FWloaAMDPzw/Hjh2DUqnEtWvXxAaUkMIFanlwTTpYfPRSSqUSvr6+0Ov1SE5ORlpaGo4cOYLAwEC0adMGFSpUQHZ2NsaOHYsaNWqIjksm1KBBA/Ts2RNr167F6tWrkZiYiCtXriAnJwfR0dG8afspLVq0gFqtxtGjR0VHof/iOT56YykpKQgKCsLMmTPh4eEBoOBJ9FZWVli4cCGAggtguOKDfMTFxWHNmjXIzs6GUqlEUlIS3nvvPfzwww+io0nKd999hxs3bmDp0qWioxBYfFQMJ0+exCeffIIDBw7AxsYGgwYNgq2tLSZNmiTLZzLKUeGOzfM7OGfPnoVSqUS5cuVQrVo1Xuj0nBs3bqBp06a4desWHwgvAWrRAch8NG3aFD4+PmjWrBkaNmwIAFi6dCnP78mIQqGATqd75p8VCgU8PDyQn58PtVrNc1lFcHZ2RqNGjbBnzx4EBASIjiN7nPio2M6dOwc7Ozs4OzuLjkImtHr1anTt2vXJ+VydTge9Xg+VSoW8vDysXr0aQUFBr3zuq5ytXr0aO3bswM6dO0VHkT0WH5VK4aOq+Mgqy7Z9+3YMGjQI7u7u6NChAyZMmICaNWs++fqxY8dw584d+Pv7C0wpbY8ePYKzszP++usvPvRBMP6kolJRKpXQarW4evUqjh07JjoOGcnevXsxZ84c7Nq1Czk5OfD19cXo0aPx4MEDAAUPMu/YsaPglNJWvnx5dO/eHVu2bBEdRfZYfFRqKpUK165dQ/fu3Z/c8E6WZeHChfD394ezszOWLFmCzZs3Iy8vD35+fqhduzb++OMP2NnZiY4peVyxQRp4qJMM5t///jd69+6NuXPnYtCgQaLjkAn88ccf8PT0xPnz51G7dm3RcSQvPz8fTk5OOHToEOrXry86jmxx4iODadOmDWJiYjB+/HgsWrRIdBwygaNHj2LAgAEsvTekVqsxZMgQrF+/XnQUWePERwZ39epV+Pj4IDAwEFOnTuUN7RYkJycHer3+yX16WVlZyMvLQ/ny5QUnMx+JiYno2bMnrl27xgvCBOGfOhlc7dq1ER8fj4iICIwePfrJfV9k3tLS0lC3bt0na/ABgI2NDUuvmBo3boyKFSsiNjZWdBTZYvGRUbz11luIjY3F6dOnERgYiNzcXNGRqJQWLFiA9u3bo2rVqqKjmL3g4GAe7hSIhzrJqLKysjBgwADk5eVh+/btsLW1FR2JSiAtLQ116tTBkSNHULduXdFxzN7t27fRsGFDJCcno2zZsqLjyA4nPjIqGxsb/Pzzz6hWrRq8vb2RmpoqOhKVwIIFC9C1a1eWnoHUqFED7733Hnbs2CE6iiyx+Mjo1Go1Vq9ejVatWqF9+/a4deuW6EhUDI8ePcK8efPw5Zdfio5iUXi4UxwWH5mEUqnErFmzMHjwYHh6euKvv/4SHYneUOG0V69ePdFRLMr777+P3377Dbdv3xYdRXZ4jo9Mbvny5fj6668RGRmJJk2aiI5Dr/Do0SO4uroiPj6exWcEw4YNg4eHB8aNGyc6iqxw4iOTGzFiBObPnw8fHx8cPnxYdBx6hQULFsDX15elZyTBwcF8hJkAnPhImJiYGAwePBjh4eHo2bOn6Dj0nMJpLy4ujo/XMhKdTodatWph9+7daNy4seg4ssGJj4Tp0qUL9uzZgw8//JB7vRK0cOFC+Pr6svSMSKlUIjAwkBe5mBgnPhLuwoUL8PX1xZgxYzBmzBjRcQgF016dOnVw+PBhFp+RXbhwAZ06dcLNmzehVqtFx5EFTnwkXIMGDRAfH49ly5bhf/7nf8B9MfEWLlwIHx8flp4JNGjQAG+//TZOnTolOopscOIjyUhJSYGfnx+aNWuGxYsXQ6VSiY4kS5z2TC87Oxt6vR42Njaio8gCJz6SjKpVq+LgwYP466+/MHDgQOTk5IiOJEsLFy6Et7c3S8+EypQpw9IzIU58JDk5OTkYPHgw0tLSEBERwZW9Tejx48dwdXXltEcWjRMfSY61tTW2bt2K2rVro3Pnzrh//77oSLLBaU9atFotDhw4gGnTpomOYlE48ZFk6fV6TJ48GTt27EBUVBScnJxER7JonPak6cyZM+jSpQv+/vtvlCtXTnQci8CJjyRLoVDg+++/x/Dhw+Hp6Yk///xTdCSLxmlPrMTExGf+/f79+9i0aRNmz56NvLw8nD17VlAyy8OJj8zCmjVrMGnSJOzevRstWrQQHcfiFE57sbGxaNCggeg4stStWzcEBQWhQYMGWL58ORISElCxYkX07t0bgwcPRqVKlURHtBi8W5LMwtChQ1GxYkX4+flhy5Yt6NSpk+hIFmXRokXo0qULS0+gfv36ITAwEO3atUObNm2wadOmZ6ZvnU4HpZIH6QyBEx+ZldjYWPTr1w9Lly5Fnz59RMexCJz2pCEnJweVKlVCamoqrK2tn/y+VqvlPa0Gpvr666+/Fh2C6E3VqlULXbp0QWBgIOzt7dGsWTPRkczenDlzYGtri48//lh0FFlTq9WoUKECbGxsUL16dWi1WiiVSigUCgAF57z1ev2Tf6eS48RHZuny5cvw8fHBxx9/jAkTJvCHQQlx2pOWpKQkxMXFYdCgQZz0jIjn+Mgsubm5IT4+Hr6+vkhJSUFYWBjLrwQWLVqEzp07s/QkwtHREampqUhPT39y68K5c+cQExMDtVoNZ2dn1KlTh/+/SokTH5m11NRUdO/eHfXr18eKFSv4dPtiSE9Ph6urKw4dOoSGDRuKjkP/lZGRAVtbW5w8eRJLly7FrVu34O7ujkqVKuHUqVNITk5GbGys6JhmjcVHZi8jIwMBAQGwtrbGli1b+MzDNzR9+nScOnUKmzdvFh2FnvPw4UNMmTIFrq6u8Pb2Rs2aNaHRaGBnZwdPT0+MGTMGAQEBomOaLV4bS2bP1tYWu3btgo2NDbp164a0tDTRkSQvPT0ds2fPxpQpU0RHoSIsWbIE2dnZCAkJgYeHBypVqgQ7OzvcunULdevWhZubm+iIZo3FRxbBysoKGzduhLu7Ozp27Ih79+6JjiRpixYtQqdOnXiIU6I0Gg1ycnJgb28PAIiOjsbIkSPRoUMHVNNGvWYAABbaSURBVK5cGR4eHoITmjce6iSLotfr8fXXX2Pz5s2IiopCrVq1REeSHJ7bk76UlBSEhoZCo9Hg/PnzqFevHlq3bo2AgADUqVNHdDyzx+Iji7RgwQLMmDED+/btg7u7u+g4kjJjxgycOHECW7ZsER2FXiE3NxexsbFwcXFBtWrVYGVlBWtraxT+yOZVzCXH4iOLtXHjRowdOxY7duxA69atRceRhMJp7+DBg9whINniOT6yWEOGDMHq1avh7++P/fv3i44jCYsXL0bHjh1ZeiRrnPjI4h05cgR9+vTBvHnzMHDgQNFxhOG0Z75yc3Oh0Wh4eNNAeLcvWby2bdsiJiYG3bp1Q2pqKkaNGiU6khCLFy9Ghw4dWHpmKCIiAvb29ujatavoKBaBxUey8M477+Dw4cPw8fHB/fv3MWXKFFntPWdkZGD27NmIiYkRHYVKIDs7Gxs2bGDxGQgPdZKs3LlzB127dkW7du0wd+5c2axvFhYWhuPHj+PHH38UHYVK4PHjx3BycsKlS5dQrVo10XHMHouPZOc///kPevbsCWdnZ6xZswYajUZ0JKPKyMiAq6srYmJieOOzGQsKCkLLli0xevRo0VHMnjx2d4meUqFCBezfvx+PHj3C+++/j8zMTNGRjGrx4sVo3749S8/MBQUFYd26daJjWAROfCRbeXl5CA0NxZUrV7B7925UrFhRdCSD47RnObRaLZydnREdHc0n7pQSJz6SLY1GgzVr1qBly5Zo3749bt++LTqSwS1ZsgTt2rVj6VkAlUqFIUOGYP369aKjmD1OfCR7er0e33//PcLDwxEVFQVXV1fRkQyC057lOXPmDPz8/HDt2jWuzl4KnPhI9hQKBSZPnowJEyagXbt2SExMFB3JIDjtWZ533nkHVapUwa+//io6ilnjxEf0lG3btuGTTz7BTz/9BC8vL9FxSozTnuWaM2cOEhMTsWbNGtFRzBaLj+g50dHRGDJkCFatWoUePXqIjlMiM2fOREJCArZt2yY6ChnYnTt3UL9+fSQnJ8PW1lZ0HLPEQ51Ez/H29saePXswfPhws7x8PCMjAzNnzsTUqVNFRyEjqF69Otq0aYOIiAjRUcwWi4+oCO+++y4OHTqEL7/8EnPnzhUdp1iWLl0KLy8vvPPOO6KjkJEEBwfz6s5S4KFOole4ceMGvL290a9fP0ybNk3yz/csPLcXHR3N4rNgWVlZcHBwwJkzZ+Dg4CA6jtnhxEf0Cs7OzoiPj8e+ffswcuRIaLVa0ZFeidOePNjY2KB3797YtGmT6ChmiRMf0RsofLxZlSpVsH79elhbW4uO9ILMzEy4uLhw2pOJ2NhY/OMf/8Dp06clfyRCajjxEb2B8uXLIzIyEvn5+ejZsyfS09NFR3rB0qVL4enpydKTCS8vLzx+/Nhi7js1JRYf0RsqU6YMtm7dCmdnZ3Tu3BkPHjwQHemJzMxMhIWF8UpOGVEqlQgMDDTLK49FY/ERFYNarcaKFSvQsWNHeHl5ISkpSXQkAAXTXtu2bdGoUSPRUciEgoKCsGnTJuTn54uOYlZYfETFpFAo8MMPPyAkJASenp64ePGi0Dyc9uSrXr16qFWrFqKjo0VHMSssPqIS+uc//4mvvvoKHTp0wB9//CEsx9KlS9GmTRtOezIVHBzMw53FxKs6iUppx44dGDFiBH788Ud07NjRpJ+dmZkJV1dX7Nu3D40bNzbpZ5M0PHjwAC4uLrhx4wbs7e1FxzELnPiISun999/H1q1bMWDAAPz8888m/exly5ahTZs2LD0Zq1y5Mjp16oSffvpJdBSzwYmPyEBOnDiBHj16YNq0aQgNDTX653Hao0IRERGYN28elyt6Qyw+IgO6dOkSfHx8MGrUKEyYMMGonzVnzhzEx8dzT5+Qk5MDBwcHHD9+HLVq1RIdR/JYfEQGlpSUBF9fX3Tv3h3Tp083ylM1OO3R80aNGoWaNWviyy+/FB1F8niOj8jAHB0dcfjwYRw+fBjDhw83yj1Wy5cvR+vWrVl69EThig2cZV6PEx+RkaSnpyMgIABly5bF5s2bUaZMGYNsNysrC66uroiMjESTJk0Msk0yf3q9HvXq1cP69evx3nvviY4jaZz4iIykXLly2L17N6ytrdGtWzc8evTIINtdtmwZWrVqxdKjZygUCgQFBfGevjfAiY/IyLRaLT799FMkJCRg7969qFatWom3xWmPXuXq1at49913kZycDCsrK9FxJIsTH5GRqVQqLFq0CD169ICnpyeuX79e4m1x2qNXqV27Nho2bIjIyEjRUSSNEx+RCc2fPx9hYWHYt28f3N3di/VeTnv0JlauXInIyEiTP0zBnLD4iExs48aNGDt2LHbu3IlWrVo9+X2dDjhwAJgxA/jtNyAzE1CpgIoVgQ8+AMqWXYXExN2IiIgQmJ6kLi0tDc7Ozrhy5QoqV64sOo4ksfiIBIiMjMQHH3yADRs2wNfXFz/+CIwZAzx+DBS1xq21tR45OTlo2TIPP/1kBycn02cm8zFw4EC0b98eI0eOFB1Fklh8RIIcOXIEffr0QceO0di9uxEyM1//HpUKsLcHYmMBDw/jZyTz9Msvv+Cbb77B0aNHRUeRJBYfkUBffpmEb7+tBKBssd5XqRKQmAg4OhonF5m3vLw8ODo6Ii4uDnXr1hUdR3J4VSeRIHfvArNmOaK4pQcAaWnAiBGGz0SWQaPRYPDgwdiwYYPoKJLE4iMSZPnykr9XqwUOHQJu3TJcHrIshY8w0+l0oqNIDouPSACtFpg3D8jOLvk29HpgyRLDZSLL0qRJE9ja2iI+Pl50FMlh8REJ8NtvQG5u6baRkwOsWWOQOGSBFAoFgoOD+QizIrD4iAS4dw8wxGpFDx+WfhtkuYYMGYKff/4ZWVlZoqNICouPSIC8PMNsR6s1zHbIMjk4OKB58+bYtWuX6CiSwuIjEqBiRcNMfLa2pd8GWTYe7nwRi49IgBYtCs7RlYZCoUPbtqU8UUgWr3fv3jhy5Aju3r0rOopksPiIBKhYEejTB1CW4m+gUpmLAwe6ISgoCL/++itX3qYilStXDr169cLmzZtFR5EMFh+RIOPGAaVZlN3FpQyuXNmCZs2a4R//+Afc3Nzw3XffITk52XAhySJwgdpnsfiIBGnWDOjcGbCxKf57bWyABQuAatWqYsyYMThz5gw2btyIa9euwcPDAz169EBERATyDHUVDZm1jh074t69ezh79qzoKJLAZ3USCZSdDXh5AefOAW96xXnZssCsWcDHHxf99YyMDGzbtg3h4eG4fPkygoKCEBoaivr16xsuOJmdiRMnQq/XY/r06aKjCMfiIxIsOxsYNAjYv7/gpvaX3aJQ9r+P9Fy9Gujf/822fenSJaxatQpr166Fi4sLQkND0b9/f5QrV84w4clsnDt3Dj4+Prhx4wZUKpXoOEKx+Igk4swZYM4cYMsWQKMp+D2FAsjPL1iNYfx4IDi4YFmi4srLy8PevXsRHh6Ow4cPo0+fPggNDUXr1q2hMMR9FWQWmjdvjh9++AHe3t6iowjF4iOSmEePCkrw4UPAygp46y2gUSPD3PcHALdv38a6deuwatUqqFQqhISEIDg4GNWqVTPMB5BkzZs3D3/88YfsL3Rh8RHJlF6vR3x8PFatWoUdO3agY8eOCA0Nha+vL9Rqteh4ZAT37t1D3bp1kZSUJOvD3Sw+IsKjR4/w448/Ijw8HDdv3sTQoUMREhICV1dX0dHIwHr06IH+/fsjODhYdBRheDsDEaF8+fL48MMP8dtvv2H//v3IyspC69at0bFjR2zYsAGZmZmiI5KBFK7TJ2ec+IioSLm5udi1axfCw8ORkJCAAQMGIDQ0FM2bN+cFMWYsKysLDg4OOH36NBwdHUXHEYITHxEVycrKCn379sXevXuRmJiImjVrol+/fmjSpAnmz5+PBw8eiI5IJWBjY4OAgABs3LhRdBRhOPER0RvT6XQ4dOgQwsPDERkZia5duyI0NBSdO3eGsjQPHiWTiouLw8cff4yzZ8/Kcnpn8RFRiTx8+BCbNm1CeHg4UlNTMWzYMAwbNgzOzs6io9Fr6HQ61KlTB9u3b0ezZs1ExzE57qIRUYlUrFgRn3zyCU6cOIGIiAikpKSgadOm8PX1xY8//oic0q67REajVCoRGBgo2/v5OPERkcFkZWUhIiIC4eHhOH36NAYPHozQ0FA0atRIdDR6zuXLl+Hp6YmkpCRoCh8VJBOc+IjIYGxsbDB48GAcOHAACQkJsLe3R/fu3dGyZUssXboUaWlpoiPSf7m5ucHV1RVRUVGio5gcJz4iMiqtVovo6GiEh4cjOjoa/v7+CA0NRbt27WR5YYWULF26FIcOHcKPP/4oOopJsfiIyGRSUlKwYcMGhIeHIycnByEhIfjggw9Qs2ZN0dFkKTU1FbVr18b169dRoUIF0XFMhoc6ichkqlb9/4VzN2zYgKtXr8Ld3Z0L5wpSqVIldOnSBdu3bxcdxaQ48RGRUFw4V6ydO3di1qxZOHz4sOgoJsPiIyLJuHjxIlatWoV169Zx4VwTyc3NhYODAxISEuDi4iI6jknwUCcRSUa9evUwffp03LhxA1988QV27twJJycnDB8+HEePHkVx99Pv3r1rpKSWw8rKCgMGDMCGDRtERzEZFh8RSY5Go4G/vz927tyJ8+fPw83NDUOHDoW7uztmzZqFe/fuvXYber0eEyZMQO3atREWFlbs0pSTwhUb5PJnxOIjIkmrUaMGvvjiC/z5559YtmwZzpw5g7p166JPnz745ZdfkJ+fX+T78vPzMXPmTPj7++PIkSNQKBSy+cFeXC1btoRSqcRvv/0mOopJsPiIyCwoFAp4eXlhzZo1uHHjBrp164Zp06ahVq1auHPnzguv12g0sLe3x8WLFzFs2DAABc+oBMACfI5CoUBwcLBsHmHGi1uIyKxdvnwZb7/9NqysrF74Wnx8PEaPHo0TJ0688LX8/HysXr0a+/btQ4sWLTB27FhYW1ubIrIkXb9+Hc2bN0dycrLF/zlw4iMis+bm5vZC6RXuz2/duhXe3t4ACp4gUygzMxOzZ8/G7t278eGHHyI+Ph67du0yXWgJevvtt/HOO+/gl19+ER3F6Fh8RGRxFAoFcnNzERcXh8DAwCe/V3ioc+fOnbhy5QqmTp2Krl27YuzYsVi9erXIyJIQFBQki8OdatEBiIgMKTk5GYsWLYJGo3kyxQB45rmge/bsQZcuXeDu7g4AiI6OhpubG4CCyVClUpk+uAT07dsXY8aMwf3791GlShXRcYyGEx8RWRQ7OzsoFAqsXbsWMTExiI+PR05ODhQKBRQKBf7++2/k5+ejefPmsLGxAQCcO3cOXbt2BQDZlh4AlC9fHt27d7f4h1az+IjIopQvXx7ffvstrl27hm3btuH27dvYsmULtm7diry8PGi1Wtja2j55/d69e6FUKuHh4SEwtXTI4XAnD3USkcXq1q0bACAnJwfnz5+HRqOBi4vLM7c/zJgxA3379oWTk5OomJLi7e2NkJAQXLx4EfXq1RMdxyg48RGRxbO2tkbTpk0BFJzr6969O3r06AFfX180aNAAn3zyyTOv1+l0uH79uiwXzlWr1Rg8eDDWr18vOorR8D4+IpIlnU6H8+fPPznEqdfrn1wAk5+fj++//x6zZs2S5cK5iYmJ8Pf3x9WrV6FUWt58xOIjInoJOS+c26hRI8yfPx8dOnQQHcXgLK/KiYgMpKiFcz08PNCzZ0/s2LHDohfOLXxwtSXixEdEVAzPL5wbHByMkJAQi1s499atW3B3d0dycjLKli0rOo5BceIjIioGW1tbDB06FHFxcYiNjYVCoUDHjh3Rtm1brFq1Cunp6aIjGkTNmjXx7rvvYufOnaKjGBwnPiKiUsrLy0NkZCRWrVqFw4cPIyAgAKGhoWjVqpVZXxCzceNGbNiwAXv37hUdxaBYfEREBnT79m2sW7cO4eHhUKvVCA0NRVBQEKpVqyY6WrFlZGTA0dERFy5cQPXq1UXHMRge6iQiMqDChXMvXrz4zMK5AQEBiIyMfGaVCKmztbVFr169sGnTJtFRDIoTHxGRkT169AhbtmxBeHg4kpOT8cEHHyAkJASurq6io73WwYMHMXbsWJw6dUp0FIPhxEdEZGTly5fHiBEjkJCQgH379iErKwutW7dGx44dsWHDBmRlZYmO+FIdOnRAamoqTp8+LTqKwXDiIyISIDc3F7t27UJ4eDiOHTuGAQMGIDQ0FM2aNZPcBTGTJ09GXl4ewsLCREcxCBYfEZFgN2/exJo1a7Bq1SrY29sjNDQUQ4YMQaVKlURHAwBcuHABnTt3xo0bN6BWm//aBjzUSUQkmJOTE6ZMmYK///4bs2bNwtGjR+Hi4oJBgwYhJibmycrxojRo0AAODg44cOCA0ByGwomPiEiCUlNTsWnTJoSHh+Phw4cYNmwYhg0bBmdnZyF5FixYgISEBGzYsEHI5xsSi4+ISOJOnjyJ8PBwbN68GS1atEBoaCh69eoFa2trk2VISUlBnTp1kJSUBDs7O5N9rjGw+IiIzERWVhYiIiIQHh6O06dPY8iQIQgNDcU777xjks/39/dHnz59MHToUJN8nrHwHB8RkZmwsbHB4MGDceDAASQkJMDOzg5+fn549913sWzZMqMvnGspKzZw4iMiMmNarRZRUVEIDw9HTEwMevXqhdDQUHh5eRn8tojs7Gw4ODjg5MmTws41GgKLj4jIQphi4dyPPvoItWrVwqRJkwy2TVNj8RERWRi9Xo9jx44hPDwc27dvR9u2bREaGoru3btDo9GUattHjhzBhx9+iHMHDkBx+jSQlgaUKQM4OADNmgESu/m+KCw+IiILZtCFc/V66GNjccjPDx20WihtbACdrqDsdDqgUiVg/HggOBgoX97w/zEGwuIjIpKJixcvYtWqVVi3bh1cXV0RGhqKfv36oVy5cq9/c2oq0K0bcP48dOnpL78y0ta24NetWwE/P0NFNygWHxGRzBQunBseHo64uLjXL5z74AHQogVw6xaQm/tmH2JjA6xaBQwcaNjwBsDiIyKSsacXztVoNAgJCXl24VytFmjZEjh37s1Lr5CNDXDgANC6teGDlwKLj4iIoNfrER8fj/DwcOzYsQOdO3dGaGgofHNzoQoKAtLTS7bhNm2AI0cMG7aUWHxERPSMpxfOXXDqFN4t7qT3tDJlgDNngDp1DBewlFh8RERUtL//hs7dHcqcnJJvQ6MBPvoIWLDAcLlKiY8sIyKiov3731CW8r4/5OUB0dGGyWMgLD4iIiraf/5TUFylZeRniBYXi4+IiIqm0QBKA9REaadGA2PxERFR0d56C1CrDbMdCWHxERFR0Xx9C+7jK41y5YARIwyTx0BYfEREVLSyZYGhQ0t3qFKnAwYPNlgkQ2DxERHRy332GaBSley91tYFD6wufH6nRLD4iIjo5erWBaZOLZj+ikOlKliq6IcfjJOrFFh8RET0ahMnAp988ublZ2UFODkBhw8D9vbGzVYCLD4iIno1hQKYMQNYvBioUaPggpWi2NgUPKIsIAA4ebJg4pMgPrKMiIjenE4HxMQUFOGJE0BGRsGEV7UqMHIkEBICVK4sOuUrsfiIiEhWeKiTiIhkhcVHRESywuIjIiJZYfEREZGssPiIiEhWWHxERCQrLD4iIpIVFh8REckKi4+IiGSFxUdERLLC4iMiIllh8RERkayw+IiISFZYfEREJCssPiIikhUWHxERyQqLj4iIZIXFR0REssLiIyIiWWHxERGRrLD4iIhIVlh8REQkK/8HbwxVNIU0VrIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "layout = nx.random_layout(G, seed=10)\n",
    "colors = ['r', 'g', 'b', 'y']\n",
    "nx.draw(G, layout, node_color=colors)\n",
    "labels = nx.get_edge_attributes(G, 'weight')\n",
    "nx.draw_networkx_edge_labels(G, pos=layout, edge_labels=labels);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute-force method is as follows. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a vertex is either 0 (meaning the vertex is in the first partition) or 1 (meaning the vertex is in the second partition). We print the binary assignment that satisfies the definition of the graph partition and corresponds to the minimal number of crossing edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective value computed by the brute-force method is 3\n"
     ]
    }
   ],
   "source": [
    "def objective_value(x, w):\n",
    "    X = np.outer(x, (1 - x))\n",
    "    w_01 = np.where(w != 0, 1, 0)\n",
    "    return np.sum(w_01 * X)\n",
    "\n",
    "def brute_force():\n",
    "    # use the brute-force way to generate the oracle\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]  # [2:] to chop off the \"0b\" part\n",
    "\n",
    "    L = num_nodes\n",
    "    max = 2**L\n",
    "    minimal_v = np.inf\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "\n",
    "        how_many_nonzero = np.count_nonzero(cur)\n",
    "        if how_many_nonzero * 2 != L:  # not balanced\n",
    "            continue\n",
    "\n",
    "        cur_v = objective_value(np.array(cur), w)\n",
    "        if cur_v < minimal_v:\n",
    "            minimal_v = cur_v\n",
    "    return minimal_v\n",
    "\n",
    "sol = brute_force()\n",
    "print(f'Objective value computed by the brute-force method is {sol}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph partition problem can be converted to an Ising Hamiltonian. Qiskit has different capabilities in the Optimization module to do this. Here, since the goal is to show QAOA, the module is used without further explanation to create the operator. The paper [Ising formulations of many NP problems](https://arxiv.org/abs/1302.5843) may be of interest if you would like to understand the technique further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.quantum_info import Pauli\n",
    "from qiskit.opflow import PauliSumOp\n",
    "\n",
    "def get_operator(weight_matrix):\n",
    "    r\"\"\"Generate Hamiltonian for the graph partitioning\n",
    "    Notes:\n",
    "        Goals:\n",
    "            1 separate the vertices into two set of the same size\n",
    "            2 make sure the number of edges between the two set is minimized.\n",
    "        Hamiltonian:\n",
    "            H = H_A + H_B\n",
    "            H_A = sum\\_{(i,j)\\in E}{(1-ZiZj)/2}\n",
    "            H_B = (sum_{i}{Zi})^2 = sum_{i}{Zi^2}+sum_{i!=j}{ZiZj}\n",
    "            H_A is for achieving goal 2 and H_B is for achieving goal 1.\n",
    "    Args:\n",
    "        weight_matrix (numpy.ndarray) : adjacency matrix.\n",
    "    Returns:\n",
    "        PauliSumOp: operator for the Hamiltonian\n",
    "        float: a constant shift for the obj function.\n",
    "    \"\"\"\n",
    "    num_nodes = len(weight_matrix)\n",
    "    pauli_list = []\n",
    "    shift = 0\n",
    "\n",
    "    for i in range(num_nodes):\n",
    "        for j in range(i):\n",
    "            if weight_matrix[i, j] != 0:\n",
    "                x_p = np.zeros(num_nodes, dtype=bool)\n",
    "                z_p = np.zeros(num_nodes, dtype=bool)\n",
    "                z_p[i] = True\n",
    "                z_p[j] = True\n",
    "                pauli_list.append([-0.5, Pauli((z_p, x_p))])\n",
    "                shift += 0.5\n",
    "\n",
    "    for i in range(num_nodes):\n",
    "        for j in range(num_nodes):\n",
    "            if i != j:\n",
    "                x_p = np.zeros(num_nodes, dtype=bool)\n",
    "                z_p = np.zeros(num_nodes, dtype=bool)\n",
    "                z_p[i] = True\n",
    "                z_p[j] = True\n",
    "                pauli_list.append([1, Pauli((z_p, x_p))])\n",
    "            else:\n",
    "                shift += 1\n",
    "                \n",
    "    pauli_list = [(pauli[1].to_label(), pauli[0]) for pauli in pauli_list]\n",
    "    return PauliSumOp.from_list(pauli_list), shift\n",
    "\n",
    "qubit_op, offset = get_operator(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So lets use the QAOA algorithm to find the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 1. 1. 0.]\n",
      "Objective value computed by QAOA is 4.0\n"
     ]
    }
   ],
   "source": [
    "from collections import OrderedDict\n",
    "from qiskit.utils import algorithm_globals\n",
    "from qiskit.algorithms import QAOA\n",
    "from qiskit.opflow import StateFn\n",
    "from qiskit.algorithms.optimizers import COBYLA\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "def sample_most_likely(state_vector):\n",
    "    \"\"\"Compute the most likely binary string from state vector.\n",
    "    Args:\n",
    "        state_vector (numpy.ndarray or dict): state vector or counts.\n",
    "    Returns:\n",
    "        numpy.ndarray: binary string as numpy.ndarray of ints.\n",
    "    \"\"\"\n",
    "    if isinstance(state_vector, (OrderedDict, dict)):\n",
    "        # get the binary string with the largest count\n",
    "        binary_string = sorted(state_vector.items(), key=lambda kv: kv[1])[-1][0]\n",
    "        x = np.asarray([int(y) for y in reversed(list(binary_string))])\n",
    "        return x\n",
    "    elif isinstance(state_vector, StateFn):\n",
    "        binary_string = list(state_vector.sample().keys())[0]\n",
    "        x = np.asarray([int(y) for y in reversed(list(binary_string))])\n",
    "        return x\n",
    "    else:\n",
    "        n = int(np.log2(state_vector.shape[0]))\n",
    "        k = np.argmax(np.abs(state_vector))\n",
    "        x = np.zeros(n)\n",
    "        for i in range(n):\n",
    "            x[i] = k % 2\n",
    "            k >>= 1\n",
    "        return x\n",
    "\n",
    "def objective_value(x, w):\n",
    "    \"\"\"Compute the value of a cut.\n",
    "    Args:\n",
    "        x (numpy.ndarray): binary string as numpy array.\n",
    "        w (numpy.ndarray): adjacency matrix.\n",
    "    Returns:\n",
    "        float: value of the cut.\n",
    "    \"\"\"\n",
    "    X = np.outer(x, (1 - x))\n",
    "    w_01 = np.where(w != 0, 1, 0)\n",
    "    return np.sum(w_01 * X)\n",
    "\n",
    "algorithm_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "qaoa = QAOA(optimizer, quantum_instance=Aer.get_backend('statevector_simulator'))\n",
    "\n",
    "result = qaoa.compute_minimum_eigenvalue(qubit_op)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "\n",
    "print(x)\n",
    "print(f'Objective value computed by QAOA is {objective_value(x, w)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The outcome can be seen to match to the value computed above by brute force. But we can also use the classical `NumPyMinimumEigensolver` to do the computation, which may be useful as a reference without doing things by brute force."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 1 0 0]\n",
      "Objective value computed by the NumPyMinimumEigensolver is 3\n"
     ]
    }
   ],
   "source": [
    "npme = NumPyMinimumEigensolver()\n",
    "result = npme.compute_minimum_eigenvalue(qubit_op)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "\n",
    "print(x)\n",
    "print(f'Objective value computed by the NumPyMinimumEigensolver is {objective_value(x, w)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is also possible to use VQE as is shown below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 1. 0. 1.]\n",
      "Objective value computed by VQE is 3.0\n"
     ]
    }
   ],
   "source": [
    "from qiskit.algorithms import VQE\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "algorithm_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "ansatz = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')\n",
    "vqe = VQE(ansatz, optimizer, quantum_instance=Aer.get_backend('statevector_simulator'))\n",
    "\n",
    "result = vqe.compute_minimum_eigenvalue(qubit_op)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "\n",
    "print(x)\n",
    "print(f'Objective value computed by VQE is {objective_value(x, w)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<h3>Version Information</h3><table><tr><th>Qiskit Software</th><th>Version</th></tr><tr><td><code>qiskit-terra</code></td><td>0.21.0</td></tr><tr><td><code>qiskit-aer</code></td><td>0.10.4</td></tr><tr><td><code>qiskit-ignis</code></td><td>0.6.0</td></tr><tr><td><code>qiskit-ibmq-provider</code></td><td>0.19.2</td></tr><tr><td><code>qiskit</code></td><td>0.37.0</td></tr><tr><td><code>qiskit-machine-learning</code></td><td>0.4.0</td></tr><tr><th>System information</th></tr><tr><td>Python version</td><td>3.7.7</td></tr><tr><td>Python compiler</td><td>MSC v.1916 64 bit (AMD64)</td></tr><tr><td>Python build</td><td>default, May  6 2020 11:45:54</td></tr><tr><td>OS</td><td>Windows</td></tr><tr><td>CPUs</td><td>8</td></tr><tr><td>Memory (Gb)</td><td>15.872657775878906</td></tr><tr><td colspan='2'>Fri Jul 15 21:05:43 2022 Hora de verano romance</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div style='width: 100%; background-color:#d5d9e0;padding-left: 10px; padding-bottom: 10px; padding-right: 10px; padding-top: 5px'><h3>This code is a part of Qiskit</h3><p>&copy; Copyright IBM 2017, 2022.</p><p>This code is licensed under the Apache License, Version 2.0. You may<br>obtain a copy of this license in the LICENSE.txt file in the root directory<br> of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.<p>Any modifications or derivative works of this code must retain this<br>copyright notice, and modified files need to carry a notice indicating<br>that they have been altered from the originals.</p></div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import qiskit.tools.jupyter\n",
    "%qiskit_version_table\n",
    "%qiskit_copyright"
   ]
  },
  {
   "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}