{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grover's Search Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Grover's algorithm is arguably one of the canonical quantum algorithms that kick-started the field of quantum computing. In the future, it could possibly serve as a hallmark application of quantum computing. Grover's algorithm allows us to find a particular register in an unordered database with $N$ entries in just $O(\\sqrt{N})$ steps, compared to the best classical algorithm taking on average $N/2$ steps, thereby providing a __quadratic speedup__. For large databases (with a large number of entries, $N$), a quadratic speedup can provide a significant advantage. For a database with one million entries, a quantum computer running Grover's algorithm would need about 1000 runs, while a classical computer would need, on average, $500,000$ runs.\n",
    "\n",
    "In this notebook, we implement Gover's algorithm based on ion-trap experiments [1]. In particular, we implement the phase oracle (see Figure 1d and 1e of this paper). For a compherensive description of the algorithm see Chapter 6 of [2]. In the ion-trap experiments [1], the oracle encodes bitstrings with length three. Here, we extend the bitstrings to arbitrary length. We use generalized Toffoli gates to construct the oracle. Following reference [3], the generalized Toffoli gates is decomposed into Toffoli gates. \n",
    "\n",
    "\n",
    "---\n",
    "# References <a name=\"ref\"></a>\n",
    "\n",
    "[1] C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath & C. Monroe (2017). \"Complete 3-Qubit Grover search on a programmable quantum computer\", Nature Communications, Vol 8, Art 1918, doi:10.1038/s41467-017-01904-7. [arXiv:1703.10535](https://arxiv.org/abs/1703.10535).\n",
    "\n",
    "[2] Nielsen, Michael A., Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press.\n",
    "\n",
    "[3] J. M. Baker, C. Duckering, A. Hoover, F. T. Chong (2019). Decomposing Quantum Generalized Toffoli with an Arbitrary Number of Ancilla. [arXiv:1904.01671](https://arxiv.org/abs/1904.01671)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from notebook_plotting import plot_bitstrings_formatted\n",
    "import numpy as np\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "from braket.aws import AwsDevice\n",
    "from braket.circuits import Circuit\n",
    "from braket.devices import LocalSimulator\n",
    "from braket.tracking import Tracker\n",
    "\n",
    "from braket.experimental.algorithms.grovers_search import (\n",
    "    build_oracle,\n",
    "    grovers_search,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number of data qubits:  3\n",
      "number of ancilla qubits:  3\n",
      "T  : |0| 1 |2| 3 |4|5| 6 |7| 8 |9|10|Result Types|\n",
      "                                                  \n",
      "q0 : -H-C-------C-H-X-C-------C-X-H--Probability--\n",
      "        |       |     |       |      |            \n",
      "q1 : -H-|-C---C-|-H-X-|-C---C-|-X-H--Probability--\n",
      "        | |   | |     | |   | |      |            \n",
      "q2 : -H-|-C---C-|-H-X-|-C---C-|-X-H--Probability--\n",
      "        | |   | |     | |   | |                   \n",
      "q3 : ---X-|-C-|-X-----X-|-C-|-X-------------------\n",
      "          | | |         | | |                     \n",
      "q4 : -----X-C-X---------X-C-X---------------------\n",
      "            |             |                       \n",
      "q5 : -X-H---X-H---X-X-H---X-H---X-----------------\n",
      "\n",
      "T  : |0| 1 |2| 3 |4|5| 6 |7| 8 |9|10|Result Types|\n"
     ]
    }
   ],
   "source": [
    "solution = \"111\"\n",
    "n_qubits = len(solution)\n",
    "\n",
    "oracle = build_oracle(solution)\n",
    "circuit = grovers_search(oracle, n_qubits=n_qubits, n_reps=1)\n",
    "\n",
    "print(\"number of data qubits: \", n_qubits)\n",
    "print(\"number of ancilla qubits: \", circuit.qubit_count - n_qubits)\n",
    "print(circuit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run on a local simulator\n",
    "We demonstrate Grover's algorithm on a classical simulator first. You can choose between a local simulator or an on-demand simulator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "local_simulator = LocalSimulator()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LocalQuantumTask('id':9c9a2aa6-703f-4fda-9132-52d3c6d7abdb)\n"
     ]
    }
   ],
   "source": [
    "task = local_simulator.run(circuit, shots=1000)\n",
    "print(task)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.036 0.033 0.032 0.032 0.034 0.023 0.023 0.787]\n"
     ]
    }
   ],
   "source": [
    "result = task.result()\n",
    "probabilities = result.values[0]\n",
    "print(probabilities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEPCAYAAABP1MOPAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAYAUlEQVR4nO3df5hddWHn8feHYKqCxR+MaJNgshrR1B+IY8CnrdUVapCniVtUEnQVik330agU3RpaZW1K21irBXdDMVIrRW1IcddOZTTWCrpbBTP8EEzSQBqBTNzqiFBxrULgs3+cM3hzc+/MzSTnnpucz+t55sk95/u9936SP+aT81u2iYiI5jqi7gAREVGvFEFERMOlCCIiGi5FEBHRcCmCiIiGO7LuAPvr2GOP9fz58+uOERFxSLnpppu+b3uo09ghVwTz589nbGys7hgREYcUSXd3G8uuoYiIhksRREQ0XKVFIGmJpO2Sdkha3WH8eEnXSbpF0m2SXl1lnoiI2FdlRSBpFrAOOB1YBKyQtKht2nuBjbZfBCwHLqsqT0REdFblFsFiYIftnbYfBDYAy9rmGPj58vUxwHcqzBMRER1UWQRzgF0ty+PlulbvB94oaRwYBd7e6YMkrZQ0JmlsYmKiiqwREY1V98HiFcAnbM8FXg1cJWmfTLbX2x62PTw01PE02IiImKEqi2A3MK9leW65rtV5wEYA218HHgscW2GmiIhoU2URbAYWSlogaTbFweCRtjn3AK8EkPRciiLIvp+IiD6q7Mpi23skrQI2AbOAj9veImkNMGZ7BHgX8DFJv0Nx4Pgc50k5ETGg5q++ttbvv2vtGZV8bqW3mLA9SnEQuHXdRS2vtwK/VGWGiIiYWt0HiyMiomYpgoiIhksRREQ0XIogIqLhUgQREQ2XIoiIaLgUQUREw6UIIiIaLkUQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcJUWgaQlkrZL2iFpdYfxP5d0a/lzh6T7q8wTERH7quxRlZJmAeuA04BxYLOkkfLxlADY/p2W+W8HXlRVnoiI6KzKLYLFwA7bO20/CGwAlk0xfwXwNxXmiYiIDqosgjnArpbl8XLdPiQ9A1gAfLnL+EpJY5LGJiYmDnrQiIgmG5SDxcuBa2w/3GnQ9nrbw7aHh4aG+hwtIuLwVmUR7AbmtSzPLdd1spzsFoqIqEWVRbAZWChpgaTZFL/sR9onSXoO8CTg6xVmiYiILiorAtt7gFXAJmAbsNH2FklrJC1tmboc2GDbVWWJiIjuKjt9FMD2KDDatu6ituX3V5khIiKmNigHiyMioiYpgoiIhksRREQ0XIogIqLhUgQREQ2XIoiIaLgUQUREw6UIIiIaLkUQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGq7QIJC2RtF3SDkmru8x5vaStkrZI+nSVeSIiYl+VPbNY0ixgHXAaMA5sljRie2vLnIXAhcAv2b5P0lOryhMREZ1VuUWwGNhhe6ftB4ENwLK2Ob8FrLN9H4Dt71WYJyIiOqiyCOYAu1qWx8t1rZ4NPFvSP0m6QdKSTh8kaaWkMUljExMTFcWNiGimug8WHwksBF4OrAA+JumJ7ZNsr7c9bHt4aGiovwkjIg5zVRbBbmBey/Lccl2rcWDE9kO2vw3cQVEMERHRJ1UWwWZgoaQFkmYDy4GRtjmfpdgaQNKxFLuKdlaYKSIi2lRWBLb3AKuATcA2YKPtLZLWSFpaTtsE3CtpK3Ad8F9t31tVpoiI2Fdlp48C2B4FRtvWXdTy2sAF5U9ERNSg7oPFERFRsxRBRETDpQgiIhouRRAR0XApgoiIhksRREQ0XIogIqLhUgQREQ2XIoiIaLgUQUREw6UIIiIaLkUQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4SotA0hJJ2yXtkLS6w/g5kiYk3Vr+vKXKPBERsa/KHlUpaRawDjgNGAc2SxqxvbVt6tW2V1WVIyIiptbTFoGk/ynpDEn7swWxGNhhe6ftB4ENwLKZhIyIiOr0+ov9MuBs4E5JayWd0MN75gC7WpbHy3XtzpR0m6RrJM3r9EGSVkoakzQ2MTHRY+SIiOhFT0Vg+0u23wCcBNwFfEnS1ySdK+kxB/D9fw/Mt/0C4B+AK7t8/3rbw7aHh4aGDuDrIiKiXc+7eiQ9BTgHeAtwC3ApRTH8Q5e37AZa/4c/t1z3KNv32v5puXgF8OJe80RExMHR08FiSf8LOAG4Cvh12/+3HLpa0liXt20GFkpaQFEAyyl2L7V+7tNbPmspsG0/80dExAHq9ayhj9kebV0h6eds/9T2cKc32N4jaRWwCZgFfNz2FklrgDHbI8A7JC0F9gA/oNjiiIiIPuq1CC4GRtvWfZ1i11BXZXmMtq27qOX1hcCFPWaIiIgKTFkEkp5GcabP4yS9CFA59PPA4yvOFhERfTDdFsGrKHbXzAU+3LL+AeD3KsoUERF9NGUR2L4SuFLSmbY/06dMERHRR9PtGnqj7U8C8yVd0D5u+8Md3hYREYeQ6XYNHVX+eXTVQSIioh7T7Rr6aPnnH/QnTkRE9Nt0u4Y+MtW47Xcc3DgREdFv0+0auqkvKSIioja9nDUUERGHsel2DV1i+3xJfw+4fdz20sqSRUREX0y3a+iq8s8/qzpIRETUY7pdQzeVf35F0mzgORRbBtvLp45FRMQhrtfbUJ8BXA78C8X9hhZI+m3bn68yXEREVK/Xu49+CHiF7R0Akp4JXAukCCIiDnG9PqHsgckSKO2kuPFcREQc4qY7a+g3ypdjkkaBjRTHCF5H8QSyiIg4xE23a+jXW15/F/jV8vUE8LhKEkVERF9Nd9bQuQfy4ZKWUDzkfhZwhe21XeadCVwDvMR2t2cgR0REBXo9a+ixwHnALwKPnVxv+zeneM8sYB1wGjAObJY0Yntr27wnAO8Ebtzv9BERccB6PVh8FfA0iieWfYXiiWXTHSxeDOywvbO85mADsKzDvD8EPgD8pMcsERFxEPVaBM+y/T7g/5X3HzoDOHma98wBdrUsj5frHiXpJGCe7Wun+iBJKyWNSRqbmJjoMXJERPSi1yJ4qPzzfknPA44BnnogXyzpCIrnIL9rurm219setj08NDR0IF8bERFter2gbL2kJwHvA0Yonlj2vmnesxuY17I8t1w36QnA84DrJUGx62lE0tIcMI6I6J+eisD2FeXLrwD/ocfP3gwslLSAogCWA2e3fOa/AcdOLku6Hnh3SiAior962jUk6SmS/rukmyXdJOkSSU+Z6j229wCrgE3ANmCj7S2S1kjK7asjIgZEr7uGNgBfBc4sl98AXA2cOtWbbI8Co23rLuoy9+U9ZomIiIOo1yJ4uu0/bFm+WNJZVQSKiIj+6vWsoS9KWi7piPLn9RS7fCIi4hA33U3nHqC4yZyA84FPlkNHAD8C3l1luIiIqN509xp6Qr+CREREPXo9RkB5ps/LysXrbX+umkgREdFPvZ4+upbixnBby593SvqTKoNFRER/9LpF8GrgRNuPAEi6ErgFuLCqYBER0R+9njUE8MSW18cc5BwREVGTXrcI/hi4RdJ1FGcQvQxYXVmqiIjom2mLoLxL6CPAKcBLytXvsf2vVQaLiIj+mLYIbD8i6Xdtb6S482hERBxGej1G8CVJ75Y0T9KTJ38qTRYREX3R6zGCsyiuMH5r2/peb0kdEREDqtciWERRAr9MUQj/G7i8qlAREdE/vRbBlcAPgY+Uy2eX615fRaiIiOifXovgebYXtSxfJ2lrFYEiIqK/ej1YfLOkUyYXJJ0M5JGSERGHgV63CF4MfE3SPeXy8cB2SbcDtv2CStJFRETlei2CJTP5cElLgEuBWcAVtte2jf8X4G3AwxTPN1hpO7ucIiL6qKcisH33/n6wpFnAOuA0YBzYLGmk7Rf9p21fXs5fCnyYGZZORETMzP7cdG5/LQZ22N5p+0FgA7CsdYLtH7YsHkVxampERPRRzw+mmYE5wK6W5XHg5PZJkt4GXADMBv5jpw+StBJYCXD88ccf9KAREU1W5RZBT2yvs/1M4D3Ae7vMWW972Pbw0NBQfwNGRBzmqiyC3cC8luW55bpuNgCvqTBPRER0UGURbAYWSlogaTawnLa7l0pa2LJ4BnBnhXkiIqKDyo4R2N4jaRWwieL00Y/b3iJpDTBmewRYJelU4CHgPuDNVeWJiIjOqjxYjO1RYLRt3UUtr99Z5fdHRMT0aj9YHBER9UoRREQ0XIogIqLhUgQREQ2XIoiIaLgUQUREw6UIIiIaLkUQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGq7QIJC2RtF3SDkmrO4xfIGmrpNsk/aOkZ1SZJyIi9lVZEUiaBawDTgcWASskLWqbdgswbPsFwDXAn1aVJyIiOqtyi2AxsMP2TtsPAhuAZa0TbF9n+8fl4g3A3ArzREREB1UWwRxgV8vyeLmum/OAz3cakLRS0piksYmJiYMYMSIiBuJgsaQ3AsPABzuN215ve9j28NDQUH/DRUQc5o6s8LN3A/NalueW6/Yi6VTg94Fftf3TCvNEREQHVW4RbAYWSlogaTawHBhpnSDpRcBHgaW2v1dhloiI6KKyIrC9B1gFbAK2ARttb5G0RtLSctoHgaOBv5V0q6SRLh8XEREVqXLXELZHgdG2dRe1vD61yu+PiIjpDcTB4oiIqE+KICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGSxFERDRciiAiouFSBBERDZciiIhouBRBRETDpQgiIhouRRAR0XApgoiIhksRREQ0XKVFIGmJpO2Sdkha3WH8ZZJulrRH0murzBIREZ1VVgSSZgHrgNOBRcAKSYvapt0DnAN8uqocERExtSqfWbwY2GF7J4CkDcAyYOvkBNt3lWOPVJgjIiKmUOWuoTnArpbl8XLdfpO0UtKYpLGJiYmDEi4iIgqHxMFi2+ttD9seHhoaqjtORMRhpcoi2A3Ma1meW66LiIgBUmURbAYWSlogaTawHBip8PsiImIGKisC23uAVcAmYBuw0fYWSWskLQWQ9BJJ48DrgI9K2lJVnoiI6KzKs4awPQqMtq27qOX1ZopdRhERUZND4mBxRERUJ0UQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGq/ReQ4Nm/upra/3+u9aeUev3R0R00qgiGGSDXFLJ1t2hmi2iVXYNRUQ0XIogIqLhsmsoooEGebfVIGc7XGWLICKi4VIEERENV2kRSFoiabukHZJWdxj/OUlXl+M3SppfZZ6IiNhXZUUgaRawDjgdWASskLSobdp5wH22nwX8OfCBqvJERERnVW4RLAZ22N5p+0FgA7Csbc4y4Mry9TXAKyWpwkwREdFGtqv5YOm1wBLbbymX/zNwsu1VLXO+Vc4ZL5f/pZzz/bbPWgmsLBdPALZXEnp6xwLfn3ZWPZJtZpJtZpJtZurM9gzbQ50GDonTR22vB9bXnUPSmO3hunN0kmwzk2wzk2wzM6jZqtw1tBuY17I8t1zXcY6kI4FjgHsrzBQREW2qLILNwEJJCyTNBpYDI21zRoA3l69fC3zZVe2rioiIjirbNWR7j6RVwCZgFvBx21skrQHGbI8AfwlcJWkH8AOKshhkte+emkKyzUyyzUyyzcxAZqvsYHFERBwacmVxRETDpQgiIhouRRAR0XApgh5IerKkJ9edIyKiCimCLiQdL2mDpAngRuAbkr5Xrptfc7yBJ+k4SSeVP8fVnWc6ko6uO0NEXXLWUBeSvg5cAlxj++Fy3SzgdcD5tk+pMV5Xkm63/fwav/9E4HKKiwMnLyCcC9wPvNX2zfUkm5qke2wfPwA5jgPmlIu7bX+3zjzTkXS07R/VnEEU9zZ79N8N+MYgX5Mk6Tm2/7nuHJNSBF1IutP2wv0d6wdJv9FtCLi82/1E+kHSrcBv276xbf0pwEdtv7CWYEWGC7oNAb9vu7bdfynQGX//rwGXAXey97/bsyj+3b5YV7ap1P3v1u6QuNdQTW6SdBnF3VF3levmUVwJfUttqQpXA58COrX4Y/ucpd1R7SUAYPsGSUfVEajFHwMfBPZ0GKt7N+kn6F6gfwUMaoHWvUvtUuBU23e1rpS0ABgFnltHqDLDR7oNAU/sY5RppQi6exPF8xL+gL03OSeviK7TbcCf2f5W+4CkU2vI0+rzkq4F/pq9C/RNwBdqS1W4Gfis7ZvaByS9pYY8rVKgM3MkMN5h/W7gMX3O0u5c4F3ATzuMrehzlill19AhSNKvAHfbvqfD2LDtsRpitWY4neJZE3sVqO3R+lKBpBOAe9tvc16OHVfn/vjyf4/PpHOBfrv19u01ZPsa8PYuBbrL9rwOb+sLSRcCr6d43knrv9tyYKPtP6kx25eB99r+Woexb9teUEOsjlIEXZR3Qz0PeA17/0L7O+AvbT9UU7Q4TA14gf7A9kSHsVoLtMzwXDr/u22tL1Vx2jnwE9s/rjNHL1IEXUj6G4oDdVfys03PuRTHCJ5s+6yaorWW1H8CfqFcPfAlJWm97ZXTz+y/Qc4WUbUUQReS7rD97P0d64cBL6luZ94I+Kbtuf3Ms1eAwc52DHAhxf9sj6M4EeB7FOW+1vb9A5DtNcBTBynbVCR93vbpdefoZNCy5WBxdz+Q9DrgM7YfAZB0BMV1BPfVmgxe3KGIxoEbJN1RR6AWE8DdFL9cJ7lcfmotiX5mkLNtBL4MvML2vwJIehpwTjn2a/VFezTby9uyvbnubJJO6jYEnNjHKPsGGOBs7bJF0EV59fAHgFdQ/O8bilO+rgNW2/52LcEASTcAH6JzSV1g++Qas90JvLLLgey6DywOcrbttk/Y37F+GPBsDwNfYe9yn3SK7cf1OdKjBjlbu2wRdGH7Lknvp7hmYK+DxXWWQGk5RUmtk3R/ue6JFCVV98N9LgGeBOzzyxb40/5G2cclDG62uyX9LnDl5MHX8irjc/jZ2TB1GeRs2yiuv7izfUBSsvUoWwRdSHoPxS/VDex9xeJyYIPttXVlg65nSvyd7W31pSpIeg6dz+JIti4kPQlYTZFtcjfVdymuW1lru7bdkQOe7bXA7ba3dxh7je3P9j/Vo98/sNnapQi6KPe1/2L7GTjl85e31HyLiYEtqfJ/jmeX2VoPZCfbDEk61/Zf1Z2jk2SbmUHLliLoQtI/A6+yfXfb+mcAX6x5v+ggl1SyHWSDdl+aVsk2M4OWLccIujsf+MfyAOPk/rzjKW5mVdtVnqVHKK4fuLtt/dPLsTol2wxIuq3bEMXppLVJtpkZ5GztUgRd2P6CpGez7+1tN0/elrpG5zO4JXU+yTYTxwGvYt9TkwXsc4uCPku2mRnkbHtJEUyhPDXzhrpztBvkkkq2GfsccLTtW9sHJF3f9zR7S7aZGeRse8kxgoiIhqv7FrIREVGzFEFERMOlCKJxJM2X1OmhPldIWlS+/r0ePud8SY+fYvzRz4sYZDlGEI1T3kfqc7afN8WcH9me8jGMku4Chrs86GbWAByAjuhJtgiiqY6U9ClJ2yRdI+nxkq6XNCxpLfA4SbeWc46SdK2kb0r6lqSzJL2D4pqE6yRdB0V5SPqQpG8CL538vJaxPyo/44byXj1Iema5fLukiyX9qFz/dElfLTN8S8VT6SIqkSKIpjoBuMz2c4EfAm+dHLC9Gvh32yfafgOwBPiO7ReWWxFfsP0R4DsUt41+RfnWo4Aby3n/p+37jgJusP1C4KvAb5XrLwUutf189n727tnAJtsnUjy4/taD9RePaJciiKbaZfufytefBH55irm3A6dJ+oCkX7H9b13mPQx8psvYgxTnlQPcBMwvX78U+Nvy9adb5m8Gzi3vgPt82w9MkS/igKQIoqnaD451PVhm+w7gJIpCuFjSRV2m/mSK4wIP+WcH5B5mmos5bX8VeBnFBW+fkPSmqeZHHIgUQTTV8ZJeWr4+G2jflfOQpMcASPoF4Me2Pwl8kKIUAB4AnnCAOW4AzixfP/osifLmht+1/THgipbvjDjoUgTRVNuBt0naRvGwmr9oG18P3CbpU8DzgW9IuhX4b8DFLXO+MHmweIbOBy4ob1D2LGByt9PLgW9KugU4i+JYQkQlcvpoRI3K6xD+3bYlLQdW2F5Wd65oltx0LqJeLwb+hyRRPBv7N+uNE02ULYKIiIbLMYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4/w+MKx9PE/+NOgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_bitstrings_formatted(probabilities)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run on a QPU or an on-demand simulator\n",
    "\n",
    "Now we run on IonQ. Toffoli gate (CCNot) is not a supported gate of IonQ device. We use the `decompose_ccnot=True` to decompose the Toffoli gate into CNot, Ti, T and H gates. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# device = AwsDevice(\"arn:aws:braket:::device/qpu/ionq/ionQdevice\") # QPU\n",
    "device = AwsDevice(\"arn:aws:braket:::device/quantum-simulator/amazon/sv1\") # on-demand simulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "from braket.tracking import Tracker\n",
    "\n",
    "tracker = Tracker().start()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "oracle = build_oracle(solution, decompose_ccnot=True)\n",
    "circuit_qpu = grovers_search(oracle, n_qubits=n_qubits, n_reps=1, decompose_ccnot=True)\n",
    "qpu_task = device.run(circuit_qpu, shots=1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.029 0.03  0.035 0.035 0.027 0.034 0.026 0.784]\n"
     ]
    }
   ],
   "source": [
    "qpu_result = qpu_task.result()\n",
    "probabilities = qpu_result.values[0]\n",
    "print(probabilities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEPCAYAAABP1MOPAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAX/klEQVR4nO3df5hddWHn8feHIFXB4g9GtEkwWY1oqhVxBHzaWl2hBnmauEUloKtQNN3HRmXRraHVrKW0jbVadDcUI7VS/BFS3LVTGY21gm4rYIbfJmlgGoOZuNURoeJahcBn/zhn8Obm3pmbSc49Nzmf1/PMk3vO93vP/TAPTz6556dsExERzXVY3QEiIqJeKYKIiIZLEURENFyKICKi4VIEERENd3jdAfbVMccc4wULFtQdIyLioHLzzTd/3/ZQp7GDrggWLFjA2NhY3TEiIg4qku7pNpZdQxERDVdpEUhaImmbpHFJqzqMHyfpOkm3SrpD0quqzBMREXurrAgkzQHWAqcDi4GzJS1um/YeYIPtFwLLgcuqyhMREZ1V+Y3gJGDc9nbbDwLrgWVtcwz8fPn6aOA7FeaJiIgOqiyCucDOluWJcl2r9wFvkDQBjAJv67QhSSskjUkam5ycrCJrRERj1X2w+GzgE7bnAa8CrpK0Vybb62wP2x4eGup49lNERMxSlUWwC5jfsjyvXNfqfGADgO0bgMcCx1SYKSIi2lRZBJuARZIWSjqC4mDwSNucbwOvAJD0XIoiyL6fiIg+qqwIbO8GVgIbga0UZwdtlnSxpKXltHcCb5F0O/AZ4FznAQkREX1V6ZXFtkcpDgK3rlvd8noL8MtVZoiIOFAWrLq21s/fseaMSrZb98HiiIioWYogIqLhUgQREQ2XIoiIaLgUQUREw6UIIiIaLkUQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGSxFERDRciiAiouEqLQJJSyRtkzQuaVWH8T+XdFv5c5ek+6vMExERe6vsmcWS5gBrgdOACWCTpJHyOcUA2P6vLfPfBrywqjwREdFZld8ITgLGbW+3/SCwHlg2zfyzgc9UmCciIjqosgjmAjtblifKdXuR9AxgIfCVLuMrJI1JGpucnDzgQSMimmxQDhYvB66x/XCnQdvrbA/bHh4aGupztIiIQ1uVRbALmN+yPK9c18lyslsoIqIWVRbBJmCRpIWSjqD4y36kfZKk5wBPAm6oMEtERHRRWRHY3g2sBDYCW4ENtjdLuljS0papy4H1tl1VloiI6K6y00cBbI8Co23rVrctv6/KDBERMb1BOVgcERE1SRFERDRciiAiouFSBBERDZciiIhouBRBRETDpQgiIhouRRAR0XApgoiIhksRREQ0XIogIqLhUgQREQ2XIoiIaLgUQUREw6UIIiIaLkUQEdFwKYKIiIartAgkLZG0TdK4pFVd5rxO0hZJmyV9uso8ERGxt8oeVSlpDrAWOA2YADZJGrG9pWXOIuAi4Jdt3yfpqVXliYiIzqr8RnASMG57u+0HgfXAsrY5bwHW2r4PwPb3KswTEREdVFkEc4GdLcsT5bpWzwaeLemfJN0oaUmnDUlaIWlM0tjk5GRFcSMimqnug8WHA4uAlwFnAx+T9MT2SbbX2R62PTw0NNTfhBERh7gqi2AXML9leV65rtUEMGL7IdvfAu6iKIaIiOiTKotgE7BI0kJJRwDLgZG2OZ+j+DaApGModhVtrzBTRES0qawIbO8GVgIbga3ABtubJV0saWk5bSNwr6QtwHXAf7N9b1WZIiJib5WdPgpgexQYbVu3uuW1gQvLn4iIqEHdB4sjIqJmKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGSxFERDRciiAiouFSBBERDZciiIhouBRBRETDpQgiIhouRRAR0XApgoiIhqu0CCQtkbRN0rikVR3Gz5U0Kem28ufNVeaJiIi9VfbMYklzgLXAacAEsEnSiO0tbVOvtr2yqhwRETG9nr4RSPpfks6QtC/fIE4Cxm1vt/0gsB5YNpuQERFRnV7/Yr8MOAe4W9IaScf38J65wM6W5YlyXbszJd0h6RpJ8zttSNIKSWOSxiYnJ3uMHBERveipCGx/2fbrgROBHcCXJX1d0nmSHrMfn/93wALbvwT8PXBll89fZ3vY9vDQ0NB+fFxERLTreVePpKcA5wJvBm4FPkxRDH/f5S27gNZ/4c8r1z3K9r22f1ouXgG8qNc8ERFxYPR0sFjS/waOB64CfsP2/y2HrpY01uVtm4BFkhZSFMByit1Lrdt9esu2lgJb9zF/RETsp17PGvqY7dHWFZJ+zvZPbQ93eoPt3ZJWAhuBOcDHbW+WdDEwZnsEeLukpcBu4AcU3zgiIqKPei2CS4DRtnU3UOwa6qosj9G2datbXl8EXNRjhoiIqMC0RSDpaRRn+jxO0gsBlUM/Dzy+4mwREdEHM30jeCXF7pp5wIda1j8A/F5FmSIioo+mLQLbVwJXSjrT9mf7lCkiIvpopl1Db7D9SWCBpAvbx21/qMPbIiLiIDLTrqEjyz+PqjpIRETUY6ZdQx8t//yD/sSJiIh+m2nX0EemG7f99gMbJyIi+m2mXUM39yVFRETUppezhiIi4hA2066hS21fIOnvALeP215aWbKIiOiLmXYNXVX++WdVB4mIiHrMtGvo5vLPr0o6AngOxTeDbeVTxyIi4iDX622ozwAuB/6F4n5DCyX9tu0vVBkuIiKq1+vdRz8IvNz2OICkZwLXAimCiIiDXK9PKHtgqgRK2yluPBcREQe5mc4a+s3y5ZikUWADxTGC11I8gSwiIg5yM+0a+o2W198Ffq18PQk8rpJEERHRVzOdNXTe/mxc0hKKh9zPAa6wvabLvDOBa4AX2+72DOSIiKhAr2cNPRY4H/hF4LFT623/1jTvmQOsBU4DJoBNkkZsb2mb9wTgHcBN+5w+IiL2W68Hi68CnkbxxLKvUjyxbKaDxScB47a3l9ccrAeWdZj3h8D7gZ/0mCUiIg6gXovgWbbfC/y/8v5DZwAnz/CeucDOluWJct2jJJ0IzLd97XQbkrRC0pikscnJyR4jR0REL3otgofKP++X9DzgaOCp+/PBkg6jeA7yO2eaa3ud7WHbw0NDQ/vzsRER0abXC8rWSXoS8F5ghOKJZe+d4T27gPkty/PKdVOeADwPuF4SFLueRiQtzQHjiIj+6akIbF9Rvvwq8B963PYmYJGkhRQFsBw4p2Wb/wYcM7Us6XrgXSmBiIj+6mnXkKSnSPofkm6RdLOkSyU9Zbr32N4NrAQ2AluBDbY3S7pYUm5fHRExIHrdNbQe+BpwZrn8euBq4NTp3mR7FBhtW7e6y9yX9ZglIiIOoF6L4Om2/7Bl+RJJZ1URKCIi+qvXs4a+JGm5pMPKn9dR7PKJiIiD3Ew3nXuA4iZzAi4APlkOHQb8CHhXleEiIqJ6M91r6An9ChIREfXo9RgB5Zk+Ly0Xr7f9+WoiRUREP/V6+ugaihvDbSl/3iHpT6oMFhER/dHrN4JXASfYfgRA0pXArcBFVQWLiIj+6PWsIYAntrw++gDniIiImvT6jeCPgVslXUdxBtFLgVWVpYqIiL6ZsQjKu4Q+ApwCvLhc/W7b/1plsIiI6I8Zi8D2I5J+1/YGijuPRkTEIaTXYwRflvQuSfMlPXnqp9JkERHRF70eIziL4grjt7at7/WW1BERMaB6LYLFFCXwKxSF8H+Ay6sKFRER/dNrEVwJ/BD4SLl8TrnudVWEioiI/um1CJ5ne3HL8nWStlQRKCIi+qvXg8W3SDplakHSyUAeKRkRcQjotQheBHxd0g5JO4AbgBdLulPSHd3eJGmJpG2SxiXtdQGapP9SbuM2Sf8oaXGn7URERHV63TW0ZF83LGkOsBY4DZgANkkasd26S+nTti8v5y8FPjSbz4qIiNnrqQhs3zOLbZ8EjNveDiBpPbCM4u6lU9v9Ycv8IynOSIqIiD7q+XkEszAX2NmyPAGc3D5J0u8AFwJHAP+x04YkrQBWABx33HEHPGhERJPty91HK2F7re1nAu8G3tNlzjrbw7aHh4aG+hswIuIQV2UR7ALmtyzPK9d1sx54dYV5IiKigyqLYBOwSNJCSUcAy2m7aZ2kRS2LZwB3V5gnIiI6qOwYge3dklYCG4E5wMdtb5Z0MTBmewRYKelU4CHgPuBNVeWJiIjOqjxYjO1RYLRt3eqW1++o8vMjImJmtR8sjoiIeqUIIiIaLkUQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGSxFERDRciiAiouFSBBERDZciiIhouBRBRETDpQgiIhqu0iKQtETSNknjklZ1GL9Q0hZJd0j6B0nPqDJPRETsrbIikDQHWAucDiwGzpa0uG3arcCw7V8CrgH+tKo8ERHRWZXfCE4Cxm1vt/0gsB5Y1jrB9nW2f1wu3gjMqzBPRER0UGURzAV2tixPlOu6OR/4QqcBSSskjUkam5ycPIARIyJiIA4WS3oDMAx8oNO47XW2h20PDw0N9TdcRMQh7vAKt70LmN+yPK9ctwdJpwK/D/ya7Z9WmCciIjqo8hvBJmCRpIWSjgCWAyOtEyS9EPgosNT29yrMEhERXVRWBLZ3AyuBjcBWYIPtzZIulrS0nPYB4CjgbyTdJmmky+YiIqIiVe4awvYoMNq2bnXL61Or/PyIiJjZQBwsjoiI+qQIIiIaLkUQEdFwKYKIiIZLEURENFyKICKi4VIEERENlyKIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiGSxFERDRciiAiouFSBBERDZciiIhouBRBRETDVVoEkpZI2iZpXNKqDuMvlXSLpN2SXlNlloiI6KyyIpA0B1gLnA4sBs6WtLht2reBc4FPV5UjIiKmV+Uzi08Cxm1vB5C0HlgGbJmaYHtHOfZIhTkiImIaVe4amgvsbFmeKNftM0krJI1JGpucnDwg4SIionBQHCy2vc72sO3hoaGhuuNERBxSqiyCXcD8luV55bqIiBggVRbBJmCRpIWSjgCWAyMVfl5ERMxCZUVgezewEtgIbAU22N4s6WJJSwEkvVjSBPBa4KOSNleVJyIiOqvyrCFsjwKjbetWt7zeRLHLKCIianJQHCyOiIjqpAgiIhouRRAR0XApgoiIhksRREQ0XIogIqLhUgQREQ2XIoiIaLgUQUREw6UIIiIaLkUQEdFwld5rKA4NC1ZdW+vn71hzRtexQc4WcbBIEUQ0UAo0WjWqCAb5f/5BzhYRh7ZGFUFEP6XcZye/t/7LweKIiIZLEURENFyKICKi4SotAklLJG2TNC5pVYfxn5N0dTl+k6QFVeaJiIi9VVYEkuYAa4HTgcXA2ZIWt007H7jP9rOAPwfeX1WeiIjorMpvBCcB47a3234QWA8sa5uzDLiyfH0N8ApJqjBTRES0ke1qNiy9Blhi+83l8n8GTra9smXON8s5E+Xyv5Rzvt+2rRXAinLxeGBbJaFndgzw/Rln1SPZZifZZifZZqfObM+wPdRp4KC4jsD2OmBd3TkkjdkerjtHJ8k2O8k2O8k2O4OarcpdQ7uA+S3L88p1HedIOhw4Gri3wkwREdGmyiLYBCyStFDSEcByYKRtzgjwpvL1a4CvuKp9VRER0VFlu4Zs75a0EtgIzAE+bnuzpIuBMdsjwF8CV0kaB35AURaDrPbdU9NIttlJttlJttkZyGyVHSyOiIiDQ64sjohouBRBRETDpQgiIhouRdADSU+W9OS6c0REVCFF0IWk4yStlzQJ3AR8Q9L3ynULao438CQdK+nE8ufYuvPMRNJRdWeIqEvOGupC0g3ApcA1th8u180BXgtcYPuUGuN1JelO28+v8fNPAC6nuDhw6gLCecD9wFtt31JPsulJ+rbt4wYgx7HA3HJxl+3v1plnJpKOsv2jmjOI4t5mj/7egG8M8jVJkp5j+5/rzjElRdCFpLttL9rXsX6Q9JvdhoDLu91PpB8k3Qb8tu2b2tafAnzU9gtqCVZkuLDbEPD7tmvb/ZcCnfXn/zpwGXA3e/7enkXxe/tSXdmmU/fvrd1Bca+hmtws6TKKu6PuLNfNp7gS+tbaUhWuBj4FdGrxx/Y5S7sj20sAwPaNko6sI1CLPwY+AOzuMFb3btJP0L1A/woY1AKte5fah4FTbe9oXSlpITAKPLeOUGWGj3QbAp7YxygzShF090aK5yX8AXt+5Zy6IrpOdwB/Zvub7QOSTq0hT6svSLoW+Gv2LNA3Al+sLVXhFuBztm9uH5D05hrytEqBzs7hwESH9buAx/Q5S7vzgHcCP+0wdnafs0wru4YOQpJ+FbjH9rc7jA3bHqshVmuG0ymeNbFHgdoerS8VSDoeuLf9Nufl2LF17o8v//X4TDoX6Ldab99eQ7avA2/rUqA7bc/v8La+kHQR8DqK5520/t6WAxts/0mN2b4CvMf21zuMfcv2whpidZQi6KK8G+r5wKvZ8y+0vwX+0vZDNUWLQ9SAF+gPbE92GKu1QMsMz6Xz721LfamK086Bn9j+cZ05epEi6ELSZygO1F3Jz756zqM4RvBk22fVFK21pP4T8Avl6oEvKUnrbK+YeWb/DXK2iKqlCLqQdJftZ+/rWD8MeEl1O/NGwO225/Uzzx4BBjvb0cBFFP+yPZbiRIDvUZT7Gtv3D0C2VwNPHaRs05H0Bdun152jk0HLloPF3f1A0muBz9p+BEDSYRTXEdxXazJ4UYcimgBulHRXHYFaTAL3UPzlOsXl8lNrSfQzg5xtA/AV4OW2/xVA0tOAc8uxX68v2qPZXtaW7U11Z5N0Yrch4IQ+Rtk7wABna5dvBF2UVw+/H3g5xb++oTjl6zpgle1v1RIMkHQj8EE6l9SFtk+uMdvdwCu6HMiu+8DiIGfbZvv4fR3rhwHP9jDwVfYs9ymn2H5cnyM9apCztcs3gi5s75D0PoprBvY4WFxnCZSWU5TUWkn3l+ueSFFSdT/c51LgScBef9kCf9rfKHu5lMHNdo+k3wWunDr4Wl5lfC4/OxumLoOcbSvF9Rd3tw9ISrYe5RtBF5LeTfGX6nr2vGJxObDe9pq6skHXMyX+1vbW+lIVJD2HzmdxJFsXkp4ErKLINrWb6rsU162ssV3b7sgBz/Ya4E7b2zqMvdr25/qf6tHPH9hs7VIEXZT72n+x/Qyc8vnLm2u+xcTAllT5L8dzymytB7KTbZYknWf7r+rO0Umyzc6gZUsRdCHpn4FX2r6nbf0zgC/VvF90kEsq2Q6wQbsvTatkm51By5ZjBN1dAPxDeYBxan/ecRQ3s6rtKs/SIxTXD9zTtv7p5Vidkm0WJN3RbYjidNLaJNvsDHK2dimCLmx/UdKz2fv2tpumbktdowsY3JK6gGSbjWOBV7L3qckC9rpFQZ8l2+wMcrY9pAimUZ6aeWPdOdoNckkl26x9HjjK9m3tA5Ku73uaPSXb7Axytj3kGEFERMPVfQvZiIioWYogIqLhUgTROJIWSOr0UJ8rJC0uX/9eD9u5QNLjpxl/dHsRgyzHCKJxyvtIfd7286aZ8yPb0z6GUdIOYLjLg27mDMAB6Iie5BtBNNXhkj4laaukayQ9XtL1koYlrQEeJ+m2cs6Rkq6VdLukb0o6S9LbKa5JuE7SdVCUh6QPSrodeMnU9lrG/qjcxo3lvXqQ9Mxy+U5Jl0j6Ubn+6ZK+Vmb4poqn0kVUIkUQTXU8cJnt5wI/BN46NWB7FfDvtk+w/XpgCfAd2y8ov0V80fZHgO9Q3Db65eVbjwRuKuf9Y9vnHQncaPsFwNeAt5TrPwx82Pbz2fPZu+cAG22fQPHg+tsO1H94RLsUQTTVTtv/VL7+JPAr08y9EzhN0vsl/artf+sy72Hgs13GHqQ4rxzgZmBB+folwN+Urz/dMn8TcF55B9zn235gmnwR+yVFEE3VfnCs68Ey23cBJ1IUwiWSVneZ+pNpjgs85J8dkHuYGS7mtP014KUUF7x9QtIbp5sfsT9SBNFUx0l6Sfn6HKB9V85Dkh4DIOkXgB/b/iTwAYpSAHgAeMJ+5rgROLN8/eizJMqbG37X9seAK1o+M+KASxFEU20DfkfSVoqH1fxF2/g64A5JnwKeD3xD0m3AfwcuaZnzxamDxbN0AXBheYOyZwFTu51eBtwu6VbgLIpjCRGVyOmjETUqr0P4d9uWtBw42/ayunNFs+SmcxH1ehHwPyWJ4tnYv1VvnGiifCOIiGi4HCOIiGi4FEFERMOlCCIiGi5FEBHRcCmCiIiG+//E6g/O6PKgGgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_bitstrings_formatted(probabilities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Task Summary\n",
      "{'arn:aws:braket:::device/quantum-simulator/amazon/sv1': {'shots': 1000, 'tasks': {'COMPLETED': 1}, 'execution_duration': datetime.timedelta(microseconds=14000), 'billed_execution_duration': datetime.timedelta(seconds=3)}} \n",
      "\n",
      "Estimated cost to run this example: 0.00 USD\n"
     ]
    }
   ],
   "source": [
    "print(\"Task Summary\")\n",
    "print(f\"{tracker.quantum_tasks_statistics()} \\n\")\n",
    "print(f\"Estimated cost to run this example: {tracker.qpu_tasks_cost() + tracker.simulator_tasks_cost():.2f} USD\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: Charges shown are estimates based on your Amazon Braket simulator and quantum processing unit (QPU) task usage. Estimated charges shown may differ from your actual charges. Estimated charges do not factor in any discounts or credits, and you may experience additional charges based on your use of other services such as Amazon Elastic Compute Cloud (Amazon EC2)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  },
  "vscode": {
   "interpreter": {
    "hash": "5904cb9a2089448a2e1aeb5d493d227c9de33e591d7c07e4016fb81e71061a5d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}