community/optimization/graph_partition.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Using Qiskit Aqua for graph partition problems*_\n",
    "\n",
    "Here we consider a simplified graph partition problem.\n",
    "Consider a graph $G = (V, E)$, where $V$ denotes the set of n vertices and $E$ the set of edges. \n",
    "The objective of graph partition is to partition $G$ into two sets of the same size (let us assume we have even number of vertices), \n",
    "while minimizing the capacity of the edges across the two sets.\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.\n",
    "\n",
    "Note the objective_value below is defined as the the number of crossing edges. The goal is to minimize this value.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The problem and the brute-force method\n",
    "\n",
    "The graph involved in our example 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.  3.]\n",
      " [ 4.  0. -5.  7.]\n",
      " [ 5. -5.  0.  0.]\n",
      " [ 3.  7.  0.  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 graph_partition\n",
    "from qiskit.aqua.algorithms import ExactEigensolver\n",
    "\n",
    "np.random.seed(100)\n",
    "num_nodes = 4\n",
    "w = graph_partition.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 in the first partition) or 1 (meaning the vertex is in the second partition). We print the binary assignment that satisfies the definition of the graph partition and corresponds to the minimial number of crossing edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective value computed by the brute-force method is 3\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # use the brute-force way to generate the oracle\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",
    "        how_many_nonzero = np.count_nonzero(cur)\n",
    "        if how_many_nonzero * 2 != L:  # not balanced\n",
    "            continue\n",
    "\n",
    "        cur_v = graph_partition.objective_value(np.array(cur), w)\n",
    "        if cur_v < minimal_v:\n",
    "            minimal_v = cur_v\n",
    "    return minimal_v\n",
    "\n",
    "sol = brute_force()\n",
    "print(\"Objective value computed by the brute-force method is\", sol)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part I: Run the optimization using the declarative approach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective value computed by ExactEigensolver is 3.0\n"
     ]
    }
   ],
   "source": [
    "qubit_op, offset = graph_partition.get_graph_partition_qubitops(w)\n",
    "algo_input = EnergyInput(qubit_op)\n",
    "\n",
    "params = {\n",
    "    'problem': {'name': 'ising'},\n",
    "    'algorithm': {'name': 'ExactEigensolver'}\n",
    "}\n",
    "result = run_algorithm(params, algo_input)\n",
    "\n",
    "x = graph_partition.sample_most_likely(result['eigvecs'][0])\n",
    "# check against the oracle\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "np.testing.assert_array_equal(ising_sol, [0, 1, 0, 1])\n",
    "print(\"Objective value computed by ExactEigensolver is\", graph_partition.objective_value(x, w))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part II: Run the optimization using the programmatic approach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective value computed by the ExactEigensolver is 3.0\n"
     ]
    }
   ],
   "source": [
    "algo = ExactEigensolver(algo_input.qubit_op, k=1, aux_operators=[])\n",
    "result = algo.run()\n",
    "\n",
    "x = graph_partition.sample_most_likely(result['eigvecs'][0])\n",
    "# check against the oracle\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "np.testing.assert_array_equal(ising_sol, [0, 1, 0, 1])\n",
    "print(\"Objective value computed by the ExactEigensolver is\", graph_partition.objective_value(x, w))"
   ]
  },
  {
   "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": [
      "Objective value computed by VQE is 3.0\n"
     ]
    }
   ],
   "source": [
    "params = {\n",
    "    'problem': {'name': 'ising', 'random_seed': 10598},\n",
    "    'algorithm': {'name': 'VQE'},\n",
    "    'optimizer': {'name': 'COBYLA'},\n",
    "    'variational_form': {'name': 'RY', 'depth': 5, 'entanglement': 'linear'}\n",
    "}\n",
    "backend = BasicAer.get_backend('statevector_simulator')\n",
    "result = run_algorithm(params, algo_input, backend=backend)\n",
    "\n",
    "x = graph_partition.sample_most_likely(result['eigvecs'][0])\n",
    "# check against the oracle\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "np.testing.assert_array_equal(ising_sol, [1, 0, 1, 0])\n",
    "print(\"Objective value computed by VQE is\", graph_partition.objective_value(x, w))"
   ]
  },
  {
   "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": [
      "Objective value computed by VQE is 3.0\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.aqua.components.variational_forms import RY\n",
    "\n",
    "aqua_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "var_form = RY(qubit_op.num_qubits, depth=5, entanglement='linear')\n",
    "vqe = VQE(qubit_op, var_form, optimizer)\n",
    "\n",
    "backend = BasicAer.get_backend('statevector_simulator')\n",
    "result = vqe.run(backend)\n",
    "\n",
    "x = graph_partition.sample_most_likely(result['eigvecs'][0])\n",
    "# check against the oracle\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "np.testing.assert_array_equal(ising_sol, [1, 0, 1, 0])\n",
    "print(\"Objective value computed by VQE is\", graph_partition.objective_value(x, w))"
   ]
  }
 ],
 "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
}