{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 量子近似优化算法\n",
    "\n",
    "\n",
    "`Linux` `CPU` `全流程` `初级` `中级` `高级`\n",
    "\n",
    "[![](https://gitee.com/mindspore/docs/raw/r1.3/resource/_static/logo_source.png)](https://gitee.com/mindspore/docs/blob/r1.3/docs/mindquantum/docs/source_zh_cn/quantum_approximate_optimization_algorithm.ipynb) [![](https://gitee.com/mindspore/docs/raw/r1.3/resource/_static/logo_notebook.png)](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/r1.3/mindquantum/zh_cn/mindspore_quantum_approximate_optimization_algorithm.ipynb) [![](https://gitee.com/mindspore/docs/raw/r1.3/resource/_static/logo_modelarts.png)](https://authoring-modelarts-cnnorth4.huaweicloud.com/console/lab?share-url-b64=aHR0cHM6Ly9taW5kc3BvcmUtd2Vic2l0ZS5vYnMuY24tbm9ydGgtNC5teWh1YXdlaWNsb3VkLmNvbS9ub3RlYm9vay9tb2RlbGFydHMvbWluZHNwb3JlX3F1YW50dW1fYXBwcm94aW1hdGVfb3B0aW1pemF0aW9uX2FsZ29yaXRobS5pcHluYg==&imageid=65f636a0-56cf-49df-b941-7d2a07ba8c8c)\n",
    "\n",
    "## 概述\n",
    "\n",
    "量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是利用量子计算机来近似解决组合优化问题的量子算法，最早由Farhi等人于2014年提出。在本教程里，我们将利用QAOA算法来解决最大割问题（Max-Cut），来熟悉MindQuantum中量子线路的搭建和训练。\n",
    "\n",
    "> 本文档适用于CPU环境。   \n",
    "> 你可以在这里找到完整的可运行的样例代码：<https://gitee.com/mindspore/mindquantum/blob/master/tutorials/source/quantum_approximate_optimization_algorithm.py>。\n",
    "\n",
    "## 环境准备\n",
    "\n",
    "本教程所需要的额外库：\n",
    "\n",
    "- networkx\n",
    "\n",
    "> `networkx`是创建、操作和研究复杂网络的结构、动态和功能库。可通过`pip3 install networkx`来进行安装。\n",
    "\n",
    "## Max-Cut问题描述\n",
    "\n",
    "Max-Cut问题是图论中的一个NP-complete问题，它需要将一个图中的顶点分成两部分，并使得两部分被切割的边最多。如下图（a），一个图由五个顶点构成，相互连接的边为```(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (0, 4)```。为了使得被切割的边最多，我们尝试通过（b）图的分割，将1、2、4分为一组，0、3分成另一组，因此可得到被切割的边有5条。当图中顶点增多时，我们很难找到有效的经典算法来解决Max-Cut问题。下面，我们介绍怎么将Max-Cut问题转化为一个哈密顿量的基态能力求解问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![max cut](./images/Max_Cut.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Max-Cut问题量子化\n",
    "\n",
    "这里我们将图中的每个顶点赋予一个量子比特，当顶点被分到左边时，我们将该顶点上的量子比特设置为$\\left|0\\right>$态，同理，右边为$\\left|1\\right>$态，当两个顶点被分到不同的集合中时，这两个顶点上的比特将处于不同的量子态。例如对于第0个顶点和第1个顶点，当其连线被切割是，两个顶点上的比特对应的量子态可以为$\\left|\\psi\\right>=\\left|0_11_0\\right>$或$\\left|\\psi\\right>=\\left|1_10_0\\right>$，其中下角标表示顶点的序号。此时，我们选择哈密顿量$H=(Z_1Z_0-1)/2$，这里$Z$为泡利$Z$算符。不难发现：\n",
    "\n",
    "$$\\left<\\psi\\right|H\\left|\\psi\\right>=-1$$\n",
    "\n",
    "而当顶点被分到同一集合中是，不难验证此时：\n",
    "\n",
    "$$\\left<\\psi\\right|H\\left|\\psi\\right>=0$$\n",
    "\n",
    "因此，我们只用按照上面的规则，写出图对应的哈密顿量$H$，利用量子计算机求得$H$的基态能量与基态，我们就可以得到该图的Max-Cut切割方案与最大切割边数。我们记所有边的集合为$C$，所有边个数为$c$，则哈密顿量可写为：\n",
    "\n",
    "$$H=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2$$\n",
    "\n",
    "## 导入相关依赖"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mindquantum import Circuit, Hamiltonian, UN, H, ZZ, RX, StateEvolution\n",
    "from mindquantum.nn import MindQuantumAnsatzOnlyLayer\n",
    "from mindquantum.ops import QubitOperator\n",
    "import networkx as nx\n",
    "import mindspore.nn as nn\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 搭建所需求解的图\n",
    "\n",
    "通过`add_path`可在图中添加边。最后画出图的结构。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAzY0lEQVR4nO3de1hU5b4H8O9cgGEUGBBQE83LKIhuzSzBK2ilZhpmWlZq2tnZyfbu1Om2O0mmpLVPaZ1dVtsu7rKduaO72cVM1FKk1EwdEDBTUxRmuN+GmWGdPwy2xCgIa3jXWvP9PA/PY8Mw8+N5evm+6zfrfV+dJEkSiIiI/IRedAFEREQdicFHRER+hcFHRER+hcFHRER+hcFHRER+hcFHRER+hcFHRER+hcFHRER+hcFHRER+hcFHRER+xSi6ACI1sVc6kb7nV+ScLkd5rRuhJiPiuoVi1vAYdOkcJLo8ImoFHffqJGrZ/hOlWJ2Rj225RQAAp7u+8Xsmox4SgOTYKCxKsmJoT4uYIomoVRh8RC14O/MXLN+Ug1q3BxcaLTodYDIa8NiUOMxJ7N1h9RHRxWGrk+gCzoZeNmpc9S0+V5KAGpcHyzdlAwDDj0iheMVHdB77T5Ri9quZqHF5Gh+T3HUo+eYNVOXsgFRXg8Cu/RB+1R8RdElsk58NDjBgw8JEDImxdHDVRNQS3tVJdB6rM/JR6/Y0eaz46zWo2LsRhk4WBPdPhPNkDs68uxie6rImz6t1e/BSRn5HlktErcTgI/LCXunEttyiJp/peapKUfnT14BOj66zlyMq5WF0GpQMqa4GFXs2Nvl5SQK2Hi6Co9LZwZUTUUsYfERepO/5tdljLvtxoN4NQ2gUDJ0sAIDAblYAQF3h0WbP1wFI39v8dYhILAYfkRc5p8ubLFkAAE9VCQBAH2hqfEz3278bvneuWnc9cgoqfFglEbUF7+ok8qK81t3sMUOncABAfV1t42PSb/9u+N7vbfzqG+T841FERUU1fkVHRzf576ioKISEhECn0/ngNyGi32PwEXkRamo+NAIiewJ6IzzlRfBUlcDQKRzOglwAQGB0H6+vkzh8CGbPiEVRUVHj1+HDh1FUVITCwsLGx9xuNyIjI72GorfQDAsLY1AStRGDj8iLuG6hCDIUwOn5990thk7h6PyHq1C5/0ucWf8YAqIuRXX2t9AFBiNk+NRmr2Ey6jFmcB9cN65fi+9XU1PTJBzPDcYjR440+15NTQ0iIyPPG4y//woPD4dez082iAAGH1Ez5eXlOJaxAbXOgdAZA5t8L/zqhYDBiOrsHXCVFCCoRyzCJ/wHDOawZq8jAZh5eUyr3jM4OBi9evVCr169WvV8p9PZLAwbvvbs2dPkarKoqAiVlZWIiIi44BXlud+LiIiAwWBoVS1EasMF7ES/qaqqwurVq/Hss89i8uTJ8Iz6D+w8XnnBbcrOR6cDJsV3xStzrpC/0DZwuVyw2+3NWqzevgoLC1FWVobw8PBWXU1GRUUhMjISRiPn0aQO/D+V/F5tbS3WrFmDp556CmPHjkVGRgbi4+O97tzSWiajAYuSrT6otm0CAgLQvXt3dO/evVXPd7vdcDgcXkPRZrM1e7y4uBhhYWGt+nyyISgDAwNbLoTIB3jFR36rrq4Oa9euxZNPPolhw4Zh2bJluOyyy5o852L26mwQHKDHY1MG+tVenR6PByUlJa26miwqKoLD4UCnTp1afUUZFRUFk8nUciFErcDgI7/jdrvxz3/+E0uXLoXVakVaWhoSEhLO+3yeziC/+vp6lJaWeg3F832ZTKZWX1FGRUXBbDaL/jVJoRh85Dfq6+vx3nvvYcmSJYiOjkZaWhqSkpJa9bM//VqKlzLysfVwEdwuFzy6f9/40XAe3/jYKCxKtnJjah+QJAllZWUtXkme+2UwGFp9RRkdHY1OnTpxiYgAIg53ZvCR5kmShE8++QSpqakIDg5GWloarrnmmjb9kXNUOnHzo8/B1K0fusb0RqgpAHHdQzDzcp7AriSSJKGysrJVV5MN35MkqdVXk1FRUQgNDWVQtoPIw50ZfKRZkiThq6++wuLFi+FyuZCWloapU6e2+4/V9OnTMW/ePMyYMUOmSkkJqqqqWn01WVRUhLq6usa1lK3ZeMBisTAofyP64wPe1UmatG3bNixevBh2ux3Lli3DjTfeKNsCbofDgcjISFlei5SjU6dO6NSpE3r37t2q59fU1MBut3sNxqNHjzYLzerqaq+bDpwvOCMiIjS56YASDndm8JGmZGZmYvHixTh69CieeOIJ3HrrrbIvxHY4HOjSpYusr0nqExwcjJ49e6Jnz56ter7T6WxcS/n7q8m9e/c2C8/y8nJERES0+oqyS5cuit90YP+JUizflOM19Kps22D/5BkAQMgV1yPi6oWN36tx1WP5phwMibHI8hk6g480Yd++fUhNTcVPP/2E1NRUzJ8/HwEBAT55L7vdzuCjixYUFIQePXqgR48erXr+uZsO/P7rwIEDzR4rLS2FxWJp9RVlZGSkz8bI+Xg73BkA3OV2FH/5EqA3APXe1802HO4sx6YQDD5StUOHDmHJkiXYuXMnHn30UaSnp/t0vZckSSgpKWHwkc+1ZdOB4uJir59L5uTkYMeOHU2uNIuLixESEtLqjdGjoqLatemAt8OdgbNjyvHZKhhCusAUdSmqs3d4/flzD3du741kDD5Spby8PCxduhSbN2/GQw89hLfeeqtD1m2VlZXBbDZ3+EyZqCVGoxHR0dGIjo7GoEGDWnx+fX19Y1D+/uvIkSPIzMxs8pjdbofZbG71xuhRUVEIDg5ufD9vhzsDQMX3H6P2Vxu6z1uF8u8/vmDNDYc739WKjd8vhMFHqnLs2DGkpaXho48+wn333YeXX34ZISEhHfb+/HyPtEKv1yMyMhKRkZEYOHBgi8+XJAmlpaVeb+Y5fvy4183RAwMDG4OxdtjNcIbHNnnNuqJfULLtTVjGzkFg174t1iDX4c4MPlKFU6dOYcWKFVi/fj3uvvtu5OXlITzc++GvvmS323lHJ/klnU6H8PBwhIeHIzY2tsXnS5KE8vLyxhB8crsdZaVNn1N9eCfgcaP2+AE4TxxCXeFRAEBN3m6UGAMRnjy/2euW17ra/bsw+EjRCgsL8de//hVr167FHXfcgZycHERFRQmrh1d8RK2j0+kQFhaGsLAwWK1W9D++D4d+PNX0SZIEQELtz3uaPOwuOwPnyRyvrxtqav/HDAw+UqSSkhI8++yzeOWVV3DLLbfg4MGDuOSSS0SXxeAjaqO4bqEIMp5uskOLZextsIy9rfG/7RufQ9XBLc2WMzQwGfWI697+jza0tzqSVK28vBxpaWno378/zpw5g7179+LFF19UROgBbHUStdXM4a07lPlCLuZw5wvhFR8pQnV1NVavXo1nnnkGkyZNQmZmJqxW5Zxn14BXfERtE9k5CEkDorA5+8x5tymLnHo/Iqfe7/V7Ot3ZjeDl2BOXV3wklNPpxAsvvACr1YqsrCxs3boV69atU2ToAQw+ova4J9kKk7Ftu8vIebgzg4+EcLlcWLNmDfr374+vvvoKn332Gd57771WrT8Sia1OorYb2tOCx6bEITjg4qLn7OHOcbId+cVWJ3Uoj8fTeAhs37598a9//QuJiYmiy2o1XvERtU/DRtM8nYE0r76+Hunp6ViyZAkiIyPx+uuvIzk5WXRZF43BR9R+cxJ7Y0iMRdjhzjyPj3xKkiR8+umnSE1NRWBgIJ588klMnDhRteeS9ejRA5mZma3ekZ+ILsxR6cRNj6yEuccARPe4tEMOd+YVH/mEJEnYvHkzFi9eDKfTibS0NEybNk21gQf8tpkur/iIZNWlcxDMx3fhjxMHISXlyg55TwYfyW779u1YvHgxCgsLsWzZMsycOVMTB2pWV1dDr9d3yGbYRP6kow93ZvCRbDIzM5GamoojR440HgJrNGrnfzGew0fkGx3dSVH/NJyE27dvH6ZNm4ZZs2Zh1qxZOHz4MObNm6ep0AM6flZK5C86elLJ4KM2s9lsmDVrFqZMmYJrrrkGeXl5WLhwoWbPquPne0Ty83g8KCsr69DTVhh8dNHy8/Mxd+5cJCcn48orr0R+fj7uvfden558rgRsdRLJr7S0FKGhoR3aIWLwUasdP34cd955JxITEzFgwADk5+fj4YcfRqdOnUSX1iHY6iSSn4gJJYOPWlRQUIA///nPGDZsGKKjo5Gbm4vU1FSEhoaKLq1DsdVJJD8RE0oGH51XUVERHnzwQQwaNAiBgYHIzs7G8uXLERERIbo0IdjqJJKfiAklg4+aKSkpweLFixEXF4eamhocOHAAK1euRHR0tOjShGKrk0h+bHWSUBUVFXjyySfRv39/FBQUYM+ePVi9ejV69OghujRFYKuTSH5sdZIQ1dXVePbZZ2G1WpGTk4Ndu3bh9ddfR+/evUWXpigMPiL5sdVJHcrpdOLFF1+E1WpFZmYmvvnmG7z99tvo37+/6NIUiWfxEclPRKtTW1trUKu4XC68+eabSEtLwx/+8Ads3LgRl19+ueiyFI9XfETyE9HqZPD5EY/Hg3feeQdLly5F79698e6772LkyJGiy1IFp9MJp9OJkJAQ0aUQaYqICSWDzw/U19fj/fffx5IlSxAREYFXX30V48ePF12WqjQMTjUfq0SkRGx1kqwkScLGjRuRmpoKo9GIVatWYdKkSfzj3QZscxL5BludJIuGQ2BTU1NRU1ODtLQ0XH/99Qy8dmDwEclPkiQUFxfzio/ap+EQ2DNnzmDZsmWYNWuWJg6BFY13dBLJr7y8HEFBQQgMDOzQ92XwaURWVhZSU1ORl5eHJUuW4LbbbtPceXgi8YqPSH6idkPipYDK/fjjj7j++utx4403YsaMGcjJycHtt9/O0JMZg49IfqLGFYNPpbKzs3HTTTfh2muvxVVXXYW8vDzcddddHd4y8BfcoJpIfqLGFYNPZY4cOYJ58+YhKSkJw4cPR35+Pv7rv/5L84fAisYNqonkx1YnXVDDIbAJCQmwWq3Iz8/HI4884jeHwIrGVieR/NjqJK8aDoG97LLLEBUVhdzcXDz++ON+dwisaGx1EsmPrU5qwm6346GHHsKgQYMQEBCA7OxsrFixwm8PgRWNrU4i+bHVSQCA0tJSpKamIjY2FlVVVThw4ABWrVqFrl27ii7Nr7HVSSQ/tjr9XEVFBZYvX47+/fvj5MmT+OGHH/DSSy/xEFgFcLvdKC8vh8ViEV0Kkaaw1emnqqursXLlSlitVthsNnz33Xd444030KdPH9Gl0W9KSkpgsVhgMBhEl0KkKaJanVzlLIjT6cSrr76KFStWIDExEVu2bMHgwYNFl0VesM1J5BuixhaDr4Odewjs4MGD8emnn2L48OGiy6IL4B2dRL4hamwx+DqIx+PB+vXr8cQTT+DSSy/F+vXrMWrUKNFlUSvwjk4i+VVXVwMAzGZzh783g8/H6uvr8cEHH+Dxxx9HeHg41qxZgwkTJoguiy4CW51E8hN5uDODz0ckScJnn32G1NRU6PV6rFy5EpMnT+aZeCrE4COSn8iPEBh8MpMkCV9//TVSU1NRVVWFtLQ0pKSkMPBUjGfxEclP5EcIDD4Z7dixA4sXL8bp06exdOlS3HTTTTwEVgMcDgesVqvoMog0RWQnhcEng4ZDYHNzc7FkyRLMmTOH5+FpCFudRPIT2erk5Ug77N+/HykpKZgxYwZuuOEGHD58GPPnz2foaQxbnUTyE9nqZPC1QXZ2Nm6++WZMmjQJ48ePR15eHv7zP/+Th8BqFK/4iOQnclwx+C7CkSNHcPvttyMpKQnDhg1Dfn4+7rvvPgQHB4sujXyIwUckP7Y6Fe748eNYuHAhEhIS0LdvX+Tl5eEvf/kLOnfuLLo08jFJklBcXMzgI5IZW50KVVBQgHvvvReXXXYZunTpgsOHD2PJkiUICwsTXRp1kLKyMpjNZgQEBIguhUhT2OpUGLvdjocffhiDBg2CwWBAdnY2nnrqKc76/RDbnES+wVanQpSWluLxxx9HbGwsKioq8NNPP+G5557jIbB+jBtUE/kGW52CVVZWYsWKFejfvz9OnDiBH374AS+//DJiYmJEl0aCcYNqIvnV1dWhpqYGoaGhQt7fr4OvpqYGq1atgtVqxcGDB/Htt99i7dq1PASWGrHVSSQ/h8OBiIgIYVs5+uVKa6fTiddeew0rVqzAiBEjsHnzZvzhD38QXRYpEFudRPIT3Unxq+BzuVx46623sGzZMgwaNAgff/wxrrjiCtFlkYKJHqBEWiS6k+IXwefxePDuu+/iiSeeQExMDN555x2MHj1adFmkAg6Hg90AIpmJ7qRoOvjq6+vx4Ycf4vHHH0dYWBj+/ve/8xBYuiiiByiRFonupGgy+CRJwqZNm5CamgoAeOaZZ3DttdfyTDy6aKIHKJEWsdUpI0mSsGXLFqSmpqKiogJpaWmYPn06A4/aTPQAJdIiu92Obt26CXt/zQTft99+i8WLF+PUqVONh8AaDAbRZZHKsdVJJD+Hw4HBgwcLe3/VB9/333+P1NRU5OTkYMmSJZg7dy7PwyNZSJLEKz4iHxA9rlS7gP2nn37C9OnTMX36dKSkpCA3NxcLFixg6JFsqqurodfrYTabRZdCpCmiOymqC76cnBzMnj0bEydORFJSEvLz83H33XfzEFiSnejBSaRVom8aU03w/fzzz5g/fz7Gjh2LoUOHIj8/H/fffz8PgSWfET04ibRKdKvT531Be6UT6Xt+Rc7pcpTXuhFqMiKuWyhmDY9Bl85BLf78iRMn8OSTTyI9PR1//vOfkZ+fz/PwqEOIHpxEWuTxeFBWVobw8HBhNfgs+PafKMXqjHxsyy0CADjd9Y3fMxlP47mvc5EcG4VFSVYM7Wlp9vOnT5/GU089hXXr1mHhwoXIzc3lHyHqUAw+IvmVlJQgLCxM6F33Pml1vp35C2a/monN2WfgdNc3CT0AqP3tsa9sZzD71Uy8nflL4/ccDgceeeQRxMfHQ6fTwWaz4emnn+YfIOpwdrudrU4imSlhQin7Fd/bmb9g+aZs1LjOhl359x+j8qfNcNmPA1I9wkbfAsvY2wAAkgTUuDxnn19Ti18z1uPFF1/ErFmzsH//fvTs2VPu8ohaTQkDlEhrlHDTmKzBt/9EKZZvymkMPQCoO50PvakzDCGR8JQXev25Glc9nvzMhuFl5fj+++/Rt29fOcsiahOHw4F+/fqJLoNIU5Rw05isrc7VGfmodXuaPBY57QF0u+1pBHa9cJjpA4IQnXQbQ48Ug61OIvkpoZMiW/DZK53YllsESWrbz0sAth4ugqPSKVdJRO2ihAFKpDVKaHXKFnzpe35t92voAKTvbf/rEMmBwUckP021OnNOlze7e/Ni1brrkVNQIVNFRO3DVieR/JQwoZQt+Mpr3TK9jkuW1yFqLyUMUCKtUUKrU7a7OkNN3l+qYv+XcJ6woe7MEQBAdV4m3GWFMA9IhHnASC+vEyBXSURt5nQ64XQ6ERISIroUIk3RVKszrlsogozNX855woaqg1vgKT+7g4ur8CiqDm5B3Zmfmz3XZNQjrjv/0JB4DocDERERPMSYSGZK6KTIdsU3c3gMnvs6t9njkVPvR+TU+1v1GhKAmZfHyFUSUZspYVZKpEVKaHXKdsUX2TkISQOi0NYJsk4HjI+NatXG1US+poRZKZHWSJKE4uJi4WNL1gXs9yRbYTK2ceNRtwu3XsYZNimDEmalRFpTXl6O4OBg4eenyhp8Q3ta8NiUOAQHXNzLBgfoMdzwC+ZfPwEHDx6UsySiNmGrk0h+SplQyr5J9ZzE3gCA5ZtyUOv2XHAnF50OMBkNeGxKHOYkXou3B0ViwoQJeOONNzB16lS5SyNqNbY6ieSnlAmlT44lmpPYGxsWJmJSfFcEGfUw/e5uT5NRjyCjHpPiu2LDwsTGsJwzZw4++eQT3HXXXXjmmWcgtXX/M6J2UsrMlEhLlDKh9NlBtENiLHhlzhVwVDqRvvdX5BRUoLzWhVBTAOK6h2Dm5d5PYE9MTERmZiZSUlJw4MABrFmzBiaTyVdlEnnlcDgwZMgQ0WUQaYpSJpQ+C74GXToH4a5xF3e0S8+ePbFjxw7Mnz8f48ePx4cffohu3br5qEKi5pQyMyXSEk23OuXQqVMnbNiwAZMnT8aIESOwb98+0SWRH1HKzJRIS5QyoVRs8AGAXq/HkiVLsHLlSkycOBHvv/++6JLITyhlZkqkJUqZUPq81SmHWbNmoV+/fpg+fToOHTqE1NRUbiVFPqWUmSmRlihlQqnoK75zXX755di9ezc2bdqE2bNno7q6WnRJpFFutxvl5eWwWCyiSyHSFKVMKFUTfADQvXt3ZGRkICAgAOPGjcPJkydFl0QaVFJSAovFAoOhjbsQEZFXSml1qir4AMBkMmHdunWYOXMmEhISkJWVJbok0hilzEqJtIatznbQ6XT4y1/+gtWrV+O6667DO++8I7ok0hAGH5H8JElSzNhSxc0t55OSkoI+ffogJSUFhw4dQlpaGvR6VWY5KYjdblfErJRISxruyzCbzYIrUekV37mGDBmCrKwsbN++HTNmzEBlZaXokkjllDIrJdISpbQ5AQ0EHwBERUVhy5Yt6NKlC0aPHo1jx46JLolUjMFHJD8ljStNBB8ABAYG4rXXXsOCBQuQmJiIb7/9VnRJpFJsdRLJTyl3dAIaCj7g7E0v9913H9auXYsZM2Zg7dq1oksiFVLSzJRIK9jq9LHJkydj+/btWLFiBR544AF4PB7RJZGKMPiI5KekcaXJ4AOAuLg47N69G/v378e0adNQVlYmuiRSCSW1ZIi0QknjSrPBBwARERH4/PPP0bdvXyQmJiI/P190SaQCSmrJEGmFksaVpoMPAAICAvDiiy/i3nvvxejRo/HNN9+ILokUTkktGSKtUNK40nzwNbj77ruxfv163HLLLXj55ZdFl0MKJUkSiouLERERIboUIk1hq1OQCRMm4LvvvsMLL7yAe+65By6XS3RJpDBlZWUwm80IDAwUXQqRprDVKZDVasWuXbtw9OhRTJ48GcXFxaJLIgVRUjuGSEuUNLb8LvgAICwsDJ9++imGDRuGhIQEZGdniy6JFEJJ7RgiLVHS2PLL4AMAg8GAZ599Fv/zP/+DpKQkfPHFF6JLIgVQUjuGSCvq6urgdDoRGhoquhQAfhx8DRYsWIAPPvgACxYswPPPPw9JkkSXRAIpqR1DpBUOhwMRERHQ6XSiSwHA4AMAjBkzBrt27cIbb7yBO++8E3V1daJLIkGU1I4h0gqljSsG32969+6NnTt3wm634+qrr0ZRUZHokkgAtjqJ5Ke0ccXgO0fnzp3xwQcfYOzYsRgxYgQOHDgguiTqYGx1EslPaeOKwfc7er0ey5cvx/LlyzFhwgR88sknokuiDqS0AUqkBUprdRpFF6BUt956K6xWK2bMmAGbzYZHHnlEMR/Mku/wLD4i+bHVqSIjRoxAZmYm0tPTMXfuXNTW1oouiXyMV3xE8lPauGLwtSAmJgbbt2+H2+1GcnIyCgoKRJdEPqS0AUqkBUprdTL4WsFsNmP9+vW47rrrkJCQgD179oguiXxAkiTFDVAiLWCrU6V0Oh1SU1Px3HPPYfLkyXjvvfdEl0Qyq66uhl6vh9lsFl0KkaYorZPCm1su0o033oi+ffti+vTpOHToEB5//HHo9Zw/aIHSBieRViitk8K/2G0wbNgw7N69G19++SVuvvlmVFVViS6JZMA7Ool8g61OjejWrRu2bt0Ks9mMsWPH4sSJE6JLonbiFR+R/NxuN8rLy2GxWESX0ojB1w4mkwn/+Mc/cMsttyAxMRGZmZmiS6J2YPARya+kpARhYWEwGAyiS2nE4GsnnU6Hhx56CH//+98xbdo0rFu3TnRJ1EZK+xyCSAuU1uYEeHOLbKZOnYqtW7fi+uuvx6FDh7BixQre9KIyShygRGqnxE4K/zLLaPDgwcjKysKuXbswffp0VFRUiC6JLoISByiR2imxk8Lgk1lkZCQ2b96Mrl27YtSoUTh69KjokqiVlDhAidROiZ0UBp8PBAYGYs2aNbjzzjsxatQobN++XXRJ1ApKHKBEaqfETgqDz0d0Oh3uvfdevPnmm5g5cyZef/110SVRC5Q4QInUTomdFAafj02cOBE7duzAX//6V9x///1wu92iS6LzUOIAJVI7JXZSGHwdIDY2Frt378bBgwcxdepUlJaWii6JvFDiACVSOyV2Uhh8HSQ8PByff/45BgwYgMTEROTl5Ykuic7hdDrhdDoREhIiuhQiTVFiJ4XB14GMRiP+9re/4b//+78xZswYfP3116JLot84HA5ERERAp9OJLoVIU5TYSWHwCbBw4UJs2LABc+bMwerVqyFJkuiS/J4SByeRFrDVSY2Sk5Oxc+dOvPTSS1i0aBFcLpfokvyaEgcnkdpJkoTi4mJERESILqUJBp9Affv2xa5du3DixAlMnDgRDodDdEl+S4mfQxCpXVlZGcxmMwIDA0WX0gSDT7DQ0FB8/PHHuPLKK5GQkACbzSa6JL/EVieR/JTaSWHwKYDBYMD//u//IjU1FcnJydi0aZPokvyOUgcokZoptZPC4FOQ22+/HR999BH++Mc/YuXKlbzppQMx+Ijkp9ROCoNPYUaNGoXMzEysW7cOd9xxB5xOp+iS/ILdblfkACVSM6VOKBl8CtSrVy98++23KCsrw4QJE1BYWCi6JM1T6gAlUjO2OumidO7cGenp6bjqqqswYsQI7N+/X3RJmsbgI5IfW5100fR6PZYtW4ann34aV199NT766CPRJWkWW51E8lPqhNIougBq2ezZs9GvXz/ccMMNsNlsePTRR7m1lsyUOkCJ1IytTmqXK6+8Ert378aHH36I2267DTU1NaJL0gy3243y8nJYLBbRpRBpClud1G49evTA9u3bIUkSkpKScOrUKdElaUJJSQnCwsJgMBhEl0KkKUrtpDD4VCY4OBjvvPMOUlJSkJCQgB9++EF0Saqn1Fkpkdqx1Umy0el0eOyxx/C3v/0N1157LTZs2CC6JFVT6qyUSM0kSVLs2OLNLSp2ww03oG/fvkhJScGhQ4fwxBNPQK/nXOZiKXVWSqRm1dXV0Ov1MJvNoktphn8lVW7o0KHIysrCN998g1mzZqGqqkp0SarDVieR/JQ8oWTwaUB0dDS2bNmC0NBQjB49GsePHxddkqootR1DpGZKnlAy+DQiKCgIb7zxBubOnYvExETs3LlTdEmqoeSZKZFaKXlCyeDTEJ1OhwceeACvvfYapk+fjjfffFN0Saqg5JkpkVopeULJm1s0aMqUKcjIyMC0adNw6NAhPPXUU1yjdgFKnpkSqZWSJ5S84tOo+Ph4ZGVl4fvvv0dKSgrKy8tFl6RYSp6ZEqmVkieUDD4N69KlC7766ivExMRg5MiR+Pnnn0WXpEhKnpkSqZWSJ5QMPo0LCAjAyy+/jEWLFmHUqFHIyMgQXZLiKHlmSqRWSp5QMvj8gE6nwz333IO3334bN998M9asWSO6JMWQJAnFxcWIiIgQXQqRpih5Qsng8yNXX301duzYgVWrVuHee++F2+0WXZJwZWVlMJvNCAwMFF0Kkaaw1UmKMWDAAGRmZuLw4cOYMmUKSkpKRJcklJJnpURqxlYnKYrFYsFnn32G+Ph4JCYmIjc3V3RJwjD4iHxDyWOLweenjEYjnn/+eTz44IMYM2YMNm/eLLokIex2u2JnpURq5XQ64XQ6ERISIroUrxh8fu7OO+9Eeno65s2bhxdeeAGSJIkuqUMpeVZKpFYN40qn04kuxSsGH2HcuHHYuXMn1qxZg7vuugt1dXWiS+owDD4i+Sl9XDH4CADQp08f7Ny5E6dPn8Y111wDu90uuqQOwVYnkfyUfEcnwOCjc4SEhODDDz/EqFGjMGLECBw8eFB0ST6n9JkpkRop+Y5OgMFHv2MwGPDUU09h6dKlGD9+PDZu3Ci6JJ9i8BHJT+njisFHXs2dOxeffvop7rrrLjzzzDOavemFrU4i+bHVSaqVmJiIzMxMrF+/HvPnz0dtba3okmSn9JkpkRqx1Umq1rNnT+zYsQNVVVWYMGECTp8+LbokWTH4iOSn9HHF4KMWderUCf/6178wceJEJCQkYN++faJLkoUkSYpvyRCpkdLHFYOPWkWv1+OJJ57AM888g4kTJ+L9998XXVK7VVdXQ6/Xw2w2iy6FSFOU3uo0ii6A1OWmm25Cv379MH36dNhsNixevFixuzO0ROntGCK1UvrY4hUfXbThw4cjKysLGzduxC233ILq6mrRJbWJ0tsxRGql9LHF4KM26d69OzIyMmA0GjFu3DicPHlSdEkXTentGCI1crvdqKiogMViEV3KeTH4qM2Cg4Oxbt063HjjjUhISEBWVpboki6K0tsxRGpUUlICi8UCg8EgupTzYvBRu+h0Ojz66KNYvXo1rrvuOqxfv150Sa2m9HYMkRqpYVzx5haSRUpKCvr06YPrr78ehw4dwrJly6DXK3texVYnkfzUMK6U/ZeJVGXIkCHIysrCtm3bcOONN6KyslJ0SRfEVieR/NQwrhh8JKvo6Ghs2bIFERERGD16NI4dOya6pPNSQ0uGSG3UMK4YfCS7wMBAvPbaa1iwYAESExPx7bffii7JKzW0ZIjURg3jisFHPqHT6XDfffdh7dq1mDFjBtauXSu6pGbU0JIhUhs1jCsGH/nU5MmTsW3bNqxYsQIPPPAAPB6P6JIaqWGAEqkNW51EAAYOHIjdu3fjxx9/xLRp01BWVia6JAA8i4/IF9jqJPpNREQEvvjiC/Tp0wcjR45Efn6+0Hrq6urgdDoREhIitA4irVFDJ4XBRx0mICAAq1evxp/+9CeMHj0aW7duFVaLw+FARESEajfYJlIqtjqJvFi0aBHWr1+P2bNn45VXXhFSA9ucRL7BVifReUyYMAHfffcd/u///g9/+tOf4HK5OvT91dCOIVKb+vp6lJSUICIiQnQpF8TgI2GsVisyMzNx5MgRXHvttSguLu6w92bwEcmvrKwMZrMZAQEBoku5IAYfCRUWFoaNGzdi6NChSEhIQE5OToe8L1udRPJTQ5sTYPCRAhgMBqxcuRKPPvooxo0bhy+++MLn78krPiL5qWVcMfhIMe644w588MEHWLBgAZ5//nlIkuSz91LLACVSEzXc0Qkw+EhhxowZg127duGNN97AwoULUVdX55P3UcsAJVITtjqJ2qh379747rvvUFhYiKuvvhpFRUWyv4daBiiRmqilk8LgI0UKCQnBhx9+iDFjxmDEiBE4cOCArK+vlgFKpCZq6aQw+Eix9Ho9VqxYgeXLl2PChAn45JNPZHtttQxQIjVRSyfFKLoAopbceuutsFqtmDFjBmw2Gx555JF2bzWmlgFKpCZq6aTwio9UYcSIEcjMzER6ejrmzp2L2traNr+W2+1GeXk5LBaLfAUSkWo6KQw+Uo2YmBhs374dLpcLycnJKCgoaNPrlJSUICwsDAaDQeYKifybWjopDD5SFbPZjHfffRfXXXcdEhISsHfv3ot+DbUMTiK1YauTyEd0Oh1SU1OxatUqTJo0Ce+9995F/bxaBieRmkiSpJpWJ29uIdWaOXMm+vXrh5SUFNhsNqSmpkKvb3kup5bBSaQmVVVVMBqNCA4OFl1Ki3jFR6o2bNgwZGVl4YsvvsDs2bNRXV3t9Xn2Side2XYE923Yhxd/cqOw37V4ZdsROCqdHVwxkTapqZOik3y5ISJRB6mtrcXChQtx6NAhfPzxx4iJiQEA7D9RitUZ+diWe3b3F6e7vvFnTEY9JADJsVFYlGTF0J4WAZUTacOePXvwxz/+Efv27RNdSot4xUeaYDKZ8Oabb+Lmm29GQkICdu/ejbczf8HsVzOxOfsMnO76JqEHALW/PfaV7Qxmv5qJtzN/EVM8kQao6aYxfsZHmqHT6fDwww9j4MCBmP7gSnQeOw8uqeWF7pIE1Lg8WL4pGwAwJ7G3jysl0h41tToZfKQ5vS4bi9AkA5yef3fxHZv+htqTNnjK7dAZAhB4yQCEj1+AwKjejc+pcdVj+aYcDImxYEiMpeMLJ1IxNd00xlYnac7qjHzU1Tf96Lryp6+gD+qETvHjoAsyo/bnPSj81xJI7qbHHtW6PXgpI78jyyXSBLY6iQSxVzqxLbcIv79lq9v85xHUzQoAcJeewclX/gOeCgfq7McbHwfOtj23Hi6Co9KJLp2DOrJ0IlVzOBzo37+/6DJahVd8pCnpe371+niTcKt3n/2HTg9D54hmz9UBSN/r/XWIyDu2OokEyTld3uzuzXPV19XA8dnzAIDQEdNh9BJ8te565BRU+KpEIk1iq5NIkPJa93m/56kuQ+G/nkDd6Tx0HjoJluQFF3gdly/KI9Is3tVJJEioyfv/0u6yQpzZkAp38UmEjpyF8KTbL/g6O775CnO//hsGDhyI+Ph4xMfHo2/fvjAaOWSIvFFTq5M7t5CmvLLtCJ77OrdZu/PXF+fBU1kMQ2gUzANGNj7eKT4JQZfENnlukFGHWbHBsLqPITs7GzabDTabDadOnYLVakV8fHyTQOzfvz+CgngjDPm3zp07o6CgACEhIaJLaRGDjzTFXunE6L9+0yz4jj091evzu0y5D52HXN3ksSCjHjsfmdDsrs6amhocPny4MQgbQvGXX35Br169GoOwIRTj4uJgNpvl/QWJFKi2thahoaFwOp3Q6VreNEI0Bh9pzsJ1P2Bz9plmSxpaQ6cDJsV3xStzrmj1z9TV1SE/P79ZIObl5aFr167NAnHgwIEICwu7+OKIFOrkyZO44oor2nw4dEfjBxakOfckW7Ejz44al+eif9ZkNGBRsrXlJ54jMDCwMdzO5fF4cPTo0cZAzMjIwMsvv4zs7GxYLJYm7dKGf6vlrjiic6npjk6AV3ykUW9n/oLlm7JR4zr/0obfCw7Q47EpA32+V2d9fT1OnDjR5PPDhivFgICAJoHYEIrdu3dXRQuJ/NPWrVuxdOlSZGRkiC6lVXjFR5rUEF7LN+Wg1u25YNtTpzt7pffYlLgO2aBar9fj0ksvxaWXXorJkyc3Pi5JEk6fPt2kXfr+++8jOzsbTqez2U01AwcORK9evVp1+C6RL6npjk6AwUcaNiexN4bEWPBSRj62Hi6CDmcXpzdoOI9vfGwUFiVbhW9MrdPp0L17d3Tv3h1XXXVVk+/Z7XZkZ2c3BuKXX34Jm82G0tJSxMXFNbtK7NOnD5deUIdhq5NIgRyVTqTv/RU5BRUor3Uh1BSAuO4hmHl5jKr35CwrK0NOTk6Tq0SbzYaCggL079/f69KLwMBA0WWTxixfvhxVVVVYsWKF6FJahcFHpEHV1dXnXXrRu3fvZjfVxMbGcukFtdn999+PmJgYPPDAA6JLaRUGH5EfcTqdTZZeNIRiXl4eunfv7nXpRWhoqOiySeHmzZuHq666CrfffuEdkZSCHwIQ+ZGgoCAMGjQIgwYNavK42+3Gzz//3Hhl+M0332D16tXIycmBxWJpdpdpfHy8qm5mIN9S0z6dAK/4iOgC6uvrcfz4ca9LL4KCgryuRezWrRuXXviZhIQEPP/88xg5cmTLT1YABh8RXTRJklBQUNDspprs7Gy4XC6vaxF79uzJpRcaZbVa8fnnn6vmIFoGHxHJqqioqDEMzw3FsrIyDBw40OvSC4PBILpsaofw8HAcOXIEERHNz7dUIgYfEXWIsrIyr4F45swZr0svrFYrl16ogNvthslkQl1dnWqu6Bl8RCRUVVWV16UXx44dQ58+fZoFYmxsLIKDg0WXTb8pLCzEoEGDUFRUJLqUVmPwEZEiOZ1O5OXlNbupJj8/H5dcconXpRdqOAtOa7Kzs3HDDTcgJydHdCmtxuUMRKRIQUFBGDx4MAYPHtzkcbfbjSNHjjReGX799dd44YUXkJOTg4iIiGaBGB8fr5rPntRIbft0ArziIyKNqK+vx7Fjx7zeaWoymbyuRezatSuXXrTTRx99hLVr1+Ljjz8WXUqr8YqPiDRBr9ejT58+6NOnD6677rrGxyVJwqlTpxpD8MCBA9iwYQNsNhvq6+vPu/SCgdg6alu8DjD4iEjjdDodevTogR49euCaa65p8r2ioqImV4afffYZbDYbKioqmi29GDhwIJdeeKHGVieDj4j8VlRUFJKSkpCUlNTk8dLS0ibt0m3btsFms6GwsBADBgxoFoj+vPRCbUcSAQw+IqJmLBYLRo4c2WwLrsrKyiZLL9566y1kZ2fj+PHj6Nu3b7ObagYMGKD5pRcOhwMDBgwQXcZF4c0tRETtVFtbi9zc3GY31Rw5cgQ9evRoFohxcXGaWXqRkpKC+fPn44YbbhBdSqsx+IiIfMTlcjVZetHwlZubiy5dunhdi6iGpRf2SifS9/yKnNPl+GLLNlz+h4EYN8SKWcPVcbAzg4+IqIN5PJ7zLr0wm81e1yJGR0cLv9N0/4lSrM7Ix7bcs7u0ON31jd8zGfWQACTHRmFRkhVDe1rEFNkKDD4iIoWQJAknT55stn2bzWYDAK/HQMXExHRIIL6d+QuWb8pBrduDC6WGTgeYjAY8NiUOcxJ7+7yutmDwEREpnCRJzZZeNPy7qqoKcXFxzQKxd+/esi29OBt62ahx1bf85N8EB+jx2JSBigw/Bh8RkYqVlJQ0a5fabDYUFRUhNjbW69KLgICAVr/+/hOlmP1qJmpcniaP2zeuQu0vP8JTUw59oBmB3awIT7odgd36NT4nOMCADQsTMSTGItevKwsGHxGRBlVWViInJ6fZJt8nTpxAv379vC69MJlMzV5n4bofsDn7TLP25ul//gWGkC7QB5lRe+wnuItPwhAahZhFaxufo9MBk+K74pU5V/j6170oDD4iIj9SU1Nz3qUXPXv2bBKIPfrG4e4v7KjzXDgmnKfzcfof9wE6PXo9+AF0hn8vEQ8y6rHzkQmKutuTwUdERHC5XMjPz2/SLt1bE4HqfhOgD/AeWuV7PoXLfgK1x/bDXXwSoQkzED7+jibPMRn1uP+aAbhrXD+vryECd24hIiIEBAQ07k/a4L4N+/DRj6fO+zPVOd/BeeIgAMAQEomgHvHNnlPrrkdOQYX8BbeDOs6JJyKiDlde677g97vd9jR6PfgBomYshqeyGEUfPQV3WaGX13H5qsQ2YfAREZFXoSbvTcF6lxNS/dm7PHXGQAT3HQ5doAmo98BdetrL67T+LtKOwFYnERF5FdctFEHG0012aAGAulOHYf/0WQT1HAS9qTOcJw5BclZDbw5DYNemn+WZjHrEdVfWvqS84iMiIq9mDo/x+rghpAuM4Zeg9uiPqNy/GfW1lTDHjUHXW5ZDb+rU5LkSgJmXe38dUXjFR0REXkV2DkLSgKhm6/gCInqg221Pt/jzOh0wPjZKUUsZAF7xERHRBdyTbIXJ2Latz0xGAxYlW2WuqP0YfEREdF5De1rw2JQ4BAdcXFyc3aszTnHblQFsdRIRUQsaNprm6QxERORXfvq1FC9l5GPr4SLocHZxeoOG8/jGx0ZhUbJVkVd6DRh8RER0URyVTqTv/RU5BRUor3Uh1BSAuO4hmHk5T2AnIiJSHN7cQkREfoXBR0REfoXBR0REfoXBR0REfoXBR0REfoXBR0REfoXBR0REfoXBR0REfoXBR0REfuX/AW4Dq0Lmn5ChAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = nx.Graph()\n",
    "nx.add_path(g, [0,1])\n",
    "nx.add_path(g, [1,2])\n",
    "nx.add_path(g, [2,3])\n",
    "nx.add_path(g, [3,4])\n",
    "nx.add_path(g, [0,4])\n",
    "nx.add_path(g, [0,2])\n",
    "nx.draw(g,with_labels=True, font_weight='bold')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如上如，我们得到一个由5个节点和6条边构成的图结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 搭建QAOA量子线路\n",
    "\n",
    "### 线路搭建\n",
    "\n",
    "这里我们采用量子绝热近似算法，经过演化将量子态从$X^{\\otimes n}$的本征态演化到图对应哈密的量的基态。\n",
    "\n",
    "搭建图对应哈密顿量的含时演化线路："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_hc(g,para):\n",
    "    hc = Circuit()\n",
    "    for i in g.edges:\n",
    "        hc += ZZ(para).on(i)\n",
    "    return hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搭建$X^{\\otimes n}$含时演化的量子线路："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def build_hb(g, para):\n",
    "    hc = Circuit()\n",
    "    for i in g.nodes:\n",
    "        hc += RX(para).on(i)\n",
    "    return hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了使得最后优化的结果足够准确，我们需要将量子线路重复多次，因此我们通过如下函数搭建多层的训练网络："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ansatz(g, p):\n",
    "    c = Circuit()\n",
    "    for i in range(p):\n",
    "        c += build_hc(g,f'g{i}')\n",
    "        c += build_hb(g,f'b{i}')\n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建图对应的哈密顿量："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ham(g):\n",
    "    hc = QubitOperator()\n",
    "    for i in g.edges:\n",
    "        hc += QubitOperator(f'Z{i[0]} Z{i[1]}')\n",
    "    return hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 生成完整的量子线路和图所对应的哈密顿量\n",
    "\n",
    "这里我们选择`p = 4`，表示选用4层的QAOA量子线路，`ansatz`是求解该问题的量子线路，`init_state_circ`是将量子态制备到均匀叠加态上的量子线路。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 4\n",
    "ham = Hamiltonian(build_ham(g))\n",
    "ansatz = build_ansatz(g, p)\n",
    "init_state_circ = UN(H, g.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 搭建待训练量子神经网络\n",
    "\n",
    "由于该问题不需要编码层量子线路，我们这里使用`MindQuantumAnsatzOnlyLayer`作为待训练的量子神经网络，并采用`Adam`优化器。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "net = MindQuantumAnsatzOnlyLayer(ansatz.para_name, init_state_circ+ansatz, ham)\n",
    "opti = nn.Adam(net.trainable_params(), learning_rate=0.05)\n",
    "train_net = nn.TrainOneStepCell(net, opti)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 训练并展示结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "train step: 0 , cut: [[3.0059216]]\n",
      "train step: 10 , cut: [[3.3262742]]\n",
      "train step: 20 , cut: [[3.7228582]]\n",
      "train step: 30 , cut: [[3.983411]]\n",
      "train step: 40 , cut: [[4.135832]]\n",
      "train step: 50 , cut: [[4.216693]]\n",
      "train step: 60 , cut: [[4.2141833]]\n",
      "train step: 70 , cut: [[4.2036085]]\n",
      "train step: 80 , cut: [[4.260594]]\n",
      "train step: 90 , cut: [[4.373112]]\n",
      "train step: 100 , cut: [[4.4853263]]\n",
      "train step: 110 , cut: [[4.5553446]]\n",
      "train step: 120 , cut: [[4.587566]]\n",
      "train step: 130 , cut: [[4.611128]]\n",
      "train step: 140 , cut: [[4.637698]]\n",
      "train step: 150 , cut: [[4.6584387]]\n",
      "train step: 160 , cut: [[4.66508]]\n",
      "train step: 170 , cut: [[4.663408]]\n",
      "train step: 180 , cut: [[4.6678705]]\n",
      "train step: 190 , cut: [[4.6875486]]\n",
      "train step: 200 , cut: [[4.7206187]]\n",
      "train step: 210 , cut: [[4.7580614]]\n",
      "train step: 220 , cut: [[4.7893686]]\n",
      "train step: 230 , cut: [[4.8074245]]\n",
      "train step: 240 , cut: [[4.8116426]]\n",
      "train step: 250 , cut: [[4.8077316]]\n",
      "train step: 260 , cut: [[4.803544]]\n",
      "train step: 270 , cut: [[4.8039436]]\n",
      "train step: 280 , cut: [[4.8088512]]\n",
      "train step: 290 , cut: [[4.8154163]]\n",
      "train step: 300 , cut: [[4.821649]]\n",
      "train step: 310 , cut: [[4.8281393]]\n",
      "train step: 320 , cut: [[4.8366113]]\n",
      "train step: 330 , cut: [[4.847317]]\n",
      "train step: 340 , cut: [[4.858108]]\n",
      "train step: 350 , cut: [[4.865946]]\n",
      "train step: 360 , cut: [[4.8693476]]\n",
      "train step: 370 , cut: [[4.869488]]\n",
      "train step: 380 , cut: [[4.868954]]\n",
      "train step: 390 , cut: [[4.8695197]]\n",
      "train step: 400 , cut: [[4.8711824]]\n",
      "train step: 410 , cut: [[4.8730283]]\n",
      "train step: 420 , cut: [[4.874686]]\n",
      "train step: 430 , cut: [[4.8768916]]\n",
      "train step: 440 , cut: [[4.880748]]\n",
      "train step: 450 , cut: [[4.8865013]]\n",
      "train step: 460 , cut: [[4.8930907]]\n",
      "train step: 470 , cut: [[4.898922]]\n",
      "train step: 480 , cut: [[4.9031305]]\n",
      "train step: 490 , cut: [[4.906122]]\n",
      "train step: 500 , cut: [[4.9088955]]\n",
      "train step: 510 , cut: [[4.9119415]]\n",
      "train step: 520 , cut: [[4.9149566]]\n",
      "train step: 530 , cut: [[4.9175825]]\n",
      "train step: 540 , cut: [[4.920064]]\n",
      "train step: 550 , cut: [[4.9228735]]\n",
      "train step: 560 , cut: [[4.925872]]\n",
      "train step: 570 , cut: [[4.9282985]]\n",
      "train step: 580 , cut: [[4.929679]]\n",
      "train step: 590 , cut: [[4.930426]]\n"
     ]
    }
   ],
   "source": [
    "for i in range(600):\n",
    "    if i%10 == 0:\n",
    "        print(\"train step:\", i, \", cut:\", (len(g.edges)-train_net())/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上面的训练结果我们发现，该问题哈密顿量的基态能量对应的边切割数趋近与5。\n",
    "\n",
    "### 量子态展示\n",
    "\n",
    "前面我们通过训练得到了量子线路中参数的最优值，下面，我们通过`StateEvolution`类的`final_state`来输出量子线路在最优参数时的量子态，其中`ket`参数表示是否将最终量子态表示为右矢形式。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.017737679183483124-0.03180303797125816j)¦00000⟩\n",
      "(-0.02683155983686447+0.0012889178469777107j)¦00001⟩\n",
      "(0.011993971653282642+0.006973826792091131j)¦00010⟩\n",
      "(-0.014608755707740784-0.003942559473216534j)¦00011⟩\n",
      "(-0.02683155983686447+0.0012889178469777107j)¦00100⟩\n",
      "(0.00725862430408597+0.10942266136407852j)¦00101⟩\n",
      "(-0.014608755707740784-0.003942559473216534j)¦00110⟩\n",
      "(0.008969870395958424-0.004171415697783232j)¦00111⟩\n",
      "(0.00950924027711153-0.00026544960564933717j)¦01000⟩\n",
      "(-0.37196943163871765-0.3156493902206421j)¦01001⟩\n",
      "(-0.040885526686906815+0.037214867770671844j)¦01010⟩\n",
      "(-0.37196943163871765-0.3156493902206421j)¦01011⟩\n",
      "(-0.03160367161035538+0.009305878542363644j)¦01100⟩\n",
      "(-0.040885526686906815+0.037214867770671844j)¦01101⟩\n",
      "(-0.03160367161035538+0.009305878542363644j)¦01110⟩\n",
      "(0.00950924027711153-0.00026544960564933717j)¦01111⟩\n",
      "(0.00950924027711153-0.00026544960564933717j)¦10000⟩\n",
      "(-0.03160367161035538+0.009305878542363644j)¦10001⟩\n",
      "(-0.040885526686906815+0.037214867770671844j)¦10010⟩\n",
      "(-0.03160367161035538+0.009305878542363644j)¦10011⟩\n",
      "(-0.37196943163871765-0.3156493902206421j)¦10100⟩\n",
      "(-0.040885526686906815+0.037214867770671844j)¦10101⟩\n",
      "(-0.37196943163871765-0.3156493902206421j)¦10110⟩\n",
      "(0.00950924027711153-0.00026544960564933717j)¦10111⟩\n",
      "(0.008969870395958424-0.004171415697783232j)¦11000⟩\n",
      "(-0.014608755707740784-0.003942559473216534j)¦11001⟩\n",
      "(0.00725862430408597+0.10942266136407852j)¦11010⟩\n",
      "(-0.02683155983686447+0.0012889178469777107j)¦11011⟩\n",
      "(-0.014608755707740784-0.003942559473216534j)¦11100⟩\n",
      "(0.011993971653282642+0.006973826792091131j)¦11101⟩\n",
      "(-0.02683155983686447+0.0012889178469777107j)¦11110⟩\n",
      "(0.017737679183483124-0.03180303797125816j)¦11111⟩\n"
     ]
    }
   ],
   "source": [
    "pr = dict(zip(ansatz.para_name, net.weight.asnumpy()))\n",
    "print(StateEvolution(init_state_circ+ansatz).final_state(pr, ket=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 概率图\n",
    "\n",
    "我们画出最终量子态在计算基矢下的概率分布"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEMCAYAAADK231MAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAnBklEQVR4nO2dedxmc/nH39csdibMFNlGTDIYZIztlyXLDBOjiBEa69hVIkKWkSJLq7JkEtFYKk0ZpCwVYUZJ6EfDTwz9aiz9Kmvy/f1xXbf7+5y5l/PMcz+L4/N+ve7Xc59zrvv6Xmf7XN/tnMdSSgghhKgug/o7ACGEEL2LhF4IISqOhF4IISqOhF4IISqOhF4IISqOhF4IISrOkP4OoMjw4cPTyJEj+zsMIYR4S3Hfffc9m1Ia0WjbgBP6kSNHMmfOnP4OQwgh3lKY2Z+bbVPXjRBCVBwJvRBCVBwJvRBCVBwJvRBCVBwJvRBCVBwJvRBCVBwJvRBCVBwJvRBCVJwB98CUGJiMPOGGptueOGtix3wtjD/hdPK46hxVC9XohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4kjohRCi4pQSejObYGaPmNlcMzuhwfZjzOxhM3vAzH5hZqtl26aY2Z/iM6WTwQshhGhPW6E3s8HABcCOwGhgLzMbXTD7HTA2pTQGuA74Uvx2OeBUYBNgHHCqmS3bufCFEEK0o0yNfhwwN6X0eErpNWAGMCk3SCndllJ6KRbvBlaO7+OBW1JKz6eUXgBuASZ0JnQhhBBlKCP0KwFPZcvzYl0zDgRu7M5vzWyqmc0xsznz588vEZIQQoiydHQw1sz2AcYC53Tndymli1NKY1NKY0eMGNHJkIQQ4m1PGaF/GlglW1451nXBzLYDTgJ2SSm92p3fCiGE6D3KCP1sYJSZrW5miwCTgZm5gZltCFyEi/zfsk03AzuY2bIxCLtDrBNCCNFHDGlnkFJ63cyOxAV6MDA9pfSQmU0D5qSUZuJdNUsB15oZwJMppV1SSs+b2Rl4sgCYllJ6vlf2RAghREPaCj1ASmkWMKuw7pTs+3YtfjsdmL6wAQohhOgZejJWCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqjoReCCEqTimhN7MJZvaImc01sxMabN/SzH5rZq+b2e6Fbf8xs/vjM7NTgQshhCjHkHYGZjYYuADYHpgHzDazmSmlhzOzJ4H9gGMbuHg5pbRBz0MVQgixMLQVemAcMDel9DiAmc0AJgFvCn1K6YnY9kYvxCiEEKIHlOm6WQl4KlueF+vKspiZzTGzu81s1+4EJ4QQoueUqdH3lNVSSk+b2XuAW83sDymlx3IDM5sKTAVYddVV+yAkIYR4+1CmRv80sEq2vHKsK0VK6en4+zhwO7BhA5uLU0pjU0pjR4wYUda1EEKIEpQR+tnAKDNb3cwWASYDpWbPmNmyZrZofB8ObEHWty+EEKL3aSv0KaXXgSOBm4E/AteklB4ys2lmtguAmW1sZvOAjwIXmdlD8fO1gTlm9nvgNuCswmwdIYQQvUypPvqU0ixgVmHdKdn32XiXTvF3dwHr9TBGIYQQPUBPxgohRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMWR0AshRMUpJfRmNsHMHjGzuWZ2QoPtW5rZb83sdTPbvbBtipn9KT5TOhW4EEKIcrQVejMbDFwA7AiMBvYys9EFsyeB/YCrCr9dDjgV2AQYB5xqZsv2PGwhhBBlKVOjHwfMTSk9nlJ6DZgBTMoNUkpPpJQeAN4o/HY8cEtK6fmU0gvALcCEDsQthBCiJGWEfiXgqWx5XqwrQ6nfmtlUM5tjZnPmz59f0rUQQogyDIjB2JTSxSmlsSmlsSNGjOjvcIQQolKUEfqngVWy5ZVjXRl68lshhBAdoIzQzwZGmdnqZrYIMBmYWdL/zcAOZrZsDMLuEOuEEEL0EW2FPqX0OnAkLtB/BK5JKT1kZtPMbBcAM9vYzOYBHwUuMrOH4rfPA2fgyWI2MC3WCSGE6COGlDFKKc0CZhXWnZJ9n413yzT67XRgeg9iFEII0QMGxGCsEEKI3kNCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFUdCL4QQFaeU0JvZBDN7xMzmmtkJDbYvamZXx/Z7zGxkrB9pZi+b2f3xubDD8QshhGjDkHYGZjYYuADYHpgHzDazmSmlhzOzA4EXUkprmtlk4Gxgz9j2WEppg86GLYQQoixlavTjgLkppcdTSq8BM4BJBZtJwHfj+3XAtmZmnQtTCCHEwlJG6FcCnsqW58W6hjYppdeB/wOWj22rm9nvzOwOM/tAD+MVQgjRTdp23fSQvwCrppSeM7ONgOvNbJ2U0j9yIzObCkwFWHXVVXs5JCGEeHtRpkb/NLBKtrxyrGtoY2ZDgGHAcymlV1NKzwGklO4DHgPeWywgpXRxSmlsSmnsiBEjur8XQgghmlJG6GcDo8xsdTNbBJgMzCzYzASmxPfdgVtTSsnMRsRgLmb2HmAU8HhnQhdCCFGGtl03KaXXzexI4GZgMDA9pfSQmU0D5qSUZgKXAleY2VzgeTwZAGwJTDOzfwNvAIemlJ7vjR0RQgjRmFJ99CmlWcCswrpTsu+vAB9t8LsfAD/oYYxCCCF6gJ6MFUKIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIiiOhF0KIijOkvwMQXRl5wg1Ntz1x1sQ+jESIgYnuke6jGr0QQlQcCb0QQlQcCb0QQlQcCb0QQlQcCb0QQlQcCb0QQlScUkJvZhPM7BEzm2tmJzTYvqiZXR3b7zGzkdm2z8b6R8xsfAdjF0IIUYK28+jNbDBwAbA9MA+YbWYzU0oPZ2YHAi+klNY0s8nA2cCeZjYamAysA7wb+LmZvTel9J9O74jof1rNb4bemePcH2V2koF2zAb68RILR5kHpsYBc1NKjwOY2QxgEpAL/STgtPh+HfANM7NYPyOl9CrwP2Y2N/z9pjPhL4gu4urQyXPZ19dFpwVc13U16K+KiaWUWhuY7Q5MSCkdFMv7ApuklI7MbB4Mm3mx/BiwCS7+d6eUvhfrLwVuTCldVyhjKjA1FtcCHun5rgEwHHi2j+3eDr76o8yB6qs/yhyovvqjzIHqq9NllmG1lNKIhltSSi0/wO7At7PlfYFvFGweBFbOlh+LHfgGsE+2/lJg93ZlduoDzOlru7eDr7d6/DoWOhZvtWPR00+ZwdingVWy5ZVjXUMbMxsCDAOeK/lbIYQQvUgZoZ8NjDKz1c1sEXxwdWbBZiYwJb7vDtyaPF3NBCbHrJzVgVHAvZ0JXQghRBnaDsamlF43syOBm4HBwPSU0kNmNg1vdszEu2SuiMHW5/FkQNhdgw/cvg4ckfp2xs3F/WD3dvDVH2UOVF/9UeZA9dUfZQ5UX50us0e0HYwVQgjx1kZPxgohRMWR0AshRMWR0DchHvjq9d/0ha9OM5BjGyjoGImBxNtO6M1sTTPbyIJY1+imXDS2NT1GZjbGzLY1sxXMbGhKKTXyVeam76SvJv4XWnjKxNYfcQ1kX6mDg18Dab/ebr56w19v+23E2+p/xprZbsA0/Em0PwH3mdllKaWXzcxqN6eZ7QycaGYHxcyhQSmlNwq+dgW+GH7mA8+a2RkppX/lvoLFgZfMbHCjWUed9JX53BR/buFx4OGU0ivF/TCzd6SU/t6gjIWJrU/j6gVfW+PTf/8XuC32r9F5XxGYn1J6vY2v8fjU5MdTSve3sG15vGpmwJuxN9uXdvvYHV8l/Q0B/t3N8t9qcXXUn5ktkVJ6Cbwy0Oga6xX64qmsgfDBa+g/AjaL5cnA+cCpwOKZ3fq4qF2Jz/lfJ9YPymwGAVfgr30A2Aw4D7gMWKqWL+Lvh4G/ABvF8uBCXB3zlfmciL9GYjpwCXANMCzfD+AjwD+B7Vocs1Kx9XVcveBre+BR/GV8F8V5X67Bed8V+Bf+dPhiTXx9MI7FseHrcuDABnajs+8Nj1cW23T8FSE7Zust+74BsGiJe6Ctr7L+gB2B64GT8v1r4GscsNZbMa6y/rrhaxfgVuBrwGeb2GyBVxIaXl8L++mYo4H+wWucPydewQAMBbbFhSs/gasB+8f3Y4HfUhB7XAAvBw6I5cHAGuHr88CQWL8W/gK3q/Da8NiafVbekFwMeuIr83kBsF98XzF83U5dCFcDbgK+BzwEfLDJMWsbW3/E1Qu+zgQ+ky2fhyf7mtgb8C48mVwC/BSvKCwgOsDewDHxfQVgAv7g4AGZzUTgDfy9T7V1jY7XfwFP4gJ4fOzPiQWbCTVfwCK1eBfGV1l/wMZxfCbjD0j+Fjg/216rmGwXvmbSRAgHalxl/XXD17pxHe4Yfh8GvpJtHwRsE75+GPvbMbHvdwHu7Q8uTjWx/AjwY2BcLC+CP9F7adgNjfWLZr8/Jk7wurG8eth+EPgDsG2sHwJshddMlo117wI+Gt8PA16gLoRL105knOAHiJpnE18rtvA1uHAhn0qITXYMzsNFb1FgWWB8bPs4/m6iD2YX75LAYvG9ZWx9GVfhBjsV+HQLX8u38xV+DNgfOL1w3ZwL3AksGctLUm8N7ownlclkrcHYdgDeIqhdc0vgN/d3gLWB5fDkuRsuWrOy3w4p+JoAnBXfF8PF4m6iNohfQ18C9oz9vp7mIjgBOLuZr1i/TBl/+AsL8/dfLYe3iM7L1i2OV5T2xrv+rgLe1+D+HJBxlfEX5/ZYYJ8Svt6HC/jQbJ/uAL6a3VcfB/YDDge+HdfN4o38dVsHO+FkoH7wLoXv4tl2c1ykjwAuxN/AWbN7MC6eH+PdE8tk2wz4NHA/cDUwA1g6tn0cmEWIfay7Gdg8W14s+34oLoSfiZN+L558VsZv/BuA7Qu+Plg72bWLu+Br41heL7uINsZr17tm+7AantDWinV5MqsJ4bYRz224kE1qEdvPga37Kq5Y3p56LXsD4G/ARwq+vge8v7auha9NamXh/y9hLrBX4fq5pLaPsTw0+14T+72i3P2BJWLb1/Aur5r/d8fyjrE8LvPzSzKxL5S/A3BX4fiuG+eith9rU09cP8Kv4wXEAe8OuLuVr1g3mnrL9U1/dE2OGwA/Ad6V/W45fEwif4nhatST/dfw7tDRhfMyIOOKbWPw+7upP/xdXkMb+cpiG4TfR98hKkGxfmngj0SFBX8RZK2CcCx+/U1sdD67rYU9dTBQP3Gw/4TXPj+Bi/h+uJgdjtem9sKbi6/i/WefwJPCwcAqma8J+CscXgWOz9a/A++vfRg4BE8ijwEfz2wGFU76yeHrCuD3eOb+XMT5Ebx5d2j4ejIutFuBDwFrFPbxMHzw8Pt462L5bNvE8PXhWN4SmANMzOPK7D+O93m/gCe+I/DukUaxXQz8H/DrPorrQfzG/zsufIfFjfNfsW23sP0I8NcocyqwaSGumq/r49iukG3bOvZ9r2zdTfj/U6gtF8dXdgbui2PxEt6lszMuvmfjN32t5nkh8LUm1+qbYo+3oHIx+DaeUGqtvyXwrqZcuPLjdT1wfXyfCnyKunh8BfhVwdfpwHFxjhchG5PI/QFLATsRyR74Ml75yZPfFLIusAaxfR2v9Y4FzgAmD7C4huH355eI+x9vOf6BronoFLxysioLtuhyXwcDe2TbjscrUSOzdTvhrQFrENdxuNhvBBwFTF1oPewtoe3vT9wweR/ojnHQpuDdDZOAH+A1019nduPjJB4UF5zF7+bjieAS4GOFsraKi3UW8CJwLV0FIxf6MXhN9Fl84HfjuOhPBkbgwvdVXCSfiO374KJ7KrBBoexf4/16c8i6MrKL6G+4WLwcsZ2ZbS+K6k3Aa8CYWG4U23dwwf1YH8b1Yzw57onXck/Ck83m+ODVX3HxexZPtPsCJ+Liun2h7Fsjrv8Bzm1wHv8IfAFvvb0e/s5tFBvenfMk/qbWdYFP4t1Hh+FjF1/HW20/wmdt3BPndVdiMDvzeyN+jf0L2Kmw7UI8GSwex+6R8JNfV0My+8vxRPsaLqBX44l7GJ6A7qTe+rgaT3A34wJ1DNFqKhyzV/E3z47K1k8HfkddFKfHtbFVIbZ8TOrq8PVy7PNAiev0OJf/xu+DK/Duu8G48D+A1953ifP0Z7y34OvAioW4ar7eAA4pbDsL+AV+3e4BvBLXyFCyMcDMfn/8Hnqawj3WLT3sb0HurQ9eC7gW2CVbtyMuxrU++qF4v2DRbnxchLW+5jXxPrbl8FbBxWQ1qrAxvEvmFLzL6BIKYh9/N8df/PaFbNu4sN8p8zUGfwtozaZWCzoFWDXz9QSeZDbE/7tXUVQ3wgcRf4kPKHWxyS6u9cLm58BRLWJbv4NxXVsyrnuA32Tb3oO3yi7Cx0HG4MnmCepjKe/BBfdb1GcDjcFbX6fhffi/IOu/DZu18a6qa/DWzAJ2WWxrxbnMB3L3xsV+fLZ8D/VWxyfwWuchZGIfx682EPdDYMNCXJfgY0WvAP8AbqnZUBAu/Bp9Fdg3lncFzsEH0JeK8n8VPv9JvRtiV1yIzqLeRbYO8EyU+zCwZSGuc/BEdmOUeU3EuWUxNrwf+q4oc52BElf8nRJ2R8Ty+/Ga9uUR+8l4hWMu8BSe2N+PT9e+mq6tw+PwSsJVeCWgmLg/jXcBP4cnjb9Tv78GFf5Oie2jcx/d1sP+EuLe+OBZcjvqA4dHx8WxWWZzbJz8HdrYfQP4GQvWCEfgWfbiKGsP6v2lQ/FWQJ4Q9sbFotZf+y68tXA+XZt1B+DdRnkT8VrgyGx547gJaiKyIt7/uxR+E20dv/lMg2NTtDku1m+NDyoehPcR7orXZCY3iw0XoqNKxDUsjkmruIo2x2XbhkTcw/GbKa9Zr4HXnPIZU41sTgOmxPJy4as2wD0ST2xfzn6Tj6k0tMMT8bD4uy/eqnl/tu0zwA9ieXF80G3PzO9euKhNzOL8QezPu/DulplEgsp+txMuYOMymy7jEfj1+eUo8/Dst/+F10wPzu6VrfFacW63BX4vHIkL3Gi822wMft0/AGxViGsNvLZ8dCx3sctiG4a3mD7fgbjWwStt7eLaGvhEm7iWjHN2LV27ZlfBW4pfjOVRYfPFgs3peHJfHO93Pxn4ZGz/MJ6YJxZiWwXvBn130Ya6yBve3Timx9rYUwcD5YML95Nx0dwTf9+BZ+WzqM8MOQ+vLTS1C1/P4c2/u4FvFcoajvdNz8a7HQ4kGzjKbrj98WTxaJTzoeyCPxwX+9pAzF5xEeW1vN1onBBuIgaEC2UuindZXYv36e0VF8rgJjZn483j7+N9zefjNdoj4jjVYpuG17T2i+VdaZwM7iS6dApxLZaVeVaUc2Ehrtxmf7zGe2i2fQPgm8Cx2bqP47XtxVrYTMT7RVcoHq/Y/h5cxE+JMk8lS7YN7K7CRWgO3pW1SvzmNDJhjrhGxffdWTAZHIcnJsMT3dLUB/XeiXcD/QRv+RiePAc3s4l178qO5QfwRLBtVuaeeMsp7xZrZjeDem13ycx+P7zPeqvsuNQmCwxuZIe3rkdH/FvjNePtGsS1SHYut2xidw31mVBLt4hrLeqJemgLuzUjrsF40rifulYYsGmc83fGumY2V2THf2ihzF1xzand/xvgs25a2WxIdGN1RB97U3z76hMn6bvU53svic/tPhO/gQ7Fa6G34ANnp7WxewZ/6GUDvIZ+Jwv++8ST8H7mZ3ARb5QQ1sOblS/g/aWHU3/QaBg+cHcdLgpPhe2u2YXcKCGchyeh3RtdCLiQH4U3aV8kG9gr2Kwdfl7Gm6GL4YL/RfwmqT0o8lu83/J8WieDM8LX8bgIfhNYqVDmFLxJ+zI+KNrIZm1gHvCfOK4jMvHaEe+K+Wocp6fxgd3VGtnEunPwG+gEYHjt5iwcj0XiWNTKbGa3URyLf8b+/iHi2AZPFJfgNfxz45xfiddEmyWD3+M1+e8AHyiUtSIu5HfEsXqMwoNfmc1VuNDcQl1034Ffz5fkv8MrNwdnywvY4V0Sc6h3cRYHQvcPP1fjYzHvaGH3KN7d8TdcqEfiFaOL6TqL6wH8PvgZfl8sYIdXfP6K32sTWbDPvhbXjfh9eWsbu+vwa3pYtm0S3oLZI5Y3C5vtm9nEul/TtTu22AXzYbwL5hf44Po7m9g8G+fiDuLa74hG9ocwdyz4rjWTI/BaUq1GsBQ+yHE2nnUH403eE5rZxXJt8GVaweY3wAVZeWfitalacnkzIVBvEg7HRecpXEAvxVsCwwr7sVVceDNxEfsQjRPCr/HZHbeH3UQKYo/PRpkbdlc0sgm7Q+KimkG9JrIEXmP6MvU55pcAJ8X2ZsngF+Hr3MzuSny62QqZr5txARxdtMni+jSepH6Ii+lRdBX7daLMZ/H+8Yub2FyN18D/hdcMz8Cb/cMbHIsD8OTzozZ2Z8RxrT1AtxPefTAJ73LZBb9B/xE+DqN5MqjN9toDF9oH8dZQXktdH08qL+D92AvYhN1d+OsDfkjXJ0tXj/N8Iz42cH7YXdnC7kI84b1ANumABZPe7U3KzO/J9+IVqxdif2fGMdkWF9tZEdcJcSwm4q3QRnafx8X7iTheM+O3axbi+ilemdg389XI7raI/xay2Sz4vb5LnLfLIq5/0LVLJ7c5Gb/H38DF/+DiscAH8HfAKwmvEhXNok38nY5f2z3urumyv/0t1j0Kvuv81i1xIVkrW7cMLr47lbC7l/oDMc1sfkXXfvxGyeU3+H/hqp3gz1Nvsn8yTmSteVab3TKcmNcfNl0SQnYxbEq9dpPbLUU9mQ3Hk8B6RZv43WDqzwbsibeEtqdeE1wCr8HUpj/uERfyAskgOw6jcLEs2s0AvpnZXYYLcCubY3BhXASvwX0VF/I8GQyNczS8mU3YrYTPly/6qjXDazfXAXgybWd3FJ40NsnW7YS3KmrXzoeAH2cxNEoGP8WF5rbMbgIx5Tdb9zmixdXCZhIupl+n3srKr/el8evmSrwy8c0WdlvgLbg5eDI/jwYijo9N/S9eqTmihd1heKtyvVjeHE/Mh+KtkS0iruvJ/kl2E7ubcKGvDUBvhifNo4nnXvBnTh4DZme+mtk9Hed5J3xQv8vURbyycBN+zx/RwuYsPFl8LfPVSOy/iM/UObyFzTg8aXdU5FN6Cws9fkP9Jk7iNFyID42L+X3UhesmvCbU1C58/RXP/q18XUKIdCw3SggfxWsA1+O1/pGFuD+J15gvijLfbMIVbPKEsHUuOI3scBFZr43NjmT917H90Ih1e2KaGN6iqQ0MbUSLZJBdpI3sFg+7SWVtYl0+IL0bfhMdFctjy9qUsNuwnR0u6gdm5U7Da8YjqfdhHx3rLM7D5bROBoviLa+i3Y54913Nbgzeymhl8268P3cwfi19Fu86evM6Dbuh+JPH7eyG44PguU1xIPGdeHdf0VfRbgW8UrAH9bn8W+DJqvbwWG02znfa2A1tYLN52OwQyyPivJSxe0/4XAqfjHAh2ZhQVmZLmxZ2xWmVy8c5b2UzjCZjST39vCX/laCZrYFn0QPwZuY2eNNoZ/wET8JFehh+s07Bu08a2T2KD+q9gs9kWKuJrzfwzP4MLkx/wS/uj+HNyyl4Df6n+I14Az7LYxd8cPJPWfyz8GmJfwnf84FLUkpPZDafxJ/gex/ehJ0R+9DIbmu85rI0XhP6SgObTfEkZEStIsXJN7OpsX0ILkLb4ULyaGw/FK9NXgA8mFL6i5ldCzyWUjohK6eLHT7GcViUdUM3feVvE90NfxjqvXE81kopPdPAZv2IfUP8Ia5nmvjK7dZMKT3dosxJeE3/9oj3GDO7EO/C+VFK6Vdmdg4+qHdmSmmO+f9TXgpPFk+llP5jZkfHMb4IeLGF3bn4gzjnppTubWJzVJzvbwP/SCnNyY7bCvh9sTz+lPAkvH/83hZ29+NjI4+mlC5r42s+cE8LXz/Cu4Iew/vSD8fF96fAnSmlf5vZlPC1ZywPamJ3CH7t743f56187ZVSerWFry52ZJjZMni30Vb4dN/BwD9TStc3sbkZT4jzc5sWvl5MKf2wha+lijYdpzeyR29/8JrJJbV7Mj4nxoFdBr8J9sdvhGvb2B2B17bWbuPrClxot8ZnKpyC95kvi/dvzsKbZ3Pw1+auEb6Oxy/41SKONfA+9HmZr5NwwR9V2M/b8f7G/ZvZhb+X8NbBlBa+foff8PvgDwvtXdg+JmL9T/grvg5gKt4yuDw+qY3djeHrDeBTC+krf/bgjfi0esLxpna+ytrhN+gTuLCtF9fC3dSvu8/h4jcH73e9Dm8Rnh/bL8Rr+R+I5W/ig3EXN7PDa+t/w6/Hsr6uBy4t7MMK+DX5QJyDa1vYfS2Ow2v44GVPfF2Ij4m8CKwf65fCW0HnUJ/X/1V8fGUz6q2iLnZ4kq09GT60J74a2A1qcL6XwQfMX4p9GNPEZlv8ifv/4JW8nvq6F+96W69XNbMvhLljwXptezO86TWHrvNsB+HzWT9b0u68Mr6yda2Sy/vxx52Pxm/UaQVfp+CDNoPiIly9ga9GCeER6vOxm9ltiA92rd/IJo7FzuErf2fM47WbINYtivfZj8eFtVkymIQ3xw9sY3cOLuKTF8ZXdkMMwYXmz3gia2azIp48D2vjqzt2fyUGorO47wLOie/L4wO+tfnjzZLBTfjNfGILuyvxFt68OJfd8XUncF0hzlOIWVDN7PBk9gDxQE4PfY2Mc/QqLs5jqXedLIUn98tin16MvzOa2F0X+/jP2N+e+GpmVxxcHhnXwitZ/I3eAvqF2Me7OuDrOLyHoEcPQ5XSzr4U6h4F6hn+v/FBrHPwgaCn6fpemfFxYbSzm4aLYztf36J90rgaF/dO+KolhPfhA0ajWth9BReqkXhtvZHNVXEs7ojvn6A+FW48Lvbj8QQ1nXgbZWxvlAzWxRPLsGZ2sY/jWtl009emYbNmC19jwtdKbcpsa4d3D9XGDw7Cu6BWzXwMx2eajI7l4/MyYl2eDJbFa+tnlrD7FpE0FsLXr/Austry6Xgttp3dz4GTe+oL7266DK/0nIK3SMZSf1CwNsYwgfqYTUO78HUg3v/fI19t7GpJwaLMbzWI/02b+HsmcFCHfB1HTNTodf3si0J6HKQPdFwNbBHLk/HZGd/HR/9rg2sH4rWw7ZvZha97cAFduoWv/fDazqM0EfHwdQfeV9sqrra+wq6TiWonvIuodsx2C9svUH+MfF28CfrvOCaX0TwZnIPPNb+1hd20iOPP+KDrQPFV1u5zeG3tYeqzk87Au+xysb+B+hzzfWieDPKZKM3sfkY9afTU13V0nUnTzO4m6lNEO+lrWLbtc/j049pbTPNXjDS0w5Ps+p3w1R9ldsPX+n2uoX1d4EIF6YJ6I/UnMwfj/Vufwvsuf4lPI/wjXZ/gbGQ3He83O7mEr5tokVwirgdwYVi6J75i/ZuJCheZniSqA/H5uIeGr0H44M+XiNo/PiD5CvWui1bJ4GXq7x5pZLcB3oc+P34zUHyVtdsY77f/O94H/f3s+jsDf7jpELw76g3gJ4XtxWTwyzi2M5rZ4TOhXgd+1lNf/VFmE1/57KXP4S3Ja+OY/bCF3e14hePv1Ke1Lqyv/iizrK+zcM14Z59qaF8W1qNAXfxmUh+QGoz32Z6PN+0Xx2sYZex2K2GzAuWSy5N4zboTvjqdqA5usJ8fw/uDF8UfKPllVl6jZLANLrjt7LbDB/ROHGC+umP3HN7ErtVoc7H/MN4KeAp/wvUymieD0+IcfbaF3VF4C++ZBmV111d/lFn09b3MJv+fArWEcXr4WsAOf0L9eepJdqF99UeZ3fB1exyvXh14baif/S3gpQP1Jx6PxGcabJmtv4Ou86Hb2nXDV5mksVIHfXUyUQ1vsZ+3Ef8Jp0l5eTLYA+8rL2O3/wD1VdouO0bL468n+H4sr4MPbtdeItcsGRyGz/bapoTdVXhLohO++qPMoq83BS7s3ouPH21X8NXI7g/4eEwnfPVHmWV9rd8v+tkfhS50sD4YdQReO56Ki9tDZE/IlrUraVM2IXTSV8cSVZnYWvh6MxmUtRuovrpjVzh2w/GHbx7BxztWLmxvmAwa+Glr10lf/VFmZvO9WN6AeHq5u3ad9NUfZZb11ZeffhfvbgfsD69sg09tuoyCsHXHrqRN2eTSSV8dSVRlY+uPuPraV3ePWfabT+FjHw2b27RJBt2x66Sv/igzs/lvfK75u9v4amrXSV/9UWZZX3316beCexy4N70HdcKunQ0lk0snfZWx605c7WLrj7j62tdCnMtl8SewW757hDbJoDt2nfTVH2UOVF8DOf6++PRr4W+1Tyuh7C1fZeze6nH1ta9u2i3WZnvZZNDWrpO++qPMgeprIMffV5+35LtuhBhImNliKaVXOmHXSV/9UeZA9dUfZZb11RdI6IUQouIM6u8AhBBC9C4SeiGEqDgSeiGEqDgSeiGEqDgSeiGEqDgSeiGEqDj/D/E1Aytbu74LAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def show_amp(state):\n",
    "    amp = np.abs(state)**2\n",
    "    n_qubits = int(np.log2(len(amp)))\n",
    "    labels = [bin(i)[2:].zfill(n_qubits) for i in range(len(amp))]\n",
    "    plt.bar(labels, amp)\n",
    "    plt.xticks(rotation=45)\n",
    "    plt.show()\n",
    "state = StateEvolution(init_state_circ+ansatz).final_state(pr)\n",
    "show_amp(state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据概率分布图我们发现，该Max-Cut问题具有四个简并解，每个解对应的概率大概为25%。\n",
    "\n",
    "## 总结\n",
    "\n",
    "这里我们通过量子近似优化算法来解决了Max-Cut问题，并得到了案例中的图对应的最大切割方案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献\n",
    "\n",
    "[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. [A Quantum Approximate Optimization Algorithm](https://arxiv.org/pdf/1411.4028.pdf)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "5545a57ef4a1ac7dca167cae0bf17fda051fcd0639773c034bd7ce77ffd97d30"
  },
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}