hackthon.004.TSPtoIsing.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Modules import completed...\n",
      "------------------------------\n",
      " ### Init IBMQ and Set up provider\n",
      "IBMQ loading completed...\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import sys\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from pathlib import Path\n",
    "from math import pi\n",
    "# qiskit\n",
    "from qiskit import (\n",
    "    IBMQ, execute, transpile,\n",
    "    QuantumRegister, ClassicalRegister, QuantumCircuit,\n",
    ")\n",
    "# qurry\n",
    "sys.path.insert(0, './')\n",
    "from backend import backendWrapper\n",
    "from mori import TagMap\n",
    "print(\"Modules import completed...\")\n",
    "print(\"-\"*30+\"\\n ### Init IBMQ and Set up provider\")\n",
    "IBMQ.load_account()\n",
    "IBMQ.providers()\n",
    "provider = IBMQ.get_provider(\n",
    "    hub='ibm-q-hub-ntu', group='ntu-internal', project='default')\n",
    "backend = backendWrapper(provider)\n",
    "print(\"IBMQ loading completed...\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "map_x = 30\n",
    "map_y = 30\n",
    "\n",
    "cityMapList = [[(10, 10), (10, 20), (22, 20)]]\n",
    "penalityList = [100, 1000, 10000]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prpepred function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_map(my_map, my_path=None):\n",
    "    xs = [x[0] for x in my_map]\n",
    "    ys = [x[1] for x in my_map]\n",
    "    plt.scatter(xs, ys, s=100)\n",
    "    plt.xlim(0, map_x)\n",
    "    plt.ylim(0, map_y)\n",
    "#     plt.figure(figsize=(5,5))\n",
    "    for i in range(len(my_map)):\n",
    "        plt.text(xs[i]+2, ys[i]-3, i, fontsize = 20)\n",
    "    \n",
    "    if my_path:\n",
    "        for i in range(len(my_path)-1):\n",
    "            plt.plot([my_map[my_path[i]][0], my_map[my_path[i+1]][0]], [my_map[my_path[i]][1], my_map[my_path[i+1]][1]], 'ro-')\n",
    "    plt.show()\n",
    "    \n",
    "def dist(p, q):\n",
    "    return math.sqrt((float(p[0]) - float(q[0])) ** 2 + (float(p[1]) - float(q[1])) ** 2)\n",
    "\n",
    "def to_distance_matrix(my_map):\n",
    "    ret = []\n",
    "    for i in range(len(my_map)):\n",
    "        this_line = []\n",
    "        for j in range(len(my_map)):\n",
    "            this_line.append(dist(my_map[i], my_map[j]))\n",
    "        ret.append(this_line)\n",
    "            \n",
    "    return ret\n",
    "\n",
    "def brute_tsp(graph, s=0):\n",
    "    vertex = []\n",
    "    V = len(graph)\n",
    "    for i in range(V):\n",
    "        if i != s:\n",
    "            vertex.append(i)\n",
    "\n",
    "    min_path = maxsize\n",
    "    next_permutation=permutations(vertex)\n",
    "    for i in next_permutation:\n",
    "        current_pathweight = 0\n",
    "        k = s\n",
    "        for j in i:\n",
    "            current_pathweight += graph[k][j]\n",
    "            k = j\n",
    "        current_pathweight += graph[k][s]\n",
    "        min_path = min(min_path, current_pathweight)\n",
    "        if min_path == current_pathweight:\n",
    "            ret_path = list(i)\n",
    "    ret_path = [0] + ret_path + [0]\n",
    "    return ret_path, min_path\n",
    "\n",
    "def tsp_matrix_to_QUBO_matrix(w, penality=1000):\n",
    "    n = len(w)\n",
    "    Q = np.zeros((n*n, n*n))\n",
    "    c = np.ones(n*n)\n",
    "    A = np.max(w) * penality # penality\n",
    "    c = c * (-4*A)\n",
    "\n",
    "    # k, l is the index of Q\n",
    "    # i, j, p, p_ is the index of w\n",
    "    for k in range(n*n):\n",
    "        for l in range(n*n):\n",
    "            i = k // n\n",
    "            j = l // n\n",
    "            p = k % n \n",
    "            p_ = l % n \n",
    "            if  (p+1)%n == p_ and i != j:\n",
    "                Q[k, l] = w[i, j] \n",
    "            elif p == p_:\n",
    "                Q[k, l] = Q[k, l] + A\n",
    "            elif i == j:\n",
    "                Q[k, l] = Q[k, l] + A\n",
    "\n",
    "    return Q, c\n",
    "\n",
    "def QUBO_to_Ising(Q, c):\n",
    "    J = Q/4\n",
    "    h = (c + np.sum(Q, axis=1))/2\n",
    "\n",
    "    for i in range(len(h)):\n",
    "        J[i][i] += h[i]\n",
    "\n",
    "    return J"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([0, 2, 1, 0], 37.62049935181331)\n"
     ]
    }
   ],
   "source": [
    "distanceMatrixList = [to_distance_matrix(m) for m in cityMapList]\n",
    "\n",
    "min_PD = [brute_tsp(distance) for distance in distanceMatrixList]\n",
    "for m in min_PD:\n",
    "    print(m)\n",
    "    \n",
    "    \n",
    "QandCSet = {\n",
    "    (i, f'p={p}'): tsp_matrix_to_QUBO_matrix(np.array(distance), p) \n",
    "for i, distance in enumerate(distanceMatrixList)\n",
    "for p in penalityList}\n",
    "\n",
    "IsingSet = {k: QUBO_to_Ising(v[0], v[1]) for k, v in QandCSet.items()}\n",
    "IsingSet = {k: v.tolist() for k, v in IsingSet.items()}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0,\n",
       "  'p=100'): [[1184.347701061905,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0], [390.5124837953327,\n",
       "   1184.347701061905,\n",
       "   390.5124837953327,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   3.905124837953327], [390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   1184.347701061905,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   390.5124837953327], [390.5124837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   1182.5374513859983,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   3.0,\n",
       "   0.0], [0.0,\n",
       "   390.5124837953327,\n",
       "   2.5,\n",
       "   390.5124837953327,\n",
       "   1182.5374513859983,\n",
       "   390.5124837953327,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   3.0], [2.5,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   1182.5374513859979,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   390.5124837953327], [390.5124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   1185.347701061905,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327], [0.0,\n",
       "   390.5124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   3.0,\n",
       "   390.5124837953327,\n",
       "   1185.347701061905,\n",
       "   390.5124837953327], [3.905124837953327,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   390.5124837953327,\n",
       "   1185.347701061905]],\n",
       " (0,\n",
       "  'p=1000'): [[11728.184763535886,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0], [3905.124837953327,\n",
       "   11728.184763535886,\n",
       "   3905.124837953327,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3.905124837953327], [3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   11728.184763535886,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   3905.124837953327], [3905.124837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   11726.374513859977,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   3.0,\n",
       "   0.0], [0.0,\n",
       "   3905.124837953327,\n",
       "   2.5,\n",
       "   3905.124837953327,\n",
       "   11726.374513859977,\n",
       "   3905.124837953327,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3.0], [2.5,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   11726.374513859984,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   3905.124837953327], [3905.124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   11729.184763535886,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327], [0.0,\n",
       "   3905.124837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3.0,\n",
       "   3905.124837953327,\n",
       "   11729.184763535886,\n",
       "   3905.124837953327], [3.905124837953327,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   3905.124837953327,\n",
       "   11729.184763535886]],\n",
       " (0,\n",
       "  'p=10000'): [[117166.55538827574,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   3.905124837953327,\n",
       "   0.0], [39051.24837953327,\n",
       "   117166.55538827568,\n",
       "   39051.24837953327,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   3.905124837953327], [39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   117166.55538827568,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   39051.24837953327], [39051.24837953327,\n",
       "   2.5,\n",
       "   0.0,\n",
       "   117164.7451385998,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   3.0,\n",
       "   0.0], [0.0,\n",
       "   39051.24837953327,\n",
       "   2.5,\n",
       "   39051.24837953327,\n",
       "   117164.7451385998,\n",
       "   39051.24837953327,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   3.0], [2.5,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   117164.7451385998,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   39051.24837953327], [39051.24837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   117167.55538827568,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327], [0.0,\n",
       "   39051.24837953327,\n",
       "   3.905124837953327,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   3.0,\n",
       "   39051.24837953327,\n",
       "   117167.55538827568,\n",
       "   39051.24837953327], [3.905124837953327,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   3.0,\n",
       "   0.0,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   39051.24837953327,\n",
       "   117167.55538827568]]}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsingSet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.7 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "159f4e407912a17e167f5db34c957ad4331db5f294b01a1425dfe1db5ae08f50"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}