{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 量子近似优化算法\n", "\n", "[![](https://gitee.com/mindspore/docs/raw/r1.6/resource/_static/logo_source.png)](https://gitee.com/mindspore/docs/blob/r1.6/docs/mindquantum/docs/source_zh_cn/quantum_approximate_optimization_algorithm.ipynb)\n", "\n", "## 概述\n", "\n", "量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是利用量子计算机来近似解决组合优化问题的量子算法，最早由Farhi等人于2014年提出。在本文档里，我们将利用QAOA算法来解决最大割问题（Max-Cut），来熟悉MindQuantum中量子线路的搭建和训练。\n", "\n", "> 本文档适用于CPU环境。\n", "> 你可以在这里找到完整的可运行的样例代码：。\n", "\n", "## 环境准备\n", "\n", "本文档所需要的额外库：\n", "\n", "- networkx\n", "\n", "> `networkx`是创建、操作和研究复杂网络的结构、动态和功能库。可通过如下代码来进行安装。" ] }, { "source": [ "```bash\n", "pip3 install networkx\n", "```" ], "cell_type": "markdown", "metadata": {} }, { "source": [ "## 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问题，因为这类NP-complete问题很有可能不存在多项式时间算法。但尽管精确解不容易得到，我们却可以想办法在多项式时间内找到问题的一个近似解，这就是近似优化算法。下面，我们介绍怎么将Max-Cut问题转化为一个哈密顿量的基态能量求解问题。" ], "cell_type": "markdown", "metadata": {} }, { "cell_type": "markdown", "metadata": {}, "source": [ "![max cut](https://gitee.com/mindspore/docs/raw/r1.6/docs/mindquantum/docs/source_zh_cn/images/Max_Cut.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Max-Cut问题量子化\n", "\n", "这里我们将图中的每个顶点赋予一个量子比特，当顶点被分到左边时，我们将该顶点上的量子比特设置为$\\left|0\\right>$态，同理，右边为$\\left|1\\right>$态，当两个顶点被分到不同的集合中时，这两个顶点上的比特将处于不同的量子态。例如对于第0个顶点和第1个顶点，当其连线被切割时，两个顶点上的比特对应的量子态可以表示为$|01\\rangle$（顶点1：左，顶点0：右）或$|10\\rangle$（顶点1：右，顶点0：左）；若它们被分到同一边，则对应量子态为$|00\\rangle$或$|11\\rangle$。因此我们只要找到一个哈密顿量$H$使得：当有连线的两个顶点处于不同量子态时，哈密顿量的期望值为-1，即\n", "\n", "$$\n", "\\langle 01|H|01\\rangle=-1,\\quad \\langle 10|H|10\\rangle=-1\n", "$$\n", "\n", "而当有连线的顶点处于相同量子态时，哈密顿量的期望值为0，即\n", "\n", "$$\n", "\\langle 00|H|00\\rangle=0,\\quad \\langle 11|H|11\\rangle=0\n", "$$\n", "\n", "随后只要使哈密顿量的期望值最小化，就可以找到最大切割边数，以及此时对应的分组情况。之所以将不同量子态时的期望值设为-1，是因为在量子神经网络的训练中，Ansatz中的参数的梯度会一直下降，同时测量值也会一直减少，该训练方法就是以找到最小值为目标，这里我们用它来寻找哈密顿量的基态能量。此时，我们选择哈密顿量$H=(Z_1Z_0-1)/2$，这里$Z$为泡利$Z$算符。此时有：\n", "\n", "$$\n", "Z_1Z_0|00\\rangle=|00\\rangle,\\quad Z_1Z_0|11\\rangle=|11\\rangle, \\quad Z_1Z_0|01\\rangle=-|01\\rangle, \\quad Z_1Z_0|10\\rangle=-|10\\rangle\n", "$$\n", "\n", "因此当顶点被分到不同集合时：\n", "\n", "$$\n", "\\left<01\\right|H\\left|01\\right>=\\frac{1}{2}\\left<01\\right|Z_1Z_0\\left|01\\right>-\\frac{1}{2}=-1\n", "$$\n", "\n", "$$\n", "\\left<10\\right|H\\left|10\\right>=\\frac{1}{2}\\left<10\\right|Z_1Z_0\\left|10\\right>-\\frac{1}{2}=-1\n", "$$\n", "\n", "而当顶点被分到同一集合中时，不难验证此时：\n", "\n", "$$\n", "\\left<00\\right|H\\left|00\\right>=\\frac{1}{2}\\left<00\\right|Z_1Z_0\\left|00\\right>-\\frac{1}{2}=0\n", "$$\n", "\n", "$$\n", "\\left<11\\right|H\\left|11\\right>=\\frac{1}{2}\\left<11\\right|Z_1Z_0\\left|11\\right>-\\frac{1}{2}=0\n", "$$\n", "\n", "因此，我们只要对图中的每条边写出上述哈密顿量，然后将所有边求和，即可写出图对应的哈密顿量$H$，利用量子计算机求得$H$的基态能量与基态，我们就可以得到该图的Max-Cut切割方案与最大切割边数。我们记所有边的集合为$C$，所有边条数为$c$，则哈密顿量可写为：\n", "\n", "$$\n", "H=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2\n", "$$\n", "\n", "## 导入相关依赖" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from mindquantum.core import Circuit, Hamiltonian, UN, H, ZZ, RX, QubitOperator\n", "from mindquantum.framework import MQAnsatzOnlyLayer\n", "from mindquantum.simulator import Simulator\n", "import networkx as nx\n", "import mindspore.nn as nn" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 搭建所需求解的图\n", "\n", "通过`add_path`可在图中添加边。最后画出图的结构。" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "output_type": "display_data", "data": { "text/plain": "
", "image/svg+xml": "\n\n\n \n \n \n \n 2022-01-04T09:57:59.051559\n image/svg+xml\n \n \n Matplotlib v3.5.0, https://matplotlib.org/\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n\n", "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8/fFQqAAAACXBIWXMAAAsTAAALEwEAmpwYAAA5L0lEQVR4nO3dd1iV9f8/8OdhKDhwK25FDdSUKYEjEE450sKVaFKRA0RRafkp26lp/vKAhqalJjgTBRVLVBBcIEMFB+AExVBxICDrjPv3h3m+kThA4D7j+biuz3UV53h46vWhp+/3fb/vl0QQBAFERER6wkDsAERERHWJxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHrFSOwARPrsdlEZwlJykHGjAAWlCpiZGMHK3Azj7DugRaP6Yscj0kkSQRAEsUMQ6ZvUa/kIjr2IuPN5AIAyhUr9momRAQQArpat4OfSHdYdm4oTkkhHsfiI6tiGhCws+DMDpQolnvbTJ5EAJkaGmDfcCpOcutRZPiJdx61Oojr0sPTSUSJXPfO9ggCUyJVY8Gc6ALD8iGoIV3xEdST1Wj48f01AiVxZ6esPzsXh9q4lAIDGDm+iuXSa+jVTY0NsneaEvh2a1kVUIp3GuzqJ6khw7EWUKiovPUXBbdyNWgEYGFb6eqlCiRWxF2szHpHeYPER1YHbRWWIO59X6TU9QRBwZ89SGDZugQaW/Sv99YIAHMzMw52islpOSqT7WHxEdSAsJeeJrxUm7URpzjm0HPkxJIb1nvg+CYCwE0/+HCJ6Piw+ojqQcaOgwpGFR8rzsnAvbj2aDpqEem0snvoZpQoVMnILaysikd7gXZ1EdaCgVFHp14szjwFKBUqvnkbZtbMov3UFAFBy4TjuGdVDM9f3//M58tqOSqTzWHxEdcDM5Ak/aoIAQEDp5ZQKX1bcv4my6xmVfI5xLaQj0i8sPqI6YGVuhvpGNx7b7mw66B00HfSO+t9vR8rw4Ez0Y8cZAKCeAWBp3rhO8hLpMl7jI6oDY+07vPBnlMvlWDNvCrZs2QK5nFueRNXFA+xEdWRaaDL2n7sBAZIq/1qJBHi9ZxsMa5yDwMBAXL58GTNnzsTUqVPRrFmzWkhLpLu44iOqAwqFAqozf0FQlFfr15sYGWLG4O7w8PBAbGwsIiIicObMGVhYWGDGjBk4f/58DScm0l0sPqJadvv2bQwbNgzZJw7hf0MsYWpctR87U2MDzBtuVeFxZXZ2dggJCcHZs2fRrFkzDBw4ECNHjkRMTAy4iUP0dCw+olqUkpICBwcH2NvbY+/evfCV9sa84T1hamwIyTN2PCWSh8/onDe85xMfUN2uXTvMnz8fWVlZGDlyJGbOnAlbW1v8/vvvKCvjU16IKsNrfES1ZP369fjkk0+wcuVKjBkzpsJraTn5WBF7EQcz8yDBw8PpjzyaxzfYshX8XLtX6cHUKpUK+/btg0wmQ1paGqZPnw5fX1+0bt26Zn5TRDqAxUdUw8rLyxEQEIADBw4gPDwcvXr1euJ77xSVIexEDjJyC1FQKoeZiTGs2jbGWLsXn8B+9uxZBAUFYdu2bRgzZgzmzJmDl19++YU+k0gXsPiIatDff/+NsWPHonXr1li/fj2aNGkidiTk5eVh1apVWLFiBXr37o2AgAAMHToUBga80kH6icVHVEMOHz4MT09P+Pn54bPPPtO4YikrK8PWrVshk8lQWlqK2bNn491330WDBg3EjkZUp1h8RC9IEAT8/PPPmD9/PtavX4+hQ4eKHempBEFAXFwcZDIZjh07hqlTp2LGjBlo37692NGI6oRm/ZWUSMsUFxfjvffew5o1axAfH6/xpQcAEokErq6u2LlzJ+Lj41FYWIg+ffpg0qRJSE5OFjseUa1j8RFV05UrVzBgwAAolUocO3YMFhZPHyukibp3747ly5fj8uXLsLGxwZgxYzBo0CDs2LEDSmXl0+KJtB23OomqISoqCu+++y7mzZsHf39/SJ51KE9LKBQK7NixAzKZDDdv3sSsWbPwwQcfwMzMTOxoRDWGxUdUBYIg4IcffsDPP/+MLVu24NVXXxU7Uq1JSEiATCbDgQMH8N5772HWrFno0qWL2LGIXhi3OomeU0FBAcaMGYPdu3cjKSlJp0sPAJycnLB161acPHkShoaGsLe3x9ixY3HkyBE+Fo20GouP6Dmkp6fD0dERbdq0QWxsrF7dAdmpUycsWbIE2dnZcHV1hbe3NxwdHbFp0yaORyKtxK1OomcIDw+Hj48PFi1ahA8++EDsOKJTKpXYs2cPZDIZLly4gJkzZ2LatGlo3ry52NGInguLj+gJlEolvvzyS2zcuBHbt2+Hg4OD2JE0zsmTJxEYGIhdu3ZhwoQJmD17NiwtLcWORfRU3OokqsSdO3cwbNgwHD9+HMnJySy9J7C1tcX69etx7tw5tGjRAoMGDcKIESMQHR3N64CksVh8RP9x4sQJODg4wMbGBlFRUWjVqpXYkTRe27Zt8f333yM7OxseHh6YNWsWbGxssG7dOpSWloodj6gCbnUS/UtISAg++ugjrFixAuPGjRM7jtYSBAH79++HTCbDyZMn4evri+nTp6NNmzZiRyNi8REBD0cJffjhh9i3bx/Cw8PRu3dvsSPpjHPnziEoKAh//PEHRo0ahYCAAPTp00fsWKTHuNVJei83Nxdubm64evUqEhMTWXo1rFevXli1ahUuXLiAbt26YciQIZBKpdizZw9UKtWzP4CohnHFR3rt6NGjGD9+PHx8fDBv3jyNGyWki8rLy/HHH39AJpPhwYMH6vFIDRs2FDsa6QkWH+klQRCwYsUKfPvtt/j9998xfPhwsSPpHUEQcPjwYchkMhw5cgSTJ0/GzJkz0aFDB7GjkY7jX29J75SUlMDb2xurVq3CsWPHWHoikUgkePXVVxEeHo6EhASUlJSgb9++mDhxIpKSksSORzqMxUd6JSsrCwMGDEBZWRni4+PRvXt3sSMRgG7duiEoKAhXrlxRPxN04MCB2L59O8cjUY3jVifpjf3798PLywv/+9//MHv2bJ0ZJaSLFAoFwsPDIZPJkJubi1mzZmHy5Mkcj0Q1gsVHOk8QBPz4448ICgrC5s2b4eLiInYkqoLjx48jMDBQPQNx1qxZWjn0lzQHtzpJpxUWFmLcuHEIDw9HYmIiS08LvfLKK9i8eTNSU1NRv359ODo6YvTo0Th8+DAfi0bVwuIjnZWRkYFXXnkFLVq0QFxcHO8W1HIdO3bE4sWLkZWVBXd3d0yePBn9+vXDxo0bUV5eLnY80iLc6iSdFBERgWnTpmHhwoWYMmWK2HGoFqhUKvV4pPPnz2PGjBmYNm0aWrRoIXY00nAsPtIpSqUSX331FUJDQxEWFgZHR0exI1EdOHXqFIKCghAREYHx48djzpw5sLKyEjsWaShudZLOuHv3Lt544w0cO3YMycnJLD098mgSRHp6Otq0aQMXFxcMHz4c+/fv53VAegxXfKQTTp06hdGjR2P06NFYtGgRjIyMxI5EIiotLcXGjRshk8kgkUgwZ84cvPPOOzAxMRE7GmkAFh9pvQ0bNiAgIADLly+Hp6en2HFIgwiCgAMHDkAmkyElJQW+vr7w8/PjeCQ9x+IjrSWXy/Hxxx9jz549CA8P56gbeqr09HQsW7YMW7ZsgYeHB+bMmQNra2uxY5EIeI2PtNKNGzfg7u6OS5cuITk5maVHz9SzZ0+sXLkSFy9exEsvvYThw4fD3d0dkZGRHI+kZ7jiI60THx+Pt99+G5MnT8ZXX33FUUJULeXl5di2bRtkMhkKCgowe/ZsvP/++xyPpAdYfKQ1BEHAqlWr8NVXX2Ht2rUYMWKE2JFIBwiCgCNHjkAmk+HQoUPq8UgdO3YUOxrVEv5VmbRCSUkJJk+ejODgYBw7doylRzVGIpFg0KBB2LFjBxITE1FWVgZra2tMmDABiYmJYsejWsDiI42XnZ2NQYMGobi4mKOEqFZZWFggMDAQV65cgaOjI8aPH48BAwYgLCwMCoVC7HhUQ7jVSRrtwIEDmDRpEj799FMEBARwlBDVKYVCgZ07d0ImkyEnJwf+/v6YMmUKmjRpInY0egEsPtJIgiBgyZIlkMlk2LRpEwYPHix2JNJzSUlJkMlk2Lt3L7y8vDBr1ix069ZN7FhUDdzqJI1TWFiIt99+G2FhYUhMTGTpkUbo168fNm3ahLS0NJiamuKVV17BqFGjcOjQIT4WTcuw+EijnD9/Hk5OTmjSpAkOHTrEO+tI43To0AGLFi1CdnY2Xn/9dUydOhUODg7YsGEDxyNpCW51ksbYtWsXpkyZgvnz52PatGlixyF6LiqVCn/99RdkMhnS09Ph5+cHHx8ftGzZUuxo9AQsPhKdUqnEt99+i3Xr1mHbtm1wcnISOxJRtaSlpSEwMBDh4eF4++23MWfOHPTs2VPsWPQf3OokUd27dw8jR45EXFwckpOTWXqk1fr27Yu1a9ciIyMDbdu2xeDBgzFs2DDs27eP1wE1CFd8JJq0tDSMGjUKb775Jn788UcYGxuLHYmoRpWWlmLTpk0IDAyESqVSj0cyNTUVO5peY/GRKDZt2oTZs2cjKCgIEydOFDsOUa0SBAExMTGQyWRISkqCj48P/Pz8YG5uLnY0vcTiozoll8vx6aefYvfu3dixYwf69u0rdiSiOpWZmYmgoCBs3rwZb775JgICAmBjYyN2LL3Ca3xUZ27evAmpVIrMzEwkJSWx9EgvWVpaYsWKFbh06RJ69uyJESNGYPDgwdi1axfHI9URrvioTiQkJGDcuHH44IMP8PXXX3OUENE/5HK5ejxSfn6+ejxSo0aNxI6ms1h8VKsEQcDq1avx5ZdfYs2aNRg5cqTYkYg0kiAIOHbsGGQyGWJjY/HBBx/A39+fD3GoBfxrN9Wa0tJSTJ06FcuWLcORI0dYekRPIZFI1JMgkpKSoFAoYGNjA09PTyQkJIgdT6ew+KhWXL16FYMGDUJBQQGOHz+Ol156SexIRFqja9euWLp0Ka5cuQInJydMnDgRzs7O+OOPPzgeqQZwq5Nq3MGDBzFx4kR8+OGH+PjjjzlKiOgFKZVK9Xikq1evqscjNW3aVOxoWonFRzVGEAQsXboUS5YswcaNG+Hu7i52JCKdk5ycjMDAQPz555+YNGkSZs+ezfFIVcStTqoRRUVF8PT0xObNm3H8+HGWHlEteTQJ4vTp02jUqBGcnJzg4eGBuLg4PhbtObH46IVduHABzs7OaNiwIY4cOYLOnTuLHYlI57Vv3x4LFy5EdnY2hg4dCh8fH9jb2yMkJITjkZ6BW530QiIjI/HBBx/gu+++g4+PD6/nEYlEpVJh7969kMlkOHv2LPz8/ODr68vxSJXgio+qRaVS4ZtvvoGvry927twJX19flh6RiAwMDDB8+HDs378fUVFRyMrKQo8ePTBt2jScO3dO7HgahcVHVfZolFBMTAySk5Ph7OwsdiQi+pc+ffrgt99+Q2ZmJjp06AB3d3cMHToUUVFRvA4IbnVSFZ0+fRqjRo3CiBEjsGTJEo4SItICZWVl2Lx5M2QyGeRyOebMmQMvLy+9HY/E4qPntmXLFvj7+0Mmk2HSpElixyGiKhIEAQcPHoRMJsPx48cxbdo0zJgxA23btq3yZ90uKkNYSg4ybhSgoFQBMxMjWJmbYZx9B7RoVL8W0tccFh89k0KhwNy5cxEeHo4dO3ZwhAqRDjh//jyCgoKwadMmjBw5EgEBAbC1tX3mr0u9lo/g2IuIO58HAChT/N9ECRMjAwgAXC1bwc+lO6w7Nq2l9C+GxUdPdevWLYwfPx7169fHpk2b0Lx5c7EjEVENunv3Ln777TcsX74c3bp1Q0BAAEaMGAFDQ8PH3rshIQsL/sxAqUKJpzWHRAKYGBli3nArTHLqUnvhq4nFR0+UmJiIsWPH4t1338W3335b6Q8CEekGuVyO7du3QyaT4c6dO5g1axa8vb3RuHFjAI9KLx0l8uefGWhqbIB5w3tqXPmx+KhSv/32Gz7//HOsXr0aHh4eYschojoiCALi4+Mhk8kQExMDb29vSMdPRsDubJTIler33Y5citKsU1CWFMCgXgPUM++OZi7voZ55xcenmRobYus0J/Tt0LSOfydPxuKjCsrKyuDv748jR44gPDwclpaWYkciIpFkZWVh+fLl2HLdDMZd7ADJ/52Au7HxfzBs3AIG9RugNDsNirvXYWjWCh381lX4DIkEGNKrDX6Z5FDX8Z+IxUdqOTk5GDNmDDp27Ih169aptziISH/dLipD/0XRKFc+uSrKblzEjd/nABIDdPp4BySGRhVer29kgGNz3TTmbk8eYCcAQGxsLBwdHTF69Ghs27aNpUdEAICwlJwnPpWpIGU37kStwO1dSwAAZo4ej5UeAEgAhJ3Iqc2YVfJ4QtIrgiAgMDAQixcvRmhoKF577TWxIxGRBsm4UVDhyMK/FWccRdm1MwAAw8YtUb99r0rfV6pQISO3sNYyVhWLT489ePAAU6ZMQWZmJhISEtClSxexIxGRhikoffLEd/N3FkFQlKPk8gnkhS9EXsQPaO/zK4yatK7kc+S1GbNKuNWppy5evAgnJyfUr18fR48eZekRUaXMTB5fH6nkZRBUD+/wlBjVg6mFPST1TACVEor8G0/4HM15vCFXfHpoz5498Pb2xjfffIPp06dzqgIRPZGVuRnqG92osN1Z/ncmbu/+f6jfsTcMTBqh7NpZCGXFMGjQBPXaPD4N3sTIAFZtNee+ARafHlGpVJg/fz5Wr16NiIgI9O/fX+xIRKThxtp3wNL9mRW+Zti4BYyatUPplVNQlZfAsIEZGlgNRJMBnjAwafjYZwgAxtp1qKPEz8bi0xP5+fnw8vLCvXv3kJSUVK2H0hKR/ok/uA8ll0/BsJPtw0N5AIybt4f5O4ue69dLJMBgy1Yac5QB4DU+vXDmzBk4OjqiS5cuiImJYekR0TMVFhZi6tSpmD17NuZPGATTetVbJ5kYGcLPtXsNp3sxLD4d98cff2Dw4MH44osvsHz5ctSrV0/sSESk4Y4cOQIbGxsIgoDU1FS8N9IV84ZbwdS4apXx8FmdVhr1uDKAW506S6FQ4LPPPkNYWBj27dv3XONGiEi/lZeX4+uvv8bvv/+OX375BW+99Zb6tUcPmtaF6QwsPh2Ul5cHT09PGBkZITk5GS1atBA7EhFpuDNnzmDSpEno0qULUlNT0br142fxJjl1Qd8OTbEi9iIOZuZBgoeH0x95NI9vsGUr+Ll217iV3iN8VqeOSU5OxpgxY/DOO+/g+++/5yghInoqlUoFmUyGRYsWYfHixfD29n6uI053isoQdiIHGbmFKCiVw8zEGFZtG2OsHSewUx1au3Yt5s6di1WrVmH06NFixyEiDZednY333nsPKpUK69evR9euXcWOVCd4c4sOKCsrg6+vL3788UccOnSIpUdETyUIAtavXw8HBwcMHz4cBw8e1JvSA3iNT+vl5ORg7NixaNu2LRITE2FmZiZ2JCLSYHl5efDx8cHFixdx4MABWFtbix2pznHFp8Xi4uLg6OiIt956C9u3b2fpEdFTRUZGwtraGt27d0dSUpJelh7AFZ9WEgQBy5Ytw8KFCxEaGorXX39d7EhEpMGKiorw4YcfYv/+/diyZQteffVVsSOJisWnZYqLizF16lScO3cOCQkJerUvT0RVd/ToUbz77rtwcXFBamoqd4bArU6tcvnyZTg7O8PQ0BBHjx5l6RHRE5WXl+Pzzz/HmDFj8NNPP2Ht2rUsvX+w+LTEX3/9BWdnZ0ydOhXr169HgwYNxI5ERBrqzJkzeOWVV3DmzBmkpqbCw8ND7EgahcWn4R6NEpoyZQq2b9+OmTNncn4eEVVKpVJh6dKlGDx4MGbOnImdO3eiTZs2YsfSOLzGp8Hu37+P9957D3l5eUhKSkK7du3EjkREGio7Oxvvv/8+5HI5jh8/DgsLC7EjaSyu+DTUuXPn4OjoiPbt2+PgwYMsPSKqlCAICAkJgYODA4YOHYq4uDiW3jNwxaeBwsLCMH36dCxZsgTvv/++2HGISEPdvn0bPj4+OH/+PPbv3w8bGxuxI2kFrvg0iEKhwNy5c/Hxxx9j7969LD0ieqI9e/bA2toaFhYWSEpKYulVAVd8GuL27dvw9PQE8HDCQsuWLUVORESaqKioCB999BGioqKwadMmuLi4iB1J63DFpwFSUlLg4OAABwcH7N27l6VHRJWKj4+HjY0NysvLkZaWxtKrJq74RPb777/jk08+wcqVKzF27Fix4xCRBiovL8e3336LNWvWYOXKlRg1apTYkbQai08k5eXlmDNnDqKjoxEXF4devXqJHYmINNC5c+cwadIktG/fHqdOnYK5ubnYkbQei68G3C4qQ1hKDjJuFKCgVAEzEyNYmZthnH3lk4j//vtvjB07Fq1bt0ZiYiKaNGkiQmoi0mQqlQrLli3DggUL8MMPP2Dy5Ml8eEUN4QT2F5B6LR/BsRcRdz4PAFCmUKlfMzEygADA1bIV/Fy6w7pjUwDA4cOH4enpCT8/P3z22WcwMOBlViKq6OrVq/D29kZpaSlCQkLQrVs3sSPpFBZfNW1IyMKCPzNQqlDiaX+CEglgYmSIz4dZIT95N+bPn4/169dj6NChdReWiLSCIAjYuHEjPvzwQ3z44Yf45JNPYGhoKHYsncPiq4aHpZeOErnq2W/+h4FKgfrn9mBP0P/4VAUiesydO3fg6+uL9PR0bNiwgefyahH32aoo9Vo+FvyZ8VjpCYpy3N33C64tewdX/99o3Aj9BGV/Z6pfVxkYQbAdhaJ6zes6MhFpuL/++gt9+/ZFp06dkJyczNKrZSy+KgqOvYhShfKxr989sBqFJyJh2LApTHs4oex6Bm5u+QLK4vvq95QpVFgRe7Eu4xKRBnvw4AGmT5+O6dOnY+PGjfjpp59gYmIidiydx+KrgttFZYg7n/fYNT3lg3wUpR0AJAZo47kArd76FA17u0IoL0FhSqT6fYIAHMzMw52isjpOTkSaJiEhATY2NigpKUFqaipcXV3FjqQ3WHxVEJaSU+nX5bevAioFDM1awbBhUwBAPfPuAIDyW1cqvFcCIOxE5Z9DRLpPLpfjyy+/hIeHBxYvXozff/+dR5rqGM/xVUHGjYIKRxYeUT64BwAwqPd/WxSSf/750WuPlCpUyMgtrMWURKSpzp07By8vL5ibm/Mwuoi44quCglJFpV83bNgMAKAqL1V/Tfjnnx+9VvFz5LWQjog0lUqlQlBQEFxcXODj44PIyEiWnoi44qsCM5PK/7iMW3YEDIygLMiD8sE9GDZshrLc8wCAeq27VvI5xrWak4g0x7Vr1+Dt7Y3i4mLEx8eje/fuYkfSe1zxVYGVuRnqGz3+R2bYsBka9XEHBBVubp6HvJ2LUXzuECT1TNHYfkSF95oYGcCqbeO6ikxEIhEEARs2bIC9vT3c3Nxw6NAhlp6G4IqvCsbad4DswPlKX2smnQYYGqE4/TDk93JRv70lmrlNhmGDihetS8vKYHwtBQpFZxgZ8Y+fSBfduXMH06dPx9mzZ7F3717Y2dmJHYn+hU9uqaJpocnYn37zqY8pexKJBHi5qRL5u5cgOzsb/v7+mDp1Kpo2bVrjOYlIHHv37sWUKVPw9ttvY+HChTyXp4G41VlFM1y7w8Soes/OMzEyxIKJr+Lw4cPYsWMHTp06BQsLC/j7++PiRR5sJ9JmDx48gJ+fH3x8fBASEoKlS5ey9DQUi6+KrDs2xbzhVjA1rtofnamxAeYNt0LfDk0BAA4ODti4cSNOnz6NRo0awdnZGW+99RZiY2PBRTiRdjl+/DhsbW1RVFSE1NRUuLm5iR2JnoJbndVU1ekM84ZbYZJTlye+78GDBwgJCUFgYCAaNGiAgIAAeHp6ol69ejUfnohqhFwux/fff49Vq1YhODgYY8eOFTsSPQcW3wtIy8nHT3vPIDYzD6YmJiitZB7fYMtW8HPtrl7pPYtKpcLevXshk8lw9uxZ+Pn5wdfXFy1btqyd3wQRVUt6ejq8vLzQunVrrFmzBm3bthU7Ej0nFt8LWrlyJWLjk+E25XNk5BaioFQOMxNjWLVtjLF2lU9gf16nT59GYGAgduzYgXHjxmHOnDno1atXDaYnoqpSqVT4+eef8f3332P+/PmYNm0aJ6NrGRbfC3r99dfh4+ODMWPG1Nr3uHXrFlauXImVK1fCxsYGAQEBeP311/nDRlTHcnJy4O3tjaKiIoSEhKBHjx5iR6JqYPG9gHv37qFz587Izc1Fw4YNa/37lZaWYvPmzZDJZFAoFJgzZw68vLxgampa69+bSJ8JgoDNmzdjzpw5mD17NubOnctzuFqMxfcCNmzYgG3btmHnzp11+n0FQUBMTAxkMhkSExMxbdo0zJgxg9cYiGrB3bt3MX36dJw+fRqhoaGwt7cXOxK9IB5neAHh4eEYNWpUnX9fiUQCd3d3REZG4vDhw7h79y569eqFd999FydPnqzzPES6KioqCn379kW7du2QkpLC0tMRXPFVU0lJCczNzXHp0iWNuOPy7t27+PXXX/Hzzz+jW7duCAgIwIgRI2BoWL3D9kT6rLi4GJ9++il27dqFdevWwd3dXexIVIO44qumffv2wc7OTiNKDwCaN2+OuXPn4vLly/Dx8cGCBQtgaWmJ5cuXo6ioSOx4RFojMTERtra2uH//PtLS0lh6OojFV00RERGibHM+i7GxMSZMmIDjx49j/fr1iIuLQ+fOnfHJJ5/g6tWrYscj0lhyuRzffPMNRo4cifnz5yM0NJTP0dVRLL5qUCgU2L17Nzw8PMSO8kQSiQQDBgxAWFgYkpOToVQqYWtri/HjxyMhIUHseEQaJSMjA/3798fx48dx8uRJjBs3TuxIVItYfNVw+PBhdOnSBZ06dRI7ynPp2rUrli5diitXrsDZ2RkTJ06Ek5MTtm7dCoWi8qnyRPrg0WH0gQMHYvLkyfjzzz/Rrl07sWNRLePNLdUwa9YstGnTBvPmzRM7SrUolUrs3LkTMpmM45FIb12/fh3e3t4oKChAaGgoD6PrEa74qkgQBI29vve8DA0NMXr0aPV4pNTUVI5HIr2yefNm2NraYtCgQThy5AhLT8+w+KooJSUFpqam6Nmzp9hRaoSDgwM2bNiA06dPo3HjxhyPRDrt7t27mDBhAr777jv8+eef+PLLL/kEFj3E4qui8PBweHh46NxzMtu3b4+FCxciOzsbw4YNg6+vL+zs7BASEoLy8nKx4xG9sH379sHa2hqtW7fGiRMn4ODgIHYkEgmv8VVRr169sHbtWjg5OYkdpVZxPBLpiuLiYsydOxc7d+7E2rVrIZVKxY5EIuOKrwoyMzORn58PR0dHsaPUOgMDAwwfPhz79+9HVFQUrly5gh49emDq1Kk4e/as2PGInktSUhLs7Oxw9+5dpKamsvQIAIuvSiIiIuDh4QEDA/36Y+vTpw/WrFmDzMxMdOjQAe7u7hgyZAj27t3L64CkkeRyOb799luMGDEC3333HTZu3IhmzZqJHYs0BLc6q8DJyQnff/89XnvtNbGjiKq0tBRbtmyBTCaDXC7neCTSKJmZmfDy8kLz5s2xZs0atG/fXuxIpGH0a+nyAq5fv47z58/D1dVV7CiiMzExwfvvv49Tp07h559/xu7du9G5c2d88cUXyM3NFTse6SlBEBAcHIwBAwbg/fffx19//cXSo0qx+J7Tzp078cYbb8DY2FjsKBpDIpHAzc0Nu3fvxpEjR3Dv3j2ORyJRXL9+HUOHDkVISAiOHj0KPz8/nbvzmmoOi+85iTV7T1u89NJLCA4OxqVLl9C7d2+8+eabcHV1xc6dO6FUKsWORzps69atsLOzw4ABA3D06FFYWlqKHYk0HK/xPYd79+6hc+fOyM3NRcOGDcWOoxXkcjnCwsIgk8lw9+5dzJ49G97e3mjUqJHY0UhH3Lt3DzNmzMCJEycQGhqKfv36iR2JtARXfM8hMjISgwcPZulVwZPGI3388cfIzs4WOx5puQMHDsDa2hotW7bEiRMnWHpUJSy+56Dtz+YU03/HIwmCADs7O7z99tuIj48XOx5pmeLiYsyaNQve3t5Ys2YNli1bhgYNGogdi7QMtzqfoaSkBObm5rh8+TJatGghdhydUFBQgHXr1iEoKAitW7dGQEAAxowZw2cm0lMlJyfDy8sLtra2CA4O5rk8qjau+J5h3759sLe3Z+nVIDMzM8yePRsXLlzA3LlzERwcDAsLCyxZsgT5+flixyMNo1Ao8N1332H48OH4+uuvsWnTJpYevRAW3zPwbs7aY2hoiFGjRuHQoUMIDw/neCR6zPnz5zFw4EAcPXoUJ0+ehKenp9iRSAew+J5CoVAgMjISHh4eYkfRefb29hyPRGqCIGDFihXo378/vLy8sHfvXh5GpxrDa3xPERMTg7lz5yIpKUnsKHqnuLgYISEhCAwMhKmpKQICAjB+/HjUr19f7GhUy/7++2988MEHuHv3LkJDQ3kuj2ocV3xPwW1O8TRo0AC+vr44d+4cFixYgNDQUHTp0gXff/898vLyxI5HteSPP/6Ara0tnJ2deRidag1XfE8gCAI6deqEqKgo9OrVS+w4BOD06dMICgrC9u3bMXbsWMyZMwe9e/cWOxbVgPz8fMycORNJSUnYsGEDz+VRreKK7wlSUlLQoEED9OzZU+wo9I8+ffrgt99+Q2ZmJjp27AipVMrxSDogOjoaffv2RbNmzXDy5EmWHtU6rvieYN68eVAqlVi0aJHYUegJysrKsHnzZo5H0lIlJSX47LPPEBYWhrVr1+L1118XOxLpCa74noDX9zRf/fr1OR5JS6WkpMDe3h43b95EWloaS4/qFIuvEpmZmbh//z63XLQExyNpD4VCgfnz52PYsGH48ssvsXnzZjRv3lzsWKRnWHyVCA8Ph4eHBwwM+MejbTgeSXNduHABgwYNwqFDh3DixAlMmDBB7Eikp/hf9kpwm1P7NW/eHHPnzsXly5fh6+uLhQsXwtLSEsuWLUNhYaHY8fSKIAhYuXIl+vfvj4kTJ2Lv3r3o0KGD2LFIj/Hmlv+4fv06+vTpg5s3b3Laug4RBAHx8fGQyWSIiYmBt7c3/P390blzZ7Gj6bTc3FxMnjwZt27dwoYNG2BlZSV2JCKu+P4rIiICb7zxBktPx0gkEvTv3x/btm1DSkoKxyPVgW3btsHGxgb9+vVDfHw8S480Bld8/yGVSuHn54fRo0eLHYVqGccj1Y78/Hz4+/sjMTERoaGhcHR0FDsSUQUsvn+5d+8eOnfujNzcXE5b1yNKpRK7du2CTCZDVlYW/P39MXXqVDRt2lTsaFrn0TbyiBEj8OOPP/LniDQStzr/JTIyEm5ubvxh1TMcj/TiSkpKEBAQgHfffRerV69GcHAwf45IY7H4/oV3c9K/xyOZmZmhf//+HI/0DCdOnICDgwP+/vtvpKamYsiQIWJHInoqbnX+o7i4GG3btsWVK1d4oJbUiouLERoaisDAQJiYmGDOnDnw9PTkeCQ8PIy+ePFiBAUFITAwEBMmTIBEIhE7FtEzsfj+ERERgeXLlyM6OlrsKKSBVCoVoqKiIJPJcObMGUyfPh2+vr5o1aqV2NFEcfHiRXh5eaFhw4ZYt24dOnbsKHYkoufGrc5/cJuTnsbAwADDhg3Dvn37sG/fPmRnZ+Oll17C1KlTcfbsWbHj1RlBELBq1So4OztjwoQJ2LdvH0uPtA5XfADkcjnMzc1x6tQp/hDTc7t16xZ++eUXrFy5En379kVAQACGDBmis9t9ubm5mDJlCm7evInQ0FCO7CKtxRUfgEOHDsHCwoKlR1XSunVrfPXVV8jKysKECRMwd+5c9O7dG6tXr0ZJSYnY8WrU9u3bYWtrC3t7e8THx7P0SKtxxQfA398fbdu2xeeffy52FNJigiDg4MGDCAwMREJCAqZNm4YZM2agbdu2Ykertvv378Pf3x/x8fEIDQ2Fk5OT2JGIXpjer/gEQUBERASv79ELezQeadeuXTh69Cjy8/PRq1cveHl54cSJE2LHq7KDBw/C2toajRo1wqlTp1h6pDP0vviSk5PRsGFDbt1QjerRowd+/vlnXL58GX369MFbb70FFxcXREREaPx4pNLSUnz44YeYNGkSVq5ciRUrVvAwOukUvS8+3s1JtalZs2b49NNPcfnyZUyfPh0//PCDRo9HOnnyJBwcHJCTk4O0tDQMGzZM7EhENY7Fx+KjOmBsbAxPT08kJCQgJCQEhw8fRpcuXfDxxx8jOztb7HhQKBRYuHAhhgwZgs8++wxbt25FixYtxI5FVCv0+jH0GRkZKCwshIODg9hRSE88Go/Uv39/ZGVlYfny5bCzs4O7uzsCAgLg7Oxc7c++XVSGsJQcZNwoQEGpAmYmRrAyN8M4+w5o0ejJT5q5dOkSvLy8YGpqipSUFN7dTDpPr+/q/OGHH5CTk4Pg4GCxo5AeKywsVI9HatWqVZXHI6Vey0dw7EXEnc8DAJQpVOrXTIwMIABwtWwFP5fusO7YVP2aIAj49ddfMW/ePHzxxRfw9/eHgYHebwKRHtDr4nN0dMTChQshlUrFjkIEpVKJ3bt3QyaT4cqVK881HmlDQhYW/JmBUoUST/tJlkgAEyNDzBtuhUlOXXDjxg1MmTIFubm5CA0NRa9evWr+N0SkofT2r3c5OTm4dOkSXFxcxI5CBODheCQPDw/ExcUhPDwcaWlpsLCwwMyZM3HhwoXH3v+w9NJRIn966QGAIAAlciUW/JmOj36JgI2NDWxtbREfH8/SI72jtyu+4OBgHD9+HCEhIWJHIXqiv//+G8HBwVi9ejWcnZ0REBAAV1dXpOXch+evCSiR/9/RiDt/LkPp9XNQFtyGxNAY9dq9hGaDvVGvVZeKH6oox3y3lpg0bFDd/maINITervh4Nydpg3bt2mHBggXIzs7GG2+8AT8/P9jZ2WFuSAxK5RXPAxal7YNB/YZo2OtVSOo3QOnlFNz642sIivIK75MY1cORO6Z1+dsg0ih6ueK7e/cuunbtitzcXDRo0EDsOETPTaVSYdvuvfjfMTkEg4o3v5TduIj65t0BAIr8m7j+y2QAgPn7geqvP1LfyADH5ro99W5PIl2llyu+yMhIuLm5sfRI6xgYGOBeU0vUq1fvsdf+XW6CSvHwHyQGMGz0+GBlCYCwEzm1FZNIo+ll8XGbk7RZxo2CCkcW/ktVXoI7ewIBAGaOHjCqpPhKFSpk5Grek2OI6oLeFV9xcTGio6MxYsQIsaMQVUtBqeKJrymL7+Pmps9Rdj0djayHoKmr91M+R14b8Yg0nt49uSUqKgr9+vVD8+aP/y2YSBuYmVT+Y6u4fws3t34Jxd3rMHMeh2Yu7z3jc4xrIx6RxtO74uMIItJGZWVliI+Px4EDB3Ag8wGEzoMgMa54Y8qN0I+hLLoLQ7NWEORluHtgNQCgYS8X1G9nWeG9JkYGsGrbuM7yE2kSvbqrUy6Xw9zcHKmpqejQoYPYcYieSKVSITU19WHRHTiAY8eOoXfv3pBKpeg30A2fHC1D+X+u82Uvqnz7vsXwOWjUt+LTiXhXJ+kzvVrxHTp0CN26dWPpkUa6fPmyuugOHjyIli1bwt3dHdOnT8fWrVsrPLpsT14y9qffrPDEls7/i3yu7yORAIMtW7H0SG/pVfHxbk7SJHl5eYiJiUF0dDQOHDiAkpISSKVSvPHGG1i6dOlT/4I2w7U7Dl+4XeHJLc/LxMgQfq7dn/1GIh2lN1udKpUKnTp1woEDB2BlZSV2HNJDDx48wJEjR9SrusuXL8PFxQVSqRTu7u7o1asXJBLJc3/e/z2r88lHG/7L1NgA84b3xCSnLtX4HRDpBr1Z8SUnJ6Nx48YsPaozCoUCycnJ6qJLTk6Gvb093N3dERwcjH79+sHYuPp3Vj4qr+pMZyDSZ3qz4vvss88gkUiwcOFCsaOQjhIEARkZGeqii4uLQ+fOnSGVSiGVSjFo0CA0atSoxr9vWk4+VsRexMHMPEjw8HD6I4/m8Q22bAU/1+7o26FpjX9/Im2jN8VnZWWFkJAQODo6ih2FdMj169cRHR2tvk5nZGSE1157DVKpFG5ubmjdunWdZblTVIawEznIyC1EQakcZibGsGrbGGPtnj6BnUjf6EXxpaen47XXXsPVq1c5YZpeyP379xEXF6de1d28eRNubm7q63TdunWr0nU6Iqp7enGNLyIiAh4eHiw9qrKysjIkJCSoi+7MmTNwcnKCVCpFaGgobGxsYGhoKHZMIqoCvVjxOTo64ocffoC7u7vYUUjDqVQqpKWlVTg4bmVlpb5O179/f5iYmIgdk4hegM4XX05ODqytrXHjxo0XuoOOdNeVK1fU1+iio6PRvHlzddG5urqiWbNmYkckohqk81udERERGDFiBEuP1G7fvo2DBw+qV3UPHjyAVCrFkCFD8OOPP6JTp05iRySiWqTzxRceHg5/f3+xY5CIiouLKxwcv3TpEgYNGgSpVAp/f3/07t2bN6QQ6RGd3uq8c+cOLCwskJuby2nrekShUCAlJUW9dZmYmAhbW1v19qWjoyN3AIj0mE6v+CIjI+Hm5sbS03GCICAzM1N9nS42NhYdO3aEVCrFRx99hFdffRWNG3MEDxE9pNPFFx4ejtGjR4sdg2pBbm6uuugOHDgAAwMDSKVSjBs3DitXroS5ubnYEYlIQ+nsVmdxcTHMzc2RlZXFaes6oKCgoMLB8dzcXAwePFi9fdm9e3depyOi56KzK76oqCg4Ojqy9LRUeXm5+uB4dHQ00tLS8Morr0AqlWL9+vWwtbXlwXEiqhadLT7O3tMuKpUKp0+fVm9fHjlyBJaWlnB3d8e3336LAQMGwNTUVOyYRKQDdHKrUy6Xw9zcHGlpaWjfvr3YcegJsrOz1VuX0dHRaNKkiXrrcvDgwVytE1Gt0MkVX1xcHLp3787S0zB37typcHC8sLAQ7u7ueO2117Bo0SJ07txZ7IhEpAd0svi4zakZSkpK1AfHo6Ojcf78efXBcT8/P7z88st8cDgR1Tmd2+pUqVTo2LEjoqOjOW29jimVSqSkpKiv0yUmJsLa2hru7u6QSqV45ZVXUK9ePbFjEpGe07kVX1JSEszMzFh6dUAQBFy4cEG9dRkbG4t27dpBKpUiICAAr776KszMzMSOSURUgc4VX0REBLc5a9GNGzcqTDIQBAFSqRRjxoxBcHAw2rZtK3ZEIqKn0rmtTisrK4SGhqJfv35iR9EJhYWFiIuLU5ddTk4OBg8erN6+fOmll3hwnIi0ik6t+NLT0/HgwQM4ODiIHUVryeVyHD9+XL19eerUKTg6OkIqlWLNmjWws7ODkZFO/d+GiPSMTv0XLDw8HB4eHlyBVIEgCDhz5oy66A4fPowePXpAKpXi66+/xoABA/iQbyLSKTq11dmvXz8sXrwYbm5uYkfRaFevXlUXXUxMDBo1alTh4HiLFi3EjkhEVGt0pviuXbsGW1tb3Lhxg1tx/3Hv3r0KB8fz8/Ph7u6u/l/Xrl3FjkhEVGd0piEiIiIwYsQIlh6A0tJSHD16VF10GRkZGDhwIKRSKXx8fNCnTx8eHCcivaUzLREeHo5Zs2aJHUMUSqUSJ0+eVBddQkIC+vbtC6lUip9++glOTk48OE5E9A+d2Oq8c+cOLCwskJubqxc3YgiCgIsXL6rP0h08eBDm5ubq63QuLi48OE5E9AQ6seKLjIyEu7u7TpfezZs3ER0drT5Pp1AoIJVK8dZbb2HZsmVo166d2BGJiLSCThRfeHg4xowZI3aMGlVUVIRDhw6pty+vXr0KV1dXSKVSfPLJJ7C0tOSxDSKiatD6rc4HDx6gXbt2yMrKQrNmzcSOU21yuRyJiYnqojt58iT69eun3r60t7fnjTtERDVA6/9LGhUVBUdHR60rPUEQcPbsWfV1ukOHDqFbt25wd3fHF198gYEDB6Jhw4ZixyQi0jlaX3zaNHvv2rVrFR7wbGpqCqlUCi8vL6xduxatWrUSOyIRkc7T6q1OuVyONm3a4PTp0xo5bf3evXuIjY1Vb1/euXNH/XBnd3d3WFhYiB2RiEjvaPWKLzY2Fj169NCY0istLcWxY8fURZeeno4BAwZAKpViy5YtsLa25sFxIiKRaXXxib3NqVQqcerUKfXWZXx8PF5++WW4u7vjxx9/hLOzM+rXry9aPiIiepzWbnWqVCp07NgRMTExsLS0rJPvKQgCLl26pL5OFxMTg9atW1c4ON60adM6yUJERNWjNSu+20VlCEvJQcaNAhSUKlBedB+mdm+iZfsutfp9b926hZiYGPX2ZXl5OaRSKUaOHInAwECN2WYlIqLno/ErvtRr+QiOvYi483kAgDKFSv2aIZQwMjKGq2Ur+Ll0h3XHpi/8/YqKinD48GH19mVWVhZcXFzUN6X07NmTB8eJiLSYRhffhoQsLPgzA6UKJZ6WUiIBTIwMMW+4FSY5danS95DL5UhKSlJvX6akpMDe3l69fdmvXz8eHCci0iEaW3wPSy8dJXLVs9/8D1NjA8wb3vOp5ScIAtLT09Vbl3Fxcejatau66AYNGsSD40REOkwjiy/1Wj48f01AiVyp/lpB0k4Upe2H/PZVQFChyYAJaDroncd+ramxIbZOc0LfDk3VX8vJyalwcLxevXp47bXX4O7uDjc3N7Ru3boufltERKQBNHIPLzj2IkoVygpfK79xEQYmjWDYuCWUBbee+GtLFUoE7U/HyGY31au6vLw8uLm5QSqV4ptvvoGFhQWv0xER6SmNK77bRWWIO5/32DW9liM/AgDc2j4fJU8pPkEADpy7gStnf8dQ1wHYtGkTbGxseHCciIgAaGDxhaXkvPBnmJqYYPz/lsLn1W41kIiIiHSJxi2DMm4UVDiyUB2lChUycgtrKBEREekSjSu+glJFDX2OvEY+h4iIdIvGFZ+ZSc3svpqZGNfI5xARkW7RuGt8VuZmqG9047HtzsLUKJRdO4fym5cAAMUXEqC4fwsNXnJCg5ecK7zXxMgAVm0b11lmIiLSHhq34htr36HSr5ddO4cHZ6KhLHj46DL5rSt4cCYa5TcvP/ZeAcBYu8o/h4iI9JtGHmCfFpqM/ek3n/qYsieRSIAhvdrgl0kONR+MiIi0nsat+ABghmt3mBgZVuvXmhgZws+1ew0nIiIiXaGRxWfdsSnmDbeCqXHV4j18VqdVhceVERER/ZvG3dzyyKMHTdf2dAYiItIvGnmN79/ScvKxIvYiDmbmQYKHh9MfMTEygABgsGUr+Ll250qPiIieSeOL75E7RWUIO5GDjNxCFJTKYWZiDKu2jTHWrgNaNKovdjwiItISWlN8RERENUEjb24hIiKqLSw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSK/8fD0mjO05Zdr8AAAAASUVORK5CYII=\n" }, "metadata": {} } ], "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条边构成的图结构。\n", "\n", "接下来我们用穷举法来看看所有情况的切割边数。" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "tags": [] }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": "one size: [0] cut= 3\none size: [1] cut= 2\none size: [1, 0] cut= 3\none size: [2] cut= 3\none size: [2, 0] cut= 4\none size: [2, 1] cut= 3\none size: [3] cut= 2\none size: [3, 0] cut= 5\none size: [3, 1] cut= 4\none size: [3, 2] cut= 3\none size: [4] cut= 2\none size: [4, 0] cut= 3\none size: [4, 1] cut= 4\none size: [4, 2] cut= 5\none size: [4, 3] cut= 2\n" } ], "source": [ "for i in g.nodes:\n", " print('one size:', [i], 'cut=', nx.cut_size(g, [i])) # 一组1个节点、另一组4个节点的所有情况\n", " for j in range(i):\n", " print('one size:', [i, j], 'cut=', nx.cut_size(g, [i, j])) # 一组2个节点、另一组3个节点的所有情况" ] }, { "source": [ "从以上结果可以看出，穷举法得到的最大切割边数为5，如果对节点分组的左右进行区分，则一共有4种分组方法可以使切割边数最大，即该问题有4个简并解。" ], "cell_type": "markdown", "metadata": {} }, { "source": [ "## QAOA算法整体流程\n", "\n", "1. 搭建QAOA量子线路，其中ansatz线路包含可以训练的参数\n", "2. 初始化线路中的参数\n", "3. 运行该量子线路，得到量子态$|\\psi\\rangle$\n", "4. 计算目标哈密顿量$H_C$的期望值$\\langle\\psi|H_C|\\psi\\rangle$\n", "5. 根据第4步的结果，使用Adam优化器优化线路中参数\n", "6. 重复3-5步，直到第4步结果基本不再变化\n", "7. 根据第4步的结果，算出目标问题的近似解\n", "\n", "在该流程中，第2-6步都可以由MindSpore和MindQuantum中现成的包和函数来实现，因此我们将重点关注第1步——量子线路的搭建。\n", "\n", "![Flowchart](https://gitee.com/mindspore/docs/raw/r1.6/docs/mindquantum/docs/source_zh_cn/images/QAOA_Flowchart.png)" ], "cell_type": "markdown", "metadata": {} }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 搭建QAOA量子线路\n", "\n", "先前提到，我们需要将问题对应的哈密顿量\n", "\n", "$$\n", "H_C=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2\n", "$$\n", "\n", "最小化来找到问题的解，也就是说我们要找到该哈密顿量的基态。对此我们可以采用量子绝热演化的方法，使系统先处于某一简单哈密顿量$H_B$的基态上，然后使简单的哈密顿量$H_B$绝热地、缓慢地演化至某一复杂的哈密顿量$H_C$，根据绝热定理，系统将始终保持在哈密顿量的基态上，最终达到复杂哈密顿量$H_C$的基态。\n", "\n", "我们将要搭建的量子线路就是采用以上思路，选取初始简单哈密顿量为\n", "\n", "$$\n", "H_B=\\sum_i X_i\n", "$$\n", "\n", "并将量子线路制备到$H_B$的基态$|s\\rangle=|+\\rangle^{\\otimes n}$，这里通过对所有量子比特作用`Hadamard`门即可实现。然后连接ansatz含参线路，通过不断地优化其中参数可以使得ansatz线路越来越接近真实绝热演化的效果，最终得到的量子线路可以视为模拟近似了一个真实的绝热演化过程。\n", "\n", "### ansatz线路\n", "\n", "在量子绝热演化中，首先选取初始哈密顿量\n", "\n", "$$\n", "H_B=\\sum_i X_i\n", "$$\n", "\n", "并使系统处于$H_B$的基态$|s\\rangle=|+\\rangle^{\\otimes n}$。然后缓慢地作用如下含时哈密顿量\n", "\n", "$$\n", "H(t)=(1-\\frac{t}{T})H_B+(\\frac{t}{T})H_C\n", "$$\n", "\n", "注意到当$t=T$时，$H(T)=H_C$。当选取的$T$足够大时（满足绝热条件），系统将始终处于$H(t)$的瞬时基态上，此时系统的量子态将从初始哈密顿量$H_B$的基态$|\\psi (0)\\rangle$绝热地演化到目标哈密顿量$H_C$的基态$|\\psi (T)\\rangle$上，即\n", "\n", "$$\n", "|\\psi (T)\\rangle=\\mathcal{T}e^{-i\\int^{T}_{0} H(t)dt}|\\psi(0)\\rangle\n", "$$\n", "\n", "也就是说，ansatz线路需要模拟的就是$\\mathcal{T}e^{-i\\int^{T}_{0} H(t)dt}$这一演化过程。接下来我们将对这个式子进行一些近似和化简，使其变为可以在量子线路中实现的形式。\n", "\n", "考虑如下trotter公式\n", "\n", "$$\n", "\\mathcal{T}e^{-i\\int^T_0 H(t)dt}=\\lim_{N\\rightarrow \\infty}\\prod^N_{l=1}e^{-iH(t_l)\\Delta t},\\quad \\Delta t=\\frac{T}{N},\\quad t_l=l\\Delta t\n", "$$\n", "\n", "略去$O(\\Delta t^2)$项，得到\n", "\n", "$$\n", "\\mathcal{T}e^{-i\\int^T_0 H(t)dt}\\approx \\lim_{N\\rightarrow \\infty}\\prod^N_{l=1}e^{-iH_B(1-t_l/T)\\Delta t}e^{-iH_C t_l\\Delta t/T}\n", "$$\n", "\n", "令$\\beta_l=(1-t_l/T)\\Delta t$，$\\gamma_l=t_l\\Delta t/T$，并取$N$为一个有限大的整数，即得到QAOA的ansatz\n", "\n", "$$\n", "|\\psi(\\gamma,\\beta)\\rangle=\\prod^p_{l=1}e^{-i\\beta_l H_B}e^{-i\\gamma_l H_C}|\\psi_{in}\\rangle\n", "$$\n", "\n", "因此我们需要搭建的ansatz线路由$U_C(\\gamma)$和$U_B(\\beta)$这两个酉变换交替构成，其中$U_C(\\gamma)=e^{-i\\gamma \\sum_{\\langle i,j\\rangle}Z_i Z_j}$可以由`ZZ`门实现，$U_B(\\beta)=e^{-i\\beta \\sum_i X_i}$则相当于在每个量子比特上作用一个`RX`旋转门，$\\gamma$和$\\beta$是可训练的参数。" ] }, { "source": [ "搭建$U_C(\\gamma)$对应的量子线路：" ], "cell_type": "markdown", "metadata": {} }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def build_hc(g, para):\n", " hc = Circuit() # 创建量子线路\n", " for i in g.edges:\n", " hc += ZZ(para).on(i) # 对图中的每条边作用ZZ门\n", " hc.barrier() # 添加Barrier以方便展示线路\n", " return hc" ] }, { "source": [ "线路展示：" ], "cell_type": "markdown", "metadata": {} }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "output_type": "display_data", "data": { "text/plain": "", "text/html": "
\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──ZZ(gamma)────ZZ(gamma)────ZZ(gamma)─────────────────────────────────────────‖\n          │            │            │                                             ‖\nq1: ──ZZ(gamma)────────┼────────────┼────────ZZ(gamma)────────────────────────────‖\n                       │            │            │                                ‖\nq2: ───────────────────┼────────ZZ(gamma)────ZZ(gamma)────ZZ(gamma)───────────────‖\n                       │                                      │                   ‖\nq3: ───────────────────┼──────────────────────────────────ZZ(gamma)────ZZ(gamma)──‖\n                       │                                                   │      ‖\nq4: ───────────────ZZ(gamma)───────────────────────────────────────────ZZ(gamma)──‖",
      "text/html": "
q0: ──ZZ(gamma)────ZZ(gamma)────ZZ(gamma)─────────────────────────────────────────‖\n          │            │            │                                             ‖\nq1: ──ZZ(gamma)────────┼────────────┼────────ZZ(gamma)────────────────────────────‖\n                       │            │            │                                ‖\nq2: ───────────────────┼────────ZZ(gamma)────ZZ(gamma)────ZZ(gamma)───────────────‖\n                       │                                      │                   ‖\nq3: ───────────────────┼──────────────────────────────────ZZ(gamma)────ZZ(gamma)──‖\n                       │                                                   │      ‖\nq4: ───────────────ZZ(gamma)───────────────────────────────────────────ZZ(gamma)──‖\n
\n"
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circuit = build_hc(g, 'gamma')\n",
    "circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搭建$U_B(\\beta)$对应的量子线路："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_hb(g, para):\n",
    "    hb = Circuit()                  # 创建量子线路\n",
    "    for i in g.nodes:\n",
    "        hb += RX(para).on(i)        # 对每个节点作用RX门\n",
    "    hb.barrier()                    # 添加Barrier以方便展示线路\n",
    "    return hb"
   ]
  },
  {
   "source": [
    "线路展示："
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "
\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──RX(beta)──‖\n                ‖\nq1: ──RX(beta)──‖\n                ‖\nq2: ──RX(beta)──‖\n                ‖\nq3: ──RX(beta)──‖\n                ‖\nq4: ──RX(beta)──‖",
      "text/html": "
q0: ──RX(beta)──‖\n                ‖\nq1: ──RX(beta)──‖\n                ‖\nq2: ──RX(beta)──‖\n                ‖\nq3: ──RX(beta)──‖\n                ‖\nq4: ──RX(beta)──‖\n
\n"
     },
     "metadata": {},
     "execution_count": 7
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circuit = build_hb(g, 'beta')\n",
    "circuit"
   ]
  },
  {
   "source": [
    "实现了一层酉变换$U_B(\\beta) U_C(\\gamma)$的ansatz线路如下所示："
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "
\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──ZZ(gamma)────ZZ(gamma)────ZZ(gamma)─────────────────────────────────────────‖──RX(beta)──‖\n          │            │            │                                             ‖            ‖\nq1: ──ZZ(gamma)────────┼────────────┼────────ZZ(gamma)────────────────────────────‖──RX(beta)──‖\n                       │            │            │                                ‖            ‖\nq2: ───────────────────┼────────ZZ(gamma)────ZZ(gamma)────ZZ(gamma)───────────────‖──RX(beta)──‖\n                       │                                      │                   ‖            ‖\nq3: ───────────────────┼──────────────────────────────────ZZ(gamma)────ZZ(gamma)──‖──RX(beta)──‖\n                       │                                                   │      ‖            ‖\nq4: ───────────────ZZ(gamma)───────────────────────────────────────────ZZ(gamma)──‖──RX(beta)──‖",
      "text/html": "
q0: ──ZZ(gamma)────ZZ(gamma)────ZZ(gamma)─────────────────────────────────────────‖──RX(beta)──‖\n          │            │            │                                             ‖            ‖\nq1: ──ZZ(gamma)────────┼────────────┼────────ZZ(gamma)────────────────────────────‖──RX(beta)──‖\n                       │            │            │                                ‖            ‖\nq2: ───────────────────┼────────ZZ(gamma)────ZZ(gamma)────ZZ(gamma)───────────────‖──RX(beta)──‖\n                       │                                      │                   ‖            ‖\nq3: ───────────────────┼──────────────────────────────────ZZ(gamma)────ZZ(gamma)──‖──RX(beta)──‖\n                       │                                                   │      ‖            ‖\nq4: ───────────────ZZ(gamma)───────────────────────────────────────────ZZ(gamma)──‖──RX(beta)──‖\n
\n"
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circuit = build_hc(g, 'gamma') + build_hb(g, 'beta')\n",
    "circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了使得最后优化的结果足够准确，我们需要将量子线路重复多次，因此我们通过如下函数搭建多层的训练网络："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ansatz(g, p):                    # g是max-cut问题的图，p是ansatz线路的层数\n",
    "    circ = Circuit()                       # 创建量子线路\n",
    "    for i in range(p):\n",
    "        circ += build_hc(g, f'g{i}')       # 添加Uc对应的线路，参数记为g0、g1、g2...\n",
    "        circ += build_hb(g, f'b{i}')       # 添加Ub对应的线路，参数记为b0、b1、b2...\n",
    "    return circ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建图对应的哈密顿量$H_C=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2$（忽略常数项和系数）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ham(g):\n",
    "    ham = QubitOperator()\n",
    "    for i in g.edges:\n",
    "        ham += QubitOperator(f'Z{i[0]} Z{i[1]}')  # 生成哈密顿量Hc\n",
    "    return ham"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 生成完整的量子线路和图所对应的哈密顿量\n",
    "\n",
    "这里我们选择`p = 4`，表示选用4层的QAOA量子线路，`ansatz`是求解该问题的量子线路，`init_state_circ`是将量子态制备到均匀叠加态（$H_B$的基态）上的量子线路。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "
\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──H────ZZ(g0)────ZZ(g0)────ZZ(g0)────────────────────────────────‖──RX(b0)──‖──ZZ(g1)────ZZ(g1)────ZZ(g1)────────────────────────────────‖──RX(b1)──‖──ZZ(g2)────ZZ(g2)────ZZ(g2)────────────────────────────────‖──RX(b2)──‖──ZZ(g3)────ZZ(g3)────ZZ(g3)────────────────────────────────‖──RX(b3)──‖\n             │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖\nq1: ──H────ZZ(g0)──────┼─────────┼───────ZZ(g0)──────────────────────‖──RX(b0)──‖──ZZ(g1)──────┼─────────┼───────ZZ(g1)──────────────────────‖──RX(b1)──‖──ZZ(g2)──────┼─────────┼───────ZZ(g2)──────────────────────‖──RX(b2)──‖──ZZ(g3)──────┼─────────┼───────ZZ(g3)──────────────────────‖──RX(b3)──‖\n                       │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖\nq2: ──H────────────────┼───────ZZ(g0)────ZZ(g0)────ZZ(g0)────────────‖──RX(b0)──‖──────────────┼───────ZZ(g1)────ZZ(g1)────ZZ(g1)────────────‖──RX(b1)──‖──────────────┼───────ZZ(g2)────ZZ(g2)────ZZ(g2)────────────‖──RX(b2)──‖──────────────┼───────ZZ(g3)────ZZ(g3)────ZZ(g3)────────────‖──RX(b3)──‖\n                       │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖\nq3: ──H────────────────┼───────────────────────────ZZ(g0)────ZZ(g0)──‖──RX(b0)──‖──────────────┼───────────────────────────ZZ(g1)────ZZ(g1)──‖──RX(b1)──‖──────────────┼───────────────────────────ZZ(g2)────ZZ(g2)──‖──RX(b2)──‖──────────────┼───────────────────────────ZZ(g3)────ZZ(g3)──‖──RX(b3)──‖\n                       │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖\nq4: ──H──────────────ZZ(g0)──────────────────────────────────ZZ(g0)──‖──RX(b0)──‖────────────ZZ(g1)──────────────────────────────────ZZ(g1)──‖──RX(b1)──‖────────────ZZ(g2)──────────────────────────────────ZZ(g2)──‖──RX(b2)──‖────────────ZZ(g3)──────────────────────────────────ZZ(g3)──‖──RX(b3)──‖",
      "text/html": "
q0: ──H────ZZ(g0)────ZZ(g0)────ZZ(g0)────────────────────────────────‖──RX(b0)──‖──ZZ(g1)────ZZ(g1)────ZZ(g1)────────────────────────────────‖──RX(b1)──‖──ZZ(g2)────ZZ(g2)────ZZ(g2)────────────────────────────────‖──RX(b2)──‖──ZZ(g3)────ZZ(g3)────ZZ(g3)────────────────────────────────‖──RX(b3)──‖\n             │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖\nq1: ──H────ZZ(g0)──────┼─────────┼───────ZZ(g0)──────────────────────‖──RX(b0)──‖──ZZ(g1)──────┼─────────┼───────ZZ(g1)──────────────────────‖──RX(b1)──‖──ZZ(g2)──────┼─────────┼───────ZZ(g2)──────────────────────‖──RX(b2)──‖──ZZ(g3)──────┼─────────┼───────ZZ(g3)──────────────────────‖──RX(b3)──‖\n                       │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖\nq2: ──H────────────────┼───────ZZ(g0)────ZZ(g0)────ZZ(g0)────────────‖──RX(b0)──‖──────────────┼───────ZZ(g1)────ZZ(g1)────ZZ(g1)────────────‖──RX(b1)──‖──────────────┼───────ZZ(g2)────ZZ(g2)────ZZ(g2)────────────‖──RX(b2)──‖──────────────┼───────ZZ(g3)────ZZ(g3)────ZZ(g3)────────────‖──RX(b3)──‖\n                       │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖\nq3: ──H────────────────┼───────────────────────────ZZ(g0)────ZZ(g0)──‖──RX(b0)──‖──────────────┼───────────────────────────ZZ(g1)────ZZ(g1)──‖──RX(b1)──‖──────────────┼───────────────────────────ZZ(g2)────ZZ(g2)──‖──RX(b2)──‖──────────────┼───────────────────────────ZZ(g3)────ZZ(g3)──‖──RX(b3)──‖\n                       │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖\nq4: ──H──────────────ZZ(g0)──────────────────────────────────ZZ(g0)──‖──RX(b0)──‖────────────ZZ(g1)──────────────────────────────────ZZ(g1)──‖──RX(b1)──‖────────────ZZ(g2)──────────────────────────────────ZZ(g2)──‖──RX(b2)──‖────────────ZZ(g3)──────────────────────────────────ZZ(g3)──‖──RX(b3)──‖\n
\n"
     },
     "metadata": {},
     "execution_count": 11
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "p = 4\n",
    "ham = Hamiltonian(build_ham(g))              # 生成哈密顿量\n",
    "init_state_circ = UN(H, g.nodes)             # 生成均匀叠加态，即对所有量子比特作用H门\n",
    "ansatz = build_ansatz(g, p)                  # 生成ansatz线路\n",
    "circ = init_state_circ + ansatz              # 将初始化线路与ansatz线路组合成一个线路\n",
    "circ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 搭建待训练量子神经网络\n",
    "\n",
    "由于该问题不需要编码层量子线路，我们这里使用`MQAnsatzOnlyLayer`作为待训练的量子神经网络，并采用`Adam`优化器。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "import mindspore as ms\n",
    "ms.context.set_context(mode=ms.context.PYNATIVE_MODE, device_target=\"CPU\")\n",
    "\n",
    "sim = Simulator('projectq', circ.n_qubits)                     # 创建模拟器，backend使用‘projectq’，能模拟5个比特（'circ'线路中包含的比特数）\n",
    "grad_ops = sim.get_expectation_with_grad(ham, circ)            # 获取计算变分量子线路的期望值和梯度的算子\n",
    "net = MQAnsatzOnlyLayer(grad_ops)                              # 生成待训练的神经网络\n",
    "opti = nn.Adam(net.trainable_params(), learning_rate=0.05)     # 设置针对网络中所有可训练参数、学习率为0.05的Adam优化器\n",
    "train_net = nn.TrainOneStepCell(net, opti)                     # 对神经网络进行一步训练"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 训练并展示结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true,
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stderr",
     "text": "train step: 0 , cut: [2.9995914]\ntrain step: 10 , cut: [4.337461]\ntrain step: 20 , cut: [4.6661634]\ntrain step: 30 , cut: [4.7908525]\ntrain step: 40 , cut: [4.8734603]\ntrain step: 50 , cut: [4.9015913]\ntrain step: 60 , cut: [4.9308434]\ntrain step: 70 , cut: [4.93566]\ntrain step: 80 , cut: [4.9383035]\ntrain step: 90 , cut: [4.938753]\ntrain step: 100 , cut: [4.9391074]\ntrain step: 110 , cut: [4.9392223]\ntrain step: 120 , cut: [4.9392357]\ntrain step: 130 , cut: [4.939245]\ntrain step: 140 , cut: [4.9392557]\ntrain step: 150 , cut: [4.939256]\ntrain step: 160 , cut: [4.939257]\ntrain step: 170 , cut: [4.939257]\ntrain step: 180 , cut: [4.939257]\ntrain step: 190 , cut: [4.939257]\n"
    }
   ],
   "source": [
    "for i in range(200):\n",
    "    cut = (len(g.edges) - train_net()) / 2      # 将神经网络训练一步并计算得到的结果（切割边数）。注意：每当'train_net()'运行一次，神经网络就训练了一步\n",
    "    if i%10 == 0:\n",
    "        print(\"train step:\", i, \", cut:\", cut)  # 每训练10步，打印当前训练步数和当前得到的切割边数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上面的训练结果我们发现，该问题哈密顿量的基态能量对应的边切割数趋近于5。\n",
    "\n",
    "### 最优参数\n",
    "\n",
    "前面我们通过训练得到了量子线路中参数的最优值，下面，我们将最优参数提取出来并存储为字典类型，与之前线路中命名的参数一一对应。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "{'g0': 0.22442764, 'b0': -1.1389775, 'g1': 0.45309508, 'b1': -0.9446367, 'g2': 0.5337557, 'b2': -0.6775904, 'g3': 0.58395565, 'b3': -0.3823515}\n"
    }
   ],
   "source": [
    "pr = dict(zip(ansatz.params_name, net.weight.asnumpy())) # 获取线路参数\n",
    "print(pr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 概率图\n",
    "\n",
    "我们将最优参数代入量子线路，通过对量子线路进行1000次采样，画出最终量子态在计算基矢下的概率分布："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "
\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "shots: 1000\nKeys: q4 q3 q2 q1 q0│0.00   0.064       0.128       0.192       0.256        0.32\n────────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n               00100│▒\n                    │\n               00101│▒▒\n                    │\n               01001│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               01010│▒\n                    │\n               01011│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               01100│▒\n                    │\n               01101│▒\n                    │\n               10011│▒\n                    │\n               10100│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               10101│▒\n                    │\n               10110│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n                    │\n               11010│▒▒\n                    │\n               11111│▒\n                    │\n{'00100': 1, '00101': 8, '01001': 224, '01010': 1, '01011': 248, '01100': 1, '01101': 3, '10011': 2, '10100': 245, '10101': 2, '10110': 256, '11010': 7, '11111': 2}",
      "text/html": "
shots: 1000\nKeys: q4 q3 q2 q1 q0│0.00   0.064       0.128       0.192       0.256        0.32\n────────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n               00100│▒\n                    │\n               00101│▒▒\n                    │\n               01001│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               01010│▒\n                    │\n               01011│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               01100│▒\n                    │\n               01101│▒\n                    │\n               10011│▒\n                    │\n               10100│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               10101│▒\n                    │\n               10110│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n                    │\n               11010│▒▒\n                    │\n               11111│▒\n                    │\n{'00100': 1, '00101': 8, '01001': 224, '01010': 1, '01011': 248, '01100': 1, '01101': 3, \n'10011': 2, '10100': 245, '10101': 2, '10110': 256, '11010': 7, '11111': 2}\n
\n"
     },
     "metadata": {},
     "execution_count": 15
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circ.measure_all()                         # 为线路中所有比特添加测量门\n",
    "sim.sampling(circ, pr=pr, shots=1000)      # 运行线路1000次并打印结果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据概率分布图我们发现，该Max-Cut问题具有四个简并解，每个解对应的概率大概为25%。\n",
    "\n",
    "- `01001`：编号为1、2、4的顶点在左边，编号为0、3的顶点在右边。\n",
    "- `10110`：编号为0、3的顶点在左边，编号为1、2、4的顶点在右边。\n",
    "- `01011`：编号为2、4的顶点在左边，编号为0、1、3的顶点在右边。\n",
    "- `10100`：编号为0、1、3的顶点在左边，编号为2、4的顶点在右边。\n",
    "\n",
    "可以发现，以上结果与先前通过穷举法得到的结果相符。\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.7.5 64-bit",
   "language": "python",
   "name": "python37564bitf15e711fd06842a7ae337b5cf8b0b378"
  },
  "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-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}