Q Quleaf 已提交 5月 18, 2021 1 2 3 4 5 6 7 8 { "cells": [ { "cell_type": "markdown", "source": [ "# Travelling Salesman Problem\n", "\n", " Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. "  Q Quleaf 已提交 11月 15, 2021 9 10  ], "metadata": {}  Q Quleaf 已提交 5月 18, 2021 11 12 13 14 15 16 17 18  }, { "cell_type": "markdown", "source": [ "## Overview\n", "\n", "One of the most famous NP-hard problems in combinatorial optimization, the travelling salesman problem (TSP) considers the following question: \"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?\" \n", "\n",  Q Quleaf 已提交 8月 12, 2021 19  "This question can also be formulated in the language of graph theory. Given a weighted undirected complete graph $G = (V,E)$, where each vertex $i \\in V$ corresponds to city $i$ and the weight $w_{i,j}$ of each edge $(i,j,w_{i,j}) \\in E$ represents the distance between cities $i$ and $j$, the TSP is to find the shortest Hamiltonian cycle in $G$, where a Hamiltonian cycle is a closed loop on a graph in which every vertex is visited exactly once. Note that because $G$ is an undirected graph, weights are symmetric, i.e., $w_{i,j} = w_{j,i}$. "  Q Quleaf 已提交 11月 15, 2021 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48  ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Use QNN to solve TSP\n", "\n", "To use QNN to solve travelling salesman problem, we need to first encode the classical problem to quantum. \n", "The encoding consists of two parts:\n", "\n", "1. The route how the salesman visits each city is encoded in quantum states -- ${\\rm qubit}_{i,t} = |1\\rangle$ corresponds to salesman visiting city $i$ at time $t$. \n", " 1. As an example, if there are two cities $\\{A,B\\}$, visiting $A$ then $B$ will be in state $|1001\\rangle$, as the salesman visits the city $A$ at time $1$ and the city $B$ at time $2$.\n", " 2. Similary, $|0110\\rangle$ means visiting $B$ then $A$.\n", " 3. Note: $|0101\\rangle$ means visiting $A$ and $B$ both at time $2$, so it is infeasible. To aviod such states, a penalty function will be used (see the next section for details.)\n", "\n", "2. The total distance is encoded in a loss function: \n", "\n", "$$\n", "L(\\psi(\\vec{\\theta})) = \\langle\\psi(\\vec{\\theta})|H_C|\\psi(\\vec{\\theta})\\rangle,\n", "\\tag{1}\n", "$$\n", "\n", "where $|\\psi(\\vec{\\theta})\\rangle$ is the output state from a parameterized quantum circuit. \n", "\n", "The details about how to encode the classical problem to quantum is given in detail in the next section. \n", "After optimizing the loss function, we will obtain the optimal quantum state. Then a decoding process will be performed to get the final route." ], "metadata": {}  Q Quleaf 已提交 5月 18, 2021 49 50 51 52  }, { "cell_type": "markdown", "source": [  Q Quleaf 已提交 11月 15, 2021 53  "### Encoding the TSP\n",  Q Quleaf 已提交 5月 18, 2021 54  "\n",  Q Quleaf 已提交 11月 15, 2021 55 56 57  "To transform the TSP into a problem applicable for parameterized quantum circuits, we need to encode the TSP into a Hamiltonian. \n", "\n", "We realize the encoding by first constructing an integer programming problem. Suppose there are $n=|V|$ vertices in graph $G$. Then for each vertex $i \\in V$, we define $n$ binary variables $x_{i,t}$, where $t \\in [0,n-1]$, such that\n",  Q Quleaf 已提交 5月 18, 2021 58 59 60 61 62 63 64  "\n", "$$\n", "x_{i, t}=\n", "\\begin{cases}\n", "1, & \\text {if in the resulting Hamiltonian cycle, vertex } i \\text { is visited at time } t\\\\\n", "0, & \\text{otherwise}\n", "\\end{cases}.\n",  Q Quleaf 已提交 11月 15, 2021 65  "\\tag{2}\n",  Q Quleaf 已提交 5月 18, 2021 66 67 68 69 70 71  "$$\n", "\n", "As there are $n$ vertices, we have $n^2$ variables in total, whose value we denote by a bit string $x=x_{1,1}x_{1,2}\\dots x_{n,n}$. Assume for now that the bit string $x$ represents a Hamiltonian cycle. Then for each edge $(i,j,w_{i,j}) \\in E$, we will have $x_{i,t} = x_{j,t+1}=1$, i.e., $x_{i,t}\\cdot x_{j,t+1}=1$, if and only if the Hamiltonian cycle visits vertex $i$ at time $t$ and vertex $j$ at time $t+1$; otherwise, $x_{i,t}\\cdot x_{j,t+1}$ will be $0$. Therefore the length of a Hamiltonian cycle is\n", "\n", "$$\n", "D(x) = \\sum_{i,j} w_{i,j} \\sum_{t} x_{i,t} x_{j,t+1}.\n",  Q Quleaf 已提交 11月 15, 2021 72  "\\tag{3}\n",  Q Quleaf 已提交 5月 18, 2021 73 74 75 76 77 78  "$$\n", "\n", "For $x$ to represent a valid Hamiltonian cycle, the following constraint needs to be met:\n", "\n", "$$\n", "\\sum_t x_{i,t} = 1 \\quad \\forall i \\in [0,n-1] \\quad \\text{ and } \\quad \\sum_i x_{i,t} = 1 \\quad \\forall t \\in [0,n-1],\n",  Q Quleaf 已提交 11月 15, 2021 79  "\\tag{4}\n",  Q Quleaf 已提交 5月 18, 2021 80 81 82 83 84 85  "$$\n", "\n", "where the first equation guarantees that each vertex is only visited once and the second guarantees that only one vertex is visited at each time $t$. Then the cost function under the constraint can be formulated below, with $A$ being the penalty parameter set to ensure that the constraint is satisfied:\n", "\n", "$$\n", "C(x) = D(x)+ A\\left( \\sum_{i} \\left(1-\\sum_t x_{i,t}\\right)^2 + \\sum_{t} \\left(1-\\sum_i x_{i,t}\\right)^2 \\right).\n",  Q Quleaf 已提交 11月 15, 2021 86  "\\tag{5}\n",  Q Quleaf 已提交 5月 18, 2021 87 88 89 90 91 92 93 94 95  "$$\n", "\n", "Note that as we would like to minimize the length $D(x)$ while ensuring $x$ represents a valid Hamiltonian cycle, we had better set $A$ large, at least larger than the largest weight of edges.\n", "\n", "We now need to transform the cost function $C(x)$ into a Hamiltonian to realize the encoding of the TSP. Each variable $x_{i,j}$ has two possible values, $0$ and $1$, corresponding to quantum states $|0\\rangle$ and $|1\\rangle$. **Note that every variable corresponds to a qubit and so $n^2$ qubits are needed for solving the TSP.** Similar as in the Max-Cut problem, we consider the Pauli $Z$ operator as it has two eigenstates, $|0\\rangle$ and $|1\\rangle$. Their corresponding eigenvalues are 1 and -1, respectively.\n", "\n", "Now we would like to consider the mapping\n", "\n", "$$\n",  Q Quleaf 已提交 11月 15, 2021 96  "x_{i,t} \\mapsto \\frac{I-Z_{i,t}}{2}, \\tag{6}\n",  Q Quleaf 已提交 5月 18, 2021 97 98  "$$\n", "\n",  Q Quleaf 已提交 8月 12, 2021 99  "where $Z_{i,t} = I \\otimes I \\otimes \\ldots \\otimes Z \\otimes \\ldots \\otimes I$ with $Z$ operates on the qubit at position $(i,t)$. Under this mapping, if a qubit $(i,t)$ is in state $|1\\rangle$, then $x_{i,t}|1\\rangle = \\frac{I-Z_{i,t}}{2} |1\\rangle = 1 |1\\rangle$, which means vertex $i$ is visited at time $t$. Also, for a qubit $(i,t)$ in state $|0\\rangle$, $x_{i,t} |0\\rangle= \\frac{I-Z_{i,t}}{2} |0\\rangle = 0|0\\rangle$.\n",  Q Quleaf 已提交 5月 18, 2021 100 101 102  "\n", "Thus using the above mapping, we can transform the cost function $C(x)$ into a Hamiltonian $H_C$ for the system of $n^2$ qubits and realize the quantumization of the TSP. Then the ground state of $H_C$ is the optimal solution to the TSP. In the following section, we will show how to use a parametrized quantum circuit to find the ground state, i.e., the eigenvector with the smallest eigenvalue.\n", "\n"  Q Quleaf 已提交 11月 15, 2021 103 104  ], "metadata": {}  Q Quleaf 已提交 5月 18, 2021 105 106 107 108 109 110 111  }, { "cell_type": "markdown", "source": [ "## Paddle Quantum Implementation\n", "\n", "To investigate the TSP using Paddle Quantum, there are some required packages to import, which are shown below. The networkx package is the tool to handle graphs."  Q Quleaf 已提交 11月 15, 2021 112 113  ], "metadata": {}  Q Quleaf 已提交 5月 18, 2021 114 115 116 117 118 119 120 121  }, { "cell_type": "code", "execution_count": 1, "source": [ "# Import related modules from Paddle Quantum and PaddlePaddle\n", "import paddle\n", "from paddle_quantum.circuit import UAnsatz\n",  Q Quleaf 已提交 11月 15, 2021 122 123 124 125 126 127 128  "\n", "# Functions for Salesman Problem\n", "from paddle_quantum.QAOA.tsp import tsp_hamiltonian # Get the Hamiltonian for salesman problem\n", "from paddle_quantum.QAOA.tsp import solve_tsp_brute_force # Solve the salesman problem by brute force\n", "\n", "# Create Graph\n", "import networkx as nx\n",  Q Quleaf 已提交 5月 18, 2021 129 130 131 132  "\n", "# Import additional packages needed\n", "from numpy import pi as PI\n", "import matplotlib.pyplot as plt\n",  Q Quleaf 已提交 11月 15, 2021 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149  "import random\n", "import time" ], "outputs": [], "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:24:17.197426Z", "start_time": "2021-05-17T08:24:12.896488Z" } } }, { "cell_type": "markdown", "source": [ "### Generate a weighted complete graph" ], "metadata": {}  Q Quleaf 已提交 5月 18, 2021 150 151 152 153 154  }, { "cell_type": "markdown", "source": [ "Next, we generate a weighted complete graph $G$ with four vertices. For the convenience of computation, the vertices here are labeled starting from $0$."  Q Quleaf 已提交 11月 15, 2021 155 156  ], "metadata": {}  Q Quleaf 已提交 5月 18, 2021 157 158 159 160 161 162 163  }, { "cell_type": "code", "execution_count": 2, "source": [ "# n is the number of vertices in the graph G\n", "n = 4\n",  Q Quleaf 已提交 11月 15, 2021 164  "E = [(0, 1, 3), (0, 2, 2), (0, 3, 10), (1, 2, 6), (1, 3, 2), (2, 3, 6)] # Parameters for edges: (vertex1, vertex2, weight(distance))\n",  Q Quleaf 已提交 5月 18, 2021 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182  "G = nx.Graph()\n", "G.add_weighted_edges_from(E)\n", "\n", "# Print out the generated graph G\n", "pos = nx.spring_layout(G)\n", "options = {\n", " \"with_labels\": True,\n", " \"font_weight\": \"bold\",\n", " \"font_color\": \"white\",\n", " \"node_size\": 2000,\n", " \"width\": 2\n", "}\n", "nx.draw_networkx(G, pos, **options)\n", "nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=nx.get_edge_attributes(G,'weight'))\n", "ax = plt.gca()\n", "ax.margins(0.20)\n", "plt.axis(\"off\")\n", "plt.show()"  Q Quleaf 已提交 11月 15, 2021 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201  ], "outputs": [ { "output_type": "display_data", "data": { "text/plain": [ "