MAXCUT_EN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-01-06T07:10:17.389768Z",
     "start_time": "2021-01-06T07:10:17.379639Z"
    }
   },
   "source": [
    "# Solving Max-Cut Problem with QAOA\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-01-06T07:12:18.621281Z",
     "start_time": "2021-01-06T07:12:18.308211Z"
    }
   },
   "source": [
    "## Overview\n",
    "\n",
    "In the [tutorial on Quantum Approximate Optimization Algorithm](./QAOA_EN.ipynb), we talked about how to encode a classical combinatorial optimization problem into a quantum optimization problem and slove it with Quantum Approximate Optimization Algorithm [1] (QAOA). In this tutorial, we will take the Max-Cut Problem as an example to further elaborate on QAOA.\n",
    "\n",
    "### Max-Cut Problem\n",
    "\n",
    "The Max-Cut Problem is a common combinatorial optimization problem in graph theory, and it has important applications in statistical physics and circuit design. The maximum cut problem is an NP-hard problem, so there is no efficient algorithm that can solve this problem perfectly.\n",
    "\n",
    "In graph theory, a graph is represented by a pair of sets $G=(V, E)$, where the elements in the set $V$ are the vertices of the graph, and each element in the set $E$ is a pair of vertices, representing an edge connecting these two vertices. For example, the graph in the figure below is represented by $V=\\{0,1,2,3\\}$ and $E=\\{(0,1),(1,2),(2,3),(3, 0)\\}$.\n",
    "\n",
    "![G](figures/maxcut-fig-maxcut_g.png \"Figure 1: A graph with four vertices and four edges\")\n",
    "<div style=\"text-align:center\">Figure 1: A graph with four vertices and four edges </div>\n",
    "\n",
    "A cut on a graph refers to a partition of the graph's vertex set $V$ into two disjoint sets. Each cut corresponds to a set of edges, in which the two vertices of each edge are divided into different sets. So we can define the size of this cut as the size of this set of edges, that is, the number of edges being cut. The Max-Cut Problem is to find a cut that maximizes the number of edges being cut. Figure 2 shows a maximum cut of the graph in Figure 1. The size of the maximum cut is $4$, which means that all edges in the graph are cut.\n",
    "\n",
    "![Max cut on G](figures/maxcut-fig-maxcut_cut.png \"Figure 2: A maximum cut of the graph in Figure 1\")\n",
    "<div style=\"text-align:center\">Figure 2: A maximum cut of the graph in Figure 1 </div>\n",
    "\n",
    "Assuming that the input graph $G=(V, E)$ has $n=|V|$ vertices and $m=|E|$ edges, we can describe the Max-Cut Problem as a combinatorial optimization problem with $n$ bits and $m$ clauses. Each bit corresponds to a vertex $v$ in the graph $G$, and its value $z_v$ is $0$ or $1$, corresponding to the vertex belonging to the set $S_{0}$ or $S_{1}$, respectively. Thus, each value $z$ of these $n$ bits corresponds to a distinct cut. Each clause corresponds to an edge $(u,v)$ in the graph $G$. A clause requires that the two vertices connected by its corresponding edge take different values, namely $z_u\\neq z_v$, which means the edge is cut. In other words, when the two vertices connected by the edge are divided into different sets, we say that the clause is satisfied. Therefore, for each edge $(u,v)$ in the graph $G$, we have\n",
    "\n",
    "$$\n",
    "C_{(u,v)}(z) = z_u+z_v-2z_uz_v,\n",
    "\\tag{1}\n",
    "$$\n",
    "\n",
    "where $C_{(u,v)}(z) = 1$ if and only if the edge is cut. Otherwise, the function is equal to $0$. The objective function of the entire combinatorial optimization problem is\n",
    "\n",
    "$$\n",
    "C(z) = \\sum_{(u,v)\\in E}C_{(u,v)}(z) = \\sum_{(u,v)\\in E}z_u+z_v-2z_uz_v.\n",
    "\\tag{2}\n",
    "$$\n",
    "\n",
    "Therefore, to solve the maximum cut problem is to find a value $z$ that maximizes the objective function in equation (2).\n",
    "\n",
    "### Encoding Max-Cut Problem\n",
    "\n",
    "Here we take the Max-Cut Problem as an example to further elaborate on QAOA. In order to transform the Max-Cut Problem into a quantum problem, we need to use $n$ qubits, where each qubit corresponds to a vertex in the graph $G$. A qubit being in a quantum state $|0\\rangle$ or $|1\\rangle$ indicates that its corresponding vertex belongs to the set $S_{0}$ or $S_{1}$, respectively. It is worth noting that $|0\\rangle$ and $|1\\rangle$ are the two eigenstates of Pauli $Z$ gate, and their eigenvalues are respectively $1$ and $-1$, namely\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Z|0\\rangle&=|0\\rangle,\\tag{3}\\\\\n",
    "Z|1\\rangle&=-|1\\rangle.\\tag{4}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Therefore, we can use Pauli $Z$ gate to construct the Hamiltonian $H_C$ of the Max-Cut Problem. Because mapping $f(x):x\\to(x+1)/2$ maps $-1$ to $0$ and $1$ to $1$, we can replace $z$ in equation (2) with $(Z+I)/2$ ($I$ is the identity matrix) to get the Hamiltonian corresponding to the objective function of the original problem:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "H_C &= \\sum_{(u,v)\\in E} \\frac{Z_u+I}{2} + \\frac{Z_v+I}{2}-2\\cdot\\frac{Z_u+I}{2} \\frac{Z_v+I}{2}\\tag{5}\\\\\n",
    "&= \\sum_{(u,v)\\in E} \\frac{Z_u+Z_v+2I-(Z_uZ_v+Z_u+Z_v+I)}{2}\\tag{6}\\\\\n",
    "&= \\sum_{(u,v)\\in E} \\frac{I-Z_uZ_v}{2}.\\tag{7}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "The expected value of this Hamiltonian for a quantum state $|\\psi\\rangle$ is\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\langle\\psi|H_C|\\psi\\rangle &= \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{I-Z_uZ_v}{2}|\\psi\\rangle\\tag{8} \\\\\n",
    "&= \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{I}{2}|\\psi\\rangle-\\langle\\psi|\\sum_{(u,v)\\in E} \\frac{Z_uZ_v}{2}|\\psi\\rangle\\tag{9}\\\\\n",
    "&= \\frac{|E|}{2}-\\frac{1}{2}\\langle\\psi|\\sum_{(u,v)\\in E} Z_uZ_v|\\psi\\rangle.\\tag{10}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "If we define\n",
    "\n",
    "$$\n",
    "H_D = -\\sum_{(u,v)\\in E} Z_uZ_v,\n",
    "\\tag{11}\n",
    "$$\n",
    "\n",
    "then finding the quantum state $|\\psi\\rangle$ that maximizes $\\langle\\psi|H_C|\\psi\\rangle$ is equivalent to finding the quantum state $|\\psi\\rangle$ such that $\\langle\\psi|H_D|\\psi \\rangle$ is the largest."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Paddle Quantum Implementation\n",
    "\n",
    "Now, let's implement QAOA with Paddle Quantum to solve the Max-Cut Problem. There are many ways to find the parameters $\\vec{\\gamma},\\vec{\\beta}$. Here we use the gradient descent method in classical machine learning.\n",
    "\n",
    "To implement QAOA with Paddle Quantum, the first thing to do is to import the required packages. Among them, the `networkx` package can help us handle graphs conveniently."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:07:36.250220Z",
     "start_time": "2021-04-30T09:07:36.223934Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>pre { white-space: pre !important; }</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "display(HTML(\"<style>pre { white-space: pre !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:07:40.001750Z",
     "start_time": "2021-04-30T09:07:36.983994Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import related modules from Paddle Quantum and PaddlePaddle\n",
    "import paddle\n",
    "from paddle_quantum.ansatz import Circuit\n",
    "from paddle_quantum.qinfo import pauli_str_to_matrix\n",
    "from paddle_quantum.loss import ExpecVal\n",
    "from paddle_quantum import Hamiltonian\n",
    "\n",
    "# Import additional packages needed\n",
    "import numpy as np\n",
    "from numpy import pi as PI\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we generate the graph $G$ in the Max-Cut Problem. For the convenience of computation, the vertices here are labeled starting from $0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:07:40.192343Z",
     "start_time": "2021-04-30T09:07:40.007013Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAjJUlEQVR4nO3deXSV5bX48e8OgYQwxoIMSk1FQHEoqFWrgAOt/Gpaa53Qqz8rTtU6UHpRm94Otl6N+oNqh1utUKWr1mqv97Y/Nd6iFSesI1JHhAoeFVEEGQLkBBKy7x/7TYgMQnLe8w7n7M9arCUvJ+/Zy5xnn32e8zz7EVXFOedcNEriDsA554qJJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnIuQJ13nnItQadwBOLerqmrqSoChwHCgO9AN2ARkgUXA4kxtdUt8ETq3c+KnAbukCpLseKAaGAvsB7QAzYAEfzT4U4p9clsAPAXUAY96EnZJ40nXJU5VTV0lMAmYCvQCemAJdlcpsAGoB6YDd2Zqq1eHHadzneFJ1yVGVU1dBXAjcAFW0VaEcNsGrAKeCVydqa1uCOGeznWaJ12XCFU1dWOBe4BKbL42bFlgNTAxU1s9Nw/3d26XeNJ1saqqqSsDbgbOJT/JdmtZYBYwJVNbvTGC53PuEzzputhU1dT1BB4GRhFNwm2VBeYDEzK11esjfF7nPOm6eAQJdy4wAiiPIYRGYCEwxhOvi5JvjnCRC6YUHia+hEvwvCOA2UE8zkXCk66Lw83YlEJcCbdVOTAa+FnMcbgi4tMLLlLBKoXZRDuHuzNZ4Hhf1eCi4EnXRSZYh/tPYHDcsWzHMmCYr+N1+ebTCy5KN2HrcJOoErgh7iBc4fNK10Ui2Nq7jPjncT9NIzDYtwy7fPJK10VlEra1N8lasE0azuWNV7ou74JuYUuBQXHHsguWAUO8O5nLF++n66IwHusW1mlj9unHsSP6c8DgPowc3Jte5V3b/u2M25/h2bdX5Rpjq97AccDfwrqhc+150nVRqMbaM3baOUfsxfH7DwwpnE9VAZyAJ12XJ550XRTG0rF+uNtQ4MO1jby2bC3rNzZz0qg9wolsWyXAuHzd3Dmf03V5FcznbiDHVQvlXUtobLJp1iM+txv3XPTFtn8LeXoBbLNEj0xttQ8OFzpfveDybSiwOdebtCbciLRgcTsXOk+6Lt+GY2eapUkzFrdzofOk6/KtOznO58ZASFZvCFdAPOm6fOtGOpOut3t0eeFJ1+XbJmzxQZoo4Ef5uLzwpOvyLUs6k2427iBcYfKk6/JtEelbD16Kxe1c6NI2GFz6LCaEN/evHjiIg/bsC8Dgvp9c8nv2EXtx3L4DAHhl6RoefPWDXJ+uBIvbudD55giXd1U1dfOAg3O5x7RTD+LUQ4bs9HH3zXuPqfe9kstTAczL1FYfmutNnNsen15wUXiK9MzrtgBPxh2EK1w+veCiUAecD/Ts7A2m3vdKGBXsrmgAHoriiVxx8krXReFRYF3cQeyiemBO3EG4wuVJ1+Vd0BB8GlZFJlkDMM0bmLt88qTronInyX+9lQCz4g7CFbakDwJXIDK11as3LV/yaEvTxkR+oaaqWWCGH0rp8s2Trss7ERkgIvd++Psrq1sa1yeyD0NLw9ouH9w5eVbccbjC50nX5Y2Ys4E3gNO1eeOGtc/86ZagqkyMlqaNuuK/r+u2afniZ0TkhyLSLe6YXOHypOvyQkQ+iy0V+z2wG/AIcMC6eQ9OEZFZJKe3QRb0txvfX3A71hHtp8ALIuKbI1xeeNJ1oRKREhG5BHgd+AqwBpgETFDVTPCwKcB8oDGOGNtpBOaXdC2/TFW/hZ0CvBg4CHhORG4SEe+r60Ll24BdaERkODATO4gS4L+BS1X1w60fW1VT1xOYC4wgx/PTOqkRWAiMydRWr2+9KCIVWLU7BStK3gIuUNUnYojRFSCvdF3ORKRURK4CXsYS7nLgVFU9ZXsJFyBIdGOwijfqqYYs8BJbJVwAVW1Q1anAF4HXgH2Ax0XkVhHpHXGcrgB50nU5EZHPA88BN2IV6++Akar6Xzv72SDhHYut4Y0q8WaD5ztu64Tbnqo+DxwCXAM0ARcDr4tIdRRBusLl0wuuU0SkHPgBcDXWw+Nd4CJVnd2Z+1XV1I0B7gUqyc/5ZFlgNTAxU1s9tyM/KCIHAL8FDgsu/QH4jqquDDdEVwy80nUdJiJHYtMC/wZ0AX4JHNDZhAsQJMJh2JxwI+FtGW4I7jcTGNbRhAugqq8BRwLfxZL3WcACETlDRBK57tgll1e6bpeJSE/gOuBy7PDGhcD5qvp0mM9TVVNXCZwLTAV6AxV0rEBowZJtPdbzYVZYO81EZCgwA5sWAbgf+Laqvh/G/V3h86TrdomIfBm4HagCNmNzuNeqat6WfVXV1JUA47GlZ+OAkVhCbW5p3NAHEUrKKuqxXr2lWGJ+A+uH+xAwJx/Na4Lq9nxgOvamUI+9QcxUH1BuJzzpuk8lIpVYcpkUXJoPnKeq/4g6liAJ7w0MX/Hn6+vo0pX+J155KvaRfxGwOFNbHdkLWkT2AG4FvhZcegy4UFX9qB+3Q5503Q6JyMnAfwADsSPJrwGmq2pTnHEBiIgCqGqsc6pB1Xs6Nq/dH3sD+AHwc1XdHGdsLpk86bptiMhA4FfAKcGludgGgYXxRfVJSUm6rUSkH3AL9iUbwPPYfPdrsQXlEslXL7g2QYOab2LzoqcA64HLgKOTlHCTSFVXqurZwFeBpdjyspdE5MfeQMe155WuA0BE9gJ+A0wILv0VuFhV34kvqh1LWqXbXrBz7QbgkuDSa1jV+3x8Ubmk8Eq3yAUNai7DGtRMAFYB5wAnJDXhJp2q1qvqt4FjsN4NBwDPiMj0oLeDK2Je6RYxEdkX2zRwVHDpP4HLVXV5fFHtmiRXuu0FXcquwZaUlQBLsPnxx+KMy8XHK90iJCJdReT7WIOao4APgZNV9fQ0JNw0UdWsql4NHA68gi15myMit4tIn3ijc3HwSrfIiMho4A5gVHDpDmCqqqbqbLC0VLrtiUhXrFfFD7GG6cuwefMHYg3MRcqTbpEIGtT8GLgS65eQwRby/y3OuDorjUm3lYiMxBroHBFcuge4QlVXxBeVi4pPLxQBERmDTSV8D/ud3wIcmNaEm3aq+gbWS/g7WI+IM7AGOmd5A53C55VuARORXkAtcGlwaQG2dOmZ+KIKR5or3fZE5HNYT4svBZfqgEtU9b34onL55JVugRKRCdj60EuBZuBaYHQhJNxCoqpvA8djDXTWAtVYs/SLRcTHZwHySrfAiMhngJ9ha20B5mHV7cvxRRW+Qql02xORwVivi5OCS09g8+7/jC0oFzp/Jy0QwRbeU7EtvOdgjbuvAo4otIRbqFR1GXAycBrwEXA08IqIXCkipbEG50LjlW4BEJFBWIX0jeDSk1iFtCi+qPKrECvd9orlE0sx8ko3xYLqdhJW3X4DWIft9z+2kBNuMVDVj1X1m1gD93exQzJfFJFrRaQs3uhcLrzSTantfOv9ELbQvii+9S70Sre9Ql6FUoy80k0ZEekiIldgKxO+BHwMnA18tVgSbrFR1XWqehl2ZNEiYD/gaRG5RUR6xBud6yivdFMk2Mk0E/hicOkeYLKqfhRfVPEopkq3vWBn4Y+wL0lTv7OwGHnSTYEd7Nm/RFXvjzWwGBVr0m0lIgdjW4lHBZfuAP5VVdfEFZPbNZ50E05EDsEG1EHBpRnAVcU+uIo96ULbm/FUrKdGGfABdhz8X+KMy306T7oJtYM+rBeq6pw440oKT7pbBH2RfwscGVxKTV/kYuRfpCWQiIzDGtRcFVz6GdagxhOu24aqvgmMBS4HNmCbKxaIyDneQCd5vNJNkO2crfU6tjToufiiSiavdLdvB2fdfUtV340vKtde0Sbdqpq6EmAoMBzojn1BtQnIYstyFmdqq1uiikdETsAGy55AE3A9cL2qbooqhjTxpLtjQXV7DnAzUImd6vw94FZVjew1nbQxlhRFk3SDF8B4rIvTWGytYwvWgUuCPxr8KcWmXhYAT2Ht9h7NxwtERPph/W3PCi69gFW3r4b9XIXEk+7OichA4JfAqcGludj5bAvz8XxJHWNJU/BJt6qmrhKYhH0h1Qvogf3yd5Vi82T1wHTgzkxtdc5H2wTVyOnYoOiPvfv/ELhFVTfnev9C50l314nIycCvgQHARuwL2umq2hTG/ZM6xpKqYJNuVU1dBXAjcAH2bhvG0dcN2LvzTODqTG11Q2duErTwuxU4Mbj0OLYy4a0QYiwKnnQ7RkQqsYQ2Kbg0H/tENb+z90zyGEuygky6VTV1Y7HdWpXYXFLYssBqYGKmtnrurv5QUN2eD0wD+mDv7FOBmVqIv4g88qTbOSJyPNazYy9gM5Y0r1XVxo7cJ6ljLA0KKulW1dSVYV8enEt+XghbywKzgCmZ2uqNn/ZAEdkb29hwXHDpAWxX2ft5jbBAedLtPBHpCVyHLTETYCFW9T69s59N8hhLi4JJulU1dT2Bh7FtkVG8GFplsY9qEzK11eu3/kcR6QJcgb3IuwMrsRf7vV7ddp4n3dyJyJHYpop9sXnVXwHfV9VtXseQ3DGWNgWRdIMXw1xgBFAeQwiNWLUwpv2LQkQOwF7UhwWX7sYa1KyMPsTC4kk3HEEDnR9gvT1KgXewdb2z2z8uqWMsjVKfdIOPO48Bo4nnxdCqEXgJOO6dG76qQA3wb0BX4H2s1+2DMcZXUDzphktERmEFwsHBpd8B31XVVUkcY2meaiiEbcA3Yx934nwxEDz/6KY1H/4eO1rlGizh3gbs7wnXJZmq/gM4HNtEsRH4JvCGiJxCwsYYti0+tVKddINvUM8l2vmlT9O9S4/K08r2HHkA8BZwjKpeoqpr4w7MuZ1R1WZVvRHraPcUMKBsz/3v0+ami0jQGAMmVdXUjYk7kM5K7fRCsEbwn8DguGPZWkvjhvX18+6vWvPkXR/HHUuh8umF/BKRkpKKvpcNOu8Xt5T23C2J/4+XAcPSuI43zZXuTdgawcQpKe/Rpe9RZ/447jic6yxVbRlyxV3Du/SoTOrcaSXWHCp1UlnpBtsOlxH/HNOnaQQGF/J2xjh5pZtfPsbyJ62V7iRs22GStWDzzc6lkY+xPEldpRt0MloKDOrsPXqXl/LlkQM4rOoz7D+4N/17lVFZ0Y2NzZvJfNzAnDc/4o6n32ZtNud+IMuAIcXQOSlqXunmTxhjDKBvRVcuHLM34/fbnSGV1pbhvdUNPLrgI25/akkY4wtSOMZK4w6gE8ZjnYw67ah9+jH9tFHbXO9WWsKBe/ThwD36cMYXhvAvM59l8YoNuTxVb2zbr5/U6tIk5zE2fEBPfn/e4Qzo/cnZiX0H9mbfgb059ZA9+b93PMei5Tnvc0jdGEvj9EI11jouZ/XZJh54eRnTH1nI7U8uYXn9lp4fA3qXc/1JB+b6FBXACbnexLmI5TTGykpLuO3sQ9oS7tpsE7c9sZjbnljcVt0O6F3OrWcdQllpzikodWMsjZXuWDrWq3Mbaxqa+MkDr/PHF96lsWnLp5LbnlzM7Mnj6N+rDIAvVO1Gj25d2LCp0+1tS4BxucTqXAxyGmMnjdqDvfv1bPv75Hvm8/iiFQA8+/bHzDrXdsUP7d+Tr4/agz+9+F4usaZujKWq0g3mmkbmep9nlnzMnX/PfCLhAqzasIkXMqva/l5SInTN/Z14ZFVNnc87ulQIY4xN2H9g23/XNza1JVyAJxatYF3jlrnc/9PusTlI1RhLVdLFzlvK66kKQ/tveYfOfLyBNQ05T/a3YHE7lwY5j7GRg3q3/ffSVZ/cu6AKS1dn2/6+36Ccpo5bpWqMpS3pDsfOW8qLyeOHMWLglhfBzx5ZFMZtm7G4nUuDnMdYZUXXtv9et3HbW61r3HJtt4puuTxVq1SNsbTN6XYnx/nc7RGBfzthPy4Ys3fbtVv+toj7X14Wyu1Jzr5153Ym1DEm27mVhD8RkKoxlrak242Qk26Pbl34xZmjGb/vAABaWpTav77JjKeWhPUUApSFdTPn8iznMba6oYmBfboA0Kt82xTTs2zLtVUNm3J5qlapGmNpS7qbsA73odijb3dmnnMo+wVzUA2bmpnyp5eZ/fqHYT0FWLxJ3b/u3NZyHmNvfFDPwD62XGzPyu6I2FwuWJU7ZLct51cu+GBdLk/VKlVjLG1zullCSrqjh/TlL98+si3hLluT5bTbngk74YLFm93po5xLhpzH2MNvbBlDvcq7cszw3dv+fszw3T9R6YY03lI1xtJW6S4ihJgP/mwld19wOOVd7SNQ8+YWHnzlA47cpx9H7tPvE4998JVlfLC2Qwelbq0Ui9u5NMh5jP15/vtcNG7vtrW6P584iruffxeAMw/7bNvjlqxcz1/+Ecq5rKkaY2lLuosJoTrfu1+PtoQLUNqlhIvG7b3dx766dE2uSbcEi9u5NMh5jG1sbuHiu+Zx13mHs3vvcnp378rFR39yRddH9Y1cfNc8NjaH0jIhVWMsVdMLQVOLBXHH0UFvZGqr09VVyBWtsMbYouXrOf7nT/Lrx99i0fJ1NGxqpmFTM4uWr+PXj7/F8T9/Moy+C61SNcbSVumCHSMymhy+Yb3vpaXc99LS8CLasRbgySieyLkQ5TzGwLbb3zR7ITfNXhhOVNuXujGWqko3UAfk1PorQg3AQ3EH4VwH+RjLozQm3UeBUNaZRKAemBN3EM51kI+xPEpd0g3mnKZh73BJ1gBMS1NzZefAx1i+pS7pBu4k+bGXALPiDsK5TvIxlidJ/5+6XcFBdDNJ6IJo3dy8SVVnpO3APOdaZWqrVzetfO+vLU0bk7oqIAukcoylMukGrgYS+T98c8Oabu/dfPr+IvK5uGNxrqNEpK+IzPhg1ndOamlcn9Q+tauA78UdRGekNulmaqsbgIkkrNrVls2bVt4/ba1uyh4HvCYik0Wky05/0LkEEJGvA28AF2jzxk1rn/rDDFVN1BjDxvzEIAekTmqTLkCmtnouNqeTlBdFVkq6zNz43mvDgHuw85tuAeaKSM4nXjiXLyKyu4jcA/wFOwX4GWDUupdnXyQis0jQGAPuzNRWPx13IJ2V6qQbmALMB3LaqxuCxiCO76rqClU9E/g6dkT0EcB8EfmhiITStdm5MIg5G9uFNhFbETAZGKuqrTvTEjfGYo4jJ6Ka1HnyXVdVU9cTmAuMAMp38vB8aAQWAmMytdWf2NsoIn2A/wdcGFx6BThfVV+MNsTCIiIKoKpJnXNMPBEZAtzGltN0HwG+papvb/3YJI+xtCmESpfglzAGexeM+mNQFniJHbwYVHWtql4EjAeWAAcBz4nITSKSmm73rnCISImIXAK8jiXcNcAkYML2Ei4ke4ylTUEkXWh7URyLrS+M6kWRDZ7vuJ29GFR1DnAgMD24dCXwiogcnd8QndtCRIYDjwG/BnoBfwZGquos3cnH3qSPsbQoiOmFrVXV1I0B7gUqyc/ZSVlsudrE4Mu8DhGRw4DfAgcEl24DrlbV+vBCLGw+vdAxIlKKzYX+BJseWA5cqqr/1Zn7JX2MJVnBVLrtBb+kYdgGikbC287YENxvJjCssy8GVX0eOAS4BmgCLgZeF5HqkOJ0ro2IfB54DrgRS7i/w6rbTiVcSP4YS7KCrHTbq6qpqwTOBaYCvbFlXB15s2nBXgj12H70WWHughGRA7Cq97Dg0h+A76jqyrCeoxB5pbtzIlIG/ADbRFAKvAtcpKqzw3yepI+xpCn4pNuqqqauBPsy6yvAOGAk9stuxvqGCnbWkmIv0BJskfiTWOu4OflqrBFsnpgM/Dv2UW0lcDlw787m2YqVJ91PJyJfxN7M98Ne0/8BfF9V89Y9LMljLEmKJuluLXiB7A0MxxJdGXaiaBY7b2lx1N3oRWQoMAP7sgLgfuDbqhrKQVKFxJPu9olIT+zN+wosyS0ELlDVyD+mJ3GMJUHRJt2kEhEBzsdWOfTGPnJNBWZ61buFJ91ticiXgduBKmAzcBPwU1WNe1ODa8eTbkKJyB7ArcDXgkuPAReqamoO4MsnT7pbiEgl9iY9Kbj0D+A8VZ0fW1Buhwpy9UIhCKYUvg6cAazAphxeFZHvegMd10pEvoHNi07CPrp/HzjME25yeaWbAiLSD2ucc1Zw6XlsK/FrsQUVs2KvdEVkIPBL4NTg0tPY3O2b8UXldoVXuimgqitV9Wzgq8BSbHnZSyLyY2+gU1yCBjXnYNXtqcB64DJgnCfcdPBKN2VEpDe2yP3i4NJrWNX7fHxRRa8YK10R2Qv4DTAhuDQba1DzTnxRuY7ySjdlVLVeVS8BjgHewrYSPyMi00SkItbgXF4EDWouwxrUTMC2x34T+Ion3PTxSjfFgi5l12BLykqwLmYXqOpjccYVhWKpdEVkBLbJ4ajg0n3AZaq6PL6oXC680k0xVc2q6tXA4cCr2EL0OSLym6CPr0spEekqIjXAy1jC/RA4WVVP84Sbbl7pFojgC7WrgB8C3bATKy5W1QdiDSxPCrnSFZHRWHU7Orh0BzBVVQu2H0Ex8aRbYIKz2H6LHREEdlbbFaq6Ir6owleISVdEyoEfYW+eXYAMtiHmb3HG5cLl0wsFRlXfwDr8fwfr3HQGsEBE/iXYYuwSSETGYDvJarBx+XPgQE+4hccr3QImIp/D9uJ/KbhUB1yiqu/FF1U4CqXSFZFeQC1waXBpAbYE8Jn4onL55JVuAQvOuzoea6CzFqjGmqV/S0T8dx8zEZmArbO+FGt/+O/AaE+4hc0r3SIhIoOxnqonBZeewOYL/xlbUDlIc6UrIrsBNwPnBJfmYdXty/FF5aLi1U6RUNVlwMnA6cBHwNHYwZhXBudnuQiIyKnYFMI52LE0VwFHeMItHl7pFiER+QzwM7ZUWi9ildYr8UXVMWmrdEVkEPAr7I0P7LSEC1V1UXxRuTh4pVuEVPVjVf0mdqzKu8ChwDwR+WlwrpYLSdCgZhLWoOZkYB1wCXCsJ9zi5JVukdvOt+dvYFXvs/FFtXNpqHS3s3rkf7AGNalfPeI6zyvdIqeq61T1MuwgwUXYYYJ/F5GbRaRHvNGlk4h0EZErsJUJXwI+Bs4Gqj3hOq90XZtgR9SPgSuxHVFvY0d2J26BflIrXRHZD9sR+MXg0j3AZFX9KL6oXJJ40nXbEJGDscQxKrh0B/Cvqromrpi2lrSkKyJdsZUIP2JL74tLVPX+WANzieNJ121XkESuxCrfbsAH2HHwf4kzrlZJSroicgj2xnRQcGkGcFWS3qRccnjSdZ9KRPbFqt4jg0v/CVwed3vBJCTdHfQzvlBV58QVk0s+T7pup4Itw98GbgB6AKuwhjp3aYQvoKqauhJgKDB8xZ9rH6RLKf1PvPI0IIt9Cbg4U1vdEkUsIjIOmAkMA1qwg0N/pKobonh+l16edN0uE5Eq7Iyu44NL/4P17H03H88XJNnxWM+IscB+WIJrbtm4oQ8IJWUV9YACpVi1uQB4Cmvu82jYSTg4o+4GbK0t2BE656vqc2E+jytcnnRdhwTtIc/BegdUYqfRXg3cpqqhJLiqmrpKYBL2sb0XVl13ZBpBgQ1APTAduDNTW51zA3AROQG4DRgCNAHXA9er6qZc7+2Khydd1ykiMhDb1npKcGkudj7bws7es6qmrgI76fgCrKIN46DNBqwCnglcnamtbujoDUSkH/Ymc3Zw6QWsun01hPhckfGk63IiIqdg3csGABuxL5amqWpzR+5TVVM3FlvTWgl0DzlMsHnf1cDETG313F35gaCqPx34JdA/uMcPgVtUdXMeYnRFwJOuy1nQqnA6cG5w6SWsEvzHzn62qqauDKsizyU/yXZrWWAWMCVTW71xRw8KWmHeCpwYXHocW5nwVr4DdIXNk64LjYgcj/Ua2AvYjE0VXKuqjdt7fFVNXU/gYWwTRhQJt1UWmA9MyNRWr2//D0F1ez4wDeiDzQtfCcwMa87aFTdPui5UItITuA64HPvy602s6v17+8cFCXcuMAIojzpOrJftQmBMa+IVkb2xjQ3HBY95ENtVtjSG+FyB8oY3LlSqul5VJ2NLvN4E9gXmisgvgoTcOqXwMPElXILnHQHM3v20a7qLyBSsQc1xwErgTOBET7gubJ50XV6o6tPAaKzqbcEq39eCKYibsSmFuBJuq3LVloNbGte/jTV17w7cDeynqvdEufHDFQ9Pui5vVLVRVX+ANUmfD+xVtuf+s3Vz00VEO4e7QyIl5RUjjhxQ9tmDVgBfU9WzVHVl3HG5wuVzui4SIlJa0r339wad96trS3vtFnc421Bt+VCkZGhn1vE61xFe6bpIqGrzkMl3D+zSo+92VzLETaSkD7a917m88krXRSLY2ruM+OdxP00jMDiMLcPO7YhXui4qk7Av1JKshS0bPJzLC690Xd4F3cKWAoM6e48pXxrG/oP7sM/uPams6EaPbl3INm3m/TVZXsys5vfPvsPC5evCCHcZMCSqFpGu+JTGHYArCuOxbmGdNnn88G2u9epSwr4Du7LvwN6cfugQLr37JR5ZkHNv9d7YWt3EnQvnCoMnXReFaqw9Y6etWLeRF99ZxburGljb0ERFWSljh/Xj83v2BaBbaQlXTRgRRtKtAE7Ak67LE0+6Lgpj6Vg/3G184fptc+D0RxbytylHM7R/TwCG7BZGJ0hKsOPoncsL/yLN5VUwnzsyzHuKQN+KrnztoMHs0XfLHos3PwxlThdgZFVNXewHXrrC5JWuy7ehWMexnO3Ztztzrz5uu/+2asMmfvLA62E8DdgqhqGAt3F0ofNK1+XbcKBDDc076p/L13HmjGeZ/96asG7ZjMXtXOg86bp8606O87mt1mSbuO6hBdz41ze54+m3yXxsB+8OG9CL/3/pUZz4+cFhPA1YvInoDeEKj08vuHzrRkhJd/3GZmY8taTt79c9tIDfTTqMMfv0o7xrF244+UCeWfwxK9bv8ECIXSVAWa43cW57vNJ1+bYJO503dJtblEfbLRGr6FbKqCF9w7i1Yue9ORc6T7ou37LkmHQPq9qNPt27bnNdBI4Z0f8T1zSc/K5Y3M6FzqcXXL4tIsfX2emH7snXPj+Y55as4vVla6lvbKayohvHjujPsAFbNrrVNzbx3JJVucYLFu+iMG7k3NY86bp8W0wIn6jKSrswbnh/xg3vv91/X9fYxBV/nM+6jaEslCjB4nYudN7wxuVdVU3dPODgzv78F6oqOeHAQYweUsmgPuX0rbCphvpsE0tWbGDu4pX88fl3Wbl+U1ghz8vUVh8a1s2ca88rXReFp7Dz0jq1iuGFzGpeyETW4rYFeDKqJ3PFx79Ic1GoAzbEHcQuagAeijsIV7g86booPAqE1hghz+qBOXEH4QqXJ12Xd0FD8GlYFZlkDcA0b2Du8smTrovKnST/9VYCzIo7CFfYkj4IXIEIDnucSXI3HWSBGX4opcs3T7ouSlcDSU1qq4DvxR2EK3yedF1kMrXVDcBEklftZoGJQXzO5ZUnXRepTG31XGzeNCmJNwvcmamtfjruQFxx8KTr4jAFmA80xhxHYxDHd2OOwxUR3wbsYlFVU9cTmAuMAMpjCKERWAiMydRWr4/h+V2R8krXxSJIdGOwSjPqqYYs8BKecF0MPOm62AQJ71hsDW9UiTcbPN9xnnBdHHx6wSVCVU3dGOBeoJL8nE+WxZarTQy+zHMuFl7pukQIEuEwbANFI+FtGW4I7jcTGOYJ18XNK12XOFU1dZXAucBUoDdQQccKhBYs2dZjPR9m+U4zlxSedF1iVdXUlQDjga8A44CRWEJtxnrzCnaemWK9oUuAN7B+uA8Bc7x5jUsaT7ouNYIkvDcwHJv3LcNO7c1iZ5otztRW+wvaJZonXeeci5B/keaccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxHypOuccxH6X4ZvoaaQCRNmAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# n is the number of vertices in the graph G, which is also the number of qubits\n",
    "n = 4\n",
    "G = nx.Graph()\n",
    "V = range(n)\n",
    "G.add_nodes_from(V)\n",
    "E = [(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)]\n",
    "G.add_edges_from(E)\n",
    "\n",
    "# Print out the generated graph G\n",
    "pos = nx.circular_layout(G)\n",
    "options = {\n",
    "    \"with_labels\": True,\n",
    "    \"font_size\": 20,\n",
    "    \"font_weight\": \"bold\",\n",
    "    \"font_color\": \"white\",\n",
    "    \"node_size\": 2000,\n",
    "    \"width\": 2\n",
    "}\n",
    "nx.draw_networkx(G, pos, **options)\n",
    "ax = plt.gca()\n",
    "ax.margins(0.20)\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Encoding Hamiltonian\n",
    "\n",
    "In Paddle Quantum, a Hamiltonian can be input in the form of `list`. Here we construct the Hamiltonian $H_D$ in equation (11)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:07:40.206426Z",
     "start_time": "2021-04-30T09:07:40.197339Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-1.0, 'z0,z1'], [-1.0, 'z1,z2'], [-1.0, 'z2,z3'], [-1.0, 'z3,z0'], [-1.0, 'z1,z3']]\n"
     ]
    }
   ],
   "source": [
    "# Construct the Hamiltonian H_D in the form of list\n",
    "H_D_list = []\n",
    "for (u, v) in E:\n",
    "    H_D_list.append([-1.0,'z'+str(u) +',z' + str(v)])\n",
    "print(H_D_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, in this example, the Hamiltonian $H_D$ is\n",
    "\n",
    "$$\n",
    "H_D = -Z_0Z_1-Z_1Z_2-Z_2Z_3-Z_3Z_0-Z_1Z_3.\n",
    "\\tag{12}\n",
    "$$\n",
    "\n",
    "We can view the matrix form of the Hamiltonian $H_D$ and get information of its eigenvalues:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:07:40.501135Z",
     "start_time": "2021-04-30T09:07:40.491760Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-5.  1. -1.  1.  1.  3.  1. -1. -1.  1.  3.  1.  1. -1.  1. -5.]\n",
      "H_max: 3.0\n"
     ]
    }
   ],
   "source": [
    "# Convert Hamiltonian H_D from list form to matrix form\n",
    "H_D_matrix = pauli_str_to_matrix(H_D_list, n)\n",
    "# Take out the elements on the diagonal of H_D\n",
    "H_D_diag = np.diag(H_D_matrix).real\n",
    "# Get the maximum eigenvalue of H_D\n",
    "H_max = np.max(H_D_diag)\n",
    "\n",
    "print(H_D_diag)\n",
    "print('H_max:', H_max)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Building the QAOA circuit\n",
    "\n",
    "Earlier we introduced that QAOA needs to apply two unitary transformations $U_C(\\gamma)$ and $U_B(\\beta)$ alternately on the initial state $|s\\rangle = |+\\rangle^{\\otimes n}$. Here, we use the quantum gates and quantum circuit templates provided in Paddle Quantum to build a quantum circuit to achieve this step. It should be noted that in the Max-Cut Problem, we simplify the problem of maximizing the expected value of the Hamiltonian $H_C$ to the problem of maximizing the expected value of the Hamiltonian $H_D$, so the unitary transformations to be used are $U_D(\\gamma)$ and $U_B(\\beta)$. By alternately placing two circuit modules with adjustable parameters, we are able to build a QAOA circuit\n",
    "\n",
    "$$\n",
    "U_B(\\beta_p)U_D(\\gamma_p)\\cdots U_B(\\beta_1)U_D(\\gamma_1),\n",
    "\\tag{13}\n",
    "$$\n",
    "\n",
    "where $U_D(\\gamma) = e^{-i\\gamma H_D}$ can be constructed with the circuit in the figure below. Another unitary transformation $U_B(\\beta)$ is equivalent to applying a $R_x$ gate to each qubit.\n",
    "\n",
    "![U_D circuit](figures/maxcut-fig-cir_ud.png \"Figure 3: Quantum circuit of unitary transformation $e^{i\\gamma Z\\otimes Z}$\")\n",
    "<div style=\"text-align:center\">Figure 3: Quantum circuit of unitary transformation $e^{i\\gamma Z\\otimes Z}$</div>\n",
    "\n",
    "Therefore, the quantum circuit that realizes a layer of unitary transformation $U_B(\\beta)U_D(\\gamma)$ is shown in Figure 4.\n",
    "\n",
    "![U_BU_D circuit](figures/maxcut-fig-cir_ubud.png \"Figure 4: Quantum circuit of unitary transformation $U_B(\\beta)U_D(\\gamma)$\")\n",
    "<div style=\"text-align:center\">Figure 4: Quantum circuit of unitary transformation $U_B(\\beta)U_D(\\gamma)$  </div>\n",
    "\n",
    "In Paddle Quantum, the default initial state of each qubit is $|0\\rangle$ (the initial state can be customized by input parameters). We can add a layer of Hadamard gates to change the state of each qubit from $|0\\rangle$ to $|+\\rangle$ so that we get the initial state $|s\\rangle = |+\\rangle^{\\otimes n}$ required by QAOA. In Paddle Quantum, we can add a layer of Hadamard gates to the quantum circuit by calling `superposition_layer()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def circuit_QAOA(p):\n",
    "    # Initialize the quantum circuit of n qubits\n",
    "    cir = Circuit(n)\n",
    "    # Prepare quantum state |s>\n",
    "    cir.superposition_layer()\n",
    "    # Build a circuit with p layers of U_D\n",
    "    cir.qaoa_layer(E,V,p)\n",
    "    \n",
    "    return cir\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After running the constructed QAOA quantum circuit, we obtain the output state\n",
    "\n",
    "$$\n",
    "|\\vec{\\gamma},\\vec{\\beta}\\rangle = U_B(\\beta_p)U_D(\\gamma_p)\\cdots U_B(\\beta_1)U_D(\\gamma_1)|s\\rangle.\n",
    "\\tag{14}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating the loss function\n",
    "\n",
    "From the output state of the circuit built in the previous step, we can calculate the objective function of the maximum cut problem\n",
    "\n",
    "$$\n",
    "F_p(\\vec{\\gamma},\\vec{\\beta}) = \\langle\\vec{\\gamma},\\vec{\\beta}|H_D|\\vec{\\gamma},\\vec{\\beta}\\rangle.\n",
    "\\tag{15}\n",
    "$$\n",
    "\n",
    "To maximize the objective function is equivalent to minimizing $-F_p$. Therefore, we define $L(\\vec{\\gamma},\\vec{\\beta}) = -F_p(\\vec{\\gamma},\\vec{\\beta})$ as the loss function, that is, the function to be minimized. Then, we use a classical optimization algorithm to find the optimal parameters $\\vec{\\gamma},\\vec{\\beta}$. The following code shows the loss function constructed with Paddle Quantum:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# construct the loss function\n",
    "loss_func = ExpecVal(Hamiltonian(H_D_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training quantum neural network\n",
    "\n",
    "After defining the quantum neural network for QAOA, we use the gradient descent method to update the parameters in the network to maximize the expected value in equation (15)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:07:44.907375Z",
     "start_time": "2021-04-30T09:07:44.901678Z"
    }
   },
   "outputs": [],
   "source": [
    "p = 4      # Number of layers in the quantum circuit\n",
    "ITR = 120  # Number of training iterations\n",
    "LR = 0.1   # Learning rate of the optimization method based on gradient descent\n",
    "SEED = 1024 # Set global RNG seed "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we optimize the loss function defined above in PaddlePaddle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iter: 10   loss: -1.8359\n",
      "iter: 20   loss: -2.5392\n",
      "iter: 30   loss: -2.7250\n",
      "iter: 40   loss: -2.8061\n",
      "iter: 50   loss: -2.8748\n",
      "iter: 60   loss: -2.9134\n",
      "iter: 70   loss: -2.9302\n",
      "iter: 80   loss: -2.9321\n",
      "iter: 90   loss: -2.9321\n",
      "iter: 100   loss: -2.9325\n",
      "iter: 110   loss: -2.9327\n",
      "iter: 120   loss: -2.9328\n"
     ]
    }
   ],
   "source": [
    "paddle.seed(SEED)\n",
    "\n",
    "cir = circuit_QAOA(p)\n",
    "# Use Adam optimizer\n",
    "opt = paddle.optimizer.Adam(learning_rate=LR, parameters=cir.parameters())\n",
    "\n",
    "for itr in range(1, ITR + 1):\n",
    "    state = cir()\n",
    "    # Calculate the gradient and optimize\n",
    "    loss = -loss_func(state)\n",
    "    loss.backward()\n",
    "    opt.minimize(loss)\n",
    "    opt.clear_grad()\n",
    "    if itr % 10 == 0:\n",
    "        print(\"iter:\", itr, \"  loss:\", \"%.4f\" % loss.numpy())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decoding the quantum solution\n",
    "\n",
    "After obtaining the minimum value of the loss function and the corresponding set of parameters $\\vec{\\gamma}^*,\\vec{\\beta}^*$, our task has not been completed. In order to obtain an approximate solution to the Max-Cut Problem, it is necessary to decode the solution to the classical optimization problem from the quantum state $|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle$ output by QAOA. Physically, to decode a quantum state, we need to measure it and then calculate the probability distribution of the measurement results:\n",
    "\n",
    "$$\n",
    "p(z)=|\\langle z|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle|^2.\n",
    "\\tag{16}\n",
    "$$\n",
    "\n",
    "Usually, the greater the probability of a certain bit string, the greater the probability that it corresponds to an optimal solution of the Max-Cut problem.\n",
    "\n",
    "Paddle Quantum provides a function to view the probability distribution of the measurement results of the state output by the QAOA quantum circuit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:10:21.794006Z",
     "start_time": "2021-04-30T09:10:21.392963Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAbZUlEQVR4nO3de7xcZX3v8c834aqggkS0EAytQYwXUAN6ausFwYajcqmo3BQVGnskBV7aaji1KGh7EKuneggeYxHRHgHvphoBq6JH+xITEIGAkYhcgqJBRFAOaOR7/lgrMExmz16z91ozk72+79drvzLr9pvfhDC/vZ7nWc8j20RERHvNGnUCERExWikEEREtl0IQEdFyKQQRES2XQhAR0XIpBBERLbfVqBMY1C677OJ58+aNOo2IiC3KFVdccYftOb2ObXGFYN68eaxevXrUaUREbFEk3TzRsTQNRUS0XKOFQNIiSWslrZO0tMfx10naIOmq8ueEJvOJiIjNNdY0JGk2sAw4CFgPrJK0wvZ1XadeZHtJU3lERER/Td4R7A+ss32j7d8BFwKHNvh+ERExBU0Wgt2AWzu215f7ur1C0tWSPiNpboP5RERED6PuLP53YJ7tZwBfBc7vdZKkxZJWS1q9YcOGoSYYETHTNVkIbgM6f8Pfvdz3INu/tH1/ufmvwLN7BbK93PZC2wvnzOk5DDYiIqaoyUKwCpgvaU9J2wBHAis6T5D0hI7NQ4DrG8wnIiJ6aGzUkO2NkpYAlwCzgY/aXiPpDGC17RXASZIOATYCdwKvayqfGA/zln55ytfedOZLa8yknfL3H700+mSx7ZXAyq59p3W8PhU4tckcIiKiv1F3FkdExIilEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREyzVaCCQtkrRW0jpJS/uc9wpJlrSwyXwiImJzjRUCSbOBZcDBwALgKEkLepy3I3AycHlTuURExMSavCPYH1hn+0bbvwMuBA7tcd67gPcA9zWYS0RETKDJQrAbcGvH9vpy34MkPQuYa/vLDeYRERF9jKyzWNIs4P3AWyqcu1jSakmrN2zY0HxyEREt0mQhuA2Y27G9e7lvkx2BpwGXSboJeC6woleHse3lthfaXjhnzpwGU46IaJ8mC8EqYL6kPSVtAxwJrNh00Pavbe9ie57tecB3gUNsr24wp4iI6NJYIbC9EVgCXAJcD3zK9hpJZ0g6pKn3jYiIwWw12QmSngdcZfu3ko4FngV8wPbNk11reyWwsmvfaROc+8JKGUdERK2q3BF8CLhX0j4UHbs/Bj7eaFYRETE0VQrBRtumeAbgbNvLKDp6IyJiBpi0aQi4R9KpwGuAPy+HfW7dbFoRETEsVe4IXg3cD7zB9u0Uw0Df22hWERExNJMWgvLL/7PAtuWuO4DPN5lUREQMz6SFQNJfAZ8BPlzu2g34QoM5RUTEEFVpGjoReB5wN4DtG4DHNZlUREQMT5VCcH85eygAkrYC3FxKERExTFUKwTcl/Xdge0kHAZ8G/r3ZtCIiYliqFIKlwAbgGuCNFE8Kv73JpCIiYngmfY7A9gPAR8qfiIiYYSYsBJI+ZftVkq6hR5+A7Wc0mllERAxFvzuCk8s/XzaMRCIiYjQm7COw/bPy5Zts39z5A7xpOOlFRETTqnQWH9Rj38F1JxIREaPRr4/gv1H85v/Hkq7uOLQj8J2mE4uIiOHo10fwSeArwP+gGEK6yT2272w0q4iIGJp+hcC2b5J0YvcBSTunGEREzAyT3RG8DLiCYvioOo4Z+OMG84qIiCGZsBDYfln5557DSyciIoatX2fxs/pdaPvK+tOJiIhh69c09L4+xwwcUHMuERExAv2ahl40zEQiImI0+jUNHWD765L+stdx259rLq2IiBiWfk1DLwC+Dry8xzEDKQQRETNAv6ahd5R/vn546URExLBVWbz+sZI+KOlKSVdI+oCkxw4juYiIaF6VSecupFih7BXAEeXri5pMKiIihmfSFcqAJ9h+V8f2uyW9uqmEIiJiuKrcEVwq6UhJs8qfVwGXNJ1YREQMR7/ho/fw0BxDpwD/Vh6aBfwG+Numk4uIiOb1GzW04zATiYiI0ajSR4CknYD5wHab9tn+VlNJRUTE8FQZPnoC8C2KfoHTyz/fWSW4pEWS1kpaJ2lpj+N/LekaSVdJ+rakBYOlHxER01Wls/hkYD/g5nL+oWcCd012kaTZwDKK9Y0XAEf1+KL/pO2n294XOAt4f/XUIyKiDlUKwX227wOQtK3tHwJPrnDd/sA62zfa/h3F8wiHdp5g++6OzUdSdE5HRMQQVekjWC/pMcAXgK9K+hVwc4XrdgNu7YwDPKf7pHIpzDcD25CprSMihm7SQmD78PLlOyV9A3g0cHFdCdheBiyTdDTwduC47nMkLQYWA+yxxx51vXVERFCtaQhJz5J0EvAMYH3Z1DOZ24C5Hdu7l/smciFwWK8DtpfbXmh74Zw5c6qkHBERFVUZNXQacD7wWGAX4DxJb68QexUwX9KekrYBjgRWdMWe37H5UuCGqolHREQ9qvQRHAPs09FhfCZwFfDufhfZ3ihpCcVw09nAR22vkXQGsNr2CmCJpAOB3wO/okezUERENKtKIfgpxYNk95Xb29K/iedBtlcCK7v2ndbx+uRqaUZERFP6zTX0vyiGc/4aWCPpq+X2QcD3hpNeREQ0rd8dweryzyuAz3fsv6yxbCIiYuj6TTp3/qbXZWfvXuXmWtu/bzqxiIgYjkn7CCS9kGLU0E0UU1LPlXRcJp2LiJgZqnQWvw94ie21AJL2Ai4Ant1kYhERMRxVHijbelMRALD9I2Dr5lKKiIhhqnJHcIWkf+WhFcqO4aGO5IiI2MJVKQR/DZwInFRu/1/gnMYyioiIoepbCMo1BX5ge2+yVkBExIzUt4/A9h+AtZIy5WdExAxVpWloJ4oni78H/HbTTtuHNJZVREQMTZVC8A+NZxERESPTb66h7Sg6ip8EXAOca3vjsBKLiIjh6NdHcD6wkKIIHEzxYFlERMww/ZqGFth+OoCkc8mMoxERM1K/O4IHJ5ZLk1BExMzV745gH0l3l68FbF9uC7DtRzWeXURENK7fNNSzh5lIRESMRpVJ5yIiYgZLIYiIaLkUgoiIlkshiIhouX5PFt8DeKLjGTUUETEz9Bs1tCOApHcBPwM+QTF09BjgCUPJLiIiGlelaegQ2+fYvsf23bY/BBzadGIRETEcVQrBbyUdI2m2pFmSjqFjOuqIiNiyVSkERwOvAn5e/ryy3BcRETPApOsR2L6JNAVFRMxYk94RSNpL0tckXVtuP0PS25tPLSIihqFK09BHgFMpZyO1fTVwZJNJRUTE8FQpBI+w3b0WQaaljoiYIaoUgjsk/Qnlw2WSjqB4riAiImaAKovXnwgsB/aWdBvwE4qHyiIiYgboe0cgaTbwJtsHAnOAvW3/me2bqwSXtEjSWknrJC3tcfzNkq6TdHXZIf3EKX2KiIiYsr6FwPYfgD8rX//W9j1VA5dFZBnFwvcLgKMkLeg67fvAQtvPAD4DnDVA7hERUYMqTUPfl7QC+DQdTxTb/twk1+0PrLN9I4CkCymeR7iuI8Y3Os7/LnBsxbwjIqImVQrBdsAvgQM69hmYrBDsBtzasb0eeE6f848HvlIhn4iIqFGVJ4tf33QSko4FFgIvmOD4YmAxwB577NF0OhERrTJpIZB0Hj3WJbD9hkkuvQ2Y27G9e7mvO/6BwN8DL7B9f69AtpdTjFxi4cKFE66REBERg6vSNPSljtfbAYcDP61w3SpgvqQ9KQrAkXRNVifpmcCHgUW2f1Ep44iIqFWVpqHPdm5LugD4doXrNkpaAlwCzAY+anuNpDOA1bZXAO8FdgA+LQngFtuHDP4xIiJiqqrcEXSbDzyuyom2VwIru/ad1vH6wCm8f0RE1KhKH0H32sW3A29rLKOIiBiqKk1DOw4jkYiIGI0q6xE8T9Ijy9fHSnp/poKIiJg5qsw++iHgXkn7AG8Bfgx8vNGsIiJiaKoUgo22TTE9xNm2lwFpLoqImCGqjBq6R9KpFPMAPV/SLGDrZtOKiIhhqXJH8GrgfuB427dTPCH83kazioiIoakyauh24P0d27eQPoKIiBmjyqih50paJek3kn4n6Q+Sfj2M5CIionlVmobOBo4CbgC2B04AzmkyqYiIGJ4qhQDb64DZtv9g+zxgUbNpRUTEsFQZNXSvpG2AqySdBfyMigUkIiLGX5Uv9NeU5y2hWKpyLvCKJpOKiIjhqTJq6GZJ2wNPsH36EHKKiIghqjJq6OXAVcDF5fa+5WL2ERExA1RpGnonsD9wF4Dtq4A9G8soIiKGqkoh+L3t7ucGsm5wRMQMUWXU0BpJRwOzJc0HTgL+s9m0IiJiWKrcEfwN8FSK+YYuAO4GTmkwp4iIGKIqo4buBf6+/ImIiBlmwkIw2cgg24fUn05ERAxbvzuC/wLcStEcdDmgoWQUERFD1a8QPB44iGLCuaOBLwMX2F4zjMQiImI4JuwsLieYu9j2ccBzgXXAZZKWDC27iIhoXN/OYknbAi+luCuYB3wQ+HzzaUVExLD06yz+OPA0YCVwuu1rh5ZVREQMTb87gmMpZhs9GThJerCvWIBtP6rh3CIiYggmLAS2s+ZAREQL5Ms+IqLlUggiIlouhSAiouVSCCIiWi6FICKi5VIIIiJartFCIGmRpLWS1kla2uP48yVdKWmjpCOazCUiInprrBBImg0sAw4GFgBHSVrQddotwOuATzaVR0RE9Fdlqcqp2h9YZ/tGAEkXAocC1206wfZN5bEHGswjIiL6aLJpaDeK9Qw2WV/uG5ikxZJWS1q9YcOGWpKLiIjCFtFZbHu57YW2F86ZM2fU6UREzChNFoLbgLkd27uX+yIiYow0WQhWAfMl7SlpG+BIoO86yBERMXyNFQLbG4ElwCXA9cCnbK+RdIakQwAk7SdpPfBK4MOSsgxmRMSQNTlqCNsrKRa26dx3WsfrVRRNRhERMSJbRGdxREQ0J4UgIqLlUggiIlouhSAiouVSCCIiWi6FICKi5VIIIiJaLoUgIqLlUggiIlouhSAiouVSCCIiWi6FICKi5VIIIiJaLoUgIqLlUggiIlouhSAiouVSCCIiWi6FICKi5VIIIiJaLoUgIqLlUggiIlouhSAiouVSCCIiWi6FICKi5VIIIiJaLoUgIqLlUggiIlouhSAiouVSCCIiWi6FICKi5VIIIiJaLoUgIqLlUggiIlqu0UIgaZGktZLWSVra4/i2ki4qj18uaV6T+URExOYaKwSSZgPLgIOBBcBRkhZ0nXY88CvbTwL+J/CepvKJiIjetmow9v7AOts3Aki6EDgUuK7jnEOBd5avPwOcLUm23URC85Z+eVrX33TmS2vKpFnT+ZxbymeEfM4qtpTPmf83q2nqc6qh71wkHQEssn1Cuf0a4Dm2l3Scc215zvpy+8flOXd0xVoMLC43nwysbSRp2AW4Y9Kzhh+r7nhtiFV3vDbEqjteG2LVHa/u3Do90facXgeavCOoje3lwPKm30fSatsLxy1W3fHaEKvueG2IVXe8NsSqO17duVXVZGfxbcDcju3dy309z5G0FfBo4JcN5hQREV2aLASrgPmS9pS0DXAksKLrnBXAceXrI4CvN9U/EBERvTXWNGR7o6QlwCXAbOCjttdIOgNYbXsFcC7wCUnrgDspisUo1dn8VHdT1rjmNq6x6o7Xhlh1x2tDrLrjNd4E3ktjncUREbFlyJPFEREtl0IQEdFyKQQRES2XQhAR0XJbxANlTZEkiqkwdit33QZ8r84hrJL2tv3DAa95NLCoK69LbN9VY14H2f7qFK4by9wk7U0xZUlnXitsX19jXq+3fV5d8SLGRWtHDUl6CXAOcAMPPei2O/Ak4E22L63pfW6xvccA578WeAdwaVdeBwGn2/74KPIa59wkvQ04CrgQWN+R15HAhbbPHEVeHdeNZfEsrxvLAjqMvKaR218Ah3Xl9kXbF9eY12m2z6gr3qTv1+JCcD1wsO2buvbvCay0/ZQBYn1wokPAcbYfNUCstRTzLd3VtX8n4HLbew0Qq/sBvs68DrD9yKqxxjk3ST8Cnmr79137twHW2J4/QKyr++S1l+1tq8Yq441l8SyvGcsCOqy8ppjbvwB7AR/vyu21wA22Tx5FXtPV5qahrXjoP2Sn24CtB4z1euAtwP09jh01YCwBvarzA+WxQfw5cCzwmx7vsf+AsTZdN465PQD8EXBz1/4nlMcGsSvwF8CveuT1nwPGAvh74NkTFU+KL5RKJimej51CbsfTu4C+H1gDVP7CnaSA7jqqvBrI7b/2+oVH0kXAj4DKhUDS3X3y2n7AvKalzYXgo8CqcnrsW8t9cyl+6zh3wFirgGttb/ZFIemdA8b6R+BKSZd25LUHxW+Q7xow1neBe21/s0deU5nBdVxzOwX4mqQbuvJ6ErBkoosm8CVgB9tX9cjrsgFjwfgWz005jGMBrTOvunO7T9J+tld17d8PuG/AWHcB+9n+efcBSbdufnpzWts0BFAulHMIm7dDXjfxVT3j7AzcZ/vemvLaieIfbnebcvc/5KEb19wkzWLzjv9Vtv8wuqxA0nHAaRRNQ5sVT9sfGyDWV4CzbH+jx7Fv2X7+gLktAs6m6CfbrIAO0uYt6VzgPNvf7nHsk7aPHkVeDeT2LOBDwI481KIwF/g1cKLtKwaI9W6K75vv9Tj2HttvqxprulpdCDYpv8ixfec4xRpXknal4wu31280o4g1QfwdbHf/Bj3UWONaPGGsC+hY5rWJpMfz8H+3t48yn+lqbSGQtAdwFnAARTUX8Cjg68DS7k7kirFeTHG7N+VYk7zPNbafPqpYkvYF/jfFdOHrKT7n7hSf+U22rxwg1jMpfrN6NA/vRB041iTvU1un23RibUnFs3yPkRbQuod2j+tQ8WHEqqLNfQQXAf8CHLPptwwV6yy/kmK0wnNHEUvSX050CHj8ADnVGqv0MeCNti/vep/nAucB+wwQ67y6Ykl680SHgB0GyKnWWGW8felRPCXdRU3FcyqxKriOojlm6LH6De2WNPDQ7rrj9XEp9f2d1RlrUm0uBLvYvqhzR/klfqGkQTs+64x1EfB/6N3BuN0IYwE8svuLG8D2dyUNNBS15lj/BLwX2Njj2KBPz9cZC8a0eJbXjWsB/QBw4ERDu4HKQ7vrjjfJUPHHDJJUnbGmq82F4ApJ5wDn8/BRQ8cB3x9hrKuBf7Z9bfcBSQeOMBbAVyR9mWLIY+fnfC0w6MM0dca6EvhCr446SSeMMBaMb/GE8S2gdQ7trjtenUPF64w1LW0uBK+lGK98Ol2jhhh8+GidsU4BJhpffPgIY2H7JEkHs/kTn8tsrxxVLIr/oSZa4nTQ9V/rjAXjWzxhfAtonUO7645X51DxOmNNS2s7iyOGZYKCt2IKBa/uWE8G7rS9ocexXQfphK4zVnnNU+j9OQca2l13vDqHitc97HxaubS1EEjaiuK3+MPomjMEOLf7qcYRxDqc4qGasYhV4b2W216cWBFbnjYXggsohiqez8PnDDkO2Nn2qxNrs3g7T3QI+IHt3RNrs3iPBk6l+G10V4qO+19QFOMzu6eeGFasrniHAY+rKbdpx5rkfb5i++A6YtUdb1xjVdHmPoJne/M5Q9YD31UxiVlibW4DxWP/nVMjuNx+XGL19CmK50letOmho/JhpNeVx14yolid8V7YFe+4aeQ27Vjl07s9DwH7DpBT7fHGNdZ0tbkQ3CnplcBnbT8ADz7N+Eo2n5MksQo3Ai+2fUv3AQ0+N0obYgHMs/2ezh3lF+WZkl4/wlj94r1H0htGGGsV8E0eXow3ecyAseqON66xpsd2K3+AeRTj7H9BMWvgj8rXFwF7JlbPeCcC+0xw7G8Sq+c1lwJvBXbt2Lcr8DbgP0YVa5xzA64F5k9w7NYpfM7a4o1rrOn+tLaPACYcSfBFT2HxizbEKuPVtmBIS2LtBCwt421qWvo5xdDiMz3AfEN1xhrn3CQdAVxje7NZaCUdZvsLVWPVHW9cY01Xa9csVrH4xScp2n8vL38ALpC0NLF6xnsrxZQZAr5X/miKuc34WAC2f2X7bbb3tr1z+fMUFzNLHjaqWOOcm+3P9PpyLO00SKy6441rrGkb5u3HOP1QNJNs3WP/NhQrDSXWFpLbuMaq8F63jGOscc4tn7OZnzZ3Fte5+EUbYo1zbuMaC9W4OladseqON66x6o43rrGmq82F4BTqW9WqDbHGObdxjQX1ro5V9zKa45pbPufUPueUtbYQ2L5Y0l7UsPhFG2KNc27jGqtU59KXdS+jOa655XNO7XNOWatHDUVERItHDUVERCGFICKi5VIIYkaTtLukL0q6QdKNks6WtG2F63qusSvpDJWL+kg6RdIjJjjvZZK+L+kHkq6T9MZy/2GSFlR4/0rnRdQhhSBmLEkCPkexYMp8YD6wPXDWVGPaPs32f5SbpwCbFQJJWwPLgZfb3gd4JnBZefgwoMoXfNXzIqYtncUxY0l6MfAO28/v2PcoimcE5gJHAAttLymPfYliac/LyjuCj1DMmnk7cKTtDZI+RjHa44+AfwbWAnfYflHHe+wM/BB4ou3/17H/T8trf13+vAI4AFhM8cDaOuA1FDNPdp8HsAyYA9wL/JXtH9byFxWtlzuCmMmeCjxs6UTbdwM3UTwX0M8jgdW2n0oxQ+Q7uuJ8EPgpxZTQL+o6difFHDs3S7pA0jGSZrlYknAF8He297X9Y+Bztvcr7xyuB46f4LzlFJPePRv4W+Ccgf82IibQ2ucIIibxAMUsrQD/RtHEVJntEyQ9HTiQ4ov7IIp1A7o9TdK7KaYd3gG4pPsESTsAfwp8umjtAmDSfo6IqlIIYia7jqL550Fl09DjKZp0nsbD74q36xNr4DZU29cA10j6BPATeheCjwGH2f6BpNcBL+xxzizgLtv7DppDRBVpGoqZ7GvAIyS9FkDSbOB9wNll2/1NwL6SZkmaS/E08SazeKiIHA18u0f8e4Adu3dK2kHSCzt27ctDcxd1X7Mj8LOyg/mYXrHL5qyfqFhkCBX26ffBIwaRQhAzlouREIcDR5RzB/0SeMD2P5anfIfiN/XrgA8CV3Zc/ltgf0nXUnTontHjLZYDF0v6Rtd+AW+VtFbSVcDpPHQ3cCHwd+XQ0j8B/oFievDvUHQwM8F5xwDHS/oBsIZi3v+IWmTUULRGOWrnAuBw21dOdn5EW6QQRES0XJqGIiJaLoUgIqLlUggiIlouhSAiouVSCCIiWi6FICKi5VIIIiJa7v8D7mXplPsnFQsAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "state = cir()\n",
    "# Repeat the simulated measurement of the circuit output state 1024 times\n",
    "prob_measure = state.measure(plot=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After measurement, we can find the bit string with the highest probability of occurrence. Let the vertices whose bit values are $0$ in the bit string belong to the set $S_0$ and the vertices whose bit values are $1$ belong to the set $S_1$. The set of edges between these two vertex sets is a possible maximum cut of the graph.\n",
    "\n",
    "The following code selects the bit string with the greatest chance of appearing in the measurement result, then maps it back to the classic solution, and draws the corresponding maximum cut:\n",
    "- The red vertex belongs to the set $S_0$,\n",
    "- The blue vertex belongs to the set $S_1$,\n",
    "- The dashed line indicates the edge being cut."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:10:36.652097Z",
     "start_time": "2021-04-30T09:10:36.465888Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The bit string form of the cut found: 0101\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAArzElEQVR4nO3deXQUVdoG8Kc7a3cIaTYhCYu4gEMQUEA0AuHzIAok4AwDqOxRNh0QEcUZFJhx/BQEZHFkU3YVhHEhyOIoiElw2D6RTRIiIAaiYCCRLJ2t7/fHtZskZK/qruqu53dOzkl3kqpXTPrpW/ete01CCAEiIiKDMGtdABERkScx+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRoTD4iIjIUBh8RERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGhMPiIiMhQGHxERGQoDD4iIjIUBh8RERkKg4+IiAyFwUdERIbC4CMiIkNh8BERkaEw+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRofhrXQCREdjtwNGjwOHDwIULwLVrQHExEBICNGgAdOwIdO4MNG2qdaVEvo/BR+QmR44Ab70F7N4N/PQTYLXKsMvLK/t9/v4yAO12+T133QXExwN//jMQFKRJ6UQ+zSSEEFoXQeQr7HZgyxZgzhzgzBmgoAAoKan9cerVA0wmYPx44C9/AVq1Ur9WIqNi8BGpZNs2YNQooLAQyMlR55iBgYDZDIweDcybJ0eGRKQMg49IoatXgXHjgO3bb7yMqRaLBbDZgE2bgB493HMOIqNg8BEp8OWXwODBMvAKCtx/PotFzv8tWgT4+bn/fES+iMFHVEdbtgAjRwL5+Z49r9UK9OoFfPQRm1+I6oLBR1QHH34o5908HXpOFgsQHQ3s2AEEBGhTA5G3YvAR1dLnnwOPPKJd6DlZLEDfvnLkaTJpWwuRN+HKLUS1cPkyMGSI9qEHyBp27QJWrtS6EiLvwhEfUS3ExgL/+Y+8ZUEvQkKAkyeBli21roTIO3DER1RDmzcDe/boK/QA2U362GMA38IS1QyDj6gGrl0Dxo513316ShQXA999B6xbp3UlRN6BwUdUA+vWyYDRq9xc4JVXOOojqgnO8RFVQwigdWvgxx+1rqRqISFy/vG++7SuhEjfOOIjqkZiIvDrr8qP07s3sGAB8NVXQHa2DFTnR0yM8uPn5cn1PImoatyWiKgaCxaoM7f39NPy/j93EUKuF3rlCtCwofvOQ+TtOOIjqkZiojpzZ0LITWgTEoD33lN+vIoEBgIHDrjn2ES+gsFHVIVLl2TjiBqGDQOaNwcGDHDfTed5ecDBg+45NpGvYPARVeHwYSA4WJ1jeWK1l+JiYO9e95+HyJsx+IiqcPCgeiM+TzlyROsKiPSNwUdUhdRUfd+/V5HMTMDh0LoKIv1i8BFVwdtGe4DcoNYTm+ISeSsGH1EVioq0rqD2zGbvrJvIUxh8RFWwWLSuoPaKi72zbiJPYfARVaFBA60rqD2zGfDn0hREleKfB1EVOneWN5ursXLLkCFA167y8xYtyn5t4kS51x8gO0k//LDu52ndmjuyE1WFwUdUhc6d1Rs99e0LjB5d8deGDr3++Zo1yoKPi1QTVY2XOomqcOednrnxXC1WK9C9u9ZVEOkbtyUiqsbttwNpaVpXUTOhoXKX+M6dta6ESL844iOqxvDh6i1b5m5BQUCnTlpXQaRvDD6iaowf7x07m1sswJQp8gZ2Iqocg4+oGs2aAQ8+qP9OSYcDGDtW6yqI9I/BR1QDzz8vG0f0ymwG+vUDbrpJ60qI9I/NLUQ1IATQo4fAN9844HDo71qixQJ8+y3Qtq3WlRDpH0d8RDVw+nQq7PY/weHQ370NISHAjBnFOHp0M/g+lqh6DD6iKpSUlGDBggXo2LEjDh/+BPXrz0JwsH72KTKbgVtvBXJyZmPIkCGIjY3FhQsXtC6LSNcYfESVSElJQc+ePfHcc8/Bbrdj1KhROHv2Jdxzjz+CgrSuTgoOlqu8tG//B9hsNmzfvh1RUVFYs2YNR39EleAcH1EFCgoK0Lp1a2RkZCAiIgIrVqxA//79AQDZ2cA99wBnz2q7/Y/FAnz0EfDww/LxxYsXMX78eGzbtg0A0K9fP6xYsQKRkZHaFUmkQww+okqsXbsWe/bswZtvvokG5bZpuHQJuPdeID1dm/CzWIC1a4HBg8s+L4TAhg0bMHnyZGRlZSEsLAyHDh3Cbbfd5vkiiXSKwUcEOZe3aNEiBAQEYNKkSTX6mStXgJgY4IcfPLeep8kkQ2/zZnn7QmWco7+SkhJ89tlnMOn9JkQiD2LwkeGlpqZizJgx2LdvH4KDg3HmzBmEh4fX6Gfz84EXXgDefdf94We1yu2MNm+Wi2dXRwiBvLw8hISEAJBzlvv27cPo0aMZhGRobG4hwyrdsblv3z6Eh4dj8+bNNQ49QI6+liwBvvgCiIx0z87nzlHeCy8Ax47VLPTkz5lcoVdSUoL4+HjEx8ez85MMj8FHhpSamlqmY3PkyJE4ceIEYp27wdZSdDRw+jQwebLcIaFePeU1BgbKrs1evYD9+4FZs4CAgLody2w2Y8KECez8JAIvdZJB9e7dG19++SXCw8OxYsWKOgdeRQoKgC1bgDlz5PwfUPMd3P395SVNIYAJE4CnnwZatVKtNHZ+EoHBRwYihHDNbaWmpmLu3Ll44403bujYVNPJk0ByMpCUBHzzDXDunAy3/PwcAAJWayiKioCwMOCuu+TorksX2TTjrnsFy3d+NmvWDGfOnIHFHddpiXSIwUc+z9mxmZycjC1btmja2FFYCGRmAhERtwDww/nzp1G/vgw+T3OO/nr16oXnnnvO8wUQaYTBRz6tdMcmAHz11VeIiYnRuCq4wlfrPz8hBIQQMJvldP8HH3wAu93Ozk/yaWxuIZ9UUcdmQkKCLkJPT0wmkyv0Ll++jIkTJ7Lzk3weg498jtodm0bRuHFjLFmypEzn5+rVqzUflRKpjcFHPmfDhg1lRnlr1651awOLrzCZTBgxYgROnjyJuLg4ZGdnc/RHPolzfOQTCgsLERgYCEAuMP2Pf/wD06ZN023g6WWOrzLlOz/vv/9+JCUlaV0WkSoYfOTVnB2bb731Fg4dOoSGDRtqXVKN6D34nDIyMvDUU09hxowZ6NKli9blEKmCwUdeq3zH5vLlyzFu3DiNq6oZbwm+ikyaNAmdO3fGqFGj2PlJXonBR17HOcqbMWMG7Ha7W1ZfcTdvDb5vvvkG0dHRALjqC3kvNreQV2HHprbuvfderFu3jmt+kldj8JFXSU9PZ8emhpydn843G9nZ2RgzZgw7P8mr8FIn6V5mZiYaNWrkerx+/XrExsZ6deB566XO0sp3fk6ePBmLFi3SuiyiajH4SLecc3kvv/wyduzYgZ49e2pdkmp8IficMjIyMGvWLMybNw/169cHUHZBcCK94aVO0qXSc3l5eXnYtWuX1iVRJZzNRc7Qy8vLQ7du3Tj3R7rF4CNdqWyNzVdffVXr0qiG3nvvPRw8eJBzf6RbvNRJunHu3DkMGzbMdV/eyJEjsXDhQq+ey6uML13qLK/83F9YWBgWLlzI+/5INxh8pBuXL19GVFQU/P39ve6+vNry5eBz4m7vpFcMPtJUWloaWrVqhYCAAADA/v370aZNG58c5ZVmhOADbhz9bdq0CUOGDNG6LDI4zvGRJpxzeXfeeSdee+011/PdunXz+dAzktL3/c2dOxeDBw92fS0/P1/DysjIGHzkceVXX/npp598fuRjdBEREXj++eddI92jR4+iVatW3O+PNMHgI4+prGNz5cqVbHowmPfeew+XL1/mfn+kCc7xkUdcvXoVsbGxhujYrAmjzPFVpqLOzzfffBOjR4/mmyByO474yCNsNhssFgvX2CQAVe/2fvHiRa3LIx/HER+5TWpqKgIDA3HzzTcDkO3tFouFgQeO+EorPforKirCsWPH0Lp1a63LIh/G4CPVld4vr1u3bti9ezfMZl5cKI3Bd6OMjAwcOXIEffv2BQA4HA5cunQJzZo107gy8jV8NSJVle/YbNWqFex2u9ZlkRcIDw93hR4ALF26FHfccQc7P0l1DD5SRWUdm2vXroXVatW6PPJCycnJZeb+2PlJauGlTlLM4XCgd+/e2LNnDwB2bNYEL3VWj52f5C4c8ZFiZrMZvXv3Zscmqaqyzs/+/fvjypUrWpdHXowjPqqT1NRUnDt3Dn369AEAFBcX49q1awy8GuKIr3ZKj/5uueUW/Pe//3Wt70pUWww+qpXSHZtWqxUnTpxg110dMPjqJiMjAzk5Obj99tsBAJcuXUJRURF3fKBa4aVOqrHyHZuxsbEICgrSuiwykPDwcFfoCSEwceJEREVFcbd3qhUGH1Wrqo5NXtokrdjtdhQWFiI7O5u7vVOtMPioWvHx8a5R3siRI3HixAmf3iSWvIPFYsHWrVuxbt062Gw2bN++HVFRUbzvj6rFOT6q1r59+zB06FAsXbqUgacSzvGpq/xu7/3798enn34KPz8/jSsjPeKIj26QkpKCefPmuR5HR0cjLS2NoUe6FRERUWb016ZNG4YeVYojPnIpKSnBwoUL8dJLL8Fut2PXrl2u2xVIXRzxuU9GRgbCwsJcKwYdPHgQERER7PwkF474CIAc5fXs2RPTpk2D3W7HqFGj0LVrV63LIqq18PBwV+j99ttvGDRoEDs/qQwGn8GVlJRg/vz56NSpE/bt24eIiAhs27YNa9asYccmeb2CggJ07NiRnZ9UBoPP4F5//fUyo7zjx4+jf//+WpdFpIomTZpU2PnJ0Z+xcY7P4LKystCnTx/MmjWLgedBnOPzvPKdn0888QTeeecdjasiLXDEZzCpqakYPXq0a488m82G/fv3M/TI55Xv/PzjH/+odUmkEQafQZSUlODNN99Ex44dsXbtWsyZM8f1NW7xQkbh3PHh7NmzZd7srV+/nnN/BsLgM4DU1FTExMRg6tSprtVXJk+erHVZRJqx2Wyuzw8cOIDRo0dz7s9AGHw+rPQoLzk5GeHh4di6dSvX2CQqpUWLFujfvz87Pw2EzS0+bNu2bYiLiwPAXdH1hs0t+lLRbu8LFy7EqFGjOBXggxh8PkwIgfHjxyMuLs4VgKQPDD59Kt/5+corr+Cll17SuCpSG4NPDcXFQH4+YDIBFgug0RqBqampmDhxIpYsWYJ27dppUgPVDINPv5yjv9mzZyMxMRERERFaFwTY7UBhIRAUJD84ClWEwVdbp08DBw4A33wDJCUBp07JX0hn2BUXA1YrEBUF9OwJdOsmP1q2dFtJpXdFt9vtGDhwID755BO3nY+UY/DpX3FxMfz9/QHIv7EXX3wRzzzzDJo3b+6+k+bmAgcPAocOAV99BRw+DPzyC2A2yw+HQ35ERgJduwIxMUDnzkCXLkBwsPvq8jWCqpeXJ8Tq1ULccYcQFosQ9eoJId+HVf1hNgsRGipEcLAQXbsKsWWLEIWFqpaWkpIioqOjBQABQIwcOVJcuXJF1XOQ+pz/v8g7LFiwQAAQYWFhYtWqVcLhcKh7ghMnhBg7Vr6+1K8vRGBgzV5jgoLk99erJ8Qzzwjxww/q1uWj+JdXlStXhJg8Wf5S1TTsqvoIDRXCZhNi5kwZpgoUFxeL+fPni+DgYAFAhIeHi4SEBJX+w8ndGHze5eLFiyIuLs71/61fv34iPT1d+YF37RKic2cZeP7+yl5fAgLkm+wePYRISlJemw/jX15ltm4VokED+Y5KaeCV/7BYhIiMFCI5uc7lnT17VlgsFo7yvBSDz/s4HA6xbt06YbPZlI/+rl4VYuhQIaxW9V9fnK8xEyYIkZur+r+DL+AcX3lXrwLjxgHbtwN5ee49l8UCxMcDb7whP69GSUkJzGaza35o9erVaNKkCTeI9UKc4/NeGRkZGD9+PBISEgAAW7ZswaBBg2p+gO3bgREj5HxeQYGbqoR8TbHZgE2bgB493HceL8TgKy0tDbj/fiA7272/kKVZLECLFkBiInDTTZV+W2pqKsaMGYMxY8bgySef9Ext5DYMPu8mfu/83Lx5Mz7++OOa7fYuBPDyy8Cbb7r/TXVpFgvw+usAV2tyYfA5HT8u3xVlZ8tfUE8KCACaNgX++1/ZrVVK+Y7NO+64A8ePH6/ZHxrpFoPP96Snp2PatGmYP3/+jbu9CwH85S/AmjWeDT0nqxWYPh2YOdPz59YhLlkGAD/8IG89yMryfOgBQFERkJEBREcDly+7nk5NTUXPnj3x3HPPudbY3LdvH0OPSIemTZuGTZs2Vbzm5/Tp2oUeIM87Zw4wb54259cbjeYW9ePaNSEiIuStB+6YZK5tV1aHDqLYbmfHpo8Dm1t8zoULF0RsbOyNnZ8rVriviaW2H1arEB9/rPU/leZ4qTM+HvjgA7kygh6EhKB4+nR03rIFR48e5RqbPoqXOn2TEGXX/GwfGor/KyhAQGGh1qVdZ7PJfoZGjbSuRDPGDr7du4G4OO0uP1TGYsH3Gzbgh8BAdmz6KAafb8vIyMD4cePw4rZt6AogQOuCSgsMBPr2BQy8upNxg+/aNeC224BLl7Su5EYmE9CuHXDkCPD7kknkWxh8vk8sXYriZ59FgKc6xGvDagU2bAAMugu9cZtbliyR4adHQgDnzgFbtmhdCRHVhd0O0/Tp+gw9QF7levppue6nARkz+EpKgIUL5Y4KepWbC8ydq3UVRFQXW7Zo0yFeG9euAV98oXUVmjBm8O3cqZ9mlqqcOiXvLyQi7zJnDpCTo3UVVcvJMeyba2MG39y5yi9z2mzAyJHAO+/IrUMuXJCrvWRnyy1F/v53QGknZmGhXOWBiLzHt98CZ84oP07DhsCrrwJHj8rXq2vX5Oevvqr8tcUpORk4f16dY3kR4zW3XLsm23iLipQdZ9Cg6ufgLl4EHngASEmp+3nq1QN++40bT/oYNrf4sOnTgfnz5ZRKXUVFAZ9/DlS2Ce7Fi0CfPsCJE3U/ByD38Pvf/wWefVbZcbyM8UZ8334rO5rUkpUFbNwo1+CbN0/+QjpFRADLlys7fkmJId+REXmtvXuVhV5wMPDRR9dD7+pVeZVqzhz5OSC/9u9/y93YlbDbZb0GY7xe+cOH1Znfu3IFeOYZYOXKsk0yc+bIebmmTeXjHj3kqK2u1/sDAmTNrVopr5mI3EsI5fPyw4YBbdpcf/z447IvAZAhtX27/LxtW/m9q1YpO9+hQ8p+3gsZb8S3d686Oy/s2QMsXnxjZ+ivv8qdFpzMZnnDaF3l5MjFq4lI/86fV36LQOl767Kzr4ceID//7bfrj//0J2XnAuS9zHq9tctNjBd8337r/nPcccf1z9PS5OiwrhwO4JtvlNdERO733XfyKo0SnTpd//zs2bJfE6Lscx07KjsXIKd+DNY9brzgc3eL8cyZQPv2ZR8rlZ2t/BhE5H7Z2cpHfKXX0Cw9uqvoucaNlZ2rqvP4MOPN8blrsViTSTa3TJ16/bnZs+UC2ErpdfUHIirLbld3NZSKurnV7vAWwjvua1aR8YLP7IZBbr16MuCcC0o7HMALL8iWZjVw/z0i7+DnpzyYMjOvb0hdv/6NXy/93K+/KjsXIOs12GuM8YJPaftveS1bAgkJQIcO8nFuLjBiBPDxx+qdIzhYvWMRkftYLMrfXB85cj34WreWweS839Nkks85ffedsnM5WSzqHMdLGG+Or1kz9Y7VrRuwf//10PvpJ6B7d3VDD5DhSkT6FxmpfMRXerug+vXlFkJOffsCoaHXH6vxWlNSUvmN8j7KeCu3PPUUsHSp8uPcdx/w5ZfX3ykVF8uFr3/++cbv3bQJSE+v23mCgoDXXjPcygq+jiu3+Cg1VoYKDpYjOee9fFlZ1xfCGDfu+nJlqamyq1Pp/FxQkLxSZaDLnca71HnffcD69cq7O9u0KXt5wN8fmDat4u89dKjuwRccDHTuXLefJSLPCg0FmjQpu4JTbdnt8v68//wHCA+X6wJPn172ezIy5Peo0ZTSpo2hQg8w4qVObwuRvDzgrru0roKIaqpLF+XHOHFC3hb12mvy89xc+XHihHyufXvl63Q6de+uznG8iPEudZaUyHdQet8yxOnWW+VN8ORTeKnThy1dKq/+5OVpXUn1QkPlkmd//rPWlXiU8UZ8fn7AE08oX13BE0JCOLdH5G0ee8x7djY3mYC4OK2r8DjjBR8ATJrkHde0HQ55awQReQ+bTW5bpvfXmMBAYPx49W/x8gLGDL5bbwW6dtW6iqr5+wOPPlrxDaxEpG9Tp+o/UMxm4Omnta5CE8YMPgCYMUNeStSrgADguee0roKI6uLuu4G2bSH0uoG0vz/Qq5dhtzszbvA99BDQu7eyLYPcJA/AyZgYiHbttC6FiOrox1dfRYFegy84WO4lalDGDT4AeOcd3S3V4wBwCcBdO3diwIABuKjkfiAi8jiHw4FFixbhD4MG4R8OB3K1Lqi8kBC52Ebz5lpXohljB1/jxsDq1XI/Kp0wWSw4/vLLsISFYdu2bYiKisL69evZ9k7kBdLS0tCrVy9MmTIF+fn5SH/sMQTdcYf6OyrUlb+/vJc5Pl7rSrQlSIgxY4SwWoWQS8Fq92G1CvHKK0IIIdLT00W/fv0EAAFAxMbGiszMTI3/oUgtzv+v5DvefvttYbFYBADRtGlT8cknn8gvpKQIUb++9q8vJpMQjRsLkZ6u7T+UDhh7xOe0ciXw4IPaXva0WuX9hTNmAAAiIyOxbds2rF69GmFhYTh37hxC9NyMQ2RweXl5yM/Px7Bhw3Dy5EkMHDhQfqFNG2D3bm2b6UwmICwMSE6+vvODgRlv5ZbKFBXJ2wd27vT8igtWKzBhgtzItoJLIhcuXEB2djba/d7scuXKFRQUFCA8PNyzdZJquHKL93M4HDh16pTr77KkpAR79+7FAw88UPEPHDgg32B7erdzs1neW5iYCLBhDoDR5/hKCwgANm8GnnzScyM/k0mea/ZsuWltJfMAkZGRrj8uAJg0aRLatWvHuT8ijaSlpSEmJgbR0dG4cOECAMDPz6/y0AOAe+65PuLy1GuM1Qrccgtw+DBDrxQGX2lmM7BokRz1hYe795fTapWXQPbvB55/vsY/VlBQgKtXryIrKwsjR47EwIED2flJ5CHOjs0OHTogKSkJwcHBOHfuXM0P0L693E4oPt69ry/ON9VTpwInTwI33+y+c3kjbacYdSw3V4gJE4SwWIQICFBvgjkoSB5z9mwhCgvrVJrD4RCrVq0SYWFhAoCw2Wxi3bp1wuFwqPyPQO4CNrd4ndOnT4vu3bu7/t8NGzZMWcNZcrIQkZFC1KunbhNLvXpC3H67EEeOqPcf72P4l1edlBQhnnpKiJAQ+VHXX8bQUCFsNiH+9jchfvpJldJ++ukn0bdvX9cfYlxcnCgqKlLl2OReDD7v8v7771fcsalUQYEQGzcKcddd8g2xn1/dXl8CAoQIDhYiOlqITz8Vgq8DVeKlzuq0aQP861/ApUvyMujdd8s1+EJC5JYeFc3Lmc1yjU2rVX7cf7+8Wf7SJeDVV1W7cbR58+b47LPPsGrVKoSFhaF58+bw9zfe3sJE7nb77bejsLDwxo5NpQIDgaFDgf/7P9n8MmqUnGYJCJBdmJWt9xkcLF9j/P2BFi3kYtNHj8o5xAED5PNUKXZ11oXDAZw+LSeMDxwAfvlFbhJpMslAbN5cTmR37iyvrXvg5tX09HTYbDbUq1cPAHDkyBHcdNNNiIiIcPu5qfbY1alvDocDn3/+OR5++GHXcykpKWjbtq1nCsjOBr79Vr7GHD0q9w8tKLgeeB07yteXTp2A3//mqeYYfD4oNzcXHTp0wJUrV7B48WIMHz7c9UJL+sDg06+0tDTEx8cjMTERW7duRZwB96vzdbzU6YPy8vLQtm3bMp2fGRkZWpdFpGulOzYTExPRtGlTTh34KAafD2rSpEmZub+EhATe90dUhfJrbDrn8vr27at1aeQGvNTp49LT0zFu3Djs2LEDABAfH493331X46qIlzr1Y/fu3YiNjUV+fj6aNm2K5cuXq9e8QrrEEZ+PK9/52a9fP61LItKVLl26oEmTJup3bJJuccRnIJmZmWjUqJHr8Ycffoju3buz81MDHPFpx+FwYNWqVXj88cdh/X1LsvJ/G+TbOOIzkNJ/2EeOHMGwYcO43x8ZinMub+zYsZjx+04oABh6BsPgM6gmTZrgwQcfZOcnGUJFHZu9evXSuizSCIPPoCIjI9n5SYZQWccm5/KMi3N8dEPn59///nfMnDlT46p8G+f4POOHH37AnXfeyY5NKoPBRwDkC/CaNWswa9YsJCYmolWrVlqX5NMYfJ4zePBgBAUFYfHixWjYsKHW5ZAOMPiojMLCQgQGBgKQ8yKzZs3CxIkT2fmpMgafezgcDrz11luIiYlBx44dAZT9nSYCOMdH5ZR+gVi2bBn++c9/svOTvIJzLu+ZZ57BmDFjUFJSAgAMPboBg48qNXDgQPTr18/V+TlgwADu9k66U1HH5qxZs+Dn56d1aaRTvNRJVRJCYO3atZgyZQqys7Nhs9m444MKeKlTHaV3UgCAYcOGcS6PqsXgoxq5cOECxo0bh+3btwMANm7ciKFDh2pclfdi8CmXn5+Pm2++GZcuXWLHJtUKg49qzDn6e//997F9+3Zu2aIAg08dS5cuRXJyMkd5VCsMPqo1IYTrhfvnn3/GtGnTMHfuXHZ+1gKDr/YcDgeWLFkCq9WKsWPHAij7u0hUUww+UmTEiBHYsGED5/5qicFXO2lpaRgzZgySkpIQEhKCM2fO4KabbtK6LPJS7OokRV5//XV2fpLblO7YTEpKQrNmzfD+++8z9EgRjvhIMXZ+1h5HfNUrPcoDgOHDh2PRokWcyyPFGHykmtKdn2azGceOHUO7du20LkuXGHzV69mzJxITE9GsWTMsX74cAwYM0Lok8hEMPlKVc/R3/vx5LnRdBQZf9Y4dO4b58+djwYIFHOWRqhh85HY7d+7E22+/jWXLlrHz83cMvrKca2wePHgQ69at4yVycisGH7mVEAIdOnTA8ePHOfdXCoPvuvKrryQnJyM6OlrjqsiXsauT3MpkMmHHjh3o27cvOz+pjIrW2Pz4448ZeuR2HPGRRzj3+3v22WfZ+QmO+MqP8h5//HEsXrwYjRo10rgyMgIGH3lU6d3eIyMj8f333yM0NFTrsjzO6MH3wgsv4I033kDTpk2xbNkyPPLII1qXRAbC4COPc3Z+hoeH46GHHgIAFBcXw8/PzzCjPyMGX3FxsWt917y8PMycORN//etfOcojj2PwkS688MILOHXqFJYvX47w8HCty3E7IwWfc43NpUuXYv/+/QgLC9O6JDI4NreQ5rKysvDuu+8iISEB7dq1427vPsS5K/qUKVOQkpKCLVu2aF0SEYOPtGez2fDdd9+V6fwcOHAgMjIytC6N6qiijs1PPvkETzzxhNalEfFSJ+mHkTo/fflSJ3dFJ73jiI90w2QyYcyYMTh+/Lhr9MdLY94nJSWlzChvw4YNDD3SFY74SJeEEFi3bh369OnjanbJyspCWFiYT4z+fG3El5WVBZvN5nq8cuVKDBo0iIFHusTgI69QXFyM6Oho10r93t756SvB5+zYfPnll/HFF1/gnnvu0bokomrxUid5hZMnTyI1NZWdnzpSumPz2rVrSEhI0Lokohph8JFXcC50zc5P7VXWsfnKK69oXRpRjfBSJ3mVijo/3377bTz22GNal1Yr3nqp88cff8SIESPYsUlejSM+8ioVdX5evnxZ67IMIyAgAMeOHWPHJnk1jvjIawkhkJCQgNjYWJjN8j1cWloabr31Vt13fnrTiO/s2bNo2bIl/Pz8AABff/012rdvz8Ajr8URH3ktk8mEAQMGuELv/PnzuPvuu7nfn0qcc3lRUVFYsGCB6/mePXsy9MirMfjIZ5w6dQpmsxnbtm1DVFQUOz8VSEtLQ0xMDKZMmYL8/HykpqZqXRKRahh85DP69OmDEydOoF+/ftztvY5Kd2wmJSWhWbNm+PTTT7Fy5UqtSyNSDef4yOc49/ubMmWKq/Nz/fr1iI2N1bo0Fz3O8WVmZuKRRx5BUlISAGD48OFYtGgRL2uSz+GIj3yOyWTC6NGjXaO/nJwcNG/eXOuydM9ms0EI4RrlrV+/nqFHPokjPvJpQggcPXoUHTt2dD339ddfo0ePHpp2fuplxJeWlgaLxYLIyEgAskGoXr16DDzyaRzxkU8zmUxlQu+jjz5CTEyMx1d9KSgADh8GVqwAZs8GgDcALMTf/gbMnQvs2gX8+qvHyikzl/fkk0+6Arhly5YMPfJ5/loXQORJRUVFCAsLQ0JCAhITE92639+xY8C//gV8+SXw449AcDBQUgLk5QHANADAa68BAQGAxQLY7UBoKHD33cATTwB//CMQGKh6WTfsl9eoUSPY7XZYLBb1T0akQ7zUSYaTnp6OcePGYceOHQCA2NhYLF++HBEREYqPXVgIfPQRMGcOkJIiH5eU1P44oaGA2QxMmAA8/TTQooXi0lw7Kfz1r39Ffn4+mjZtiuXLl2PgwIHKD07kRRh8ZEgVdX7u2LED9957b52PuX07MHKkDLtr19SpMygIMJnkCHDuXMBqrdtxSkpK8OCDD2LPnj0A2LFJxsY5PjKk8p2fDRs2xJ133lmnY2VlAY8+CgweDGRmqhd6gJwbtNuBVauANm2A5OS6HcfPzw/3338/OzaJwBEfEYQQ+OWXX9CsWTMAQE5ODj777DMMGTKk2rm/r74CBg0CcnNlSLmbxQKMHQssWAD8vnRmpdLS0nDhwgXExMQAAAoLC5GTk8PAI8PjiI8Mz2QyuUIPAF588UU8+uij1XZ+fvwx0K8fcOWKZ0IPAPLzgXfekY0vhYUVf0/pjs2hQ4ciMzMTABAYGMjQIwKDj+gGXbt2dXV+Vrbb+7//DQwbJoPI0/LygC++AOLigOLisl8rvSt6fn4+evfurfudKog8jZc6iSpQvvMzLi4Oy5cvR3h4OL78EhgwwHlbgnasVqB/f2DTJkAIdmwS1RSDj6gS5Xd7b9CgAfbuPYEePcKRna11dVJICLBwIbB37whs2LABAHdFJ6oOg4+oGs7Rn81mQ27u+9i5s/L5NS2EhADvvJOMqVMHY+nSpRzlEVWDwUdUA0IIbNxYiCefDNL8Emd5/v7AvfcCu3blw2rl6itE1WHwEdXAtWtAy5bynj09CgkBli0Dhg/XuhIi/WNXJ1ENbNgAFBVpXUXlcnPl4td8G0tUPY74iKohBHDLLcC5c1pXUrWQEHmbg4JV14gMgSM+omokJQGXLys/zuzZwNatwOnT8qb3oiIgOxs4ehR4+22gfXtlx8/PB+bNU14nka/jiI+oGn/6E/DJJ8ovI1b384WFcr3PrVvrfo7gYODiRaBBg7ofg8jXMfiIqtGokRyhKfXzz3L0eOaMPF69ekCfPkDXrte/5+RJICqq7ucIC5M3tD/0kPJ6iXwVg4+oCpcvA82bu+++PZMJ+P57oG1b+Tg/v+5bDwFyU9uZM4GXXlKnPiJfxDk+oiocPix3RFCbyQQ0bCi3M2rZ8vrzx44pO25Rkdwxgogq5691AUR6duCAvFVALa1aVd4d+uuvwOTJys9x5IjyYxD5Mo74iKqQmnrjDgjucPIk8D//A+zfr/xYmZmAw6H8OES+iiM+oiqoOdoDZFPLtGlymbFmzYDYWOC224B27eToMj4e2LhR2Tn8/OT+gO64REvkC9jcQlSF2Fjgs8/cd3w/P2DnTqB3b/k4Nxe49Vbgl1/qfsyAAHnZtH59dWok8jW81ElUheBg9x6/pARISLj+OCQE6NZN2TGLi91fN5E3Y/ARVUGtLe169Kj4pnKTCejbt+xzSq/BmM1y1EdEFeMcH1EV7r5b3lendCui+HjgscfkrQbffit3eWjcGOjXT87vOWVnA3v3KjvXzTfLQCWiijH4iKrQubNsRFFDUJBcUaWyVVV++03e1/fbb8rOc999yn6eyNcx+Iiq0KGDXE1FqXfflYF2771yJZhGjeTzV68CKSlyV4UVK4BLl5Sdx2oFundXXi+RL2NXJ1E1brsN+OEHrauomdBQYPduoEsXrSsh0i82txBV4/HHvadLMigIuOsurasg0jcGH1E1Jk70jp3Ng4OBZ56R9wYSUeUYfETVCA+XN5h7Q6fkuHFaV0Ckfww+ohp4/nll2wW5m9kMPPwwcNNNWldCpH9sbiGqASFkt+SBA55ZtLq2LBa5hdIf/qB1JUT6xxEfUQ2YTMAHH8jmEb0JCZEbzzL0iGqGwUdUQy1bAvPmyaDRC5MJaN0amD5d60qIvAcvdRLVghBy3c2DB4HCQq2rkfOOhw5xtEdUGxzxEdWCySR3U2jRQr2lzOrKYgE+/JChR1RbDD6iWmrQAEhOBiIjtdsFwWKRy6D176/N+Ym8GS91EtXRr78CMTHAmTOA3e6Zc5pMMvQ2bgTi4jxzTiJfwxEfUR01bixvbxg9WoaRu1mtct3QffsYekRKcMRHpIKvv5ZbCmVlqbObQ2kmk1yObOpUYNYsbjJLpBSDj0gleXkymJYtk49zcpQdLzBQrsjStSuweDHQqZPiEokIDD4i1eXnA5s3A3PmAOfOyVsgajoK9PeXlzQdDmDsWGDSJHmfHhGph8FH5EZHj8oO0KQkYP9+4Px5eanSbJaXMB0OoKhI3hTfqZNslunaFXjgAe/ZConI2zD4iDyooAC4fFmOAEtKZLjVrw80bKh1ZUTGweAjIiJD4e0MRERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGhMPiIiMhQGHxERGQoDD4iIjIUBh8RERkKg4+IiAyFwUdERIbC4CMiIkNh8BERkaEw+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRoTD4iIjIUBh8RERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGhMPiIiMhQGHxERGQo/w9aFCJRiVNAFQAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Find the most frequent bit string in the measurement results\n",
    "cut_bitstring = max(prob_measure, key=prob_measure.get)\n",
    "print(\"The bit string form of the cut found:\", cut_bitstring)\n",
    "\n",
    "# Draw the cut corresponding to the bit string obtained above on the graph\n",
    "node_cut = [\"blue\" if cut_bitstring[v] == \"1\" else \"red\" for v in V]\n",
    "\n",
    "edge_cut = []\n",
    "for u in range(n):\n",
    "    for v in range(u+1,n):\n",
    "        if (u, v) in E or (v, u) in E:\n",
    "            if cut_bitstring[u] == cut_bitstring[v]:\n",
    "                edge_cut.append(\"solid\")\n",
    "            else:\n",
    "                edge_cut.append(\"dashed\")\n",
    "nx.draw(\n",
    "        G,\n",
    "        pos,\n",
    "        node_color=node_cut,\n",
    "        style=edge_cut,\n",
    "        **options\n",
    ")\n",
    "ax = plt.gca()\n",
    "ax.margins(0.20)\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, in this example, QAOA has found a maximum cut on the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_______\n",
    "\n",
    "## References\n",
    "\n",
    "[1] Farhi, E., Goldstone, J. & Gutmann, S. A Quantum Approximate Optimization Algorithm. [arXiv:1411.4028 (2014).](https://arxiv.org/abs/1411.4028)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "3b61f83e8397e1c9fcea57a3d9915794102e67724879b24295f8014f41a14d85"
  },
  "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.13"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "426.667px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  },
  "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": 4
}