examples/QAOA_LABS_optimization.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import qokit\n",
    "import scipy.optimize\n",
    "from qokit import parameter_utils\n",
    "from qokit.qaoa_objective_labs import get_qaoa_labs_objective"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Optimize QAOA parameters for LABS problem\n",
    "\n",
    "We'll show an example of optimizing overlap with the ground state. Expectation value optimization is analogous.\n",
    "\n",
    "\n",
    "First, let's get known parameters for largest depth $p$ that we have. QOKit has a built-in set of good LABS parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum p available for N=10 is 8\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>N</th>\n",
       "      <th>p</th>\n",
       "      <th>overlap</th>\n",
       "      <th>gamma</th>\n",
       "      <th>beta</th>\n",
       "      <th>merit factor</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>35</th>\n",
       "      <td>10</td>\n",
       "      <td>1</td>\n",
       "      <td>0.127219</td>\n",
       "      <td>[0.0788139605]</td>\n",
       "      <td>[-0.1899602111]</td>\n",
       "      <td>1.923268</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>36</th>\n",
       "      <td>10</td>\n",
       "      <td>2</td>\n",
       "      <td>0.196232</td>\n",
       "      <td>[0.06896497310000001, 0.1511922366]</td>\n",
       "      <td>[-0.1966433649, -0.1328573804]</td>\n",
       "      <td>2.174876</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>37</th>\n",
       "      <td>10</td>\n",
       "      <td>3</td>\n",
       "      <td>0.258441</td>\n",
       "      <td>[0.063816785, 0.1396294913, 0.1538820941]</td>\n",
       "      <td>[-0.2082662354, -0.1383489014, -0.1215130558]</td>\n",
       "      <td>2.320238</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>38</th>\n",
       "      <td>10</td>\n",
       "      <td>4</td>\n",
       "      <td>0.318326</td>\n",
       "      <td>[0.0655247286, 0.1319443875, 0.1430007569, 0.1...</td>\n",
       "      <td>[-0.20560510070000002, -0.1459282952, -0.12584...</td>\n",
       "      <td>2.445458</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>39</th>\n",
       "      <td>10</td>\n",
       "      <td>5</td>\n",
       "      <td>0.362467</td>\n",
       "      <td>[0.0661013761, 0.1351407309, 0.136539053600000...</td>\n",
       "      <td>[-0.2261604879, -0.1482192504, -0.1413220406, ...</td>\n",
       "      <td>2.506400</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     N  p   overlap                                              gamma  \\\n",
       "35  10  1  0.127219                                     [0.0788139605]   \n",
       "36  10  2  0.196232                [0.06896497310000001, 0.1511922366]   \n",
       "37  10  3  0.258441          [0.063816785, 0.1396294913, 0.1538820941]   \n",
       "38  10  4  0.318326  [0.0655247286, 0.1319443875, 0.1430007569, 0.1...   \n",
       "39  10  5  0.362467  [0.0661013761, 0.1351407309, 0.136539053600000...   \n",
       "\n",
       "                                                 beta  merit factor  \n",
       "35                                    [-0.1899602111]      1.923268  \n",
       "36                     [-0.1966433649, -0.1328573804]      2.174876  \n",
       "37      [-0.2082662354, -0.1383489014, -0.1215130558]      2.320238  \n",
       "38  [-0.20560510070000002, -0.1459282952, -0.12584...      2.445458  \n",
       "39  [-0.2261604879, -0.1482192504, -0.1413220406, ...      2.506400  "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N = 10\n",
    "parameters = parameter_utils.get_best_known_parameters_for_LABS_wrt_overlap(N)\n",
    "known_p = parameters.p.max()\n",
    "print(f\"Maximum p available for N={N} is {known_p}\")\n",
    "parameters.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have the parameters for `p_known`, let's find parameters for a larger depth! We will extrapolate the parameters that we already know to have a good starting point for optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = known_p + 1\n",
    "gamma, beta = parameter_utils.get_best_known_parameters_for_LABS_wrt_overlap_for_p(N, known_p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next cell will find an initial guess and create a function which maps parameters to the overlap. We can use `get_qaoa_labs_objective` with different parameterizations, but in this case, we'll use Fourier-transformed basis. \n",
    "\n",
    "The simulation will run on GPU if it is available, and if the problem is small, you will get a `NumbaPerformanceWarning`, which just indicates that you're not saturating capabilities of your GPU."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "u, v = parameter_utils.to_fourier_basis(gamma, beta)\n",
    "init_u, init_v = parameter_utils.extrapolate_parameters_in_fourier_basis(u, v, p, 1)\n",
    "init_freq = np.hstack([init_u, init_v])\n",
    "f = get_qaoa_labs_objective(N, p, parameterization='freq', objective='overlap')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success probability at p=9 before optimization is 0.49333386759027686\n"
     ]
    }
   ],
   "source": [
    "print(f\"Success probability at p={p} before optimization is {1-f(init_freq)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will try optimizing further!\n",
    "\n",
    "Specifically, we will extrapolate the parameters in the fourier basis using the interpolation scheme of https://arxiv.org/abs/1812.01041 and then optimize in the fourier basis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "res = scipy.optimize.minimize(f, init_freq, method='COBYLA', options={'rhobeg': 0.01/N})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success probability at p=9 after optimization is 0.5243370462962005\n"
     ]
    }
   ],
   "source": [
    "gamma, beta = parameter_utils.from_fourier_basis(res.x[:p], res.x[p:])\n",
    "f_bg = get_qaoa_labs_objective(N, p, parameterization='gamma beta', objective='overlap')\n",
    "\n",
    "print(f'Success probability at p={p} after optimization is {1-f_bg(gamma, beta)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use these parameters to solve LABS on a quantum computer!\n",
    "\n",
    "---"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py39",
   "language": "python",
   "name": "py39"
  },
  "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.9.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}