community/optimization/max_cut.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## _*Using Qiskit Aqua for max-cut problems*_\n",
    "\n",
    "This Qiskit Aqua Optimization notebook demonstrates how to use the VQE quantum algorithm to compute the max cut of a given graph. \n",
    "\n",
    "The problem is defined as follows. Given a graph $G = (V,E)$ with weights $w_{ij}$ on the edges, we are looking for a subset $S \\subseteq V$ such that $\\sum_{(i,j) \\in E : i \\in S, j \\not\\in S} w_{ij}$ is maximized.\n",
    "\n",
    "The graph provided as an input is used first to generate an Ising Hamiltonian, which is then passed as an input to VQE.  As a reference, this notebook also computes the max cut using the Exact Eigensolver classical algorithm and the solver embedded in the commercial non-quantum IBM CPLEX product (if it is available in the system and the user has followed the necessary configuration steps in order for Qiskit Aqua to find it).  Please refer to the Qiskit Aqua Optimization documentation for installation and configuration details for CPLEX."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from qiskit.aqua import Operator, run_algorithm\n",
    "from qiskit.aqua.input import EnergyInput\n",
    "from qiskit.aqua.translators.ising import max_cut\n",
    "from qiskit.aqua.algorithms.classical.cplex.cplex_ising import CPLEX_Ising\n",
    "from qiskit import Aer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here an Operator instance is created for our Hamiltonian. In this case the paulis are from an Ising Hamiltonian translated from the max-cut problem. We load a small sample instance of the max-cut problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = max_cut.parse_gset_format('sample.maxcut')\n",
    "qubitOp, offset = max_cut.get_max_cut_qubitops(w)\n",
    "algo_input = EnergyInput(qubitOp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also offer a function to generate a random graph as a input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  8. -9.  0.]\n",
      " [ 8.  0.  7.  9.]\n",
      " [-9.  7.  0. -8.]\n",
      " [ 0.  9. -8.  0.]]\n"
     ]
    }
   ],
   "source": [
    "if True:\n",
    "    np.random.seed(8123179)\n",
    "    w = max_cut.random_graph(4, edge_prob=0.5, weight_range=10)\n",
    "    qubitOp, offset = max_cut.get_max_cut_qubitops(w)\n",
    "    algo_input.qubit_op = qubitOp\n",
    "print(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we test for the presence of algorithms we want to use in this notebook. If Aqua is installed correctly `ExactEigensolver` and `VQE` will always be found. `CPLEX.Ising` is dependent on IBM CPLEX being installed (see introduction above). CPLEX is *not required* but if installed then this notebook will demonstrate the `CPLEX.Ising` algorithm , that uses CPLEX, to compute max-cut as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ExactEigensolver', 'CPLEX.Ising', 'VQE']\n"
     ]
    }
   ],
   "source": [
    "to_be_tested_algos = ['ExactEigensolver', 'CPLEX.Ising', 'VQE']\n",
    "print(to_be_tested_algos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now use the Operator without regard to how it was created. First we need to prepare the configuration params to invoke the algorithm. Here we will use the ExactEigensolver first to return the smallest eigenvalue. Backend is not required since this is computed classically not using quantum computation. We then add in the qubitOp Operator in dictionary format. Now the complete params can be passed to the algorithm and run. The result is a dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "energy: -20.5\n",
      "max-cut objective: -24.0\n",
      "solution: [1. 0. 1. 1.]\n",
      "solution objective: 24.0\n"
     ]
    }
   ],
   "source": [
    "algorithm_cfg = {\n",
    "    'name': 'ExactEigensolver',\n",
    "}\n",
    "\n",
    "params = {\n",
    "    'problem': {'name': 'ising'},\n",
    "    'algorithm': algorithm_cfg\n",
    "}\n",
    "result = run_algorithm(params,algo_input)\n",
    "# print('objective function:', max_cut.max_cut_obj(result, offset))\n",
    "x = max_cut.sample_most_likely(result['eigvecs'][0])\n",
    "print('energy:', result['energy'])\n",
    "print('max-cut objective:', result['energy'] + offset)\n",
    "print('solution:', max_cut.get_graph_solution(x))\n",
    "print('solution objective:', max_cut.max_cut_value(x, w))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note*: IBM CPLEX is an _optional_ installation addition for Aqua. If installed then the Aqua CPLEX.Ising algorithm will be able to be used. If not, then solving this problem using this particular algorithm will simply be skipped. \n",
    "\n",
    "We change the configuration parameters to solve it with the CPLEX backend. The CPLEX backend can deal with a particular type of Hamiltonian called Ising Hamiltonian, which consists of only Pauli Z at most second order and often for combinatorial optimization problems that can be formulated as quadratic unconstrained binary optimization problems, such as the max-cut problem.\n",
    "\n",
    "Note that for a max-cut problem, since we are computing a bipartition of the graph, every binary vector $x$ and its complement (i.e., the vector $y$ such that $y_j = 1 - x_j$ for all $j$) represent exactly the same solution, and will have the same objective function value. Different solution methods may return solutions that look different, but in fact have the same objective function value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPXPARAM_TimeLimit                               600\n",
      "CPXPARAM_Read_DataCheck                          1\n",
      "CPXPARAM_Threads                                 1\n",
      "CPXPARAM_MIP_Tolerances_MIPGap                   0\n",
      "CPXPARAM_MIP_Tolerances_Integrality              0\n",
      "CPXPARAM_MIP_Display                             0\n",
      "energy: -20.5\n",
      "time: 0.026632682000126806\n",
      "max-cut objective: -24.0\n",
      "solution: [1 0 1 1]\n",
      "solution objective: 24.0\n"
     ]
    }
   ],
   "source": [
    "cplex_installed = True\n",
    "try:\n",
    "    CPLEX_Ising.check_pluggable_valid()\n",
    "except Exception as e:\n",
    "    cplex_installed = False\n",
    "\n",
    "\n",
    "if cplex_installed:\n",
    "    algorithm_cfg = {\n",
    "        'name': 'CPLEX.Ising',\n",
    "        'display': 0\n",
    "    }\n",
    "\n",
    "    params = {\n",
    "        'problem': {'name': 'ising'},\n",
    "        'algorithm': algorithm_cfg\n",
    "    }\n",
    "\n",
    "    result = run_algorithm(params, algo_input)\n",
    "\n",
    "    x_dict = result['x_sol']\n",
    "    print('energy:', result['energy'])\n",
    "    print('time:', result['eval_time'])\n",
    "    print('max-cut objective:', result['energy'] + offset)\n",
    "    x = np.array([x_dict[i] for i in sorted(x_dict.keys())])\n",
    "    print('solution:', max_cut.get_graph_solution(x))\n",
    "    print('solution objective:', max_cut.max_cut_value(x, w))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we want VQE and so change it and add its other configuration parameters. VQE also needs and optimizer and variational form. While we can omit them from the dictionary, such that defaults are used, here we specify them explicitly so we can set their parameters as we desire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "energy: -20.499999999997623\n",
      "time: 12.321285724639893\n",
      "max-cut objective: -23.999999999997623\n",
      "solution: [1. 0. 1. 1.]\n",
      "solution objective: 24.0\n"
     ]
    }
   ],
   "source": [
    "algorithm_cfg = {\n",
    "    'name': 'VQE',\n",
    "    'operator_mode': 'matrix'\n",
    "}\n",
    "\n",
    "optimizer_cfg = {\n",
    "    'name': 'L_BFGS_B',\n",
    "    'maxfun': 6000\n",
    "}\n",
    "\n",
    "var_form_cfg = {\n",
    "    'name': 'RYRZ',\n",
    "    'depth': 3,\n",
    "    'entanglement': 'linear'\n",
    "}\n",
    "\n",
    "params = {\n",
    "    'problem': {'name': 'ising'},\n",
    "    'algorithm': algorithm_cfg,\n",
    "    'optimizer': optimizer_cfg,\n",
    "    'variational_form': var_form_cfg\n",
    "}\n",
    "\n",
    "backend = Aer.get_backend('statevector_simulator')\n",
    "result = run_algorithm(params, algo_input, backend=backend)\n",
    "\n",
    "x = max_cut.sample_most_likely(result['eigvecs'][0])\n",
    "print('energy:', result['energy'])\n",
    "print('time:', result['eval_time'])\n",
    "print('max-cut objective:', result['energy'] + offset)\n",
    "print('solution:', max_cut.get_graph_solution(x))\n",
    "print('solution objective:', max_cut.max_cut_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": 1
}