tutorial/315_vertexcover.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HQ7BEHkZcF0a"
   },
   "source": [
    "# Vertex Cover\n",
    "\n",
    "In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.\n",
    "\n",
    "https://en.wikipedia.org/wiki/Vertex_cover\n",
    "\n",
    "![vertex cover](https://github.com/mdrft/Wildqat/blob/master/examples_ja/img/016_1.png?raw=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "H_IExOtlcF0b"
   },
   "source": [
    "## Installation\n",
    "\n",
    "If you don't have blueqat yet please install it.\n",
    "\n",
    "```bash\n",
    "pip install blueqat\n",
    "```\n",
    "\n",
    "Let's start."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "pc93_6HxcF0d"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from blueqat import vqe\n",
    "from blueqat.pauli import qubo_bit as q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HZEenCgicF0h"
   },
   "source": [
    "## QUBO\n",
    "Now we have the cost function\n",
    "\n",
    "$ H = H_{A} + H_{B} $\n",
    "\n",
    "$H_{A} and H_{B}$ are,\n",
    "\n",
    "$ \\displaystyle H _ { A } = A \\sum _ { u v \\in E } \\left( 1 - x _ { u } \\right) \\left( 1 - x _ { v } \\right)$\n",
    "\n",
    "$ \\displaystyle H _ { B } = B \\sum _ { v } x _ { v }$\n",
    "\n",
    "each $x_{u}, x_{v}$ shows that if the vertex colored it is 1 and else 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4RPRas2UcF0i"
   },
   "source": [
    "and now we have\n",
    "\n",
    "$ \\displaystyle H _ { A } = A \\sum _ { u v \\in E } \\left( 1 - x _ { u } - x _ { v } + x_{u}x_{v}\\right)$\n",
    "\n",
    "we can ignore the constant term and from the binary rules we have.\n",
    "\n",
    "$ \\displaystyle H_{A} = A \\sum _ { u v \\in E } \\left( - x_{u}x_{u} - x_{v}x_{v} + x_{u}x_{v}\\right) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BQijk-KDcF0j"
   },
   "source": [
    "And we have also the second cost function\n",
    "\n",
    "$ \\displaystyle H_{B} = B \\sum _ { u,v: u = v } x_{u}x_{v}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "nPu1B4ZQcF0m"
   },
   "source": [
    "## Coding and Calculation\n",
    "The undirected graph are defined like this,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "sSUoeGUocF0n"
   },
   "outputs": [],
   "source": [
    "edge_def = [\n",
    "    [1,5],      # vertex connected to (0) are (1) and (5)\n",
    "    [2,5],      # vertex connected to (1) are (2) and (5)\n",
    "    [3,5],      #  :\n",
    "    [4],        #  :\n",
    "    [5,6,7,8],\n",
    "    [6,7],\n",
    "    [7],\n",
    "    [],\n",
    "    []\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "e39ttcHgcF0q"
   },
   "outputs": [],
   "source": [
    "A = 1.0\n",
    "B = 0.9\n",
    "def get_qubo(edges):\n",
    "    Q = 0\n",
    "\n",
    "    for u in range(len(edges)):\n",
    "        for v in range(u, len(edges)):\n",
    "            if u == v:\n",
    "                Q += B*q(u)*q(v)\n",
    "            if v in edges[u]:    #if xu and xv are connected each other or not\n",
    "                Q +=  +A*q(u)*q(v)\n",
    "                Q +=  -A*q(u)*q(u)\n",
    "                Q +=  -A*q(v)*q(v)\n",
    "\n",
    "    return Q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "A4ubjZotcF0u"
   },
   "source": [
    "Let's create the function to see the result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gQBhLrgscF0y"
   },
   "source": [
    "Let's try 5 times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 442
    },
    "colab_type": "code",
    "id": "nTOCyx7ycF00",
    "outputId": "9d1aed94-5e78-4ca5-d987-eb91809c472c"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((1, 0, 1, 0, 1, 1, 0, 0, 0), 0.06207651954649183), ((0, 1, 1, 0, 1, 1, 1, 0, 0), 0.02338393285879112), ((0, 1, 1, 0, 1, 1, 0, 1, 0), 0.023383932858791), ((0, 1, 1, 0, 1, 1, 0, 0, 0), 0.021010052183916723), ((0, 1, 1, 1, 1, 1, 0, 0, 0), 0.019841428826055496), ((1, 0, 1, 0, 1, 0, 1, 1, 0), 0.018890212543527754), ((0, 1, 0, 1, 1, 1, 1, 0, 0), 0.0158630980527213), ((0, 1, 0, 1, 1, 1, 0, 1, 0), 0.015863098052721267), ((0, 0, 1, 1, 1, 1, 0, 0, 0), 0.015539534721227048), ((1, 1, 1, 0, 1, 1, 0, 1, 0), 0.014296493084748528), ((1, 1, 1, 0, 1, 1, 1, 0, 0), 0.014296493084748492), ((0, 0, 1, 0, 1, 1, 0, 0, 0), 0.013801376043899659))\n"
     ]
    }
   ],
   "source": [
    "h = get_qubo(edge_def)\n",
    "step = 200\n",
    "result = vqe.Vqe(vqe.QaoaAnsatz(h, step)).run()\n",
    "print(result.most_common(12))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "tutorial016_vertex_cover_en.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}