{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 量子近似优化算法\n", "\n", "[![](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/r1.7/resource/_static/logo_source.png)](https://gitee.com/mindspore/docs/blob/r1.7/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`是创建、操作和研究复杂网络的结构、动态和功能库。可通过如下代码来进行安装。" ] }, { "cell_type": "markdown", "metadata": {}, "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": {}, "source": [ "![max cut](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/r1.7/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": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAA4+klEQVR4nO3deViU5eI+8HtmWIZFAlxABcVCxRVFUPZlvq64DbjkVmappaYtHj2mdY6e0vJXqZmaWWmamgvKKLknu7iAGiYKihuiiIgioGwzzO8Pj++JXEHgneX+XNf3ujozw8zN9UVunud9nueVaLVaLYiIiIyEVOwARERE9YnFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERsVE7ABEpNtuFZch4ng20m8UorBUDRu5CdwcbTCsmxMaWpuLHY+o2iRarVYrdggi0j2pVwuwPDYTcefyAABl6krhObmJFFoAwW0bY3KQK9ydbcUJSVQDLD4iesT6I5cxf3c6StUaPO03hEQCyE1kmBPqhjHeLvWWj+hFcKqTiKp4UHpnUVJR+czXarVASYUG83efBQCWH+kFjviISJB6tQAjfjiCkgrNI8/dOxOHWzu/BAA08BwE+54TqzxvYSrD5one6OxkWx9RiWqMqzqJSLA8NhOl6kdLT114C7f3rQCksid+balagxWxmXUZj6hWsPiICMCD1Ztx5/Ieuaan1WqRv2sRZA0awrKt7xO/XqsFYjLykF9cVsdJiV4Mi4+IAAARx7Mf+3hR8g6UZp9Bo4H/gERm9tT3kACIOPH49yHSFSw+IgIApN8orLJlAQDK8y7jTtxa2AaMgZnDy898j1J1JdJziuoqIlGt4KpOIgIAFJaqH3nsfkYSoFGjNOtPlF1NQ/nNSwCAkvNHccfEDHbBbzzmfSrqOirRC2HxERm54uJiJCYmIvPMNUDqWPVJrRaAFqUXj1d5WH03F2XX0h/7fjZy0zpKSlQ7WHxERqakpASHDx9GdHQ0YmJikJqaCk9PTzT2H4EcLfDX7Xu2AaNhGzBa+N+3fluMe6cPPnY7A/DgRBe3pg3q49sgqjEWH5GBKy8vx7FjxxATE4Po6GgkJyejU6dOUCgU+M9//gMfHx9YWlriVnEZ/BZGA5XP3rj+JFoAQz2cai88UR3gBnYiA6NWq3Hy5ElER0cjOjoahw8fRuvWraFQKBASEoKAgAA0aPD4UdnEX1Jw4GzuU48pexKJBOjT3gErx3i+4HdAVLdYfER6rrKyEn/++acwdRkfHw9nZ2eEhIRAoVAgKCgIdnZ2z/VeTzu55VnMTSTY+rYvT24hncfiI9IzWq0W6enpwtRlbGws7O3toVAooFAoEBwcjCZNmtT4/atzVudDJpJKlB3+Fbu+mYXOnTvX+LOJ6gOLj0jHabVaXLx4USi6mJgYmJubC1OXISEhcHKq3etqNbk7g+mVo5g2bRq2bdsGf3//Ws1DVJtYfEQ6KDs7Wyi56OhoVFRUCEWnUCjQqlWrOs9wKrsAK2IzEZORBwkebE5/6OH9+ELaNsbkYFdhenP//v0YPXo0fv75Z/Tv37/OMxLVBIuPSAfk5uYiNjZWWJBSUFCA4OBgoezatm0LiUQiSrb84jJEnMhGek4RCksrYCM3hVvTBhjq8fg7sB85cgRKpRJfffUVxowZI0Jioqdj8RGJ4Pbt24iLixNGddnZ2QgKChJGdB07doRUqr8nCp45cwZ9+/bF9OnT8d5774kdh6gKFh9RPSgsLERCQoIwdZmZmQlfX19hQUrXrl0hkz35lj/66MqVK+jduzeGDRuGTz/9VLQRK9HfsfiI6sD9+/eRlJQkTF2mpaXBy8tLmLr08vKCmdnT73RgCPLy8tCvXz94enpi+fLlBlfupJ9YfES1oKysDEePHhWmLo8fP44uXboIU5c+Pj6Qy+VixxRFUVERlEol7O3tsX79epibP3pdkKg+sfiIakCtViMlJUWYujxy5Ajc3NyEqUs/Pz9YW1uLHVNnlJaWYvTo0bh79y4iIyOfeHIMUX1g8RE9h8rKSqSmpgpTl4mJiXBxcRGmLgMDA2Frayt2TJ2m0WgwadIknDx5Env27EGjRo3EjkRGisVH9BharRZnzpwRpi7j4uLQpEmTKseANW7cWOyYeker1WLOnDnYvn079u/fjxYtWogdiYwQi48ID34hZ2ZmVjkdxcrKqsoxYM2aNRM7psFYvHgxFi9ejH379qFdu3ZixyEjw+Ijo3XlypUqRafVaqscA+bi4iJ2RIO2bt06zJw5Ezt37kT37t3FjkNGhMVHRiMnJwcxMTFC2RUVFQlTlyEhIWjdujX3mtWzqKgovPnmm9i4cSN69eoldhwyEiw+Mlj5+fnCMWAxMTG4ceMGgoKChKLr0KEDi04HJCQkYMiQIVi2bBmGDx8udhwyAiw+Mhh3795FfHy8UHSXLl2Cv7+/MKpzd3fnBmodlZqaitDQUHz88ceYNGmS2HHIwLH4SG/du3cPiYmJwtTl2bNn0aNHD2FE5+npCVNTU7Fj0nO6cOECevfujTfeeAMff/wxR+NUZ1h8pDdKS0tx5MgRYUR38uRJeHh4CEXn7e3NU0H0XE5ODvr27Yvg4GAsXrxYrw/qJt3F4iOdVVFRgeTkZKHojh49io4dOwpTl76+vrCyshI7JtWygoICDBw4EC1btsSaNWs4aqdax+IjnaHRaHDy5Elh6vLQoUN45ZVXhBFdQEAAXnrpJbFjUj24f/8+Xn31VWg0GkRERMDS0lLsSGRAWHwkmsrKSqSlpVU5HaVZs2ZC0QUFBaFhw4ZixySRVFRUYPz48cjMzERUVBTs7e3FjkQGgsVH9Uar1eLcuXNVNo3b2toKU5fBwcFwdHQUOybpkMrKSsyYMQP79+/Hvn37eHoO1QoWH9WpS5cuVSk6mUxW5XQUntVIz6LVarFw4UKsWrUK+/btQ+vWrcWORHqOxUe16tq1a1WKrqSkRBjRKRQKvPzyy1ymTjXyww8/4N///jd27dqFrl27ih2H9BiLj17IzZs3ERsbK5TdrVu3EBwcLIzq2rVrx6KjWrNt2zZMmjQJW7ZsQXBwsNhxSE+x+Kha7ty5U+V0lKysLAQEBAhF17lzZ+69ojoVHR2NESNGYNWqVVAqlWLHIT3E4qOnKioqQmJiolB0GRkZ8PX1FaYvPTw8YGJiInZMMjIpKSkYOHAgFixYgHHjxokdh/QMi4+qKCkpQVJSkjB1eerUKXh6egojuu7du/N0FNIJGRkZ6NOnD6ZMmYIZM2aIHYf0CIvPyJWXl+PYsWPCiC45ORmdO3cWis7X1xcWFhZixyR6rOzsbPTp0wf9+/fHwoULeT2ZnguLz8io1WqcOHFCKLqkpCS0bdtWmLr09/dHgwYNxI5J9Nzy8/PRv39/tG/fHqtWreLUOz0Ti8/AVVZW4tSpU8LUZUJCApydnaucjmJnZyd2TKIXUlxcjCFDhsDCwgKbNm2CXC4XOxLpMBafgdFqtUhPTxdGdLGxsWjYsGGV01GaNGkidkyiWldeXo7XX38dN27cwI4dO3iuKz0Ri0/PabVaXLx4USi6mJgYmJubCxvGQ0JC0Lx5c7FjEtULjUaDadOmISkpCXv37oWDg4PYkUgHsfj00NWrV6ucjlJRUSGUnEKhQKtWrcSOSCQarVaLefPmYcOGDdi/fz//PdAjWHx6IDc3VxjNRUdHo6CgQDgdRaFQoE2bNlzNRvQ3y5YtwxdffIG9e/eiY8eOYschHcLi00G3b9+ucgzY9evXERgYKIzqOnbsyNNRiJ7Dr7/+ivfffx+RkZHw9fUVOw7pCBafDigsLERCQoIwdZmZmQk/Pz9h6rJr166QyWRixyTSS3v37sVrr72GtWvXIjQ0VOw4pANYfCK4f/8+Dh06JIzoTp8+je7duwtTl15eXjA1NRU7JpHBOHz4MJRKJRYtWoTRo0eLHYdExuKrB2VlZTh69Ciio6MRHR2NEydOoEuXLsLUpY+PD/cdEdWxtLQ09O3bFzNmzMC0adPEjkMiYvHVAbVajZSUFGHq8siRI2jXrp0wdenn5wdra2uxYxIZncuXL6N3794YMWIE5s2bx0VhRorFVws0Gg1SU1OFoktMTISLi4swdRkQEABbW1uxYxIRHtxDsl+/fujevTuWLVvG6+dGiMVXA1qtFmfOnBGmLuPi4uDg4CBMXQYHB6NRo0ZixySiJygsLIRSqUSjRo3wyy+/8I4jRkZviu9WcRkijmcj/UYhCkvVsJGbwM3RBsO6OaGhdd3+0Gq1WmRmZlY5HcXa2rrKMWDNmjWr0wxEVLtKS0sxatQoFBUVITIykpcfjIjOF1/q1QIsj81E3Lk8AECZulJ4Tm4ihRZAcNvGmBzkCndn21r73CtXrghFFx0dDQBVjgFr2bJlrX0WEYlDrVbjnXfewZ9//oldu3ZxpsZI6HTxrT9yGfN3p6NUrcHTUkokgNxEhjmhbhjj7VKjz8rJyalyDFhRUVGVY8BcXV15IZzIAGm1WsyePRsqlQr79++Hs7Oz2JGojuls8T0ovbMoqah89ov/y8JUijmh7Z6r/G7dulXldJTc3FwEBQUJZdehQwcWHZER+frrr7F06VLs27cPbm5uYsehOqSTxZd6tQAjfjiCkgqN8Nit3xah9PIf0JQUQmpmCTNHV9gFjYWZ4ytVvtbCVIbNE73R2cm2yuMFBQWIj48Xiu7y5cvw9/cXis7d3Z2ru4iM3Nq1azFr1izs3LkTXl5eYsehOqKTtypeHpuJUrWmymPquzdh3qITpOaWKL1yCqWXTuBm/lU4TV5T5XWlag1WxGbi67B2SExMFKYuz549C29vb4SEhOD7779Ht27deDoKEVUxduxY2NnZoX///ti4cSN69uwpdiSqAzo34rtVXAa/hdFVFrH8XdmNTNz4+X1AIkWLf2yHRPa3/q5UI/+nd9C1fWthQUqPHj24ZJmInkt8fDyGDh2KFStWYOjQoWLHoVqmcyO+iOPZT3yu8HgUKm5dRemVVACATXflo6UHwNTEBJ9visG7PTlPT0TVFxgYiP3796N///7Iz8/H22+/LXYkqkU6V3zpNwqfONq7n34IZVdPAwBkDRrBvHn7x76uohK4kF9aZxmJyPB16dIF8fHx6N27N27duoXZs2dzwZuB0LmbuhWWqp/4nOPoL9DiH9vROPxjaIpvI0/1OdQFuU94n4q6ikhERuKVV15BYmIiNm/ejA8//BCVlc+/ypx0l84Vn4380UFoZUUZtJUPFrtITMxg8XI3SMzkQKUG6ruPLz4bOReuENGLa9q0KeLi4pCcnIyxY8eiooJ/VOs7nSs+N0cbmJtUjVV+PQPXVoxD3o6FyN+3HDk/vwdt2X1ILV+CmcMrj7yH3EQKt6YN6isyERk4Ozs77N+/H3fu3EFYWBju378vdiR6ATpXfEO7OT3ymKxBQ5jYNUPppT9QnHoAlaXFsHTzh8PI+ZDKrR55vRbAUI9H34eIqKYsLS0RGRkJOzs79O7dG3fu3BE7EtWQzm1nAICJv6TgwNncpx5T9iQSCdCnvQNWjvGs/WBEZPQqKysxffp0HDx4EHv37uUB9XpI50Z8ADAl2BVyk5qdoiJDJSYFPTr9SURUG6RSKRYtWoQRI0bA398fmZmZYkeiatLJ4nN3tsWcUDdYmFYvnrmJBLJTO7H4kw9QUlJSR+mIyNhJJBLMnj0bs2bNQmBgIP744w+xI1E16GTxAcAYbxfMCW0HC1MZnrV1RiJ5cEbnJ/3b48TmJSgtLYW/vz+uXLlSP2GJyChNnDgRS5cuRe/evREfHy92HHpOOnmN769OZRdgRWwmYjLyIAFQ+pj78YW0bYzJwa7CwdRarRZff/01vvrqK2zcuBEKhUKU7ERkHA4ePIiRI0fixx9/xKBBg8SOQ8+g88X3UH5xGSJOZCM9pwiFpRWwkZvCrWkDDPV48h3Yf//9d4wZMwYzZ87EBx98wFMXiKjOJCcnY9CgQfj888/xxhtviB2HnkJviq+mLl++jPDwcLRt2xY//vgjrKwe3f5ARFQb0tPT0adPH0ydOhX/+Mc/xI5DT6Cz1/hqi4uLCw4dOgRTU1P4+vri4sWLYkciIgPl5uaGxMRErF69GrNmzYKBjyv0lsEXHwBYWFhg7dq1GD9+PHx8fLBv3z6xIxGRgXJ2dkZCQgJiYmIwYcIEqNVPPn+YxGHwU51/Fx8fjxEjRmDq1KmYNWsWr/sRUZ0oLi5GeHg4rK2tsXHjRsjlcrEj0X8ZXfEBQHZ2NoYMGQInJyf8/PPPaNCA53oSUe0rKyvD66+/jry8PKhUKtjY2IgdiWAkU51/5+TkhPj4eNjb26NHjx7IyMgQOxIRGSBzc3Ns3LgRbdu2RUhICG7evCl2JIKRFh/w4Afyhx9+wPvvv4+AgABERUWJHYmIDJBMJsOKFSswYMAA+Pv74/Lly2JHMnpGOdX5d4cPH8awYcMwfvx4/Otf/4JUarR/DxBRHVq6dCm+/PJL7NmzBx07dhQ7jtFi8f1XTk4Ohg0bBjs7O6xfvx4vvfSS2JGIyABt2LABH374IVQqFXx8fMSOY5Q4tPmvpk2bIjo6Gi1btoSXlxfOnDkjdiQiMkCjR4/Gzz//jEGDBmHv3r1ixzFKLL6/MDMzw7JlyzB79mwEBQUhIiJC7EhEZID69euHHTt2YOzYsfj111/FjmN0ONX5BCkpKRgyZAhGjRqFzz77DDJZze4PSET0JKdPn0bfvn0xa9YsvPvuu2LHMRosvqfIy8vD8OHDYWZmhl9//RX29vZiRyIiA3P58mX07t0bI0eOxNy5c3moRj3gVOdTNG7cGAcOHEDHjh3h6emJ1NRUsSMRkYFxcXFBQkICoqKi8O6770Kj0YgdyeBxxPecNm7ciPfeew/ffPMNRo0aJXYcIjIwd+/exeDBg+Ho6Ih169bBzMxM7EgGi8VXDampqQgPD4dSqcTChQthYmIidiQiMiClpaUYOXIk7t+/j23btsHa2lrsSAaJU53V4O7ujuTkZJw+fRq9e/dGXl6e2JGIyIDI5XJs3boVTk5O6NmzJ/Lz88WOZJBYfNVkb2+P3bt3w9vbG56enkhJSRE7EhEZEBMTE/z4448ICgpCQEAAsrOzxY5kcFh8NSCTybBgwQIsWrQI/fr1w88//yx2JCIyIBKJBAsXLsS4cePg7+/Pg/RrGa/xvaC0tDSEhYWhV69eWLx4MS9IE1GtWrNmDWbPno2oqCh4enqKHccgcMT3gjp06IBjx44hKysLCoUCN27cEDsSERmQcePGYeXKlQgNDcXBgwfFjmMQWHy1wNbWFjt27EDPnj3h6emJw4cPix2JiAzI4MGDsXXrVowcORLbtm0TO47e41RnLYuKisJbb72Fzz77DBMnThQ7DhEZkJMnT6J///6YN28eJkyYIHYcvcXiqwPnzp2DUqmEn58fli1bBnNzc7EjEZGBOH/+PPr06YMJEyZg1qxZPOKsBjjVWQfatGmDo0eP4vbt2wgMDORyZCKqNa1bt0ZiYiI2btyI6dOno7KyUuxIeofFV0caNGiAiIgIKJVKdO/eHfHx8WJHIiID0axZM8THx+Po0aN44403UFFRIXYkvcKpznqwd+9ejB07FnPmzMHUqVM5NUFEteL+/fsYOnQoZDIZNm/eDEtLS7Ej6QUWXz25ePEiwsLC4O7uju+//x4WFhZiRyIiA1BRUYFx48bhypUriIqKgq2trdiRdB6nOuvJyy+/jKSkJKjVavj5+eHy5ctiRyIiA2Bqaop169bBw8MDQUFByMnJETuSzmPx1SMrKyts2LABr732Gry9vbkZlYhqhVQqxZIlSzBs2DD4+/vjwoULYkfSaZzqFElMTAxGjRqF6dOnY/r06bzuR0S1YuXKlfj000+xe/duuLu7ix1HJ7H4RJSVlYXw8HC4urrip59+gpWVldiRiMgAbNmyBe+++y62bduGgIAAsePoHE51iqhFixZISEiAXC6Ht7c3MjMzxY5ERAZg+PDh2LBhA8LDwxEVFSV2HJ3D4hOZhYUF1qxZg3feeQe+vr7Ys2eP2JGIyAD06tULu3btwoQJE7Bu3Tqx4+gUTnXqkISEBLz66quYMmUKPvroI0il/LuEiF7M2bNn0adPH7z//vv48MMPxY6jE1h8OubatWsYOnQoHB0dsXbtWtjY2IgdiYj0XFZWFvr06QOlUokFCxYY/WI6Dil0TPPmzREbGwsHBwf06NGDd14mohf2cD3BwYMHMXHiRGg0GrEjiYrFp4PMzc2xcuVKTJ8+HQEBAdixY4fYkYhIzzVq1AgHDx7EpUuXMHz4cJSWloodSTSc6tRxR48exdChQzFu3DjMnTuX1/2I6IWUlZVhzJgxyM/Ph0qlMsrLKfwtquN69OiBlJQUxMbGYuDAgSgoKBA7EhHpMXNzc2zatAlt2rSBQqHAzZs3xY5U71h8esDBwQEHDx7EK6+8Ai8vL5w+fVrsSESkx2QyGb777jv069cPAQEBuHLlitiR6hWLT0+Ymppi6dKl+OSTTxASEoKtW7eKHYmI9JhEIsGnn36KyZMnw9/fH2lpaWJHqje8xqeHTpw4gfDwcLz66qtYsGABZDKZ2JGISI+tX78e06dPx44dO+Dt7V3luVvFZYg4no30G4UoLFXDRm4CN0cbDOvmhIbW5iIlfjEsPj1169YtjBgxAlKpFL/++isaNmwodiQi0mO7d+/G2LFjsX79evTp0wepVwuwPDYTcefyAABl6krhtXITKbQAgts2xuQgV7g724oTuoZYfHpMrVbjo48+QkREBCIjI9GlSxexIxGRHjt06BDCw8Mx4pMV2H/TCqVqDZ7WEBIJIDeRYU6oG8Z4u9RbzhfF4jMAmzZtwtSpU7FkyRKMHj1a7DhEpMcWbkvCiiM3IDF5/mlMC1Mp5oS205vyY/EZiFOnTiEsLAwDBw7El19+CVNTU7EjEZGeSb1agBE/HEFJRdWTXbTqctyJXo176QnQlpfAzOEV2P3feJg3ayu8xsJUhs0TvdHZybaeU1cfV3UaiM6dOyM5ORkZGRno1auXUe7NIaIXszw2E6XqR48zu/37KhSd+A0yK1tYtPZG2bV05G76GJr7d4XXlKo1WBGrH7dWY/EZEHt7e/z222/w9/eHp6cnkpOTxY5ERHriVnEZ4s7lPXJNT3OvAMWnfgckUjiMmI/Gg2fCqkMwtOUlKDr+m/A6rRaIychDfnFZPSevPhafgZHJZPjss8/wzTffIDQ0FKtXrxY7EhHpgYjj2Y99vOJWFlCphsymMWRWtgAAM0dXAED5zUtVXisBEHHi8e+jS0zEDkB1IywsDG5ubggLC0NKSgqWLFkCMzMzsWMRkY5Kv1FYZcvCQ5p7dwAAUjO58Jjkv//98LmHStWVSM8pqsOUtYMjPgPWrl07HD16FNeuXUNISAhycnLEjkREOqqwVP3Yx2VWdgCAyvL/3c1B+9//fvhc1fepqIN0tYvFZ+BeeuklREZGom/fvvDy8kJSUpLYkYhIh1y/fh0bNmxA2h8pj33etJEzIDWBpjBPGOGV5ZwDAJg1afXI623kur+inMVnBKRSKT755BN8//33UCqV+O6778BdLETGKS8vD1u3bsWkSZPg5uaGTp06Yfv27WjbxApmskfvzC6zsoN1p/8DtJXI/XUO8nYsxP0z8ZCYWaBBtwFVXis3kcKtaYP6+lZqjPv4jMz58+ehVCrh7e2N5cuXQy6XP/uLiEhvFRQUIC4uDjExMYiOjkZWVhb8/f2hUCgQEhICd3d3SKVS3Coug9/C6Mde56usKMOdmNW4fzYBleUlMHd8BXaKt2DevF2V15mbSJH0T4XOn+HJ4jNCxcXFGDduHK5cuYJt27bB2dlZ7EhEVEuKi4uRmJiI6OhoxMTEID09HT4+PkLRdevWDSYmj1/XOPGXFBw4m/vUY8qeRCIB+rR3wMoxni/4HdQ9Fp+R0mq1+PLLL7F48WJs2rQJQUFBYkciohooKSnB4cOHhaJLTU2Fp6cnQkJCoFAo0L17d5ibP98I7EkntzwPfTq5hcVn5A4cOIAxY8Zg9uzZmDZtGiSSR+f4iUh3lJeX49ixY8LUZXJyMjp16iSM6Hx9fWFpaVnj919/5DLm7z6LkopHpzyfhGd1kt65dOkSwsLC0LFjR6xateqF/tEQUe1Sq9U4efKkMKJLSkpC69athRFdQEAAGjSo3QUlD8ovnXdnIMN2//59TJw4EWlpadi+fTtatXp0mTIR1b3Kykr8+eefwoguPj4eTk5OUCgUUCgUCAwMhL29fZ3nOJVdgBWxmYjJyIMEDzanP/TwfnwhbRtjcrCrXkxv/hWLjwRarRbffPMNPv/8c6xfvx69evUSOxKRwdNqtcjIyEB0dDSio6MRGxsLe3t7YeoyODgYDg4OouXLLy5DxIlspOcUYffvMfDq0hEBnV7GUA/egZ0MSGxsLEaOHIkPPvgAM2bM4HU/olqk1Wpx6dIlYeoyOjoaZmZmwoguJCQETk5OYsd8rF69emHmzJl6/0cxz+qkRwQHB+PYsWMIDw9HSkoKVq9eDWtra7FjEemt7OxsoeRiYmJQVlYmFN2nn36KVq1a6cUfmFZWViguLhY7xgtj8dFjOTs7IyEhAZMnT4a3tzdUKhVcXV3FjkWkF27evImYmBih7G7fvo2QkBCEhITgn//8J9q2basXRfd31tbWLD4ybHK5HD/99BNWrlwJX19frFmzBv379xc7FpHOuX37dpXTUbKzsxEYGAiFQoFJkyahU6dOkEr1/4RIKysr3Lt3T+wYL4zFR08lkUgwadIkdO7cGcOHD8c777yDOXPmGMQ/YqKaKioqQkJCgjB1ef78efj6+iIkJARr1qxB165dn3g6ij7jiI+Mip+fH5KTkzF06FAcP34ca9euxUsvvSR2LKJ6cf/+fSQlJQkjuj///BNeXl5QKBRYunQpvLy8jOJ+lxzxkdFp1qwZYmNj8d5776FHjx6IjIxEu3btnv2FRHqmvLwcR48eFbYYHD9+HO7u7lAoFJg/fz58fHxgYWEhdsx6Z21tjby8PLFjvDAWH1WLmZkZvvvuO6xevRqBgYFYtWoVwsLCxI5F9ELUajWOHz8uTF0ePnwYbm5uCAkJwUcffQR/f3+ubMaD4rt8+bLYMV4Yi49q5M0330THjh2Fqc958+ZBJpOJHYvouVRWViI1NVWYukxMTESLFi2gUCgwZcoUbN68GXZ2j95d3NhxOwMZve7duyMlJQXDhw/HwIEDsWHDBv6yIJ2k1Wpx9uxZYUQXGxuLxo0bQ6FQYOzYsVizZg0aN24sdkydx8UtRACaNGmCAwcOYMaMGfDy8kJkZCQ6deokdiwyclqtFhcuXKiyadzS0hIhISEIDw/Ht99+i2bNmokdU+9wcQvRf5mammLJkiXw9PSEQqHA8uXLMXz4cLFjkZHJysqqUnQajQYKhQK9evXCggULePB6LeCIj+hvxowZgw4dOiA8PBzJycn4/PPPDXIvE+mGGzduVDkdpbCwEMHBwVAoFJgzZw5at26tl6ej6DJDGfHxkGqqdfn5+RgxYgS0Wi02bdqERo0aiR2JDEB+fj7i4uKELQY5OTkICgoSDnbu0KEDD1aoY+fPn0e/fv2QmZkpdpQXwuKjOqHRaDBnzhxs2rQJ27dvh4eHh9iRSM8UFhYiPj5emLq8cOEC/P39hRuwdunShSuJ61lOTg48PDyQk5MjdpQXwuKjOrVlyxZMmTIFixYtwmuvvSZ2HNJh9+7dw6FDh4SpyzNnzqB79+7CiM7LywumpqZixzRqhYWFaN68OYqKisSO8kJYfFTnTp8+jbCwMISGhuKrr77iLy8CAJSVleHIkSPCiO7EiRPo2rWrUHTe3t6Qy+Vix6S/0Gg0MDMzg1qt1uvrpyw+qhd37tzBmDFjUFxcjC1btoh6R2kSR0VFBVJSUoQR3dGjR9G+fXth6tLPzw9WVlZix6RnsLCwQH5+PiwtLcWOUmMsPqo3lZWVmDt3Ln7++WdERESge/fuYkeiOqTRaJCamiosRjl06BBatWoljOgCAwN50Lkeaty4MdLS0tCkSROxo9QYi4/qnUqlwoQJE/D5559j/PjxYsehWqLVapGWliZMXcbFxcHR0VEY0QUFBXGFrwFo1aoVoqOj9XpfJDdZUb1TKpVwc3NDWFgYkpOTsXTpUpibm4sdi6pJq9Xi/PnzwtRlbGwsrK2toVAoMHz4cKxYsQJNmzYVOybVMkM4r5PFR6Jwc3PD0aNHMXbsWAQHB2Pbtm08QkoPXLlyRZi6jImJgUQigUKhQL9+/fD//t//Q8uWLcWOSHXM2tpa7zexs/hINDY2Nti2bRs+//xzeHl5YfPmzfD39xc7Fv3F9evXq5yOcu/ePWHq8l//+hdcXV31enUfVR9HfEQvSCqVYs6cOfDw8EB4eDjmzp2LSZMm8ZepSG7duoXY2FhhRJebmyscA/bBBx+gffv2/P+NkeOIj6iW9OvXD0lJScJ1v++++457uOpBQUEB4uPjhRHd5cuXERAQgJCQEEyYMAGdO3fm6ShUBUd8RLXI1dUVhw8fxltvvYWAgABs27YNLVq0EDuWQbl37x4SExOF63Tp6enw9vaGQqHA999/j27duvGAAXoqQ7hDA4uPdIq1tTU2bdqEr776Cj169MDGjRsREhIidiy9VVpaisOHDwtTl3/88Qe6deuGkJAQfP311+jRowdX1FK1cKqTqA5IJBLMmDEDXbt2xciRIzFz5kx88MEHvLb0HCoqKnDs2DFh6jI5ORkdOnSAQqHA3Llz4evrq9cnbpD4ONVJVId69uyJI0eOIDw8HCkpKfjxxx/5S/tvNBoNTp48KUxdJiUlwdXVFQqFAtOnT0dAQABsbGzEjkkGxNraGrdv3xY7xgth8ZFOc3FxwaFDh/D222/Dx8cHkZGRePnll8WOJZrKykqcPn1amLqMj49H8+bNERISgrfffhsbN26Evb292DHJgFlZWSErK0vsGC+ExUc6z8LCAmvXrsWyZcvg4+ODX375Bb179xY7Vr3QarXIyMiocjqKra0tFAoFRo0ahVWrVvHAb6pXvMZHVE8kEgmmTp2Kzp07Y+TIkZg2bRr++c9/GuR1v0uXLgkjuujoaJiamkKhUGDgwIFYtGgRnJ2dxY5IRozX+IjqWVBQEI4dO4YhQ4bg+PHjWL16NRo0aCB2rBdy7do1oeSio6NRVlYmnI4yb948vPzyywZZ8KSfuJ2BSAROTk6Ii4vD1KlT4e3tjcjISLRp00bsWM/t5s2bVU5Hyc/PR3BwMEJCQjBjxgy4ubmx6EhncaqTSCRyuRw//PADVq1aBX9/f6xevRoDBgx47GtvFZch4ng20m8UorBUDRu5CdwcbTCsmxMaWtf9HrY7d+4gLi5OGNVdvXoVAQEBUCgUmDRpEjp16gSpVFrnOYhqgyFMdfJ+fKT3Dh8+jGHDhmHChAn45JNPhBJJvVqA5bGZiDuXBwAoU1cKXyM3kUILILhtY0wOcoW7s22t5SkqKhJOR4mJiUFGRgZ8fX2FG7B6eHjAxIR/c5J+OnfuHAYMGIBz586JHaXGWHxkEHJycjBs2DDY29vjl19+QdTZO5i/Ox2lag2e9hMukQByExnmhLphjLdLjT67pKQESUlJQtGdOnUKXl5ewnW67t27w8zMrGbfGJGOuXbtGry8vHD9+nWxo9QYi48MRnl5OT788EPsySyGiedwlGme/0fbwlSKOaHtnqv8ysvLcfToUWHqMiUlBZ07d4ZCoYBCoYCPjw8sLCxe4Dsh0l13795FixYtcPfuXbGj1BiLjwxK6tUCDP0uERXa/y0Oyd+zFGXZZ6EuzINEZgqzZm1gF/ImzBpXvWmqhakMmyd6o7OTbZXH1Wo1Tpw4IYzokpKS0LZtW2Hq0t/fX+9XlhI9L7VaDXNzc6jVar1dhMXiI4My8ZcUHDibW2V688oXA2DWrC3MGrdEyeVUaO7mQtagIZq//QMkJv+bgpRIgD7tHbBilAdOnToljOgSEhLQokULYeoyMDAQdnZ2Inx3RLpBLpfjzp07ejuzwSvsZDBuFZch7lzeI9f0HMZ8CblTOwCAuiAX11a+BU1RPspvZcHc0VV4nVYL7PvzGpq0GIaGVmZQKBR47bXX8NNPP6FJkyb1+a0Q6bSHWxpYfEQiizie/djHH5YeAGgr1Q/+QyKFzPrRMy1lMhlmfrcNMwd61ElGIkPwcEtDo0aNxI5SI9w8RAYj/UZhlS0Lf1dZXoL8XYsBADbdlTB5TPGptRLk3Oc/C6Kn0fdN7BzxkcEoLFU/8TnN/bu4uXUuynPOw9q9D2yDxz3lfSrqIh6RwdD3TewsPjIYNvLH/zir795E7uZPoL59DTbeQ2EX/MYz3se0DtIRGQ59H/FxTocMhpujDcxNHv2RvvHLP6C+fQ0ym8bQqstx+/dVuP37KpRdz3jktVp1GdKS9mPPnj0oKyurj9hEekffD6pm8ZHBGNrN6bGPa4of3C1aU5iHopSdwv9V3Lr6yGvNzeUIdDLDggUL4ODggFdffRW//vqrXm/WJaptnOok0hGNrM0R1KbxI/v4Ws767bm+XiIBFG5N8PGYUHw8433k5ubit99+w8aNG4U7wCuVSgwaNAjNmzevo++CSPdxqpNIh0wJdoXcRFajr5WbyDA5+H/7+hwcHPDWW28hKioK169fx8SJE3Ho0CF06tQJPXr0wBdffIH09PTaik6kN/R9xMfiI4Pi7myLOaFusDCt3o/2g7M63R45ruwha2trDBkyBOvXr0dubi7mz5+P7Oxs9OzZE25ubpg1axaOHDmCysonb6cgMhQc8RHpmDHeLpgT2g4WpjI86yhBieTBGZ3Pe0A1AJiamqJnz55YtmwZrl69ivXr18PExATjx49H8+bN8c4772Dv3r1cHEMGS99HfDyrkwzWqewCrIjNRExGHiQASh9zP76Qto0xOdj1iSO96jp//jx27NgBlUqFtLQ09OnTB0qlEqGhobCxsamVzyAS27fffotz587h22+/FTtKjbD4yODlF5ch4kQ20nOKUFhaARu5KdyaNsBQj7q9A3tubi6ioqKgUqkQHx8PPz8/YXFM06ZN6+xzieramjVrEB8fjzVr1ogdpUZYfET1oKioCHv37oVKpcLu3bvh5uYGpVIJpVKJtm3bih2PqFq2bNmCrVu3YuvWrWJHqRFuZyCqBw0aNMCwYcMwbNgwlJeXIy4uDiqVCgqFAjY2NkIJenl5QSrlpXfSbVzcQkTVYmZmhl69emH58uW4evUq1q1bB6lUijfffBNOTk6YNGkS9u3bh/LycrGjEj2Wvi9uYfERiUgqlcLLywvz589HWloaYmNj0apVK8ybNw8ODg4YNWoUtmzZgsLCQrGjEgn0fcTHa3xEOionJ0dYHJOYmAh/f39hcYyjo6PY8ciIpaenY/DgwcjIePS8W33A4iPSA4WFhcLimD179qBdu3bCdcE2bdqIHY+MTHZ2Nry9vZGd/fibP+s6Fh+RnikvL0dsbCxUKhVUKhVsbW2hVCoRFhaGbt26cXEM1bmCggK4uLigoKBA7Cg1wuIj0mOVlZVITk4WSrCoqAiDBw+GUqlEUFAQzMzMxI5IBqiiogIWFhaoqKiA5FnHI+kgFh+RAUlPTxdOjsnIyEC/fv2gVCrRt29fNGjQQOx4ZEDMzc1RWFgIc/O6OwSirrD4iAxUTk4Odu7cCZVKhUOHDiEgIEBYHOPg4CB2PNJz9vb2OH/+PBo2bCh2lGpj8REZgbt372LPnj1QqVTYu3cvOnbsKCyOcXV1ffYbEP1NixYtkJiYiBYtWogdpdpYfERGpqysDDExMVCpVNixYwcaNmwolGC3bt308poN1b927dph27ZtaN++vdhRqo3Lv4iMjLm5Ofr27YuVK1fi2rVr+PHHH6FWqzF69Gi0aNEC7777Ln7//XdUVFSIHZV0mD5vYmfxERkxqVQKb29vfPHFF8jIyMCBAwfg5OSEjz/+GA4ODhgzZgwiIiL0+ngqqhvW1tZ6+3PB4iMiwV/vJn/69Gn4+/vjhx9+QLNmzTBgwAD89NNPuHnzptgxSQfo83mdLD4ieqxmzZrhnXfewb59+5CVlYXRo0dj//79aNOmDQICAvD111/jwoULYsckkejzVCdvS0REz2Rra4uRI0di5MiRKCsrQ3R0NFQqFfz8/NC4cWNhcYyHhwcXxxgJjviIyGiYm5ujX79++P7773H9+nWsWrUK5eXlGDlyJFq2bImpU6fi4MGDXBxj4PR5xMfiI6Iak0ql8PHxwcKFC5GRkYF9+/ahadOm+Oijj+Do6IjXX38d27dv19tfkPRkXNxCREZPIpGgXbt2mD17No4dO4bU1FR4e3tj5cqVaNq0KQYNGoTVq1cjLy9P7KhUC6ysrPT2DxoWHxHVCScnJ0yePBn79+9HVlYWRowYgb1796J169YIDAzEokWLcPHiRbFjUg3p84iPi1uIqM7Z2tpi1KhRGDVqFEpLS4XFMT4+PnBwcEBYWBiUSiW6dOnCxTF6gotbiIiek1wuR2hoKFatWoXr16/ju+++w/379zFs2DC4uLjgvffeQ0xMDNRqtdhR6Sm4uIWIqAZkMhn8/Pzw5Zdf4vz589i9ezeaNGmCmTNnwtHREWPHjkVkZKTe/oI1ZBzxERG9IIlEgg4dOmDOnDlITk7GyZMn0b17d6xYsQJNmzbF4MGDsWbNGi6O0REc8RER1TJnZ2dMmTIFBw4cwJUrVzB8+HDs3r0brq6uCAoKwuLFi3Hp0iWxYxotfV7cwtsSEZFeKS0txe+//w6VSoWdO3eiWbNmwskx7u7uXBxTT86ePYvw8HCcPXtW7CjVxuIjIr2l0Whw+PBhqFQqREZGQqPRCCXo7+8PExMuXK8rV69eha+vL65evSp2lGpj8RGRQdBqtUhLS4NKpYJKpcLly5cxYMAAKJVK9O7dG5aWlmJHNCi3b9+Gq6srbt++LXaUamPxEZFBysrKws6dOxEZGYnk5GQoFAqEhYVhwIABaNiwodjx9F55eTmsra1RXl4udpRqY/ERkcG7ffs2du3aBZVKhd9//x0eHh5QKpUYPHgwXFxcxI6nt0xNTXHv3j2YmZmJHaVaWHxEZFRKSkqExTFRUVFo3ry5cF2wc+fOXBxTDXZ2drh48SLs7OzEjlItLD4iMloajQZJSUnC4hitViuUoJ+fHxfHPIOzszOSkpLg7OwsdpRqYfEREeHB4pjTp08Li2OysrIwcOBAKJVK9OrVCxYWFmJH1Dlubm5QqVRwc3MTO0q1cAM7EREenBzTqVMnfPLJJzh+/DhSUlLQpUsXLFmyBI6OjggPD8e6deuQn58vdlSdoa+b2Fl8RESP0bJlS0ybNg3R0dG4ePEilEolVCoVXn75ZSgUCixduhRXrlwRO6ao9PWefCw+IqJnaNiwoXA3+ZycHLz//vv4448/4OnpCQ8PD/znP//BqVOnYGxXjvR1xMcrt0RE1WBpaYlBgwZh0KBBUKvVSEpKQmRkJAYPHgypVCosjvH19YVMJhM7bp3S1zs0cMRHRFRDJiYmCAwMxOLFi3Hx4kVs374dNjY2mDZtGpo2bYq33noLUVFRKCkpETtqndDXOzSw+IiIaoFEIoG7uzv+/e9/4+TJkzh27Bg6d+6MRYsWwdHREUOGDMEvv/yil0d8PYm+TnWy+IiI6sBf7yZ/4cIFDBo0CNu3b4eLiwv+7//+D99++61eHvD8V1zcQkREj9WoUSPhbvI3btzA1KlTcfz4cXTt2hWenp747LPPcPr0ab1bHKOvIz4ubiEiqkeWlpbCAhi1Wo3ExESoVCoMGDAAJiYmwnM+Pj46vzjGysoKeXl5YseoNo74iIhEYmJiguDgYCxZsgSXLl1CREQErK2t8e6776JZs2YYP348fvvtN5SWlood9bH0dcTH4iMi0gESiQRdunTB3Llz8ccff+DIkSPo2LEjvvrqKzg6OmLYsGHYsGED7ty5I3ZUAYuPiIhqTatWrfD+++8jNjYWmZmZCA0NxZYtW9CyZUv06tULy5cvR3Z2tqgZubiFiIjqRKNGjTBu3Djs2LEDOTk5mDx5Mo4dOwZ3d3d4eXlh/vz5SEtLq/fFMfo64uPiFiIiPWJlZYWwsDCEhYVBrVYjISEBKpUKoaGhMDMzExbHeHt71/niGH0d8fG2REREBkCr1eKPP/4Q7i2Ym5uLQYMGISwsDAqFAnK5vFY/71ZxGZbvPo51O39HUK9+sJGbwM3RBsO6OaGhtXmtflZtY/ERERmgCxcuYMeOHVCpVDh16hR69+4NpVKJ0NBQ2Nra1vh9U68WYHlsJuLO5UGr1aJc878KkZtIoQUQ3LYxJge5wt255p9Tl1h8REQG7ubNm/jtt9+gUqkQGxsLb29vKJVKDB48GM2bN3/u91l/5DLm705HqVqDpzWHRALITWSYE+qGMd4uL/4N1DIWHxGRESkuLsb+/fuhUqmwa9cuvPLKK8J1wXbt2kEikTz26x6U3lmUVFQ+92dZmEoxJ7SdzpUfi4+IyEhVVFQIi2NUKhUsLCyEEuzRowek0gcL/1OvFmDED0dQUqERvrYweQeKTx1Axa0sQFuJl/xGwjZg9COfYWEqw+aJ3ujsZFtf39YzcTsDEZGRMjU1rXI3+Y0bN8LMzAwTJ05E8+bN8fbbb2PPnj34NvocStWaKl9bfiMTUrk1ZA0aPfUzStUarIjNrMtvo9o44iMiokdkZmZix44d2LZrP651ewcSE7PHvu7mts9Qcv7IE0d8AGBuIkXSPxU6s9qTIz4iInqEq6srpk+fjtf/vQLm5i9WWBIAESfEPWXmr1h8RET0ROk3CqtsWaiJUnUl0nOKainRi2PxERHRExWWqmvpfSpq5X1qA4uPiIieyEZeOydb2shNa+V9agPP6iQioidyc7SBuckNlKmr7t8rSt2HsqtnUJ57AQBw//wRqO/ehGUbb1i28anyWrmJFG5NG9Rb5mfhiI+IiJ5oaDenxz5edvUM7p0+CE3hgzuwV9y8hHunD6I89+Ijr9UCGOrx+PcRA7czEBHRU038JQUHzuY+9ZiyJ5FIgD7tHbByjGftB6shjviIiOippgS7Qm5Ss1scyU1kmBzsWsuJXgyLj4iInsrd2RZzQt1gYVq9ynhwVqebTh1XBnBxCxERPYeHB03z7gxERGRUTmUXYEVsJmIy8iDBg83pDz28H19I28aYHOyqcyO9h1h8RERUbfnFZYg4kY30nCIUllbARm4Kt6YNMNSDd2AnIiLSKVzcQkRERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERoXFR0RERuX/AyOl0kFOs5cVAAAAAElFTkSuQmCC", "text/plain": [ "
" ] }, "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条边构成的图结构。\n", "\n", "接下来我们用穷举法来看看所有情况的切割边数。" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "tags": [] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "one size: [0] cut= 3\n", "one size: [1] cut= 2\n", "one size: [1, 0] cut= 3\n", "one size: [2] cut= 3\n", "one size: [2, 0] cut= 4\n", "one size: [2, 1] cut= 3\n", "one size: [3] cut= 2\n", "one size: [3, 0] cut= 5\n", "one size: [3, 1] cut= 4\n", "one size: [3, 2] cut= 3\n", "one size: [4] cut= 2\n", "one size: [4, 0] cut= 3\n", "one size: [4, 1] cut= 4\n", "one size: [4, 2] cut= 5\n", "one 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个节点的所有情况" ] }, { "cell_type": "markdown", "metadata": {}, "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://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/r1.7/docs/mindquantum/docs/source_zh_cn/images/QAOA_Flowchart.png)" ] }, { "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$是可训练的参数。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "搭建$U_C(\\gamma)$对应的量子线路：" ] }, { "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "线路展示：" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": "\n\n\nq0:\n \n\nq1:\n \n\nq2:\n \n\nq3:\n \n\nq4:\n \n\n\n\n\n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\nZZ\n \n\ngamma\n \n\n\n", "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circuit = build_hc(g, 'gamma')\n", "circuit.svg()" ] }, { "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "线路展示：" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": "\n\n\nq0:\n \n\nq1:\n \n\nq2:\n \n\nq3:\n \n\nq4:\n \n\n\n\n\n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n", "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circuit = build_hb(g, 'beta')\n", "circuit.svg()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "实现了一层酉变换$U_B(\\beta) U_C(\\gamma)$的ansatz线路如下所示：" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": "\n\n\nq0:\n \n\nq1:\n \n\nq2:\n \n\nq3:\n \n\nq4:\n \n\n\n\n\n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\nZZ\n \n\ngamma\n \n\n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n\n\nRX\n \n\nbeta\n \n\n\n", "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circuit = build_hc(g, 'gamma') + build_hb(g, 'beta')\n", "circuit.svg()" ] }, { "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": [ { "data": { "image/svg+xml": "\n\n\nq0:\n \n\nq1:\n \n\nq2:\n \n\nq3:\n \n\nq4:\n \n\n\n\n\n\n\n\n\nH\n \n\n\n\n\nH\n \n\n\n\n\nH\n \n\n\n\n\nH\n \n\n\n\n\nH\n \n\n\n\n\nZZ\n \n\ng0\n \n\n\n\n\nZZ\n \n\ng0\n \n\n\n\n\n\n\n\nZZ\n \n\ng0\n \n\n\n\n\n\n\n\nZZ\n \n\ng0\n \n\n\n\n\nZZ\n \n\ng0\n \n\n\n\n\nZZ\n \n\ng0\n \n\n\n\n\n\nRX\n \n\nb0\n \n\n\n\n\nRX\n \n\nb0\n \n\n\n\n\nRX\n \n\nb0\n \n\n\n\n\nRX\n \n\nb0\n \n\n\n\n\nRX\n \n\nb0\n \n\n\n\n\n\nZZ\n \n\ng1\n \n\n\n\n\nZZ\n \n\ng1\n \n\n\n\n\n\n\n\nZZ\n \n\ng1\n \n\n\n\n\n\n\n\nZZ\n \n\ng1\n \n\n\n\n\nZZ\n \n\ng1\n \n\n\n\n\nZZ\n \n\ng1\n \n\n\n\n\n\nRX\n \n\nb1\n \n\n\n\n\nRX\n \n\nb1\n \n\n\n\n\nRX\n \n\nb1\n \n\n\n\n\nRX\n \n\nb1\n \n\n\n\n\nRX\n \n\nb1\n \n\n\n\n\n\nZZ\n \n\ng2\n \n\n\n\n\nZZ\n \n\ng2\n \n\n\n\n\n\n\n\nZZ\n \n\ng2\n \n\n\n\n\n\n\n\nZZ\n \n\ng2\n \n\n\n\n\nZZ\n \n\ng2\n \n\n\n\n\nZZ\n \n\ng2\n \n\n\n\n\n\nRX\n \n\nb2\n \n\n\n\n\nRX\n \n\nb2\n \n\n\n\n\nRX\n \n\nb2\n \n\n\n\n\nRX\n \n\nb2\n \n\n\n\n\nRX\n \n\nb2\n \n\n\n\n\n\nZZ\n \n\ng3\n \n\n\n\n\nZZ\n \n\ng3\n \n\n\n\n\n\n\n\nZZ\n \n\ng3\n \n\n\n\n\n\n\n\nZZ\n \n\ng3\n \n\n\n\n\nZZ\n \n\ng3\n \n\n\n\n\nZZ\n \n\ng3\n \n\n\n\n\n\nRX\n \n\nb3\n \n\n\n\n\nRX\n \n\nb3\n \n\n\n\n\nRX\n \n\nb3\n \n\n\n\n\nRX\n \n\nb3\n \n\n\n\n\nRX\n \n\nb3\n \n\n\n", "text/plain": [ "" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "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.svg()" ] }, { "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": [ { "name": "stdout", "output_type": "stream", "text": [ "train step: 0 , cut: [3.0001478]\n", "train step: 10 , cut: [4.1718774]\n", "train step: 20 , cut: [4.6871986]\n", "train step: 30 , cut: [4.7258005]\n", "train step: 40 , cut: [4.804503]\n", "train step: 50 , cut: [4.8477592]\n", "train step: 60 , cut: [4.8705964]\n", "train step: 70 , cut: [4.9060946]\n", "train step: 80 , cut: [4.933446]\n", "train step: 90 , cut: [4.9356637]\n", "train step: 100 , cut: [4.938308]\n", "train step: 110 , cut: [4.9390197]\n", "train step: 120 , cut: [4.939068]\n", "train step: 130 , cut: [4.9392157]\n", "train step: 140 , cut: [4.939249]\n", "train step: 150 , cut: [4.939247]\n", "train step: 160 , cut: [4.939255]\n", "train step: 170 , cut: [4.939257]\n", "train step: 180 , cut: [4.939257]\n", "train 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": [ { "name": "stdout", "output_type": "stream", "text": [ "{'g0': 0.22448167, 'b0': -1.1390871, 'g1': 0.45314747, 'b1': -0.94472605, 'g2': 0.5338268, 'b2': -0.67756957, 'g3': 0.58400834, 'b3': -0.38243017}\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": [ { "data": { "image/svg+xml": "\n\n\nShots:\n 1000\n \n\nKeys: q0 q1 q2 q3 q4\n \n\n\n\n0.0\n \n\n\n\n0.05\n \n\n\n\n0.1\n \n\n\n\n0.151\n \n\n\n\n0.201\n \n\n\n\n0.251\n \n\n\n00000\n \n\n\n\n4\n \n\n00001\n \n\n\n\n2\n \n\n00011\n \n\n\n\n1\n \n\n00100\n \n\n\n\n1\n \n\n00101\n \n\n\n\n6\n \n\n01001\n \n\n\n\n251\n \n\n01010\n \n\n\n\n3\n \n\n01011\n \n\n\n\n220\n \n\n01100\n \n\n\n\n1\n \n\n01101\n \n\n\n\n3\n \n\n01110\n \n\n\n\n1\n \n\n10010\n \n\n\n\n1\n \n\n10011\n \n\n\n\n1\n \n\n10100\n \n\n\n\n248\n \n\n10101\n \n\n\n\n2\n \n\n10110\n \n\n\n\n247\n \n\n11000\n \n\n\n\n1\n \n\n11001\n \n\n\n\n1\n \n\n11010\n \n\n\n\n5\n \n\n11111\n \n\n\n\n1\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\nprobability\n \n", "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circ.measure_all() # 为线路中所有比特添加测量门\n", "sim.sampling(circ, pr=pr, shots=1000).svg() # 运行线路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": "d62cf896b9ca57de08105ce3983377439eacacf6f6599f9150bf400edf4fa4b8" }, "kernelspec": { "display_name": "MindSpore", "language": "python", "name": "mindspore" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" } }, "nbformat": 4, "nbformat_minor": 4 }