docs/tutorials/04_grover_optimizer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grover Optimizer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Grover Adaptive Search (GAS) has been explored as a possible solution for combinatorial optimization problems, alongside variational algorithms such as Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). The algorithm iteratively applies Grover Search to find the optimum value of an objective function, by using the best-known value from the previous run as a threshold. The adaptive oracle used in GAS recognizes all values above or below the current threshold (for max and min respectively), decreasing the size of the search space every iteration the threshold is updated, until an optimum is found.\n",
    "\n",
    "In this notebook we will explore each component of the `GroverOptimizer`, which utilizes the techniques described in GAS, by minimizing a Quadratic Unconstrained Binary Optimization (QUBO) problem, as described in [1]\n",
    "\n",
    "### References\n",
    "\n",
    "[1] [A. Gilliam, S. Woerner, C. Gonciulea, *Grover Adaptive Search for Constrained Polynomial Binary Optimization,*  arXiv  preprint arXiv:1912.04088  (2019).](https://arxiv.org/abs/1912.04088)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grover Adaptive Search\n",
    "Grover Search, the core element of GAS, needs three ingredients:\n",
    "\n",
    "1. A state preparation operator $A$ to construct a superposition of all states in the search space.\n",
    "\n",
    "2. An oracle operator $O$, that recognizes the states of interest and multiplies their amplitudes by -1.\n",
    "\n",
    "3. The Grover diffusion operator $D$, that multiplies the amplitude of the $|0\\rangle_n$ state by -1.\n",
    "\n",
    "While implementations of GAS vary around the specific use case, the general framework still loosely follows the steps described below.\n",
    "\n",
    "<br>\n",
    "<div>\n",
    "<img src=\"aux_files/GAS-Algorithm.png\" width=\"400\"/>\n",
    "</div>\n",
    "<br>\n",
    "\n",
    "`GroverOptimizer` uses `QuadraticProgramToNegativeValueOracle` to construct $A_y$ such that it prepares a $n$-qubit register to represent the equal superposition of all $|x\\rangle_n$ and a $m$-qubit register to (approximately) represent the corresponding $|Q(x)-y\\rangle_m$. Then, all states with $(Q(x) - y)$ negative should be flagged by $O_y$. Note that in the implementation discussed, the oracle operator is actually independent of $y$, but this is not a requirement. For clarity, we will refer to the oracle as $O$ when the oracle is independent of $y$.\n",
    "\n",
    "Put formally, `QuadraticProgramToNegativeValueOracle` constructs an $A_y$ and $O$ such that:\n",
    "\n",
    "<br>\n",
    "<div>\n",
    "<img src=\"aux_files/a-o-dfn.png\" width=\"400\"/>\n",
    "</div>\n",
    "<br>\n",
    "\n",
    "where $|x\\rangle$ is the binary encoding of the integer $x$. \n",
    "\n",
    "At each iteration in which the threshold $y$ is updated, we adapt $A_y$ such that the function values are shifted up or down (for minimum and maximum respectively) by $y$. For example, in the context of finding the minimum, as the value of $y$ decreases, the search space (negative values) also decreases, until only the minimum value remains. A concrete example will be explored in the next section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find the Minimum of a QUBO Problem using GroverOptimizer\n",
    "The following is a toy example of a minimization problem.\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\min_{x \\in \\{0, 1\\}^3} -2x_0x_2 - x_1x_2 - 1x_0 + 2x_1 - 3x_2.\n",
    "\\end{eqnarray}\n",
    "\n",
    "For our initial steps, we create a docplex model that defines the problem above, and then use the `from_docplex_mp()` function to convert the model to a `QuadraticProgram`, which can be used to represent a QUBO in Qiskit Optimization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit_algorithms import NumPyMinimumEigensolver\n",
    "from qiskit.primitives import Sampler\n",
    "from qiskit_optimization.algorithms import GroverOptimizer, MinimumEigenOptimizer\n",
    "from qiskit_optimization.translators import from_docplex_mp\n",
    "from docplex.mp.model import Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem name: docplex_model1\n",
      "\n",
      "Minimize\n",
      "  -2*x0*x2 - x1*x2 - x0 + 2*x1 - 3*x2\n",
      "\n",
      "Subject to\n",
      "  No constraints\n",
      "\n",
      "  Binary variables (3)\n",
      "    x0 x1 x2\n",
      "\n"
     ]
    }
   ],
   "source": [
    "model = Model()\n",
    "x0 = model.binary_var(name=\"x0\")\n",
    "x1 = model.binary_var(name=\"x1\")\n",
    "x2 = model.binary_var(name=\"x2\")\n",
    "model.minimize(-x0 + 2 * x1 - 3 * x2 - 2 * x0 * x2 - 1 * x1 * x2)\n",
    "qp = from_docplex_mp(model)\n",
    "print(qp.prettyprint())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we create a `GroverOptimizer` that uses 6 qubits to encode the value, and will terminate after there have been 10 iterations of GAS without progress (i.e. the value of $y$ does not change). The `solve()` function takes the `QuadraticProgram` we created earlier, and returns a results object that contains information about the run."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "objective function value: -6.0\n",
      "variable values: x0=1.0, x1=0.0, x2=1.0\n",
      "status: SUCCESS\n"
     ]
    }
   ],
   "source": [
    "grover_optimizer = GroverOptimizer(6, num_iterations=10, sampler=Sampler())\n",
    "results = grover_optimizer.solve(qp)\n",
    "print(results.prettyprint())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This results in the optimal solution $x_0=1$, $x_1=0$, $x_2=1$ and the optimal objective value of $-6$ (most of the time, since it is a randomized algorithm).\n",
    "In the following, a custom visualization of the quantum state shows a possible run of `GroverOptimizer` applied to this QUBO.\n",
    "\n",
    "<br>\n",
    "<div>\n",
    "<img src=\"aux_files/GAS-QUBO-Example.png\" width=\"800\"/>\n",
    "</div>\n",
    "<br>\n",
    "\n",
    "Each graph shows a single iteration of GAS, with the current values of $r$ (= iteration counter) and $y$ (= threshold/offset) shown in the title. The X-axis displays the integer equivalent of the input (e.g. '101' $\\rightarrow$ 5), and the Y-axis shows the possible function values. As there are 3 binary variables, there are $2^3=8$ possible solutions, which are shown in each graph. The color intensity indicates the probability of measuring a certain result (with bright intensity being the highest), while the actual color indicates the corresponding phase (see phase color-wheel below). Note that as $y$ decreases, we shift all of the values up by that amount, meaning there are fewer and fewer negative values in the distribution, until only one remains (the minimum).\n",
    "\n",
    "<br>\n",
    "<div>\n",
    "<img src=\"aux_files/color-wheel-phase.png\" width=\"200\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Check that GroverOptimizer finds the correct value\n",
    "\n",
    "We can verify that the algorithm is working correctly using the `MinimumEigenOptimizer` in Qiskit optimization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "objective function value: -6.0\n",
      "variable values: x0=1.0, x1=0.0, x2=1.0\n",
      "status: SUCCESS\n"
     ]
    }
   ],
   "source": [
    "exact_solver = MinimumEigenOptimizer(NumPyMinimumEigensolver())\n",
    "exact_result = exact_solver.solve(qp)\n",
    "print(exact_result.prettyprint())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<h3>Version Information</h3><table><tr><th>Qiskit Software</th><th>Version</th></tr><tr><td><code>qiskit-terra</code></td><td>0.23.0</td></tr><tr><td><code>qiskit-aer</code></td><td>0.11.1</td></tr><tr><td><code>qiskit-optimization</code></td><td>0.5.0</td></tr><tr><td><code>qiskit-machine-learning</code></td><td>0.6.0</td></tr><tr><th>System information</th></tr><tr><td>Python version</td><td>3.9.15</td></tr><tr><td>Python compiler</td><td>Clang 14.0.0 (clang-1400.0.29.102)</td></tr><tr><td>Python build</td><td>main, Oct 11 2022 22:27:25</td></tr><tr><td>OS</td><td>Darwin</td></tr><tr><td>CPUs</td><td>4</td></tr><tr><td>Memory (Gb)</td><td>16.0</td></tr><tr><td colspan='2'>Tue Dec 06 21:47:01 2022 JST</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div style='width: 100%; background-color:#d5d9e0;padding-left: 10px; padding-bottom: 10px; padding-right: 10px; padding-top: 5px'><h3>This code is a part of Qiskit</h3><p>&copy; Copyright IBM 2017, 2022.</p><p>This code is licensed under the Apache License, Version 2.0. You may<br>obtain a copy of this license in the LICENSE.txt file in the root directory<br> of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.<p>Any modifications or derivative works of this code must retain this<br>copyright notice, and modified files need to carry a notice indicating<br>that they have been altered from the originals.</p></div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import tutorial_magics\n",
    "\n",
    "%qiskit_version_table\n",
    "%qiskit_copyright"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}