{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5c020e2b",
   "metadata": {},
   "source": [
    "# Inside Grover Optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1493d362",
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit_optimization import QuadraticProgram \n",
    "from qiskit_optimization.algorithms import CplexOptimizer, GroverOptimizer\n",
    "from qiskit.algorithms import QAOA\n",
    "from qiskit import BasicAer\n",
    "import time\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0d018bf7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    from cplex.exceptions import CplexSolverError\n",
    "    _HAS_CPLEX = True\n",
    "except ImportError:\n",
    "    _HAS_CPLEX = False\n",
    "    \n",
    "print(_HAS_CPLEX)\n",
    "from qiskit_optimization.algorithms import CplexOptimizer\n",
    "print(CplexOptimizer.is_cplex_installed() )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee01e5d8",
   "metadata": {},
   "source": [
    "# Conclusions\n",
    "\n",
    "increasing num_qubits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "32a6c193",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_qubo_random(num_variables):\n",
    "    \"\"\"\n",
    "    Creates an artificial, hardcoded optimisation problem with num_variables binary variables and random weights.\n",
    "    It contains some linear terms and some quadratic terms.\n",
    "    :return: QuadraticProgram instance\n",
    "    \"\"\"\n",
    "    qubo = QuadraticProgram()\n",
    "    for index in range(num_variables):\n",
    "        qubo.binary_var('x' + str(index + 1))\n",
    "\n",
    "    quadratic = {}\n",
    "    for i in range(0, num_variables):\n",
    "        for j in range(i + 1, num_variables):\n",
    "            quadratic[('x' + str(i + 1), 'x' + str(j + 1))] = random.random()\n",
    "\n",
    "    linear = []\n",
    "    for value in range(num_variables):\n",
    "        linear.append(random.uniform(-10, 10))\n",
    "    qubo.minimize(linear=linear,\n",
    "                  quadratic=quadratic)\n",
    "    return qubo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e58d3f0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "backend = BasicAer.get_backend('qasm_simulator')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4c1b8bd0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24\n"
     ]
    }
   ],
   "source": [
    "print(backend.configuration().n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "613d9575",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "def call_grover(qubo, num_qubits):\n",
    "    t0 = time.time()\n",
    "    grover_optimizer = GroverOptimizer(num_qubits, num_iterations=20, quantum_instance=backend)\n",
    "    results = grover_optimizer.solve(qubo)\n",
    "    t1 = time.time()\n",
    "    return results, t1-t0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "03c9baac",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b1d9b6e1",
   "metadata": {},
   "source": [
    "# Generate 2 qubit problem and solve it increasing num_value_qubits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "4f242b79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: -15.398312956457627\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS\n",
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: CPLEX\n",
      "\n",
      "Minimize\n",
      " obj: - 6.244078881466 x1 - 9.279059437896 x2 + [ 0.249650725810 x1*x2 ]/2\n",
      "Subject To\n",
      "\n",
      "Bounds\n",
      " 0 <= x1 <= 1\n",
      " 0 <= x2 <= 1\n",
      "\n",
      "Binaries\n",
      " x1 x2\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "NUM_QUBITS=2\n",
    "qubo = create_qubo_random(NUM_QUBITS)\n",
    "result = CplexOptimizer().solve(qubo)\n",
    "print(result)\n",
    "print(qubo.export_as_lp_string())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "cc2f1e2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "results = []\n",
    "times = []\n",
    "for num_value_qubits in range(1, 10):\n",
    "    result, exec_time =  call_grover(qubo, num_value_qubits)\n",
    "    print(result)\n",
    "    print(exec_time)\n",
    "    results.append(result)\n",
    "    times.append(exec_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "6575415c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[optimal function value: -15.398312956457625\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS, optimal function value: -9.279059437896395\n",
      "optimal value: [0. 1.]\n",
      "status: SUCCESS, optimal function value: -6.244078881466164\n",
      "optimal value: [1. 0.]\n",
      "status: SUCCESS, optimal function value: -6.244078881466164\n",
      "optimal value: [1. 0.]\n",
      "status: SUCCESS, optimal function value: -15.398312956457625\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS, optimal function value: -15.398312956457625\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS, optimal function value: -15.398312956457625\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS, optimal function value: -15.398312956457625\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS, optimal function value: -15.398312956457625\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS]\n",
      "[3.836414098739624, 2.934094190597534, 4.148914813995361, 6.56948184967041, 2.630277156829834, 23.678771018981934, 7.046514987945557, 12.200111865997314, 60.14390707015991]\n"
     ]
    }
   ],
   "source": [
    "print(results)\n",
    "print(times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "1516bbb6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS\n",
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: CPLEX\n",
      "\n",
      "Minimize\n",
      " obj: 8.123429358118 x1 + 0.938533695469 x2 + [ 1.819401629187 x1*x2 ]/2\n",
      "Subject To\n",
      "\n",
      "Bounds\n",
      " 0 <= x1 <= 1\n",
      " 0 <= x2 <= 1\n",
      "\n",
      "Binaries\n",
      " x1 x2\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "NUM_QUBITS=2\n",
    "qubo = create_qubo_random(NUM_QUBITS)\n",
    "result = CplexOptimizer().solve(qubo)\n",
    "print(result)\n",
    "print(qubo.export_as_lp_string())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "867dd80e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: 0.9385336954690473\n",
      "optimal value: [0. 1.]\n",
      "status: SUCCESS\n",
      "1.4535810947418213\n",
      "optimal function value: 8.123429358117868\n",
      "optimal value: [1. 0.]\n",
      "status: SUCCESS\n",
      "1.460085153579712\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS\n",
      "1.950566291809082\n",
      "optimal function value: 9.971663868180201\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS\n",
      "2.2134788036346436\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS\n",
      "10.296104192733765\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS\n",
      "8.375697135925293\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS\n",
      "6.709075212478638\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS\n",
      "14.770597696304321\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS\n",
      "56.80534100532532\n",
      "[optimal function value: 0.9385336954690473\n",
      "optimal value: [0. 1.]\n",
      "status: SUCCESS, optimal function value: 8.123429358117868\n",
      "optimal value: [1. 0.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS, optimal function value: 9.971663868180201\n",
      "optimal value: [1. 1.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0.]\n",
      "status: SUCCESS]\n",
      "[1.4535810947418213, 1.460085153579712, 1.950566291809082, 2.2134788036346436, 10.296104192733765, 8.375697135925293, 6.709075212478638, 14.770597696304321, 56.80534100532532]\n"
     ]
    }
   ],
   "source": [
    "results2 = []\n",
    "times2 = []\n",
    "for num_value_qubits in range(1, 10):\n",
    "    result, exec_time =  call_grover(qubo, num_value_qubits)\n",
    "    print(result)\n",
    "    print(exec_time)\n",
    "    results2.append(result)\n",
    "    times2.append(exec_time)\n",
    "print(results2)\n",
    "print(times2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15c04b17",
   "metadata": {},
   "source": [
    "# Generate 3 qubit problem and solve it increasing num_value_qubits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "e553ae46",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: -0.31784204496715773\n",
      "optimal value: [0. 1. 0.]\n",
      "status: SUCCESS\n",
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: CPLEX\n",
      "\n",
      "Minimize\n",
      " obj: 2.486841652500 x1 - 0.317842044967 x2 + 1.061092209495 x3 + [\n",
      "      1.841053002139 x1*x2 + 0.083291792134 x1*x3 + 1.650105056575 x2*x3 ]/2\n",
      "Subject To\n",
      "\n",
      "Bounds\n",
      " 0 <= x1 <= 1\n",
      " 0 <= x2 <= 1\n",
      " 0 <= x3 <= 1\n",
      "\n",
      "Binaries\n",
      " x1 x2 x3\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "NUM_QUBITS=3\n",
    "qubo = create_qubo_random(NUM_QUBITS)\n",
    "result = CplexOptimizer().solve(qubo)\n",
    "print(result)\n",
    "print(qubo.export_as_lp_string())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "fda4f1d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "results = []\n",
    "times = []\n",
    "for num_value_qubits in range(1, 10):\n",
    "    result, exec_time =  call_grover(qubo, num_value_qubits)\n",
    "    results.append(result)\n",
    "    times.append(exec_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "1cc07eb0",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[optimal function value: 3.089526108602299\n",
      "optimal value: [1. 1. 0.]\n",
      "status: SUCCESS, optimal function value: 3.5895797580617916\n",
      "optimal value: [1. 0. 1.]\n",
      "status: SUCCESS, optimal function value: 2.486841652500022\n",
      "optimal value: [1. 0. 0.]\n",
      "status: SUCCESS, optimal function value: 3.089526108602299\n",
      "optimal value: [1. 1. 0.]\n",
      "status: SUCCESS, optimal function value: 2.486841652500022\n",
      "optimal value: [1. 0. 0.]\n",
      "status: SUCCESS, optimal function value: 1.5683026928151689\n",
      "optimal value: [0. 1. 1.]\n",
      "status: SUCCESS, optimal function value: 3.5895797580617916\n",
      "optimal value: [1. 0. 1.]\n",
      "status: SUCCESS, optimal function value: 1.5683026928151689\n",
      "optimal value: [0. 1. 1.]\n",
      "status: SUCCESS, optimal function value: 1.5683026928151689\n",
      "optimal value: [0. 1. 1.]\n",
      "status: SUCCESS]\n",
      "[7.621005058288574, 5.797473907470703, 27.164788007736206, 14.36255407333374, 14.704663038253784, 25.877529859542847, 53.53490209579468, 265.0189833641052, 246.1127049922943]\n"
     ]
    }
   ],
   "source": [
    "print(results)\n",
    "print(times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "50270076",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: -1.0089613928311163\n",
      "optimal value: [1. 0. 0.]\n",
      "status: SUCCESS\n",
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: CPLEX\n",
      "\n",
      "Minimize\n",
      " obj: - 1.008961392831 x1 + 3.943078387440 x2 + 6.725876209684 x3 + [\n",
      "      1.349722117642 x1*x2 + 0.533352704144 x1*x3 + 1.872752796434 x2*x3 ]/2\n",
      "Subject To\n",
      "\n",
      "Bounds\n",
      " 0 <= x1 <= 1\n",
      " 0 <= x2 <= 1\n",
      " 0 <= x3 <= 1\n",
      "\n",
      "Binaries\n",
      " x1 x2 x3\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "NUM_QUBITS=3\n",
    "qubo = create_qubo_random(NUM_QUBITS)\n",
    "result = CplexOptimizer().solve(qubo)\n",
    "print(result)\n",
    "print(qubo.export_as_lp_string())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1c61f3e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "results = []\n",
    "times = []\n",
    "for num_value_qubits in range(1, 10):\n",
    "    result, exec_time =  call_grover(qubo, num_value_qubits)\n",
    "    results.append(result)\n",
    "    times.append(exec_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "f0bd9571",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[optimal function value: -12.83161851988641\n",
      "optimal value: [0. 1. 1.]\n",
      "status: SUCCESS, optimal function value: -9.025151258904998\n",
      "optimal value: [0. 1. 0.]\n",
      "status: SUCCESS, optimal function value: -9.025151258904998\n",
      "optimal value: [0. 1. 0.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0. 0.]\n",
      "status: SUCCESS, optimal function value: -15.659763328522677\n",
      "optimal value: [1. 1. 1.]\n",
      "status: SUCCESS, optimal function value: -15.659763328522677\n",
      "optimal value: [1. 1. 1.]\n",
      "status: SUCCESS, optimal function value: -15.659763328522677\n",
      "optimal value: [1. 1. 1.]\n",
      "status: SUCCESS, optimal function value: -15.659763328522677\n",
      "optimal value: [1. 1. 1.]\n",
      "status: SUCCESS, optimal function value: -12.83161851988641\n",
      "optimal value: [0. 1. 1.]\n",
      "status: SUCCESS]\n",
      "[5.8248291015625, 5.7138519287109375, 8.509468078613281, 15.318723678588867, 46.17552208900452, 46.848917961120605, 92.52067303657532, 321.0398819446564, 665.3400218486786]\n"
     ]
    }
   ],
   "source": [
    "print(results)\n",
    "print(times)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f1d7bc6",
   "metadata": {},
   "source": [
    "\n",
    "# Generate 4 qubit problem and solve it increasing num_value_qubits\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "fb99f5ef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: -8.152247856583777\n",
      "optimal value: [0. 0. 0. 1.]\n",
      "status: SUCCESS\n"
     ]
    }
   ],
   "source": [
    "NUM_QUBITS=4\n",
    "qubo = create_qubo_random(NUM_QUBITS)\n",
    "result = CplexOptimizer().solve(qubo)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "c97aee4f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: 14.834838973815149\n",
      "optimal value: [1. 0. 1. 0.]\n",
      "status: SUCCESS\n",
      "37.90915608406067\n",
      "optimal function value: 18.675638232775764\n",
      "optimal value: [1. 1. 1. 1.]\n",
      "status: SUCCESS\n",
      "75.60953974723816\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0. 0. 0.]\n",
      "status: SUCCESS\n",
      "62.50232195854187\n",
      "optimal function value: -1.9554189836465237\n",
      "optimal value: [0. 0. 1. 1.]\n",
      "status: SUCCESS\n",
      "100.16268014907837\n",
      "optimal function value: 15.234904691570323\n",
      "optimal value: [0. 1. 1. 0.]\n",
      "status: SUCCESS\n",
      "225.51152515411377\n",
      "optimal function value: 0.0\n",
      "optimal value: [0. 0. 0. 0.]\n",
      "status: SUCCESS\n",
      "263.3851127624512\n",
      "optimal function value: -8.152247856583777\n",
      "optimal value: [0. 0. 0. 1.]\n",
      "status: SUCCESS\n",
      "801.6616072654724\n",
      "optimal function value: 18.675638232775764\n",
      "optimal value: [1. 1. 1. 1.]\n",
      "status: SUCCESS\n",
      "2161.110187768936\n",
      "optimal function value: 8.337606913015312\n",
      "optimal value: [0. 1. 1. 1.]\n",
      "status: SUCCESS\n",
      "3465.0600917339325\n"
     ]
    }
   ],
   "source": [
    "results = []\n",
    "times = []\n",
    "for num_value_qubits in range(1, 10):\n",
    "    result, exec_time =  call_grover(qubo, num_value_qubits)\n",
    "    print(result)\n",
    "    print(exec_time)\n",
    "    results.append(result)\n",
    "    times.append(exec_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "2edbd3bf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[optimal function value: 14.834838973815149\n",
      "optimal value: [1. 0. 1. 0.]\n",
      "status: SUCCESS, optimal function value: 18.675638232775764\n",
      "optimal value: [1. 1. 1. 1.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0. 0. 0.]\n",
      "status: SUCCESS, optimal function value: -1.9554189836465237\n",
      "optimal value: [0. 0. 1. 1.]\n",
      "status: SUCCESS, optimal function value: 15.234904691570323\n",
      "optimal value: [0. 1. 1. 0.]\n",
      "status: SUCCESS, optimal function value: 0.0\n",
      "optimal value: [0. 0. 0. 0.]\n",
      "status: SUCCESS, optimal function value: -8.152247856583777\n",
      "optimal value: [0. 0. 0. 1.]\n",
      "status: SUCCESS, optimal function value: 18.675638232775764\n",
      "optimal value: [1. 1. 1. 1.]\n",
      "status: SUCCESS, optimal function value: 8.337606913015312\n",
      "optimal value: [0. 1. 1. 1.]\n",
      "status: SUCCESS]\n",
      "[37.90915608406067, 75.60953974723816, 62.50232195854187, 100.16268014907837, 225.51152515411377, 263.3851127624512, 801.6616072654724, 2161.110187768936, 3465.0600917339325]\n"
     ]
    }
   ],
   "source": [
    "print(results)\n",
    "print(times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3853d034",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}