{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a06ce7d1",
   "metadata": {},
   "source": [
    "# Portfolio Optimization with Grover Adaptive Search\n",
    "\n",
    "Let's consider a portfolio optimization where we want to find the optimal combination of three possible assets. The optimization problem is given by\n",
    "\n",
    "$$\n",
    "\\min_x x^T Q x + \\mu^T x\n",
    "$$\n",
    "\n",
    "with\n",
    "\n",
    "$$\n",
    "Q \n",
    "=\n",
    "\\begin{pmatrix}\n",
    "1 & 0 & -2 \\\\\n",
    "0 & 2 & -1 \\\\\n",
    "-2 & -1 & 5\n",
    "\\end{pmatrix},~~\n",
    "\\mu = \n",
    "\\begin{pmatrix}\n",
    "-1 \\\\ 2 \\\\ -3\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "432f0197",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "Q = np.array([\n",
    "    [1, 0, -2],\n",
    "    [0, 2, -1],\n",
    "    [-2, -1, 5]\n",
    "]) \n",
    "mu = np.array([-1, 2, -3])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb6aee57",
   "metadata": {},
   "source": [
    "We define a `QuadraticProgram` based on the above"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "67bedda1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "minimize x0^2 - 4*x0*x2 + 2*x1^2 - 2*x1*x2 + 5*x2^2 - x0 + 2*x1 - 3*x2 (3 variables, 0 constraints, '')\n"
     ]
    }
   ],
   "source": [
    "from qiskit_optimization import QuadraticProgram\n",
    "\n",
    "qp = QuadraticProgram()\n",
    "_ = [qp.binary_var() for _ in range(3)]\n",
    "qp.minimize(linear=mu, quadratic=Q)\n",
    "print(qp)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "387d1f6c",
   "metadata": {},
   "source": [
    "and then use Qiskit Optimization's `GroverOptimizer` to optimize!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "40082a3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.primitives import Sampler\n",
    "from qiskit_optimization.algorithms import GroverOptimizer\n",
    "\n",
    "num_value_qubits = 6  # number of qubits to represent the threshold and cost\n",
    "num_iterations = 10  # number of times the solution has to stay the same\n",
    "opt = GroverOptimizer(num_value_qubits, num_iterations=num_iterations, sampler=Sampler())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0ae7478a",
   "metadata": {},
   "outputs": [],
   "source": [
    "result = opt.solve(qp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1b9390d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fval=-2.0, x0=1.0, x1=0.0, x2=1.0, status=SUCCESS\n"
     ]
    }
   ],
   "source": [
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4adaec92",
   "metadata": {},
   "source": [
    "Since this is a small instance we can manually verify the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d1df38ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "possible_states = [np.array([x1, x2, x3]) for x1 in range(2) for x2 in range(2) for x3 in range(2)]\n",
    "values = [x.dot(Q.dot(x)) + mu.dot(x) for x in possible_states]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5c06e660",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAEPCAYAAABLIROyAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAAsTAAALEwEAmpwYAAARRElEQVR4nO3de7CcdX3H8feHi5eRCCpRUQih1aqAinpqcWzVItYLiNihirYV7UzTaauFahUYOhV1Wpney9DapoVBERW0KshFbpJQdVQSjFwMl1ZB0CrBegGdWi7f/rEbOJycc3Jywu5vk9/7NZPJ7vPsPr/P7En2c557qgpJUn92aB1AktSGBSBJnbIAJKlTFoAkdcoCkKRO7dQ6wJbYfffda/ny5a1jSNI2Ze3atXdU1dKZ07epAli+fDlr1qxpHUOStilJbpltupuAJKlTFoAkdcoCkKROWQCS1CkLQJI61bwAkuyY5KtJzmudRZJ60rwAgKOB9a1DSFJvmhZAkj2BQ4B/a5lDknrU+kSwvwfeBSyZ6wVJVgArAJYtWzaeVLrf8uPObzb2zScdMu/8Sc6mxWn5M4X+fq7N1gCSHArcXlVr53tdVa2sqqmqmlq6dJMzmSVJi9RyE9ALgcOS3Ax8DDgoyYcb5pGkrjQrgKo6vqr2rKrlwJHA56rqt1rlkaTeTMJRQJKkBlrvBAagqlYBqxrHkKSuuAYgSZ2yACSpUxaAJHXKApCkTlkAktQpC0CSOmUBSFKnLABJ6pQFIEmdsgAkqVMWgCR1ygKQpE5ZAJLUKQtAkjplAUhSpywASeqUBSBJnbIAJKlTFoAkdcoCkKROWQCS1CkLQJI6ZQFIUqcsAEnqVLMCSPKIJF9J8rUk1yV5T6ssktSjnRqO/TPgoKq6K8nOwOeTXFhVX2qYSZK60awAqqqAu4ZPdx7+qVZ5JKk3TfcBJNkxyTrgduCSqvryLK9ZkWRNkjUbNmwYe0ZJ2l41LYCqureqDgD2BJ6fZP9ZXrOyqqaqamrp0qVjzyhJ26uJOAqoqn4IrAJe0TaJJPWj5VFAS5PsNnz8SOBg4PpWeSSpNy2PAtoD+GCSHRkU0dlVdV7DPJLUlZZHAV0NPKfV+JLUu4nYByBJGj8LQJI6ZQFIUqcsAEnqlAUgSZ2yACSpUxaAJHXKApCkTlkAktQpC0CSOmUBSFKnLABJ6pQFIEmdsgAkqVMWgCR1ygKQpE5ZAJLUKQtAkjplAUhSpywASeqUBSBJnbIAJKlTFoAkdcoCkKRONSuAJHsluTzJ+iTXJTm6VRZJ6tFODce+B3hHVV2VZAmwNsklVfX1hpkkqRvN1gCq6r+r6qrh4zuB9cCTW+WRpN60XAO4X5LlwHOAL88ybwWwAmDZsmXjDTYmy487v9nYN590SLOxJbXVfCdwkl2AfweOqaofz5xfVSuraqqqppYuXTr+gJK0nWpaAEl2ZvDlf2ZVfbJlFknqTcujgAKcCqyvqr9tlUOSetVyDeCFwG8DByVZN/zzqoZ5JKkrzXYCV9XngbQaX5J613wnsCSpDQtAkjplAUhSpywASeqUBSBJnbIAJKlTFoAkdcoCkKROWQCS1CkLQJI6ZQFIUqcsAEnqlAUgSZ3aogJIskOSR48qjCRpfDZbAEk+kuTRSR4FfB24Ick7Rx9NkjRKC1kD2Hd4r97DgQuAZQxu5CJJ2oYtpAB2Ht6793DgnKq6G6iRppIkjdxCCuBfgJuBRwFXJNkb+PEoQ0mSRm+zt4SsqpOBk6dNuiXJr44ukiRpHBayE/gJSU5NcuHw+b7AUSNPJkkaqYVsAjoduAh40vD5jcAxI8ojSRqThRTA7lV1NnAfQFXdA9w70lSSpJFbSAH8JMnjGB75k+RA4EcjTSVJGrnN7gQG3g6cC/x8ki8AS4EjRppKkjRyCzkK6KokLwaeBgS4YXguwFZLchpwKHB7Ve3/UCxTkrQwmy2AJG+aMem5SaiqDz0E458OnAI8FMuSJG2BhWwC+sVpjx8BvBS4iofgS7uqrkiyfGuXI0nacgvZBPS26c+T7AqcMbJEMyRZAawAWLZs2biGlaTt3mLuB/BT4KkPdZC5VNXKqpqqqqmlS5eOa1hJ2u4tZB/AZ3jg4m87APsCZ48ylCRp9BayD+Cvpz2+B7ilqm4bUR5J0pgsZB/A6lENnuSjwEuA3ZPcBry7qk4d1XiSpAfMWQBJ7mT26/4HqKra6ltDVtUbtnYZkqTFmbMAqmrJOINIksZrIfsAAEjyeAbnAQBQVd8aSSJJ0lgs5H4AhyW5CfgmsJrB3cEuHHEuSdKILeQ8gPcBBwI3VtU+DM4E/sJIU0mSRm4hBXB3VX0f2CHJDlV1OXDAaGNJkkZtIfsAfphkF+A/gDOT3M7gfABJ0jZsIWsAVwC7AUcDnwX+C3j1CDNJksZgIQUQBvcEXgXsApw13CQkSdqGbbYAquo9VbUf8IcMbgy/OsmlI08mSRqpLbka6O3Ad4HvA48fTRxJ0rgs5DyA30+yCrgM2B343ap61qiDSZJGayFHAe0NHFNV60acRZI0Rgu5Guhx4wgiSRqvxdwRTJK0HbAAJKlTFoAkdcoCkKROWQCS1CkLQJI6ZQFIUqcsAEnqlAUgSZ2yACSpUxaAJHWqaQEkeUWSG5L8ZxKvOSRJY9SsAJLsCPwj8EpgX+ANSfZtlUeSepOqajNw8gLgxKp6+fD58QBV9f653rNkyZJ63vOeN6aE4/Olb7S7w+aBP/e4eeebbXaby6bFafkzhe3357p69eq1VTU1c/pC7gcwKk8Gbp32/Dbgl2a+KMkKYAXAwx/+8PEkG7NJ/kdntu3PJBenP9PxalkAmWXaJqsjVbUSWAkwNTVVq1atGnEsafu2/Ljzm4296qRDmo3ds2S2r9u2O4FvA/aa9nxP4DuNskhSd1oWwJXAU5Psk+RhwJHAuQ3zSFJXmm0Cqqp7krwVuAjYETitqq5rlUeSetNyHwBVdQFwQcsMktQrzwSWpE5ZAJLUKQtAkjplAUhSpywASeqUBSBJnbIAJKlTFoAkdcoCkKROWQCS1CkLQJI6ZQFIUqcsAEnqlAUgSZ2yACSpUxaAJHXKApCkTlkAktQpC0CSOmUBSFKnLABJ6pQFIEmdsgAkqVMWgCR1qkkBJPmNJNcluS/JVIsMktS7VmsA1wK/DlzRaHxJ6t5OLQatqvUASVoML0liG9gHkGRFkjVJ1mzYsKF1HEnaboxsDSDJpcATZ5l1QlWds9DlVNVKYCXA1NRUPUTxJKl7IyuAqjp4VMuWJG29id8EJEkajVaHgb42yW3AC4Dzk1zUIock9azVUUCfAj7VYmxJ0oCbgCSpUxaAJHXKApCkTlkAktQpC0CSOmUBSFKnLABJ6pQFIEmdsgAkqVMWgCR1ygKQpE5ZAJLUKQtAkjplAUhSpywASeqUBSBJnbIAJKlTFoAkdcoCkKROWQCS1CkLQJI6ZQFIUqcsAEnqlAUgSZ1qUgBJ/irJ9UmuTvKpJLu1yCFJPWu1BnAJsH9VPQu4ETi+UQ5J6laTAqiqi6vqnuHTLwF7tsghST3bqXUA4HeAs+aamWQFsAJg2bJl48okbbduPumQ1hE0IUZWAEkuBZ44y6wTquqc4WtOAO4BzpxrOVW1ElgJMDU1VSOIKkldGlkBVNXB881PchRwKPDSqvKLXZLGrMkmoCSvAI4FXlxVP22RQZJ61+oooFOAJcAlSdYl+edGOSSpW03WAKrqKS3GlSQ9wDOBJalTFoAkdcoCkKROWQCS1KlsS4fgJ9kA3NJo+N2BOxqNvTlmWxyzLY7ZFqdltr2raunMidtUAbSUZE1VTbXOMRuzLY7ZFsdsizOJ2dwEJEmdsgAkqVMWwMKtbB1gHmZbHLMtjtkWZ+KyuQ9AkjrlGoAkdcoCkKROWQCS1CkLQJI6NQn3BJ44SQI8H3gyUMB3gK9M8p3Lkjy9qq5vnMHPTdqGeBTQDEl+Dfgn4Cbg28PJewJPAf6gqi5ulW0+Sb5VVcsaju/ntnU5LM/FZfBz2wquAWzqH4CDq+rm6ROT7ANcADyjRahhhpPnmgXsNsYos/FzW6T5yjPJxJYncDEwkb90+LktjAWwqZ2A22aZ/m1g5zFnmektwDuAn80y7w1jzjKTn9viWZ6L4+e2lSyATZ0GXJnkY8Ctw2l7AUcCpzZLNXAlcG1VfXHmjCQnjj/Og/i5LZ7luTh+blvJfQCzSLIvcBiD7Yph8I/s3Kr6euNcjwX+t6p+2jLHXJI8A3gNfm5bJMnxwOuA2crz7Kp6f8NsnwP+dI7y/GZV7dMg1sbx/dy2kgUgTQB/6Vgcf+nYOhbADEl2BY4HDgc23kDhduAc4KSq+mGbZJOdbT5JLqyqV7bOMZtJziaNmvsANnU28DngJVX1XYAkTwTeDHwceFm7aHNmO6p1tiTPnWsWcMAYo2waYIKzwWQX+yRnm88kF/skZXMNYIYkN1TV07Z03jhMeLZ7gdUMvlRnOrCqHjnmSPeb5GwASS5iUOwfnOWXjpdWVctinyvbUQyOwJnUXzrOq6o9xpnnQQEmONt0FsAMSS4GLmXwD/57w2lPYPCf8WVVdbDZZs12LfDaqrpplnm3VtVeDWJtHH9isw0zTHKxT3K2iS32Sc42nZuANvV64Dhg1fDLFeB7wLkMjjhoaZKzncjc15Z62xhzzOZEJjcbwC1J3sXsxX7rfG8cg0nOth74vbmKvUGe6SY52/1cA5jFjCMLNp5efk5VrW8ajInP9nQ2zXau2eaX5DEMiv01wOOHkzcW+0lV9QOzzZrtCOCaqrphlnmHV9Wnx5/q/vEnNtt0Xg10hiTHAh9h8CXxZeArw1kfTXJcs2BMfLZ3MTgeOwxyXTl8bLbNqKofVNWxVfX0qnrs8M8zqupYBjtfzTZ7tk/M9gU79JixhplhkrNN5xrADEluBParqrtnTH8YcF1VPbVNMrMt1iRn25xJuVjdbMy2OJOUzX0Am7oPeBJwy4zpewzntWS2xZnkbCS5eq5ZwBPmmDcWZlucSc42nQWwqWOAy5LcxAM7uZYxuKzxW1uFGjoGsy3GMUxuNhh8IbwcmLk9PcAmlxIYM7MtziRnu58FMENVfTbJL/DANcY3nl5+ZVXdazazjcB5wC5VtW7mjCSrxp7mwcy2OJOc7X7uA5CkTnkUkCR1ygKQpE5ZANIsktw1x/T3JlnUJTeSHJDkVdOeHzYJ5yGoX+4DkGaR5K6q2uUhXuabgamqmoQjjyTXALR9SPKmJFcn+VqSM5LsneSy4bTLkiwbvu70JB9IcnmSbyR5cZLTkqxPcvqMZf5NkquG71867f1HDB/fnOQ9w9dcM7zcBEmen+SLSb46/Ptpw5PO3gu8Psm6JK9P8uYkpwzfM1/ek4fL+ca0sfdIcsVwWdcm+ZUxfdTajlgA2uYl2Q84ATioqp4NHA2cAnyoqp4FnAlMv0n3Y4CDgD8GPgP8HbAf8MwkBwxf8yjgqqp6LoOrOr57juHvGL7mA8CfDKddD7yoqp4D/BnwF1X1f8PHZ1XVAVV11ozlzJd3D+CXgUOBk4bT3ghcVFUHAM8G1s33GUmzsQC0PTgI+ERV3QFQVf8DvIDBdZMAzmDwBbrRZ2qw7fMa4HtVdU1V3QdcBywfvuY+YOOX9IdnvH+6Tw7/XjvtvbsCH8/gMtQby2Vz5sv76aq6b3ibw41nkV4JvCWDm9o/s6ruXMAY0oNYANoehMEF8uYzff7Phn/fN+3xxudznRw51/I3vv/eae99H3B5Ve0PvBp4xGaybW686RkDUFVXAC8Cvg2ckeRNixhDnbMAtD24DHhdksfB/Tfk/iJw5HD+bwKf38Jl7gAcMXz8xi18/64MvphhcN38je4Elszxni3Km2Rv4Paq+lfgVGCuO1BJc/JSENrmVdV1Sf4cWJ3BnZi+CvwRcFqSdwIbgLds4WJ/AuyXZC3wIwY341movwQ+mOTtDG6nuNHlwHFJ1gHvn/GeLc37EuCdSe4G7gJcA9AW8zBQSeqUm4AkqVMWgCR1ygKQpE5ZAJLUKQtAkjplAUhSpywASerU/wPqlg+To/dyYwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "labels = [\"\".join(map(str, x)) for x in possible_states]\n",
    "plt.bar(np.arange(len(values)), values)\n",
    "plt.xticks(np.arange(len(values)), labels, rotation=90)\n",
    "plt.axhline(0, color=\"k\")\n",
    "\n",
    "plt.xlabel(\"combinations\")\n",
    "plt.ylabel(\"values\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cb48386",
   "metadata": {},
   "source": [
    "Indeed, `101` is the combination with the minimal cost: the optimal portfolio combines assets 1 and 3!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67920a56",
   "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.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}