community/optimization/vertex_cover.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Using Qiskit Aqua for the vertex-cover problems*_\n",
    "\n",
    "A vertex 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. The goal of NPC problem is to minimize the size of the vertex cover. \n",
    "\n",
    "We will go through three examples to show:\n",
    "1. How to run the optimization using the declarative approach\n",
    "2. How to run the optimization using the programmatic approach\n",
    "3. How how to run the optimization with the VQE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The problem and the brute-force method\n",
    "\n",
    "The problem is as follows. the graph is in the adjacent matrix form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 4. 5.]\n",
      " [4. 0. 3.]\n",
      " [5. 3. 0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from qiskit import BasicAer\n",
    "from qiskit.aqua import run_algorithm\n",
    "from qiskit.aqua.input import EnergyInput\n",
    "from qiskit.aqua.translators.ising import vertex_cover\n",
    "from qiskit.aqua.algorithms import ExactEigensolver\n",
    "\n",
    "np.random.seed(100)\n",
    "num_nodes = 3\n",
    "w = vertex_cover.random_graph(num_nodes, edge_prob=0.8, weight_range=10)\n",
    "print(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute-force method is as follows. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a vertex is either 0 (meaning the vertex is not in the cover) or 1 (meaning the vertex is in the cover). We print the binary assignment that satisfies the definition of the vertex cover and corresponds to the minimial size. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the vertex cover 2\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # brute-force way\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]  # [2:] to chop off the \"0b\" part\n",
    "\n",
    "    L = num_nodes\n",
    "    max = 2**L\n",
    "    minimal_v = np.inf\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "\n",
    "        cur_v = vertex_cover.check_full_edge_coverage(np.array(cur), w)\n",
    "        if cur_v:\n",
    "            nonzerocount = np.count_nonzero(cur)\n",
    "            if nonzerocount < minimal_v:\n",
    "                minimal_v = nonzerocount\n",
    "\n",
    "    return minimal_v\n",
    "\n",
    "size = brute_force()\n",
    "print('Size of the vertex cover', size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part I: Run the optimization using the declarative approach\n",
    "\n",
    "Here the steps are:\n",
    "* Create the qubit operator i.e. Ising Hamiltonian, using `vertex_cover` ising translator\n",
    "* Create an EnergyInput object and a dictionary describing the algorithm and the components for Aqua to solve the problem\n",
    "* Run the algorithm and get the result\n",
    "* Use the result with the `vertex_cover` object to determine a solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the vertex cover 2\n"
     ]
    }
   ],
   "source": [
    "qubit_op, offset = vertex_cover.get_vertex_cover_qubitops(w)\n",
    "\n",
    "algo_input = EnergyInput(qubit_op)\n",
    "params = {\n",
    "    'problem': {'name': 'ising'},\n",
    "    'algorithm': {'name': 'ExactEigensolver'}\n",
    "}\n",
    "result = run_algorithm(params, algo_input)\n",
    "\n",
    "x = vertex_cover.sample_most_likely(len(w), result['eigvecs'][0])\n",
    "sol = vertex_cover.get_graph_solution(x)\n",
    "np.testing.assert_array_equal(sol, [0, 1, 1])\n",
    "print('Size of the vertex cover', np.count_nonzero(sol))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part II: Run the optimization using the programmatic approach\n",
    "\n",
    "The main difference here is running the Aqua algorithm. Here we directly construct the algorithm and then run() it to get the result. The post computation on the result is identical."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the vertex cover 2\n"
     ]
    }
   ],
   "source": [
    "algo = ExactEigensolver(qubit_op)\n",
    "result = algo.run()\n",
    "\n",
    "x = vertex_cover.sample_most_likely(len(w), result['eigvecs'][0])\n",
    "sol = vertex_cover.get_graph_solution(x)\n",
    "np.testing.assert_array_equal(sol, [0, 1, 1])\n",
    "print('Size of the vertex cover', np.count_nonzero(sol))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part III: Run the optimization with the VQE\n",
    "\n",
    "##### Declarative\n",
    "\n",
    "We reuse the EnergyInput object we created above. VQE algorithm needs an optimizer and a variational form. Then also we need a quantum backend on which the algorithm will run."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the vertex cover 2\n"
     ]
    }
   ],
   "source": [
    "params = {\n",
    "    'problem': {'name': 'ising', 'random_seed': 100},\n",
    "    'algorithm': {'name': 'VQE', 'operator_mode': 'paulis'},\n",
    "    'optimizer': {'name': 'SPSA', 'max_trials': 200},\n",
    "    'variational_form': {'name': 'RYRZ', 'depth': 3}\n",
    "}\n",
    "backend = BasicAer.get_backend('qasm_simulator')\n",
    "result = run_algorithm(params, algo_input, backend=backend)\n",
    "\n",
    "x = vertex_cover.sample_most_likely(len(w), result['eigvecs'][0])\n",
    "sol = vertex_cover.get_graph_solution(x)\n",
    "print('Size of the vertex cover', np.count_nonzero(sol))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Programmatic\n",
    "\n",
    "We can create the objects directly ourselves too and run VQE for the result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the vertex cover 2\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.aqua.components.optimizers import SPSA\n",
    "from qiskit.aqua.components.variational_forms import RYRZ\n",
    "\n",
    "aqua_globals.random_seed = 100\n",
    "\n",
    "optimizer = SPSA(max_trials=200)\n",
    "var_form = RYRZ(qubit_op.num_qubits, depth=3)\n",
    "vqe = VQE(qubit_op, var_form, optimizer, operator_mode='paulis')\n",
    "\n",
    "backend = BasicAer.get_backend('qasm_simulator')\n",
    "result = vqe.run(backend)\n",
    "\n",
    "x = vertex_cover.sample_most_likely(len(w), result['eigvecs'][0])\n",
    "sol = vertex_cover.get_graph_solution(x)\n",
    "print('Size of the vertex cover', np.count_nonzero(sol))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}