{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Quantum Approximate Optimization Algorithm\n", "\n", "[![Download Notebook](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/resource/_static/logo_notebook_en.svg)](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/master/mindquantum/en/case_library/mindspore_quantum_approximate_optimization_algorithm.ipynb) \n", "[![Download Code](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/resource/_static/logo_download_code_en.svg)](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/master/mindquantum/en/case_library/mindspore_quantum_approximate_optimization_algorithm.py) \n", "[![View source on Gitee](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/resource/_static/logo_source_en.svg)](https://gitee.com/mindspore/docs/blob/master/docs/mindquantum/docs/source_en/case_library/quantum_approximate_optimization_algorithm.ipynb)\n", "\n", "## Overview\n", "\n", "Quantum approximate optimization algorithm (QAOA) is a quantum algorithm that uses quantum computers to solve combination optimization problems. It was first proposed by Farhi et al. in 2014. In this tutorial, we will use QAOA to solve the Max-Cut problem and get familiar with the construction and training of quantum circuits in MindSpore Quantum.\n", "\n", "## Environment Preparation\n", "\n", "This tutorial requires the following library:\n", "\n", "- networkx\n", "\n", "> `NetworkX` is a library for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. You can install it with:\n", "\n", "```bash\n", "pip3 install networkx\n", "```\n", "\n", "## Max-Cut Problem Description\n", "\n", "The Max-Cut problem is an NP-complete problem in the graph theory. It needs to divide vertices of a graph into two parts and make the most edges be cut. As shown in the following figure (a), a graph consists of five vertices, and the interconnected edges are ```(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), and (0, 4)```. To maximize the number of edges to be cut, we divide 1, 2, and 4 into one group, and 0 and 3 into another group, as shown in the figure (b). Therefore, five edges are to be cut. When the number of vertices in a graph increases, it is difficult to find an effective typical algorithm to solve the Max-Cut problem. The following describes how to transform the Max-Cut problem into a Hamiltonian ground state capability solution problem.\n", "\n", "![max cut](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/docs/mindquantum/docs/source_en/images/Max_Cut.png)\n", "\n", "## Max-Cut Problem Quantization\n", "\n", "Assign each vertex a quantum bit. If the vertex is allocated to the left side, its quantum bit is set to the $\\left|0\\right>$ state. If the vertex is on the right side, its quantum bit is set to the $\\left|1\\right>$ state. When two vertices are in different sets, the bits on the two vertices are in different quantum states. For the vertex 0 and the vertex 1, when their connection line is cut, quantum states corresponding to bits on the two vertices may be $|01\\rangle$ (vertax 1: left, vertax 0: right) or $|10\\rangle$ (vertax 1: right, vertax 0: left). If they are partitioned to the same side, the corresponding quantum state is $|00\\rangle$ or $|11\\rangle$. So we just need to find a Hamiltonian $H$ that makes the expectation value of the Hamiltonian to -1 when there are connected two vertices in different quantum states, i.e.\n", "\n", "$$\n", "\\langle 01|H|01\\rangle=-1,\\quad \\langle 10|H|10\\rangle=-1\n", "$$\n", "\n", "When vertices are in the same quantum state, the expected value of Hamiltonian quantity is 0, i.e\n", "\n", "$$\n", "\\langle 00|H|00\\rangle=0,\\quad \\langle 11|H|11\\rangle=0\n", "$$\n", "\n", "Subsequently the maximum number of cut edges, and the corresponding grouping case at that point, can be found by simply minimizing the expected value of the Hamiltonian quantity. The reason why the expected value at different quantum states is set to -1 is that in the training of the quantum neural network, the gradient of the parameters in Ansatz keeps decreasing, and also the measured value keeps decreasing. The training method is aimed at finding the minimum value, and here we use it to find the ground state energy of the Hamiltonian quantity. At this point, we choose the Hamiltonian $H=(Z_1Z_0-1)/2$, where $Z$ is the Pauli $Z$ operator. We can see that:\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", "Thus when the vertices are partitioned into different sets:\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", "And when the vertices are partitioned into the same set, it is not difficult to verify that:\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", "Therefore, we just write the above Hamiltonian for each edge in the graph and then sum up all the edges to write the Hamiltonian $H$ corresponding to the graph. Using a quantum computer to find the ground state energy and ground state of $H$, we can get the Max-Cut cutting scheme and the maximum number of cutting edges of the graph. We write down the set of all edges as $C$ and the number of all edge strips as $c$, then the Hamiltonian quantity can be written as:\n", "\n", "$$\n", "H=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2\n", "$$\n", "\n", "## Importing Dependencies\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from mindquantum.core.circuit import Circuit, UN\n", "from mindquantum.core.gates import H, Rzz, RX\n", "from mindquantum.core.operators import Hamiltonian, 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": [ "## Building a Graph to Be Solved\n", "\n", "Use `add_path` to add edges to a graph. Then, the graph structure is drawn." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAApQAAAHzCAYAAACe1o1DAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAA9hAAAPYQGoP6dpAABmtElEQVR4nO3deUBU5f4G8GeGYZHNBUQFxQ1FRRAX3EUJxJ1lMHHfUNCsq5aV2TXrerPVslu3YjT3XRkWF5RFRcwFrFxC3BVwJcCNAUGY+f1Rzq+67gy8szyfv5RhznmwxIfvec97JBqNRgMiIiIiohckFR2AiIiIiAwbCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVUJCyURERERVQkLJRERERFVCQslEREREVWJTHQAIiJTpCqrwOVCFcor1LCQSdHMwQY2lvyWTESGid+9iIhqyLmb97DuSC72nslHblEJNH96TQLAtZ41/NydMKabK1o1sBMVk4jouUk0Go3m6Z9GREQvKq+oBPNiTyL9fAHMpBJUqh//bffh633cHLEo1BNN6lnXYFIiohfDQklEVI02ZuZiQUIWKtSaJxbJvzOTSiCTSvBBkAdG+rhWY0IioqpjoSQiqibf7D2Hz5POVvk4cwJb41W/VjpIRERUPXiXNxFRNdiYmauTMgkAnyedxabMXJ0ci4ioOnBCSUSkY3lFJQj4Mg1lFeq/fLzsxnncObgJD/Ivo7L0DjTl9yG1tIF5/aaw8egH2w4DIJFIHnlMS5kUKbP7ck0lEeklTiiJiHRsXuxJVDxiveSDgjyUnj2EitvXoSkrATRqqO/fQ1neryja9Q1u7fnhscesUGswL/ZkdcYmInph3DaIiEiHzt28h/TzBY98zbxuQ9QbMANWzTpAZueIytK7uJ22BqpfUwEAxSeSUc9/yiPfW6nWIP18Ac7n34ObE7cUIiL9wgklEZEOrTuSCzPpYy5bu7SFXcdBMK/rDInMAjI7R9h3DdG+LjF78s/4ZlIJ1h7mWkoi0j8slEREOrT3TP4zbQ+k0ahRcfc33M2I037M3ifkie+pVGuw92x+FRMSEekeL3kTEelIcVkFcotKnvp511e/gfJrZ/7/A1Iz1O036S/TysfJLSyBqqyCj2kkIr3CCSURkY7kFKrwQttmqCtxa88y3Dm89amfqgFwuVD1ImchIqo2/BGXiEhHyv+2TdDjNBq/GBp1JSpVt1B8PBl3DqwDANzevxa2Xv1hZl1bJ+chIqopnFASEemIhezZv6VKpGaQ2TmiTu9RkFja/P5BdQUqbt/Q6XmIiGoCJ5RERDrSzMEGEuCxl72LUhSwbOwBy4ZuMLOrB3VpMYpPJEFT9sclbIkUstoNnngOyR/nISLSJyyUREQ6Uqa6C3uzctyptHjk6yVnD+Pe0YTHvr92j5dhZlPniedwdbDmDTlEpHd43YSIqAo0Gg3S09MxduxYODs742pmEqB59BpHu46DYOnqCTPbeoCZDDCTwcy+Pmq17oH6wxegju+4J57LTCqBX2un6vgyiIiqhM/yJiJ6AYWFhVi9ejUUCgVOnz4NNzc3REZGos/QERi5+tdqO2/KbF8+KYeI9A6vmxARPaOH00iFQoGtW7dCrVZDLpfjv//9L/r16wep9PeLPn3cbuDgxcJn2uD8WZlJJejZwoFlkoj0EieURERP8bhp5MSJE1G/fv3/+fy8ohIEfJmGMp1t76OBpcwMKbP7okk9ax0dk4hIdzihJCJ6BI1Gg/3792unkRqNBmFhYfj222/Rr18/SCSPfl43ADSpZ40PgjwwV3lSR2kk6Gl5hWWSiPQWCyUR0Z8UFBRop5FnzpxBq1at8OGHH2LChAmPnEY+zkgfVxQUl+HzpLNVzuQtzcXK+a/A9cEVvP/++08ss0REIrBQEpHJeziNjI6ORkxMDABALpfj+++/R9++fV+4wL3q1wqOtpZYkJCFCrXmudZUmkklkEkl+FeQB8J9huBjuzt45513UFxcjM8//5ylkoj0CtdQEpHJKigowKpVq6BQKHD27Fm0bt0akZGRGD9+/HNNI58mr6gE82JPIv18AcykkicWy4ev93FzxKJQz79c5v7mm2/w2muvISoqCt9++632JiAiItFYKInIpGg0GqSlpUGhUGinkWFhYYiMjKzSNPJZnLt5D+uO5GLv2XzkFpb85Yk6Evy+ablfayeM7e762Lu5V6xYgSlTpmD06NFYsWIFZDJeaCIi8VgoicgkFBQUYOXKlVi6dCnOnj0Ld3d37TTS0dGxxvOoyipwuVCF8go1LGRSNHOweeYn4GzatAljx45FUFAQNmzYAAuLRz+Zh4ioprBQEpHR0mg02LdvHxQKBZRKJQBg+PDhiIyMhK+vr0GvQ9y2bRuGDx8Of39/xMTEoFatWqIjEZEJY6EkIqPz22+/addGnjt3Tvg0srqkpKQgODgYXbt2RUJCAuzsuOk5EYnBQklERuHhNDI6OhpKpRISiQTDhw9HVFQU+vTpY9DTyCc5cOAAhgwZgrZt2yIxMRF169YVHYmITBALJREZtPz8fKxatQpLly7FuXPn0KZNG+000sHBQXS8GvHTTz8hMDAQTZo0QVJSEpycnERHIiITw0JJRAZHrVb/ZW2kVCrVro005mnkk/z6668ICAhA3bp1kZKSAhcXF9GRiMiEsFASkcHIz8/X3ql9/vx5tGnTBlFRURg3bpzJTCOf5Ny5c/D394dMJkNqaiqaN28uOhIRmQgWSiLSa2q1Gnv37oVCoUBsbCykUilefvllREZGonfv3iY5jXySnJwc+Pv74/79+0hNTYW7u7voSERkAlgoiUgv/X0a2bZtW+00sl69eqLj6bXr168jICAABQUFSE5OhpeXl+hIRGTkWCiJSG88nEZGR0cjLi4OUqkUI0aMQGRkJHr16sVp5HMoKChAYGAgLl++jN27d8PHx0d0JCIyYiyURCTczZs3tdPICxcucBqpI7dv38bgwYPx66+/Yvv27fD19RUdiYiMFAslEQmhVquxZ88eKBQKTiOrUXFxMYKDg3Ho0CHExcUhMDBQdCQiMkIslERUo27evIkVK1Zg6dKluHjxItq1a4eoqCiMHTuW08hqUlpaipdffhnJycnYtGkTQkJCREciIiPDQklE1U6tViM1NVU7jZTJZNppZM+ePTmNrAHl5eUYO3YslEol1qxZg1GjRomORERGhIWSiKrNjRs3tGsjL168CA8PD+00ko8IrHkVFRWYMmUKVq9eDYVCgSlTpoiORERGQiY6ABEZF7VajZSUFCgUCsTHx0MmkyE8PBxr1qxBjx49OI0USCaTYfny5bC2tsbUqVOhUqkwc+ZM0bGIyAiwUBKRTty4cUO7NvLSpUto3749vvjiC04j9YxUKsV///tf2NraYtasWVCpVJg3b57oWERk4FgoieiFPZxGRkdHIyEhAebm5ggPD8e6devQvXt3TiP1lEQiwSeffAJbW1u8++67KC4uxocffsj/XkT0wlgoiei53bhxA8uXL8eyZcu008gvv/wSY8eORZ06dUTHo2cgkUjw3nvvwcbGBnPmzEFxcTGWLFkCqVQqOhoRGSAWSiJ6Jmq1GsnJyVAoFJxGGpE33ngDtra2mD59OlQqFRQKBczMzETHIiIDw0JJRE90/fp17drIy5cvw9PTE0uWLMGYMWM4jTQSUVFRsLa2xsSJE1FSUoLVq1fD3NxcdCwiMiAslET0P9RqNZKSkrTTSAsLC4wcORKRkZHo1q0bp5FGaNy4cbC2tsaoUaNQUlKCTZs2wcrKSnQsIjIQ3IeSiLSuXbumnUbm5OTA09MTUVFRnEaakMTERMjlcvTp0wexsbGwsbERHYmIDAALJZGJq6ys1E4jt23bBktLS+00smvXrpxGmqB9+/Zh6NCh6NixI7Zv347atWuLjkREeo6FkshEXbt2TXundk5ODry8vLTTSBYIOnz4MAYOHIhWrVph165dcHBwEB2JiPQYCyWRCXncNDIqKgo+Pj6cRtJf/PLLLwgMDETDhg2RnJyMhg0bio5ERHqKhZLIBPx9GtmhQwdERUVh9OjRnEbSE2VnZ8Pf3x+2trZITU1FkyZNREciIj3EQklkpCorK7F7924oFAps374dlpaWGDVqFCIjIzmNpOdy4cIF+Pv7AwBSUlLg5uYmOBER6RsWSiIjc/XqVe00Mjc3VzuNHDNmDOzt7UXHIwOVl5eHgIAA3Lt3DykpKWjXrp3oSESkR1goiYxAZWUldu3apZ1G1qpVSzuN7NKlC6eRpBM3b95E//79cf36dSQlJaFjx46iIxGRnmChJDJgV65c0U4j8/Ly4O3trV0byWkkVYeioiIMHDgQZ8+eRWJiInr06CE6EhHpARZKIgPzcBoZHR2NHTt2aKeRUVFR6Ny5M6eRVO3u3r2LoUOH4ueff8a2bdvg5+cnOhIRCcZCSWQgrly5gh9++AE//PAD8vLy0LFjR0RFRWHUqFGcRlKNKykpQWhoKPbv34+YmBgMHjxYdCQiEoiFkkiPVVZWIjExEQqFQjuNHD16tHZtJJFIZWVlCA8Px86dO7F+/XoMHz5cdCQiEoSFkkgP5eXladdGXrlyBZ06ddJOI+3s7ETHI9J68OABJkyYgE2bNmHFihUYP3686EhEJIBMdAAi+l1FRYV2Grlz505YW1trp5GdO3cWHY/okczNzbFmzRpYW1tjwoQJUKlUmD59uuhYRFTDWCiJBMvLy9Oujbxy5Qo6d+6M7777jtNIMhhmZmZQKBSwsbHBK6+8ApVKhTlz5oiORUQ1iIWSSICH08jo6GgkJiZyGkkGTyqVYsmSJbC1tcWbb76J4uJiLFiwgLsOEJkIFkqiGpSbm6udRl69ehVdunTB999/j5EjR3IaSQZPIpHgww8/hK2tLebNm4fi4mJ89tlnLJVEJoCFkqiaVVRUYOfOnVAoFNpp5JgxYxAZGYlOnTqJjkekc++88w5sbGwwc+ZMqFQq/Pe//4VUKhUdi4iqEQslUTXJzc3FsmXL8MMPP+DatWvo0qULoqOjMXLkSNja2oqOR1St/vGPf8DW1hZTpkyBSqXC8uXLIZPxnxwiY8W/3UQ6VFFRgR07dminkba2thgzZgymTp3KaSSZnMmTJ8Pa2hpjx45FSUkJ1q9fDwsLC9GxiKgacB9KIh3IycnRro28du0afHx8EBUVhfDwcE4jyeTFx8djxIgRCAgIwNatW1GrVi3RkYhIx1goiV7Qw2lkdHQ0du3aBVtbW4wdOxZTp05Fx44dRccj0ivJyckIDg5G9+7dER8fz5vQiIwMCyXRc8rJycGyZcuwfPlyXLt2DV27dkVkZCSnkURPkZ6ejiFDhsDDwwOJiYmoU6eO6EhEpCMslETP4MGDB9q1kX+eRkZGRsLb21t0PCKDkZmZiYEDB8LV1RVJSUmoX7++6EhEpAMslERPcPnyZe008vr16+jatat2baSNjY3oeEQG6eTJkwgICICDgwNSUlLg7OwsOhIRVRELJdHfPHjwANu3b4dCocDu3bthZ2enXRvJaSSRbpw9exb+/v6wsLBAamoqmjVrJjoSEVUBCyXRH/4+jezWrRuioqIwYsQITiOJqsHly5fh7++P8vJypKamonXr1qIjEdELYqEkk/ZwGhkdHY2kpCTY2dlh3LhxmDp1Kjp06CA6HpHRu3btGgICAlBUVITk5GR4enqKjkREL4CFkkzSpUuXtNPIGzduoHv37oiMjOQ0kkiA3377DYGBgcjNzcXu3bvRpUsX0ZGI6DmxUJLJePDgAbZt2waFQoGkpCTY29trp5FeXl6i4xGZtNu3b2PQoEHIysrCzp070bt3b9GRiOg5sFCS0bt06RKWLl2K5cuX4+bNm+jRo4d2GmltbS06HhH9obi4GEFBQTh8+DDi4+PRv39/0ZGI6BmxUJJRevDgARISErTTyNq1a2PcuHGIjIzkGi0iPVZaWorhw4cjJSUFW7ZsQVBQkOhIRPQMWCjJqFy8eFG7NvLhNDIqKgovv/wyp5FEBqK8vByjR49GXFwc1q5di5EjR4qORERPIRMdgKiqHjx4gPj4eCgUCiQnJ6N27doYP348pk6dymkkkQGysLDAxo0bMXnyZIwePRolJSWYPHmy6FhE9AQslGSwLly4gGXLlmHFihW4efMmevbsiZUrV3IaSWQEZDIZVq5cCRsbG0RERKC4uBj/+Mc/RMciosdgoSSDUl5ejoSEBERHRyMlJQV16tTRTiPbt28vOh4R6ZBUKsW3334LGxsbzJw5EyqVCu+8847oWET0CCyUZBAuXLiApUuXYsWKFcjPz0evXr2watUqDB8+nNNIIiMmkUjw2Wefwc7ODvPmzUNxcTH+/e9/QyKRiI5GRH/CQkl6q7y8XLs28s/TyMjISHh4eIiOR0Q1RCKRYMGCBbCxscGbb76J4uJiLFmyhKWSSI+wUJLeOX/+vHZtZH5+Pnr37o3Vq1dj+PDhqFWrluh4RCTInDlzYGNjg1deeQUlJSX4/vvvYWZmJjoWEYGFkvREeXk54uLioFAokJqaijp16mDChAmYOnUqp5FEpDV9+nTY2Nhg0qRJUKlUWLVqFczNzUXHIjJ5LJQk1Pnz57VrI3/77TdOI4noqcaPHw9ra2uMGjUKJSUl2LRpEywtLUXHIjJp3NicatzDaWR0dDT27NmDunXraqeR7dq1Ex2PiAzEjh07EBYWhr59+yI2NpY36BEJxEJJNebcuXNYunQpVq5cid9++w19+vRBZGQkwsLCOI0koheyZ88eBAUFoVOnTti+fTvs7e1FRyIySSyUVK3Kysq0ayP/PI2MjIxE27ZtRccjIiNw6NAhDBo0CK1bt8auXbtQr1490ZGITA4LJVWLh9PIFStWoKCgAL6+vtpppJWVleh4RGRkfvnlFwQGBqJRo0ZITk5GgwYNREciMikslKQzZWVliI2NhUKhwN69e1GvXj3t2khOI4moup06dQoBAQGws7NDSkoKmjRpIjoSkclgoaQqO3v2rHZt5MNpZFRUFORyOaeRRFSjLly4AH9/fwBAamoqWrZsKTgRkWlgoaQX8nAaGR0djX379qFevXqYOHEipk6dijZt2oiOR0QmLC8vD/7+/lCpVEhJSeEVEqIawEJJz+XMmTPaaWRhYSH69u2LyMhITiOJSK/cuHED/fv3x40bN5CcnAxvb2/RkYiMGgslPVVZWRmUSiWio6ORlpYGBwcH7dpITiOJSF8VFhZiwIABuHDhAhITE9G9e3fRkYiMFgslPdbp06exdOlSrFq1CoWFhejXrx8iIyMRGhrKaSQRGYQ7d+5g6NCh+OWXX7B9+3b069dPdCQio8RCSX9x//59KJVKKBQK7TTy4dpId3d30fGIiJ6bSqVCSEgIDhw4AKVSiUGDBomORGR0WCgJwKOnkVFRUQgNDeUzconI4N2/fx/h4eFITEzEhg0bEBYWJjoSkVFhoTRhD6eR0dHR2L9/PxwdHbXTyNatW4uOR0SkUw8ePMC4ceOwZcsWrFy5EuPGjRMdichoyEQHoJqXnZ2tnUYWFRXBz88PGzduREhICKeRRGS0zM3NsW7dOtjY2GDChAkoKSlBVFSU6FhERoGF0kTcv38fMTExiI6ORnp6OhwdHREREYEpU6ZwGklEJsPMzAxLly6FjY0Npk2bBpVKhddff110LCKDx0Jp5LKzs6FQKLB69WoUFRXhpZde4jSSiEyaVCrFV199BVtbW7zxxhsoLi7G/PnzIZFIREcjMlgslEaotLQUMTExUCgUf5lGTp06Fa1atRIdj4hIOIlEgkWLFsHW1hbvvvsuiouL8cknn7BUEr0gFkojcurUKe008tatW3jppZewadMmBAcHcxpJRPQI8+bNg7W1NWbPng2VSoWvv/4aUqlUdCwig8NCaeBKS0uxdetWKBQKHDhwAPXr18fUqVMxZcoUTiOJiJ7BrFmzYGtri8jISKhUKixbtgwyGf95JHoe/BtjoP4+jfT398fmzZsRHBwMCwsL0fGIiAzKlClTYG1tjfHjx6OkpARr167l91Ki58B9KA3Iw2lkdHQ0fvzxRzg5OWHSpEmYMmUK3NzcRMcjIjJ4cXFxCA8PR//+/bFlyxbUqlVLdCQig8BCaQCysrK008jbt28jICAAkZGRnEYSEVWD3bt3IzQ0FD169EB8fDxsbW1FRyLSeyyUeqq0tBRbtmyBQqHQTiMnT56MKVOmoGXLlqLjEREZtf3792Po0KFo3749du7ciTp16oiORKTXWCj1zK+//gqFQoE1a9bg9u3b6N+/PyIjIxEUFMRpJBFRDcrIyMDAgQPRrFkzJCUlwdHRUXQkIr3FQqkHSkpKtNPIgwcPchpJRKQnTpw4gf79+8PR0RHJyclwdnYWHYlIL7FQCvSoaWRUVBSGDRvGaSQRkZ44c+YM/P39YWVlhdTUVDRt2lR0JCK9Y/KFUlVWgcuFKpRXqGEhk6KZgw1sLKtvN6WH08jo6GgcOnQIDRo00E4jW7RoUW3nJSKiF3fp0iX4+/ujoqICKSkpaN26tehIRHrFJAvluZv3sO5ILvaeyUduUQn+/AcgAeBazxp+7k4Y080VrRrY6eScJ0+e1E4j79y5g8DAQO3aSHNzc52cg4iIqs/Vq1cREBCAW7duISUlBe3btxcdiUhvmFShzCsqwbzYk0g/XwAzqQSV6sd/6Q9f7+PmiEWhnmhSz/q5z1dSUoLNmzdDoVDg0KFDaNiwISZPnoyIiAhOI4mIDFB+fj4CAwORl5eHpKQkdO7cWXQkIr1gMoVyY2YuFiRkoUKteWKR/DszqQQyqQQfBHlgpI/rM73n5MmTiI6Oxtq1a3H37l3tNHLYsGGcRhIRGbhbt25h0KBByM7Oxo4dO9C7d2/RkYiEM4lC+c3ec/g86WyVjzMnsDVe9Xv087FVKpV2Gnn48GHtNHLKlClo3rx5lc9NRET64969exg2bBgyMzMRHx+PgIAA0ZGIhDL6QrkxMxdzlSd1drxP5J4I/9Ok8sSJE9q1kffu3cOAAQMQGRmJoUOHchpJRGTESkpKEBYWhj179mDr1q0YNmyY6EhEwhh1ocwrKkHAl2koq1A/8fNubnoP9y/9rP2989TvYO7Q5JGfaymTIiHKBz8mJUChUODIkSNo2LAhIiIiEBERwWkkEZEJKSsrw+jRo5GQkIC1a9ciPDxcdCQiIapvfxw9MC/2JCqesl6y+ETyX8rk05Q/qMBLby/F9Q3vYsCAAVAqlZxGEhGZKEtLS2zatAmTJk3C6NGjUVJSgkmTJomORVTjjLZQnrt5D+nnC574ORX3CnErdRkgkUJiJoOmovypx9VIpDB39cLen7LRt6O7ruISEZGBkslkWLVqFWxsbDB58mSoVCq8+uqromMR1SijLZTrjuQ+dWugot3/hbpMBfuucqhOH0Dl3fxnOraZVIK9eRXo21FXaYmIyJBJpVJ89913sLa2xmuvvYbi4mLMnTtXdCyiGmO0hXLvmfwnlsnirL0oPZ8BWT0X1O4zBqrTB5752JVqDfaezcf78NBFVCIiMgISiQSLFy+GnZ0d3nnnHRQXF2PhwoWQSCSioxFVO6MslMVlFcgtKnns65WqW7iVshSQSOEweCak5pbPfY7cwhKoyiqq9TGNRERkWCQSCT744APY2Njg7bffhkqlwhdffMFSSUbPKNtQTqEKT7oVpyjpO6hL78KuSzCsGrd7oXNoAFwuVMHDufYLvZ+IiIzXW2+9BVtbW8yYMQMqlQrfffcdzMzMRMciqjZGWSjLn7BNUNn1cyg5cxBSSxtYt+6Bsuvnfn9BXfH/7/8tFxqNBhaOT34yzpPOQ0REpu2VV175y406q1atgkxmlP/sEhlnobSQSR/7mqa8FACgLlPh5vpHL5guiPsI5k7N4Tz56xc+DxER0YQJE2Btba3dUmjjxo2wtHz+ZVZE+s4oG1EzBxtU92oVyR/nISIiepKXX34ZsbGxSExMRHBwMEpKHr/Gn8hQGe2Tcvp+thc5T7gx5++ufDtZu23Qk56U81BTB2ukzfGrUkYiIjIdqampCA4ORufOnbFt2zbY29uLjkSkM0Y5oQQAP3cnmEmrZ05pJpXAr7VTtRybiIiMk7+/P5KSknDs2DH0798fRUVFoiMR6YzRTijP3byH/kv2V9vxU2b7ws3JrtqOT0RExunnn39GYGAgXFxckJSUhAYNGoiORFRlRjuhbNXADn3cHHU+pTSTStDHzZFlkoiIXkinTp2QlpaG/Px89O3bF1euXBEdiajKjLZQAsCiUE/IdFgoNRoNJJpKLAr11NkxiYjI9Hh4eCA9PR2lpaXo06cPLl68KDoSUZUYdaFsUs8aHwTp7vGIEokEN3d8jQ/nvY7y8nKdHZeIiEyPm5sb0tPTIZPJ0KdPH5w+fVp0JKIXZtSFEgBG+rhiTmBrnRzrzUB3fPnaCCxfvhwBAQHIz8/XyXGJiMg0ubq6Yv/+/ahbty58fX1x/Phx0ZGIXojR3pTzdxszc7EgIQsVag0q1c/+JZtJJZBJJfhXkAfCfX5/cs6PP/4IuVwOKysrxMfHw9vbu5pSExGRKSgoKMCAAQNw8eJF7Nq1C926dRMdiei5GP2E8qGRPq5Imd0XPVs4AMBTb9Z5+HrPFg5Imd1XWyYBoFevXsjMzISjoyN69uyJLVu2VF9wIiIyeo6OjtizZw/atWuHgIAApKWliY5E9FxMZkL5Z+du3sO6I7nYezYfuYUl+PMfgASAq4M1/Fo7YWx31yfezV1SUoKIiAhs3LgR//znP/HBBx9AKjWZjk5ERDqmUqkQHByMH3/8EbGxsRg4cKDoSETPxCQL5Z+pyipwuVCF8go1LGRSNHOwgY3lsz/iXKPR4JNPPsG8efMwbNgwrFmzhk8/ICKiF3b//n28/PLL2L17NzZt2oTQ0FDRkYieyuQLpa7s2LEDo0ePRuPGjZGQkICWLVuKjkRERAbqwYMHGDt2LGJiYrBy5UqMHTtWdCSiJ+L1WR0ZMmQIDh8+jPLycvj4+CAlJUV0JCIiMlDm5uZYv349xo0bh/Hjx0OhUIiORPRELJQ61LZtW2RkZMDHxwcDBgzAV199BQ6AiYjoRZiZmeGHH37AK6+8gqioKHz55ZeiIxE91rMvFqRnUrduXezYsQNz587FrFmzcPz4cXz33XewtLQUHY2IiAyMVCrF119/DVtbW7z++usoLi7GP//5T0gkun2sMFFVsVBWA5lMhs8//xxeXl6IjIxEdnY2lEolGjVqJDoaEREZGIlEgo8++gi2traYP38+VCoVPvroI5ZK0iu8KaeaZWRkICQkBFKpFLGxsfDx8REdiYiIDNSXX36J119/HTNmzMB//vMfblVHeoP/J1azrl274ujRo3BxcUGfPn2wdu1a0ZGIiMhAzZ49G9HR0fj2228RERGByspK0ZGIAPCSd41wdnZGWloaoqKiMG7cOBw/fhwff/wxzMzMREcjIiIDExkZCRsbG0yYMAElJSVYs2YNLCwsRMciE8dL3jVIo9FgyZIlmDNnDgIDA7FhwwbUqVNHdCwiIjJAsbGxCA8Px4ABA7BlyxZYWVmJjkQmjIVSgKSkJISHh8PJyQkJCQlwd3cXHYmIiAzQrl27EBoail69eiEuLg62traiI5GJ4hpKAQIDA5GRkQEzMzN07doVO3fuFB2JiIgM0MCBA7Fr1y4cOXIEAwYMwJ07d0RHIhPFQilIq1atcPjwYfj6+mLo0KH49NNPuQk6ERE9t759+yIlJQWnTp3CSy+9hIKCAtGRyASxUApkb2+PuLg4zJ07F2+//TbGjh2L0tJS0bGIiMjAdOvWDfv27UNeXh769euH69evi45EJoZrKPXEpk2bMGnSJLRr1w5xcXFo3Lix6EhERGRgTp8+DX9/f1hbWyMlJQVNmzYVHYlMBCeUeiI8PBwHDhxAfn4+unTpgoMHD4qOREREBqZNmzZIT09HZWUl+vTpg3PnzomORCaChVKPdOrUCZmZmWjVqhX8/PywfPly0ZGIiMjAtGjRAvv374e1tTV8fX2RlZUlOhKZABZKPdOgQQOkpqZiwoQJiIiIwMyZM1FRUSE6FhERGZDGjRtj//79cHJyQt++ffHTTz+JjkRGjmso9ZRGo8G3336LmTNnom/fvti8eTMcHBxExyIiIgNSVFSEQYMG4fTp09i5cyd69eolOhIZKRZKPbdv3z4MHz4ctWvXRnx8PNq3by86EhERGZC7d+9i2LBhOHr0KBISEuDv7y86EhkhXvLWc/369UNmZiZsbGzQo0cPxMfHi45EREQGxN7eHomJiejTpw+GDBmC7du3i45ERoiF0gA0b94cBw8eRGBgIEJCQrBw4UJugk5ERM/M2toa8fHxGDRoEEJDQ7F582bRkcjIsFAaCFtbW2zZsgXvv/8+3nvvPYwYMQIqlUp0LCIiMhCWlpbYvHkzRowYgVGjRmHlypWiI5ER4RpKA6RUKjF+/Hi0bNkS8fHxaNasmehIRERkICorKzF9+nQsXboU33zzDWbMmCE6EhkBTigNkFwux6FDh3Dv3j34+PggLS1NdCQiIjIQZmZmiI6OxqxZs/Dqq6/i008/FR2JjAALpYHy9PRERkYGPD09ERAQgO+//150JCIiMhASiQRffPEF/vnPf+Ltt9/Ge++9x7X5VCUy0QHoxTk6OmL37t14/fXXMX36dBw7dgz/+c9/YGFhIToaERHpOYlEgoULF8LW1hZz585FcXExFi9eDIlEIjoaGSAWSgNnbm6Or7/+Gh06dMArr7yCU6dOYevWrXBychIdjYiIDMDbb78NGxsbvPbaa1CpVPjuu+8glfICJj0f3pRjRA4cOICwsDBYWVkhPj4e3t7eoiMREZGBWLFiBaZMmYLRo0djxYoVkMk4c6Jnxx9BjEjv3r2RmZkJR0dH9OzZE1u2bBEdiYiIDMSkSZOwfv16bNy4ESNGjEBZWZnoSGRAWCiNjKurK9LT0xEcHIwRI0Zg/vz5UKvVomMREZEBCA8Ph1KpxI4dOxASEoKSkhLRkchA8JK3kdJoNPjkk08wb948DBs2DGvWrIG9vb3oWEREZABSUlIQHBwMHx8fbNu2DXZ2dqIjkZ5joTRy27dvx+jRo9GkSRMkJCSgZcuWoiMREZEBOHDgAIYMGYK2bdsiMTERdevWFR2J9BgveRu5oUOH4siRIygvL4ePjw9SUlJERyIiIgPQu3dv7NmzB+fOnYOfnx/y8/NFRyI9xkJpAtq2bYuMjAz4+PhgwIAB+Oqrr7iBLRERPVXnzp2RlpaGGzduoG/fvrh69aroSKSnWChNRN26dbFjxw7Mnj0bs2bNQkREBO/gIyKip2rfvj3S09OhUqnQp08fXLp0SXQk0kNcQ2mCVq9ejcjISHTs2BFKpRKNGjUSHYmIiPRcTk4O/P39cf/+faSmpsLd3V10JNIjLJQmKiMjAyEhIZBKpYiNjYWPj4/oSEREpOeuX7+OgIAAFBQUIDk5GV5eXqIjkZ7gJW8T1bVrVxw9ehQuLi7o06cP1q5dKzoSERHpuUaNGiEtLQ0uLi7o168fMjIyREciPcFCacKcnZ2RlpaG8PBwjBs3Dm+99RYqKytFxyIiIj3m6OiIPXv2oE2bNvD398f+/ftFRyI9wEveBI1GgyVLlmDOnDkYMGAA1q9fjzp16oiORUREeqy4uBjBwcE4dOgQYmNjMWDAANGRSCAWStJKSkpCeHg4nJyckJCQwAXXRET0RKWlpXj55ZeRnJyMTZs2ISQkRHQkEoSXvEkrMDAQGRkZMDMzQ9euXbFz507RkYiISI/VqlULSqUSwcHBGD58ONavXy86EgnCQkl/0apVKxw+fBi+vr4YOnQoPv30U26CTkREj2VhYYH169dj7NixGDt2LJYuXSo6EgkgEx2A9I+9vT3i4uIwf/58vP322zh+/DiWLVuGWrVqiY5GRER6SCaTYfny5bCxsUFkZCRUKhVmzZolOhbVIBZKeiQzMzMsWrQIHTp0wKRJk3D27FnExsaicePGoqMREZEekkql+Oabb2BjY4PZs2dDpVJh3rx5kEgkoqNRDeBNOfRUP//8M0JCQlBeXg6lUomePXuKjkRERHpKo9Hg3//+N9577z3MnTsXixYtYqk0AVxDSU/VqVMnZGZmws3NDX5+fli+fLnoSEREpKckEgnmz5+PxYsX4+OPP8bMmTOhVqtFx6Jqxkve9EwaNGiAPXv24NVXX0VERASOHz+OxYsXQybj/0JERPS/Xn/9ddjY2GD69OkoLi7G0qVLYWZmJjoWVRO2AXpmFhYWiI6ORocOHTBz5kxkZWVh06ZNcHBwEB2NiIj0UFRUFKytrTFx4kSUlJRgzZo1MDc3Fx2LqgHXUNIL2bdvH4YPH47atWsjISEBHh4eoiMREZGeiomJwahRozBw4EBs3rwZVlZWoiORjnENJb2Qfv36ITMzEzY2NujevTvi4+NFRyIiIj0VFhaG+Ph4JCcnY9iwYVCpVKIjkY6xUNILa968OQ4ePIjAwECEhIRg4cKF3ASdiIgeadCgQUhMTMShQ4cwYMAA3Llz55nepyqrQNa1O/gl9xayrt2BqqyimpPSi+Alb6oytVqNhQsX4v3338fw4cOxcuVK2NjYiI5FRER66PDhwxg0aBBatmyJ3bt3P3Id/rmb97DuSC72nslHblEJ/lxUJABc61nDz90JY7q5olUDuxrLTo/HQkk6o1QqMX78eLi5uSE+Ph5NmzYVHYmIiPTQsWPH0L9/fzRs2BDJyclo2LAhACCvqATzYk8i/XwBzKQSVKofX1Eevt7HzRGLQj3RpJ51TcWnR2ChJJ06efIkgoODce/ePcTExMDX11d0JCIi0kPZ2dkICAiAtbU1UlNTcfAmsCAhCxVqzROL5N+ZSSWQSSX4IMgDI31cqzExPQkLJelcQUEBRowYgfT0dHz99deYNm2a6EhERKSHLl68CH9/f6jbBkLSIajKx5sT2Bqv+rXSQTJ6Xrwph3TO0dERu3fvxrRp0zB9+nRMmzYN5eXlomMREZGeadGiBd78PlYnZRIAPk86i02ZuTo5Fj0fTiipWi1btgyvvPIKunfvjq1bt8LJyUl0JCIi0hN5RSUI+DINZRW6ezSjpUyKlNl9uaayhrFQUrU7cOAAwsLCYGVlhfj4eHh7e4uOREREemDcD0dw8GLhI9dM3s/LgupUGsqvnUHFvUKoy4phZlMPFk7NYN99OKwat3vkMc2kEvRs4YA1Ed2qOz79CS95U7Xr3bs3MjMz4ejoiF69emHLli2iIxERkWDnbt5D+vmCx96Ao8rai+JfdqL85gWoS24DlRWovJuP0vMZuLn2Ldw7tuuR76tUa5B+vgDn8+9VY3r6OxZKqhGurq5IT09HUFAQRowYgfnz50Ot1t0lDiIiMizrjuTCTCp5/CdIpLB27wWn8IVo8vpWuMxYCWv3XtqXb6ethkZd+ci3mkklWHuYaylrkkx0ADId1tbWWL9+PTp06IB58+bhxIkTWLNmDezt7UVHIyKiGrb3TP4Ttweq228ipJb/vw5SamGFegNeQcmZHwEA6tK7UJfchZlt3f95b6Vag71n8/E+PHQfnB6JE0qqURKJBHPnzkVCQgL27t2LHj164MKFC6JjERFRDSouq0BuUckTP+fPZfIhzYMy7a8l5paQ1nr8U3JyC0v4mMYaxEJJQgwdOhRHjhxBeXk5fHx8kJKSIjoSERHVkJxCFZ73jmCNRoNbe37Q/t7WeyAkZo+/0KoBcLlQ9WIB6bmxUJIwbdu2RUZGBnx8fDBw4EB89dVX4KYDRETGr/w5twnSVD5A4fbF2svdVk29ULfvRJ2fh14cCyUJVbduXezYsQOzZs3CrFmzEBERgbKysqe/kYiIDJaF7Nnrh7qsBPmbF0CVtQ8AUMutG+oPXwCJzFyn56Gq4U05JJxMJsPnn38OLy8vREZGIjs7G0qlEo0aNRIdjYiIqkEzBxtIgKde9q64V4D8ze/jwW+XAQB2nYagbkAkJFKzp55D8sd5qGawupPeGD9+PPbv34+cnBz4+PggMzNTdCQiIqoGNpYyuD7lSTblv13GjdVz/iiTEtTxm4R6gdOfqUwCgKuDNWwsOTerKfyTJr3StWtXHD16FKGhoejTpw9++OEHjBkzRnQsIiLSoXPnzsG84Cw0aPTYgnj3SCwq7xX88TsNbu9dgdt7V/zlcxqMWgSrpl7/814zqQR+rfmo35rECSXpHWdnZ6SlpSE8PBxjx47FW2+9hcrKR29eS0REhqGsrAwbN27ESy+9hNatW+P41m+eedr4vCrVGozt7lotx6ZH47O8SW9pNBosWbIEc+bMwYABA7B+/XrUqVNHdCwiInoOZ8+exdKlS7Fy5UoUFBTA19cXkZGRCAsLw9R1xx/7LO8XxWd5i8FCSXovKSkJ4eHhcHJyQkJCAtzd3UVHIiKiJygrK0NsbCyio6Oxb98+1KtXDxMnTsTUqVPRpk0b7eflFZUg4Ms0lOlwex9LmRQps/uiyVPWaJJu8ZI36b3AwEBkZGTAzMwMXbt2xc6dO0VHIiKiRzhz5gzmzJkDFxcXjBo1ChqNBuvWrcPVq1exePHiv5RJAGhSzxofBOn28Yj/CvJgmRSAhZIMQqtWrXD48GH4+vpi6NCh+PTTT7kJOhGRHigrK8OGDRvQr18/tGnTBitXrsSECROQnZ2Nffv2YfTo0bCysnrs+0f6uGJOYGudZHkz0B3hPlw7KQIveZNBqaysxPz58/HRRx9hzJgxWLp0KWrVqiU6FhGRyTl9+jSWLl2KVatWobCwEP369UNkZCRCQ0OfWCAfZ2NmLhYkZKFCrXmuNZVmUglkUgn+FeTBMikQCyUZpE2bNmHSpEnw8PBAbGwsGjduLDoSEZHRu3//PpRKJRQKBdLS0uDg4KBdG6mL9e15RSWYF3sS6ecLYCaVPLFYPny9j5sjFoV68jK3YCyUZLB+/vlnhISEoLy8HEqlEj179hQdiYjIKJ0+fRoKhQKrVq1CUVGRdhopl8thaWmp8/Odu3kP647kYu/ZfOQWlvzliToajQYOFmoEdWmJsd1d4eZkp/Pz0/NjoSSDdvPmTYSFhSEzMxPfffcdJk+eLDoSEZFRuH//PmJiYqBQKLB//344Ojpi4sSJmDJlSo3utqEqq8DlQhXKK9SwkEkxzK87QocOxuLFi2ssAz0dn5RDBq1BgwbYs2cPXn31VUREROD48eNYvHgxZDL+r01E9CKys7O1ayOLiorg5+eHDRs2IDQ0tFqmkU9jYymDh3Nt7e87tm+HY8eO1XgOejL+q0sGz8LCAtHR0ejQoQNmzpyJrKwsbNq0CQ4ODqKjEREZhIfTyOjoaKSnp8PR0RGTJ0/G1KlT0bq1bu7A1hVvb28sWbIEGo0GEolEdBz6A7cNIqMgkUgwY8YMpKSk4NixY+jatSuysrJExyIi0mvZ2dmYPXs2XFxcMHbsWJibm2Pjxo24cuUKPvvsM70rk8DvhbKoqAhXrlwRHYX+hIWSjEq/fv2QmZkJGxsbdO/eHfHx8aIjERHpldLSUqxduxa+vr5o164d1q5di4iICJw5cwapqakIDw8Xcmn7WXl7ewMAL3vrGRZKMjrNmzfHwYMHERgYiJCQECxcuJCboBORyTt16hRmzZoFFxcXjBs3Dubm5ti0aROuXLmCTz/9VC+nkY/SuHFj1KtXj4VSz3ANJRklW1tbbNmyBQsXLsR7772HEydOYOXKlbCxsREdjYioxpSWlmLr1q1QKBQ4cOAA6tevj6lTp2LKlClo1aqV6HgvRCKRwNvbm4VSz3BCSUZLKpViwYIFiImJQWJiInr16oWcnBzRsYiIql1WVpZ2Gjl+/HhYWlpi8+bNuHLlCj755BODLZMPsVDqHxZKMnpyuRyHDh3C3bt30aVLF+zfv190JCIinSstLcXq1avRu3dvtG/fHhs2bEBkZCTOnTuHlJQUvPzyy7CwsBAdUye8vb1x8eJF3LlzR3QU+gMLJZkET09PZGRkwNPTE/7+/vj+++9FRyIi0omsrCzMnDkTzs7OmDBhAmrVqoXNmzcjLy8PH3/8Mdzc3ERH1LmHN+acOHFCbBDSYqEkk+Ho6Ijdu3dj2rRpmD59OqZNm4by8nLRsYiIntvDaWSvXr3Qvn17bNy4EVFRUTh37hySk5ONahr5KG3atIGFhQUve+sR3pRDJsXc3Bxff/01vLy8MGPGDJw6dQpbt26Fk5OT6GhERE/166+/QqFQYM2aNbh9+zYCAgKwZcsWBAUFGXWB/Dtzc3O0b9+ehVKP8FneZLIOHDiAsLAwWFlZIT4+XnsJhYhIn5SUlGDLli1QKBQ4ePAgnJycMHnyZEyZMgUtW7YUHU+YiIgIHDt2DD/99JPoKARe8iYT1rt3b2RmZsLR0RG9evXCli1bREciItL69ddf8Y9//AMuLi6YOHEibGxssHXrVuTl5eGjjz4y6TIJ/L6O8tdff8WDBw9ERyGwUJKJc3V1RXp6OoKCgjBixAjMnz8farVadCwiMlElJSVYuXIlevbsCU9PT2zevBnTp0/HhQsXkJSUhLCwMJO6tP0k3t7eKC8vx+nTp0VHIXANJRGsra2xfv16dOjQAfPmzcOJEyewZs0a2Nvbi45GRCbi5MmT2rWRd+7cQWBgILZu3YqgoCCYm5uLjqeXvLy8APz+CEZPT0/BaYhrKIn+ZPv27Rg9ejSaNGmChIQEk7+kRETVp6SkBJs3b0Z0dDQOHz6Mhg0bYvLkyYiIiECLFi1ExzMILVu2RHBwML744gvRUUweL3kT/cnQoUNx5MgRlJeXw8fHBykpKaIjEZGROXHiBF599VU4Oztj8uTJqF27NmJiYpCbm4sPP/yQZfI58Ik5+oOFkuhv2rZti4yMDPj4+GDgwIH46quvwEE+EVWFSqXCihUr0L17d3To0AExMTGYMWMGLly4gF27dkEul/PS9gt4WCj5PVo8FkqiR6hbty527NiBWbNmYdasWYiIiEBZWZnoWERkYI4fP44ZM2bA2dkZERERqFu3LpRKpXYa2bx5c9ERDZq3tzdu3bqFvLw80VFMHm/KIXoMmUyGzz//HF5eXoiMjER2djaUSiUaNWokOhoR6TGVSoVNmzZBoVDgyJEjaNiwIV577TVERESwQOrYw/2Djx07BldXV7FhTBwnlERPMX78eKSlpSEnJwc+Pj7IzMwUHYmI9NDx48fxyiuvwNnZGVOmTPnLNPLf//43y2Q1aNy4MerVq8d1lHqAhZLoGXTr1g1Hjx6Fi4sL+vTpg3Xr1omORER6oLi4GD/88AO6desGb29vxMXF4R//+AcuXryIxMREhIaGcm1kNZJIJLwxR0+wUBI9I2dnZ6SlpSE8PBxjx47FW2+9hcrKStGxiEiAY8eOaaeRU6dOhYODA2JjY5GTk4OFCxeiWbNmoiOaDBZK/cBCSfQcrKyssHLlSnzxxRdYvHgxhg0bhtu3b4uORUQ14OE0smvXrujYsSPi4uIwc+ZMXLp0CTt37kRISAinkQJ4e3vj0qVL/F4sGAsl0XOSSCSYPXs2EhMTcejQIXTr1g1nzpwRHYuIqskvv/yC6dOna6eR9evXR1xcHHJzc7Fw4UI0bdpUdEST1rFjRwC/7+9J4rBQEr2gwMBAZGRkwMzMDF27dsXOnTtFRyIiHSkuLsayZcvQtWtXdOrUCQkJCZg1axYuXbqEHTt2IDg4GDIZN0rRB+7u7rC0tORlb8FYKImqoFWrVjh8+DB8fX0xdOhQfPrpp9xgl8iA/fLLL5g2bRoaNWqEyMhI1K9fH/Hx8cjJycG//vUvTiP1kLm5Odq3b89CKRh/vCKqInt7e8TFxWH+/Pl4++23ceLECSxduhS1atUSHY2InsG9e/ewceNGKBQK7W4Or7/+OiIiIri3oYHw9vbGzz//LDqGSWOhJNIBMzMzLFq0CB06dMCkSZNw5swZxMbGonHjxqKjEdFj/Pzzz1AoFFi3bh1KSkowaNAgJCQkYNCgQbycbWC8vb2xZs0alJeXw8LCQnQck8RL3kQ6FB4ejgMHDuDmzZvo0qULDh48KDoSEf3JvXv3oFAo0KVLF3Tu3Bnbt2/HG2+8gUuXLmH79u0YNmwYy6QB8vb2Rnl5OU6fPi06islioSTSsU6dOiEzMxNubm7w8/PD8uXLRUciMnk//fQToqKi4OzsjOnTp6NRo0ZISEjA5cuX8f777/PStoHz8vICAK6jFIiFkqgaNGjQAHv27MGECRMQERGBmTNnoqKiQnQsIpPycBrZuXNndOnSBTt27MAbb7yBy5cvY9u2bZxGGhF7e3u0bNmShVIg/k0iqiYWFhaIjo5Ghw4dMHPmTGRlZWHTpk1wcHAQHY3IqB09ehQKhQLr169HaWkpBg8ejA8++AADBw5kgTRifGKOWJxQElUjiUSCGTNmICUlBceOHUPXrl2RlZUlOhaR0bl79y6io6PRuXNn+Pj4IDExEW+++aZ2Gjl06FCWSSP3sFBy6zYxWCiJakC/fv2QmZkJGxsbdO/eHfHx8aIjERk8jUaDo0ePYurUqXB2dsYrr7wCFxcXbNu2DZcvX8aCBQvQpEkT0TGphnh7e+PWrVvIy8sTHcUksVAS1ZDmzZvj4MGD6N+/P0JCQrBw4UL+JE30Au7evYvvv/9eO43cvXs33nrrLeTk5CAhIQFDhw6FmZmZ6JhUw7y9vQHwxhxRWCiJapCtrS22bt2K999/H++99x5GjBgBlUolOhaR3tNoNMjMzNROI2fMmIEmTZpg+/btuHTpEt577z3u+2riXFxc4ODgwEIpiETDEQmREEqlEuPHj4ebmxvi4+P5SDeiR7h79y7Wr1+P6OhoHDt2DE2aNMHUqVMxadIkFkj6HwEBAbC3t4dSqRQdxeRwQkkkiFwux6FDh3D37l106dIF+/fvFx2JSC9oNBpkZGRgypQpaNSoEV599VU0bdoUO3bswKVLlzB//nyWSXok3uktDgslkUCenp7IyMiAp6cn/P398f3334uORCTMnTt38N1336FTp07o1q0bkpOTMXfuXOTk5CAuLg6DBw/m2kh6Im9vb1y6dAm3b98WHcXksFASCebo6Ijdu3dj2rRpmD59OqZNm4by8nLRsYhqhEajwZEjRxAREQFnZ2e89tpraNasGXbu3ImLFy9i/vz5cHFxER2TDMTDG3NOnDghNogJ4qZcRHrA3NwcX3/9Nby8vDBjxgycOnUKMTExqF+/vuhoRNXizp07WLduHRQKBY4fPw5XV1e88847mDRpEgskvTB3d3dYWlri2LFj8PX1FR3HpPCmHCI9c+DAAYSFhcHKygrx8fHan7iJDN3DtZHR0dHYtGkTysrKMGzYMERFRaF///68nE060aVLF3h5eWH58uWio5gUXvIm0jO9e/dGZmYmHB0d0atXL2zZskV0JKIquX37Nv773//C29sb3bt3x549ezBv3jzk5uYiNjYWAwcOZJkkneGNOWKwUBLpIVdXV6SnpyMoKAgjRozA/PnzoVarRcciemYajQaHDx/G5MmT4ezsjJkzZ6Jly5ZITEzEhQsX8O6778LZ2Vl0TDJC3t7eyMrK4lr0GsY1lER6ytraGuvXr4eXlxfeffddnDhxAmvWrIG9vb3oaESPdfv2baxbtw7R0dE4efIkmjZtinfffReTJ09Go0aNRMcjE+Dt7Y3y8nKcPn0aXl5eouOYDK6hJDIA27dvx+jRo9GkSRMkJCSgZcuWoiMRaT2cRioUCmzatAnl5eUIDg5GZGQk+vfvD6mUF8Oo5ty9exe1a9fGqlWrMH78eNFxTAb/lhMZgKFDh+LIkSMoLy+Hj48PUlJSREciwu3bt/HNN9+gQ4cO6NmzJ/bt24d//vOfyMvLQ0xMDAYMGMAySTXO3t4eLVu25DrKGsa/6UQGom3btsjIyICPjw8GDhyIr776CrzAQDVNo9Hg0KFDmDhxIpydnTF79my0atUKu3fvxoULFzBv3jxe2ibheGNOzWOhJDIgdevWxY4dOzBr1izMmjULERERKCsrEx2LTMCtW7e0e6X27NkT+/fvx/z585Gbm4uYmBgEBgZyGkl642Gh5A/dNYc35RAZGJlMhs8//xxeXl6IjIxEdnY2lEolp0Kkcw+nkQ/XRlZUVCA4OBiLFy9GQEAACyTpLW9vb9y6dQt5eXlwdXUVHcck8LsBkYEaP3480tLSkJOTAx8fH2RmZoqOREbi1q1b+M9//gNPT0/06tUL6enpWLBgAfLy8rB161ZOI0nvPXwgBC971xx+RyAyYN26dcPRo0fh4uICX19frFu3TnQkMlAajQY//vgjJkyYAGdnZ7zxxhto27YtkpKScO7cOcydOxcNGzYUHZPombi4uMDBwYGFsgbxkjeRgXN2dkZaWhqioqIwduxYHD9+HB999BGfPELP5NatW1izZg0UCgWysrLQokULvP/++5g4cSIaNGggOh7RC5FIJPD29sYvv/wiOorJYKEkMgJWVlZYuXIlvL29MWfOHPz6669Yv3496tSpIzoa6aGH00iFQoEtW7agoqICISEhWLJkCV566SVeziaj4O3tjZiYGNExTAY3NicyMklJSQgPD4eTkxMSEhLg7u4uOhLpiaKiIu008tSpU2jRogUiIyM5jSSjtHbtWowbNw63bt3iD9c1gD+GEhmZwMBAZGRkwMzMDF27dkViYqLoSCSQRqNBeno6xo0bB2dnZ8yZMwceHh5ITk7GuXPn8Pbbb7NMklHq2LEjAOD48eOCk5gGFkoiI9SqVSscPnwYvr6+GDJkCD777DPux2ZiioqKsGTJEnh4eMDX1xeHDh3Cv/71L1y5cgWbN2/mtj9k9Nzd3WFpackbc2oI11ASGSl7e3vExcVh/vz5eOutt3D8+HEsXboUtWrVEh2NqolGo8GBAwe0ayPVajVCQ0Px9ddfw8/PjwWSTIpMJoOnpycLZQ3hGkoiE7Bp0yZMmjQJHh4eiI2NRePGjUVHIh0qLCzUro3Mzs6Gm5sbIiMjMWHCBDg5OYmORyTM1KlTcfToUd7tXQP44yqRCQgPD8eBAwdw8+ZNdOnSBQcPHhQdiapIo9Fg//79GDt2LFxcXPDWW2/By8sLqampOHPmDN58802WSTJ53t7eyMrKQnl5uegoRo+FkshEdOrUCZmZmXBzc4Ofnx+WL18uOhK9gMLCQnz55Zdo164d+vbtiyNHjmDhwoW4evUqNm7cyG1/iP7E29sbDx48QHZ2tugoRo/fdYhMSIMGDbBnzx5MmDABERERmDVrFioqKkTHoqfQaDRIS0vDmDFj4OzsjLfffhve3t7Ys2cPzp49izfffBP169cXHZNI73h5eQHgIxhrAgslkYmxsLBAdHQ0vvnmG3zzzTcYOHAgCgsLRceiRygoKMAXX3yBtm3bol+/fsjMzMSHH36Iq1evYsOGDfDz84NEIhEdk0hv2dnZwc3NjYWyBvCmHCITtm/fPgwfPhy1a9dGQkICPDw8REcyeQ/XRkZHR2uf8iGXyxEVFYW+ffuyQBI9p5dffhkFBQXYu3ev6ChGjRNKIhP2cOplY2OD7t27Iz4+XnQkk1VQUIDFixejTZs26NevH3766ScsWrQIV65cwYYNG9CvXz+WSaIX4O3tjWPHjnEv3mrGQklk4po3b46DBw+if//+CAkJwb///W9+460hGo0G+/btw+jRo+Hi4oJ58+ahc+fO2Lt3L06fPo033niDayOJqsjb2xu3b99Gbm6u6ChGjYWSiGBra4utW7fi/fffx/z58xEeHg6VSiU6ltEqKCjA559/jjZt2sDPz087jbx69SrWr1/PaSSRDnl7ewPgjTnVjYWSiAAAUqkUCxYsQExMDHbu3IlevXohJydHdCyjodFosHfvXowaNQouLi5499130aVLF+zbt087jXR0dBQdk8joODs7w9HRkYWymvGmHCL6HydPnkRwcDDu3buHmJgY+Pr6io5ksH777TesWrUKCoUC586dg7u7OyIjIzF+/HgWSKIa0r9/f9ja2iI2NlZ0FKPFCSUR/Q9PT09kZGTA09MT/v7++P7770VHMigPp5EjR47UTiN9fHyQlpaG7OxsvP766yyTRDXo4Y05VH1YKInokRwdHbF7925MmzYN06dPx/Tp0/n4sqfIz8/HZ599Bnd3d7z00ks4fvw4PvnkE1y7dg3r1q2Dr68v10YSCeDt7Y3Lly/j9u3boqMYLZnoAESkv8zNzfH111/Dy8sLM2bMwKlTp7B161beefwnarUa+/btg0KhgFKphFQqxfDhw7Fs2TL06dOHBZJIDzy8Mef48ePo27ev2DBGihNKInqqqVOnYs+ePTh9+jS6dOnCS0f4fRr56aefwt3dHf7+/jh+/Dg+/fRTXL16FWvXruU0kkiPuLu7w9LSkt+7qhELJRE9k969eyMzMxOOjo7o1asXtmzZIjpSjVOr1UhNTUV4eDgaN26M9957D927d8f+/ftx6tQpzJo1Cw4ODqJjEtHfyGQyeHp6slBWIxZKInpmrq6uSE9PR1BQEEaMGIH58+dDrVaLjlXt/jyNDAgIwMmTJ/HZZ5/h2rVrWLNmDS9tExkA3phTvbiGkoiei7W1NdavXw8vLy+8++67OHnyJNasWQM7OzvR0XRKrVZjz549UCgUiIuLg1QqxYgRI7BixQr06tWLBZLIwHh7e2PVqlUoLy+HhYWF6DhGh/tQEtEL2759O0aPHg1XV1fEx8ejZcuWoiNV2c2bN7Fy5UosXboUFy5cQNu2bREVFYVx48ahXr16ouMR0Qv68ccf0bt3bxw7dgwdOnQQHcfo8JI3Eb2woUOH4siRIygrK4OPjw9SUlJER3oharUaycnJePnll9G4cWMsWLAAPXv2RHp6OrKysjBz5kyWSSID5+XlBYCPYKwuLJREVCVt27ZFRkYGfHx8MHDgQHz11Vd43gsfqrIKZF27g19ybyHr2h2oyiqqKe1f3bhxAx9//DFatWqFwMBAnDp1CosXL8a1a9ewevVq9O7dm5e2iYyEnZ0d3NzcWCirCddQElGV1a1bFzt27MDcuXMxa9YsHD9+HN999x0sLS0f+55zN+9h3ZFc7D2Tj9yiEvy5gkoAuNazhp+7E8Z0c0WrBrpbn/nwTu2HayNlMhlGjBiB1atXo2fPniyQREaMN+ZUH66hJCKdWr16NSIjI9GxY0colUo0atToL6/nFZVgXuxJpJ8vgJlUgkr1478FPXy9j5sjFoV6okk96xfOdePGDe3ayIsXL8LDwwNRUVEYO3Ys6tat+8LHJSLD8eGHH+Lzzz9HUVERf3jUMRZKItK5I0eOIDQ0FFKpFLGxsfDx8QEAbMzMxYKELFSoNU8skn9nJpVAJpXggyAPjPRxfeb3qdVqpKSkQKFQID4+HjKZDOHh4YiMjESPHj34DwqRidmxYweGDh2Ky5cvo2nTpqLjGBUWSiKqFteuXUNoaChOnDiBZcuW4ZZzV3yedLbKx50T2Bqv+rV64ufcuHEDK1aswNKlS3Hp0iW0b98ekZGRnEYSmbirV6+icePGiIuLQ3BwsOg4RoWFkoiqzf379xEVFQXlsRtwGPwPnR33E7knwv82qXx4p7ZCoUBCQgLMzc2108ju3btzGklE0Gg0cHJywquvvooFCxaIjmNUWCiJqFrlFqrg9/keVGgkOit1ljIpUmb3RZN61rh+/bp2Gnn58mW0b99euzayTp06OjkfERmP/v37w9bWFrGxsaKjGBXe5U1E1erduF8BqRkkj1kzqS4vxZ3DW1Fy+gAq7uRDam4JC2d31O7xMqyatH/keyrUGkQu24tah39AQkICLCwsEB4ejqioKHTr1o3TSCJ6LG9vb2zdulV0DKPDQklE1ebczXtIP1/w2NfV5fdxc91clN+88P8fq3yA+xd/wv1Lv8Bx2Buwadf3f95XqdYg+xZgc+MOvvrqK4wZM4bTSCJ6Jt7e3vj8889x+/Ztft/QIW5sTkTVZt2RXJhJHz8tvHNwo7ZMWrfpg8b/WAenkf+GxNwS0KhRuPu/qCy998j3SiXA8LlfYcaMGfxHgYiembe3NwDg+PHjYoMYGRZKIqo2e8/kP3Z7II1Gg+ITydrf1/WbBDPr2qjVzBvWbfr8/jllJSjJTn/k+9UaYN/Z33QfmoiMmru7O6ysrLjBuY6xUBJRtSguq0BuUcljX6+4cxPqkjsAAIlFLchqO2lfs6j///vDlV07/dhj5BaW1NhjGonIOMhkMnh6erJQ6hgLJRFVi5xCFZ60hYRadUv7a6mV7V9ek1jaaH9dqbr92GNoAFwuVL1gQiIyVXwEo+6xUBJRtSivUD/7J//P7mV/+v1T7th+rvMQEeH3QpmVlYXy8nLRUYwGCyURVQsL2ZO/vUht/v+JNeqyv04ZNff///dm1nWqdB4ior/z9vbGgwcPcOrUKdFRjAa/ExNRtWjmYIMnzRbN6zSE9I+yqCkvRcWdfO1r5b/laH9t6ez+2GNI/jgPEdHz8PT0hEQi4WVvHWKhJKJqYWMpg2s96yd+jq1XgPbXt/auQGXJHZRePoaSMwcAABJLa1i37fP496MUZ0+dBB/4RUTPw87ODm5ubiyUOsRCSUTVxs/d6Yn7UNbuORIWDVoCAEpOp+PKf8Ygf+M/oXlQBkikcBgwA2a17B79Zo0aBSfT0alTJ7Ro0QJvvPEGfvzxR6jVXFNJRE/HG3N0i4WSiKrNmG6uj92HEgCkFlZoMPoj2PcMh6yuM2Amg9TSBlYtOqPBqEWPfEqOlkSKPYr3kZycjEGDBmH9+vXo3bs3XFxc8MorryAlJQUPHjyohq+KiIzBw0LJKxy6IdHwT5KIqtG4H47g4MXCJxbL52UmlaBnCwesieim/Zharcbhw4cRExMDpVKJy5cvo27duggKCkJYWBj69+8PKysrnWUgIsO2c+dODBkyBJcuXUKzZs1ExzF4LJREVK3yikoQ8GUaynS4vY+lTIqU2X3R5DFrNDUaDY4dOwalUomYmBhkZ2fD1tYWgwcPhlwux+DBg2Fn95hL6URkEq5duwYXFxfExsYiJCREdByDx0veRFStmtSzxgdBHjo95r+CPB5bJgFAIpGgY8eOWLhwIU6dOoVTp07hnXfewYULFzBy5EjUr18fQUFBWLlyJQoLC3WajYgMQ6NGjVC/fn2uo9QRTiiJqEZ8s/ccPk86W+XjvBnojhl+bi/8/suXLyM2NhZKpRI//vgjpFIp+vXrh7CwMISEhKBRo0ZVzkhEhiEwMBDW1taIi4sTHcXgsVASUY3ZmJmLBQlZqFBrnmtNpZlUAplUgn8FeSDcx1VneW7cuIH4+HjExMRg7969qKysRI8ePSCXyyGXy9G8eXOdnYuI9M9bb72FzZs34/Lly6KjGDwWSiKqUXlFJZgXexLp5wtgJpU8sVg+fL2PmyMWhXo+8TJ3VRUVFWH79u1QKpXYvXs37t+/j44dO2rLZbt27art3EQkxvr16zFmzBgUFRWhbt26T38DPRYLJREJce7mPaw7kou9Z/ORW1jy56d3QwLA1cEafq2dMLa7K9ycavYGmuLiYiQmJkKpVGL79u0oLi5GmzZttOWyU6dOkDzlGeNEpP9OnToFDw8P7N27F/369RMdx6CxUBKRcKqyClwuVKG8Qg0LmRTNHGxgYykTHQsAcP/+faSmpiImJgbx8fEoKiqCq6sr5HI5wsLC0KNHD5iZmYmOSUQvoKKiAnZ2dvjoo48wa9Ys0XEMGgslEdEzqqiowP79+6FUKqFUKnH9+nU0aNAAISEhkMvl8PPzg7m5ueiYRPQcunbtinbt2mHlypWioxg0FkoiohegVqtx5MgR7V6Xly5dQp06dRAUFAS5XI7AwEDUqlVLdEwieorIyEhkZGRw+6AqYqEkIqoijUaDEydOaJ/Sk5WVBRsbGwwaNAhhYWEYPHgw7O3tRcckokf49ttvMWvWLBQXF8PCwkJ0HIPFQklEpGNnzpxBbGwsYmJicPToUVhYWKB///6Qy+UICgqCo6Oj6IhE9IeDBw+iV69e+OWXX+Dt7S06jsFioSQiqka5ubnajdTT09MhlUrRt29fyOVyhISEwMXFRXREIpN279491K5dG8uXL8fEiRNFxzFYLJRERDXk5s2biI+Ph1KpRGpqKioqKtC9e3ftdkQtW7YUHZHIJLVu3RqDBw/GkiVLREcxWCyUREQC3Lp1Czt27EBMTAx27dqF+/fvo0OHDtpy6eHhwb0uiWrIiBEjkJ+fj3379omOYrBYKImIBFOpVNi1axeUSiW2bduGe/fuoXXr1tpy2aVLF5ZLomq0aNEifPrpp7h16xb/rr0gFkoiIj1SVlaG1NRUKJVKxMXFobCwEE2aNEFoaCjCwsLQq1cvbqROpGM7d+7EkCFDcOnSJTRr1kx0HIPEQklEpKcqKipw4MABxMTEIDY2FlevXkX9+vW1G6m/9NJL3OaESAeuXbsGFxcXxMbGIiQkRHQcg8RCSURkANRqNTIzM7UbqV+4cAG1a9fGsGHDIJfLMWDAAFhbW4uOSWSQNBoNGjRogFdeeQXvv/++6DgGiYWSiMjAaDQanDx5UvsIyJMnT8La2hqDBg2CXC7HkCFDULt2bdExiQxKYGAgrK2tERcXJzqKQWKhJCIycOfOndNupJ6RkQFzc3MEBARALpcjODgY9evXFx2RSO+99dZb2Lx5My5fviw6ikFioSQiMiJ5eXmIi4uDUqnE/v37AQC+vr6Qy+UIDQ1F48aNBSck0k/r16/HmDFjUFRUhLp164qOY3BYKImIjFR+fj4SEhKgVCqRkpKCBw8eoFu3btrtiNzc3ERHJNIbp06dgoeHB/bu3Yt+/fqJjmNwWCiJiEzAnTt3sH37diiVSiQmJqK0tBSenp4ICwuDXC5H+/btuf8embTKykrY2dlh0aJFmDVrlug4BoeFkojIxJSUlGD37t3ajdTv3LkDNzc37eTSx8cHUqlUdEyiGtetWze0bdsWK1euFB3F4LBQEhGZsPLycuzZs0e7kfpvv/2Gxo0bIzQ0FHK5HL1794ZMJhMdk6hGREVF4ciRIzh27JjoKAaHhZKIiAD8fsnvwIED2u2Irly5AkdHx79spG5paSk6JlG1+e677zBz5kwUFxfzoQHPiYWSiIj+h0ajwdGjR7UbqZ87dw729vYYOnQo5HI5Bg4cCBsbG9ExiXTq0KFD6NmzJ3755Rd4e3uLjmNQWCiJiOiJNBoNsrKytJPL48ePo1atWhg4cCDkcjmGDh2KOnXqiI5JVGXFxcWwt7fH8uXLMXHiRNFxDAoLJRERPZfz588jNjYWSqUShw8fhrm5Ofz9/bUbqTs5OYmOSPTC3N3dMWjQICxZskR0FIPCQklERC/s6tWr2nKZlpYGAOjduzfCwsIQGhqKJk2aCE5I9HzCw8Nx8+ZN7Nu3T3QUg8JCSUREOlFQUKDdSD05ORnl5eXw8fHRbkfUunVr0RGJnuqjjz7CJ598glu3bnFv1ufAQklERDp3584d7Ny5E0qlEjt37kRJSQk8PDy0G6l7eXnxH2vSS4mJiRg8eDAuXbqEZs2aiY5jMFgoiYioWpWWlmo3Uk9ISMCdO3fQokUL7eSyW7du3Eid9Mb169fh7OwMpVKJ0NBQ0XEMBgslERHVmPLycuzbtw8xMTGIi4tDfn4+nJ2dtRup+/r6ciN1Ekqj0aBhw4aYNm0aPvjgA9FxDAYLJRERCVFZWYmDBw9qtyPKzc2Fg4MDgoODIZfLERAQwI3USYgBAwbAysoK8fHxoqMYDBZKIiISTqPR4KefftJupH727FnY2dlhyJAhCAsLw8CBA2Frays6JpmIt99+Gxs3bkROTo7oKAaDhZKIiPSKRqNBdnY2YmJioFQqcezYMVhZWWHAgAGQy+UYNmwY6tatKzomGbENGzZg9OjRKCwsRL169UTHMQgslEREpNcuXryo3evy4MGDkMlkeOmll7QbqTds2FB0RDIy2dnZaNeuHfbs2QM/Pz/RcQwCCyURERmMa9euIS4uDkqlEvv27YNarUavXr20G6k3bdpUdEQyApWVlbCzs8OHH36I2bNni45jEFgoiYjIIBUWFmLbtm2IiYlBUlISysvL0blzZ8jlcoSFhcHd3V10RDJg3bp1Q5s2bbBq1SrRUQwCCyURERm8e/fuaTdS37FjB1QqFdq1a6fd69Lb25sbqdNziYqKwuHDh3H8+HHRUQwCCyURERmV0tJSJCcnazdSv3XrFpo3b64tl927d+dG6vRU3333Hf7xj3+guLiY21c9AxZKIiIyWg8ePEBaWhpiYmIQGxuLmzdvolGjRggJCUFYWBh8fX1hbm4uOibpoUOHDqFnz574+eef0bFjR9Fx9B4LJRERmYTKykocPnxYu9dlTk4O6tWrh6CgIMjlcvTv3x9WVlaiY5KeKC4uhr29PX744QdMmjRJdBy9x0JJREQmR6PR4JdfftE+pSc7Oxu2trYYMmQI5HI5Bg0aBDs7O9ExSTB3d3cMHDgQX331legoeo+FkoiITF52dra2XP7888+wtLREYGAgwsLCMGzYMG5ubaLCw8Nx48YNpKWliY6i91goiYiI/uTy5cuIjY1FTEwMDh48CKlUCj8/P8jlcoSEhKBRo0aiI1IN+eijj/Dxxx/j9u3b3CXgKVgoiYiIHuP69euIj4+HUqnEnj17oFar0bNnT8jlcoSGhqJ58+aiI1I1SkxMxODBg3Hx4kX+t34KFkoiIqJnUFRUhG3btkGpVGL37t0oKytDx44dERYWBrlcjrZt24qOSDp2/fp1ODs7Q6lUIjQ0VHQcvcZCSURE9JyKi4uRmJiImJgY7NixA8XFxWjTpo12r8tOnTrxEqkR0Gg0aNiwIaZNm4YPPvhAdBy9xkJJRERUBffv30dKSgqUSiXi4+NRVFSEpk2bastljx49YGZmJjomvaABAwbAysoK8fHxoqPoNRZKIiIiHXnw4AH2798PpVKJ2NhYXL9+HQ0aNNBupN6vXz9upG5g3n77bWzcuBE5OTmio+g1FkoiIqJqoFarceTIEcTExECpVOLSpUuoU6eOdiP1wMBA1KpVS3RMeooNGzZg9OjRKCws5PZRT8BCSUREVM00Gg2OHz+ufUrPqVOnYGNjg8GDB0Mul2Pw4MGwt7cXHZMeITs7G+3atcOePXvg5+cnOo7eYqEkIiKqYadPn0ZsbCyUSiWOHj0KCwsL9O/fH2FhYQgKCoKDg4PoiPSHyspK2NnZ4cMPP8Ts2bNFx9FbLJREREQC5eTkaMvlgQMHIJVK0bdvX+1el87OzqIjmrzu3bvD3d0dq1atEh1Fb7FQEhER6YmbN29qN1JPTU1FRUUFevToob1jvEWLFqIjmqRp06bh0KFDOH78uOgoeouFkoiISA/dunUL27dvh1KpxK5du3D//n14e3try2W7du2412UN+f777/Haa6+huLgYlpaWouPoJRZKIiIiPadSqbBr1y7ExMRg+/btuHfvHlq3bg25XI6wsDB07tyZ5bIaHT58GD169MDPP/+Mjh07io6jl1goiYiIDEhZWRlSU1OhVCoRFxeHwsJCNGnSRDu57NWrFzdS1zGVSgU7Ozv88MMPmDRpkug4eomFkoiIyEBVVFQgPT0dSqUSSqUS165dg5OTE0JCQiCXy+Hn5wcLCwvRMY1CmzZtMGDAAHz11Veio+glFkoiIiIjoFarkZGRod3r8uLFi6hduzaGDRuGsLAwBAYGwtraWnRMgzVy5Ehcv34daWlpoqPoJRZKIiIiI6PRaHDy5Eltufz1119hbW2NQYMGQS6XY+jQodxI/Tl9/PHH+Oijj3D79m2uV30EFkoiIiIjd/bsWe1elxkZGbCwsEBAQADkcjmCgoJQv3590RH13q5duzBo0CBcvHgRzZs3Fx1H77BQEhERmZC8vDxtuUxPTwcA7UbqISEhaNy4seCE+unGjRto1KgRlEolQkNDRcfROyyUREREJio/Px8JCQmIiYlBamoqHjx4gG7dumnvGHdzcxMdUa80bNgQUVFR+OCDD0RH0TsslERERITbt29jx44dUCqVSExMRGlpKby8vLTlsn379ia/dnDgwIGwtLREfHy86Ch6h4WSiIiI/kKlUmH37t1QKpXYtm0b7t69i1atWmnLpY+Pj0mWy7lz52LDhg3IyckRHUXvsFASERHRY5WXl/9lI/WCggI0btxYWy579+5tMhupb9y4EaNGjUJhYSHq1asnOo5eYaEkIiKiZ1JRUYEff/xRu5H6lStXUL9+fQQHB0Mul+Oll14y6mddnz59Gm3btsWePXvg5+cnOo5eYaEkIiKi56ZWq3H06FHtXpfnz5+Hvb09hg0bBrlcjgEDBsDGxkZ0TJ2qrKyEnZ0d/v3vf+P1118XHUevsFASERFRlWg0Gvz666/ayeWJEydQq1YtDBw4ULuRep06dUTH1Inu3bujdevWWL16tegoeoWFkoiIiHTq/PnziI2NRUxMDI4cOQJzc3P4+/tDLpcjODgYTk5OoiO+sGnTpuHgwYM4ceKE6Ch6hYWSiIiIqs2VK1cQFxcHpVKpfQ52nz59IJfLERoaiiZNmghO+Hy+//57vPbaa7h37x6srKxEx9EbLJRERERUI3777TckJCRAqVQiOTkZDx48gI+PD8LCwiCXy9GqVSvREZ/q8OHD6NGjB3766Sd06tRJdBy9wUJJRERENe7OnTvYuXMnYmJikJiYiJKSErRv3167HZGXl5de7nWpUqlgZ2eHZcuWYfLkyaLj6A0WSiIiIhKqpKQESUlJUCqVSEhIwJ07d9CyZUttuezatSukUqnomFpt2rRBYGAg/vOf/4iOojdYKImIiEhvlJeXY+/evdqN1PPz8+Hi4oLQ0FDI5XL06dMHMplMaMaRI0fiyo3fEL1eifIKNSxkUjRzsIGNpdhcIrFQEhERkV6qrKzEwYMHERMTA6VSiby8PDg4OCA4OBhhYWHw9/ev0Y3Uz928h3VHcqE8cgZ3Ki3+ckleAsC1njX83J0wppsrWjWwq7Fc+oCFkoiIiPSeRqPBTz/9pN1I/ezZs7Czs8PQoUMhl8sxcOBA2NraVsu584pKMC/2JNLPF8BMKkGl+vHV6eHrfdwcsSjUE03qWVdLJn3DQklEREQGRaPR4NSpU9qN1I8dOwYrK6u/bKRet25dnZxrY2YuFiRkoUKteWKR/DszqQQyqQQfBHlgpI+rTrLoMxZKIiIiMmgXL17UlstDhw5BJpPhpZdeQlhYGIKDg9GgQYMXOu43e8/h86SzVc43J7A1XvXT/y2RqoKFkoiIiIzGtWvXtBup79u3D2q1Gr1799ZupN60adNnOs7GzFzMVZ7UWa5P5J4IN+JJJQslERERGaWCggJs27YNSqUSSUlJKC8vR5cuXbTbEbm7uz/yfXlFJQj4Mg1lFWqdZbGUSZEyu6/RrqlkoSQiIiKjd/fuXezcuRNKpRI7d+6ESqVCu3bttE/p6dChg/au7XE/HMHBi4WPXTOpqXyA2/vXouz6WZTfOA9NeSkAwLJJezQc8/Ej32MmlaBnCwesiehWPV+gYCyUREREZFJKS0uRnJyMmJgYJCQk4Pbt22jevDnkcjm6BYbgzb13nvh+9f1i5C0Z+T8ff1KhfChlti/cnIxvSyEWSiIiIjJZDx48wL59+6BUKhEbG4tyz2DYdRoCidTsse9Rl9/Hrb3LYdmo1e+/TokG8PRCaSaVYFy3png/yEPnX4doLJRERERE+H0j9R6LkpBf8uxrJ0sv/oT8zQsAPNuEsqmDNdLm+FUppz7SnwdjEhEREQlUWqHBb89RJl9EbmEJVGUV1XoOEVgoiYiIiADkFKpQ3ZdtNQAuF6qq+Sw1j4WSiIiICEC5DrcJ0ofz1CQWSiIiIiIAFrKaqUU1dZ6aZHxfEREREdELaOZgA0k1n0Pyx3mMDQslEREREQAbSxlcn/FJNpUld1BZcgfqspL//6C68v8//uD+I9/n6mANG0uZLuLqFeP7ioiIiIhekJ+7E9YcyXnsU3IeuvKfMf/zsbKr2dqP1+41CnX6/PVzzKQS+LV20l1YPcIJJREREdEfxnRzfWqZfFGVag3GdnetlmOLxgklERER0R9aNbBDHzfHJz7LGwCazt3+XMd9+CxvY3zsIsAJJREREdFfLAr1hEyq29tzZFIJFoV66vSY+oSFkoiIiOhPmtSzxgc6ft72v4I80OQZb/gxRCyURERERH8z0scVcwJb6+RYbwa6I9zHONdOPiTRaDTV/ZQhIiIiIoO0MTMXCxKyUKHWPNfNOmZSCWRSCf4V5GH0ZRJgoSQiIiJ6oryiEsyLPYn08wUwk0qeWCwfvt7HzRGLQj2N+jL3n7FQEhERET2DczfvYd2RXOw9m4/cwhL8uUBJ8Pum5X6tnTC2u6vR3s39OCyURERERM9JVVaBy4UqlFeoYSGTopmDjVE+AedZsVASERERUZXwLm8iIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqhIWSiIiIiKqEhZKIiIiIqoSFkoiIiIiqpL/AwQsOHKXFj0iAAAAAElFTkSuQmCC", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "graph = nx.Graph()\n", "nx.add_path(graph, [0, 1])\n", "nx.add_path(graph, [1, 2])\n", "nx.add_path(graph, [2, 3])\n", "nx.add_path(graph, [3, 4])\n", "nx.add_path(graph, [0, 4])\n", "nx.add_path(graph, [0, 2])\n", "nx.draw(graph, with_labels=True, font_weight='bold')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As shown in the preceding figure, a graph structure consisting of five vertices and six edges is obtained.\n", "\n", "Next we use the exhaustive method to see the number of cutting edges for all cases." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "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 graph.nodes:\n", " print('one size:', [i], 'cut=', nx.cut_size(graph, [i])) # All cases with 1 node in one group and 4 nodes in the other group\n", " for j in range(i):\n", " print('one size:', [i, j], 'cut=', nx.cut_size(graph, [i, j])) # All cases with 2 nodes in one group and 3 nodes in the other group" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "From the above results, it can be seen that the maximum number of cutting edges obtained by the exhaustive method is 5. If a distinction is made between the left and right of the node grouping, there are a total of 4 grouping methods that maximize the number of cutting edges, i.e., there are 4 simplex solutions to the problem.\n", "\n", "## The Process of QAQA Algorithm\n", "\n", "1. Build a QAOA quantum circuit, where the ansatz circuit contains parameters that can be trained\n", "2. Initialize the parameters in the circuit\n", "3. Run this quantum circuit and get the quantum state $|\\psi\\rangle$\n", "4. Compute the expected value $\\langle\\psi|H_C|\\psi\\rangle$ of the target Hamiltonian $H_C$\n", "5. Based on the results of step 4, use the Adam optimizer to optimize the parameters in the circuit\n", "6. Repeat steps 3-5 until the results in step 4 are basically unchanged\n", "7. Based on the result of step 4, the approximate solution of the target problem is calculated\n", "\n", "In this process, steps 2-6 can all be implemented by packages and functions available in MindSpore and MindSpore Quantum, so we will focus on step 1: building the quantum circuit.\n", "\n", "![Flowchart](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/docs/mindquantum/docs/source_en/images/QAOA_Flowchart.png)\n", "\n", "## Setting up a QAOA Quantum Circuit\n", "\n", "As mentioned previously, we need to combine the Hamiltonian quantities corresponding to the problem:\n", "\n", "$$\n", "H_C=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2\n", "$$\n", "\n", "Minimization to find the solution of the problem, which means we have to find the ground state of that Hamiltonian quantity. We can use quantum adiabatic evolution to make the system first on the ground state of some simple Hamiltonian $H_B$, and then make the simple Hamiltonian $H_B$ evolve adiabatically and slowly to some complex Hamiltonian $H_C$. According to the adiabatic theorem, the system will always remain on the ground state of the Hamiltonian, and finally reach the ground state of the complex Hamiltonian $H_C$.\n", "\n", "The quantum circuit we are going to build is using the above idea, choosing the initial simple Hamiltonian quantity as:\n", "\n", "$$\n", "H_B=\\sum_i -X_i\n", "$$\n", "\n", "Prepare the quantum circuit to the ground state $|s\\rangle=|+\\rangle^{\\otimes n}$ of $H_B$, which can be achieved here by acting [Hadamard](https://www.mindspore.cn/mindquantum/docs/en/master/core/gates/mindquantum.core.gates.HGate.html) gate on all quantum bits. Then the ansatz circuits are connected, and by continuously optimizing the parameters, the ansatz circuits can be made closer to the real adiabatic evolution, and the finally obtained quantum circuits can be regarded as simulating a real adiabatic evolution.\n", "\n", "### ansatz Circuit\n", "\n", "In the quantum adiabatic evolution, the initial Hamiltonian quantities are first selected\n", "\n", "$$\n", "H_B=\\sum_i -X_i\n", "$$\n", "\n", "Put the system in the $H_B$ ground state $|s\\rangle=|+\\rangle^{\\otimes n}$. Then slowly act on the following time-dependent Hamiltonian:\n", "\n", "$$\n", "H(t)=(1-\\frac{t}{T})H_B+(\\frac{t}{T})H_C\n", "$$\n", "\n", "Notice that $H(T)=H_C$ when $t=T$. When the chosen $T$ is large enough (satisfying the adiabatic condition), the system will always be on the instantaneous ground state of $H(t)$, when the quantum state of the system will evolve adiabatically from the ground state $|\\psi (0)\\rangle$ of the initial Hamiltonian $H_B$ to the ground state $|\\psi (T)\\rangle$ of the target Hamiltonian $H_C$, i.e.\n", "\n", "$$\n", "|\\psi (T)\\rangle=\\mathcal{T}e^{-i\\int^{T}_{0} H(t)dt}|\\psi(0)\\rangle\n", "$$\n", "\n", "That is, the ansatz circuit needs to model the evolution process $\\mathcal{T}e^{-i\\int^{T}_{0} H(t)dt}$. Next we will make some approximations and simplifications to this equation to make it into a form that can be implemented in quantum circuits.\n", "\n", "Considering the following trotter formula:\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", "Omitting the $O(\\Delta t^2)$ term, we obtain:\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", "Let $\\beta_l=(1-t_l/T)\\Delta t$, $\\gamma_l=t_l\\Delta t/T$, and take $N$ as a finite large integer, that is, the ansatz of QAOA is obtained:\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", "Thus the ansatz line we need to build consists of $U_C(\\gamma)$ and $U_B(\\beta)$ which alternate the two unitary transformations, where $U_C(\\gamma)=e^{-i\\frac{\\gamma}{2} \\sum_{\\langle i,j\\rangle}Z_i Z_j}$ can be implemented by the [Rzz](https://www.mindspore.cn/mindquantum/docs/en/master/core/gates/mindquantum.core.gates.Rzz.html) gate. $U_B(\\beta)=e^{i\\beta \\sum_i X_i}$ is then equivalent to acting a [RX](https://www.mindspore.cn/mindquantum/docs/en/master/core/gates/mindquantum.core.gates.RX.html) revolving gate on each quantum bit, with $\\gamma$ and $\\beta$ as trainable parameters.\n", "\n", "Build the quantum circuit corresponding to $U_C(\\gamma)$:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def build_hc(g, para):\n", " hc = Circuit() # Build quantum circuit\n", " for i in g.edges:\n", " hc += Rzz(para).on(i) # Act Rzz gate on each edge of the diagram\n", " hc.barrier() # Add Barrier for easy display of circuits\n", " return hc" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Display the circuits:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "q0: q1: q2: q3: q4: Rzz gamma Rzz gamma Rzz gamma Rzz gamma Rzz gamma Rzz gamma " ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circuit = build_hc(graph, 'gamma')\n", "circuit.svg()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Build the quantum circuits corresponding to $U_B(\\beta)$:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "def build_hb(g, para):\n", " hb = Circuit() # Build quantum circuit\n", " for i in g.nodes:\n", " hb += RX(para).on(i) # Act RX gate on each node\n", " hb.barrier() # Add Barrier for easy display of circuits\n", " return hb" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Display the circuits:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "q0: q1: q2: q3: q4: RX beta RX beta RX beta RX beta RX beta " ], "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circuit = build_hb(graph, 'beta')\n", "circuit.svg()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The ansatz circuit that implements a layer of unitary transform $U_B(\\beta) U_C(\\gamma)$ is shown below:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "q0: q1: q2: q3: q4: Rzz gamma Rzz gamma Rzz gamma Rzz gamma Rzz gamma Rzz gamma RX beta RX beta RX beta RX beta RX beta " ], "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circuit = build_hc(graph, 'gamma') + build_hb(graph, 'beta')\n", "circuit.svg()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In order to make the final optimization result accurate enough, we need to repeat the quantum circuit several times, so we build a multilayer training network by the following function:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "# g is the graph of the max-cut problem, and p is the number of layers of the ansatz circuit\n", "def build_ansatz(g, p):\n", " circ = Circuit() # Build quantum circuit\n", " for i in range(p):\n", " # Add the circuit corresponding to Uc, with parameters noted as g0, g1, g2...\n", " circ += build_hc(g, f'g{i}')\n", "\n", " # Add the circuit corresponding to Ub, with parameters noted as b0, b1, b2...\n", " circ += build_hb(g, f'b{i}')\n", " return circ" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Hamiltonian quantity $H_C=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2$ corresponding to construction graph(ignoring the constant terms and coefficients)." ] }, { "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]}') # Generate hamiltonian Hc\n", " return ham" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generating a Complete Quantum Circuit and the Hamiltonian Corresponding to the Graph\n", "\n", "In this example, `p = 4` is selected, indicating that the four-layer QAOA quantum circuit is used. `ansatz` is a quantum circuit for solving the problem, and `init_state_circ` is a quantum circuit for preparing a quantum state on a uniformly superposed state." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "q0: q1: q2: q3: q4: H H H H H Rzz g0 Rzz g0 Rzz g0 Rzz g0 Rzz g0 Rzz g0 RX b0 RX b0 RX b0 RX b0 RX b0 Rzz g1 Rzz g1 Rzz g1 Rzz g1 Rzz g1 Rzz g1 RX b1 RX b1 RX b1 RX b1 RX b1 q0: q1: q2: q3: q4: Rzz g2 Rzz g2 Rzz g2 Rzz g2 Rzz g2 Rzz g2 RX b2 RX b2 RX b2 RX b2 RX b2 Rzz g3 Rzz g3 Rzz g3 Rzz g3 Rzz g3 Rzz g3 RX b3 RX b3 RX b3 RX b3 RX b3 " ], "text/plain": [ "" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "p = 4\n", "ham = Hamiltonian(build_ham(graph)) # Generate Hamiltonian quantities\n", "init_state_circ = UN(H, graph.nodes) # Generate uniform superposition states, i.e., act H-gate on all quantum bits\n", "ansatz = build_ansatz(graph, p) # Generate ansatz circuit\n", "circ = init_state_circ + ansatz # Combine the initialized circuit and the ansatz circuit into one circuit\n", "circ.svg(width=1200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Approach One: Use Traditional Optimization Method\n", "\n", "### Generating Gradient Operator\n", "\n", "First, we use a simulator to generate computational operators for calculating expectations and gradients of QAOA variational quantum circuit." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "sim = Simulator('mqvector', circ.n_qubits)\n", "grad_ops = sim.get_expectation_with_grad(ham, circ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`grad_ops` is a operator to calculate the expectation and gradient. For example, we can use this operator to calculate the expectation and gradient at `p0`." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Expectation Value: [[2.2839928+4.88195544e-17j]]\n", "Expectation Value Shape: (1, 1)\n", "Gradient: [[[ 0.60966156+0.j -0.50977303+0.j 1.96920626+0.j -1.89443604+0.j\n", " 0.9840882 +0.j -1.85238736+0.j 1.27387126+0.j -0.03135037+0.j]]]\n", "Gradient Shape: (1, 1, 8)\n" ] } ], "source": [ "import numpy as np\n", "\n", "rng = np.random.default_rng(10)\n", "p0 = rng.random(size=len(circ.params_name)) * np.pi * 2 - np.pi\n", "f, g = grad_ops(p0)\n", "print('Expectation Value: ', f)\n", "print('Expectation Value Shape: ', f.shape)\n", "print('Gradient: ', g)\n", "print('Gradient Shape: ', g.shape)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here, we get the expectation values as an $(m=1,n=1)$-dimensional array, where $m$ represents how many data points were encoded into a quantum state during this computation. Since QAOA tasks do not require an encoder, the default value for $m$ is 1. Meanwhile, $n$ represents how many Hamiltonian expectation values were computed in this operation (MindQuantum supports parallel processing of multiple Hamiltonians). In this case, we only calculate the expectation value for `ham`, so $n=1$. Similarly, for the gradient values, their dimensions are $(m=1,n=1,k=8)$, where the additional dimension $k=8$ represents the number of ansatz variational parameters in the entire circuit.\n", "\n", "We introduce the second-order optimizer BFGS from scipy to optimize the Max-Cut problem. To do this, we first define the function to be optimized:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2.2839927952206174,\n", " array([ 0.60966156, -0.50977303, 1.96920626, -1.89443604, 0.9840882 ,\n", " -1.85238736, 1.27387126, -0.03135037]))" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0604\n", "global step\n", "step = 0\n", "\n", "\n", "def fun(p, grad_ops):\n", " global step\n", " f, g = grad_ops(p)\n", " f = np.real(f)[0, 0]\n", " g = np.real(g)[0, 0]\n", " step += 1\n", " if step % 10 == 0:\n", " print(f\"train step: {step} , cut: [{(len(graph.edges) - f) / 2}]\")\n", " return f, g\n", "\n", "\n", "fun(p0, grad_ops)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Training Process\n", "\n", "`BFGS` is a second-order optimizer that performs well. By specifying `jac=True`, you are telling the optimizer that the function to be optimized will return both the function value and the gradient at the same time. If set to `False`, the optimizer will use finite differences to approximate the gradient on its own, which can be computationally expensive." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "train step: 10 , cut: [3.5103176644442238]\n", "train step: 20 , cut: [3.868695972469235]\n", "train step: 30 , cut: [4.194720830469368]\n", "train step: 40 , cut: [4.649109856438022]\n", "train step: 50 , cut: [4.752059940467564]\n", "train step: 60 , cut: [4.777656304269479]\n", "train step: 70 , cut: [4.820166856240324]\n", "train step: 80 , cut: [4.825019042509073]\n", "train step: 90 , cut: [4.826176814772741]\n" ] } ], "source": [ "from scipy.optimize import minimize\n", "\n", "step = 0\n", "res = minimize(fun, p0, args=(grad_ops, ), method='bfgs', jac=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At the optimal solution, the variational parameters obtained from training are:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'g0': -0.7937405245633787, 'b0': 0.24377670109607055, 'g1': 1.6118673525265843, 'b1': -2.0908435247717794, 'g2': -0.21919996577600231, 'b2': -1.955308095101507, 'g3': 1.2663769844140762, 'b3': 2.752892656008665}\n" ] } ], "source": [ "print(dict(zip(circ.params_name, res.x)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Approach two: Use MindSpore to Train Quantum Neural Network\n", "\n", "### Building a Quantum Neural Network to Be Trained\n", "\n", "This problem does not require a coding-layer quantum circuit, so we use [MQAnsatzOnlyLayer](https://www.mindspore.cn/mindquantum/docs/en/master/framework/layer/mindquantum.framework.MQAnsatzOnlyLayer.html) as a quantum neural network to be trained and an [Adam](https://www.mindspore.cn/docs/en/master/api_python/nn/mindspore.nn.Adam.html) optimizer." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "import mindspore as ms\n", "\n", "ms.set_context(mode=ms.PYNATIVE_MODE, device_target=\"CPU\")\n", "\n", "sim = Simulator('mqvector', circ.n_qubits) # Create a simulator, backend uses 'mqvector' and can simulate 5 bits (the number of bits contained in the 'circ' line)\n", "\n", "# Obtain the operator to calculate the expectation and gradient of the variational quantum circuit\n", "grad_ops = sim.get_expectation_with_grad(ham, circ)\n", "\n", "# Generate the neural network to be trained\n", "net = MQAnsatzOnlyLayer(grad_ops)\n", "\n", "# Set the Adam optimizer for all trainable parameters in the network with a learning rate of 0.05\n", "opti = nn.Adam(net.trainable_params(), learning_rate=0.05)\n", "\n", "# One-step training of neural networks\n", "train_net = nn.TrainOneStepCell(net, opti)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Training and Displaying Results" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "train step: 0 , cut: [3.0004191]\n", "train step: 10 , cut: [4.440877]\n", "train step: 20 , cut: [4.699215]\n", "train step: 30 , cut: [4.7900705]\n", "train step: 40 , cut: [4.8516107]\n", "train step: 50 , cut: [4.8745494]\n", "train step: 60 , cut: [4.89936]\n", "train step: 70 , cut: [4.9250917]\n", "train step: 80 , cut: [4.938618]\n", "train step: 90 , cut: [4.937195]\n", "train step: 100 , cut: [4.9391575]\n", "train step: 110 , cut: [4.939012]\n", "train step: 120 , cut: [4.9392276]\n", "train step: 130 , cut: [4.939231]\n", "train step: 140 , cut: [4.9392524]\n", "train step: 150 , cut: [4.9392548]\n", "train step: 160 , cut: [4.9392567]\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", " # Train the neural network for one step and calculate the result (number of cut edges). Note: Every time 'train_net()' is run, the neural network is trained for one step\n", " cut = (len(graph.edges) - train_net()) / 2\n", " if i % 10 == 0:\n", " print(\"train step:\", i, \", cut:\", cut) # For every 10 training steps, print the current number of training steps and the current number of cutting edges obtained" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Based on the above training results, we find that the number of cut edges corresponding to the ground state energy of Hamiltonian is close to 5.\n", "\n", "### Optimal Parameter\n", "\n", "Previously, we obtained the optimal values of the parameters in the quantum circuit by training. In the following, we extract the optimal parameters and store them as dictionary types, which correspond to the parameters named in the previous circuit." ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'g0': 0.44889548, 'b0': -1.1389917, 'g1': 0.9062595, 'b1': -0.94462746, 'g2': 1.0675684, 'b2': -0.6775048, 'g3': 1.1679738, 'b3': -0.38228452}\n" ] } ], "source": [ "pr = dict(zip(ansatz.params_name, net.weight.asnumpy())) # Obtain circuit parameters\n", "print(pr)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Probabilistic Graph\n", "\n", "We substitute the optimal parameters into the quantum circuit and draw the probability distribution of the final quantum state under the computed vector by sampling the quantum circuit 1000 times:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Shots:\n", " 1000 Keys: q4 q3 q2 q1 q0 0.0 0.05 0.1 0.151 0.201 0.251 00000 1 00001 1 00101 14 01001 251 01010 2 01011 233 01100 1 01101 1 01110 2 10010 2 10100 250 10101 2 10110 222 11010 11 11011 1 11100 2 11101 1 11110 1 11111 2 probability " ], "text/plain": [ "" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# pylint: disable=W0104\n", "circ.measure_all() # Add measurement gates for all bits in the circuit\n", "sim.sampling(circ, pr=pr, shots=1000).svg() # Run the circuit 1000 times and print the results\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "According to the probability distribution diagram, the Max-Cut problem has four degenerate solutions, and the probability corresponding to each solution is about 25%.\n", "\n", "- `01001`: The vertices numbered 1, 2, and 4 are on the left, and the vertices numbered 0 and 3 are on the right.\n", "- `10110`: The vertices numbered 0 and 3 are on the left, and the vertices numbered 1, 2, and 4 are on the right.\n", "- `01011`: The vertices numbered 2 and 4 are on the left, and the vertices numbered 0, 1, and 3 are on the right.\n", "- `10100`: The vertices numbered 0, 1, and 3 are on the left, and the vertices numbered 2 and 4 are on the right.\n", "\n", "It can be found that the above results are consistent with the previous results obtained by the exhaustive method.\n", "\n", "## Summary\n", "\n", "We use the quantum approximation optimization algorithm to solve the Max-Cut problem and obtain the Max-Cut solution corresponding to the graph in the case." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", " \n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", " \n", " \n", "\n", "\n", "
SoftwareVersion
mindquantum0.9.11
scipy1.10.1
numpy1.21.6
SystemInfo
Python3.9.13
OSLinux x86_64
Memory16.62 GB
CPU Max Thread16
DateMon Oct 30 20:17:07 2023
\n" ], "text/plain": [ "" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from mindquantum.utils.show_info import InfoTable\n", "\n", "InfoTable('mindquantum', 'scipy', 'numpy')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## References\n", "\n", "[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. [A Quantum Approximate Optimization Algorithm](https://arxiv.org/pdf/1411.4028.pdf)" ] } ], "metadata": { "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.17" } }, "nbformat": 4, "nbformat_minor": 2 }