{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simon's Algorithm\n",
    "\n",
    "This notebook demonstrates the execution of Simon's algorithm on Amazon Braket. \n",
    "\n",
    "\n",
    "Suppose we’re given a function $f:\\{0,1\\}^n \\rightarrow \\{0,1\\}^n$ that maps bit strings to bit strings along with the promise that\n",
    "$$\\forall x,y \\in \\{0,1\\}^n, \\quad f(x) = f(y) \\iff x=y\\oplus s,$$\n",
    "for some unknown $n$-bit string $s \\in \\{0,1\\}^n$, and where $\\oplus$ means bitwise addition modulo 2.\n",
    "\n",
    "The goal of Simon's problem is to determine if $f$ is one-to-one, or two-to-one, or equivalently to find the secret string $s$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References \n",
    "[1] Wikipedia: [Simon's Problem](https://en.wikipedia.org/wiki/Simon%27s_problem)\n",
    "\n",
    "[2] SIAM: [Original article](https://epubs.siam.org/doi/10.1137/S0097539796298637)\n",
    "\n",
    "[3] Amazon Braket's github repository: [Detailed example notebook](https://github.com/aws/amazon-braket-examples/blob/main/examples/advanced_circuits_algorithms/Simons_Algorithm/Simons_Algorithm.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run on a local simulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy.random as npr\n",
    "from braket.aws import AwsDevice\n",
    "from braket.devices import LocalSimulator\n",
    "from braket.tracking import Tracker\n",
    "\n",
    "from braket.experimental.algorithms.simons import (\n",
    "    get_simons_algorithm_results,\n",
    "    run_simons_algorithm,\n",
    "    simons_algorithm,\n",
    "    simons_oracle,\n",
    ")\n",
    "\n",
    "tracker = Tracker().start()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "string_length = 5\n",
    "string = \"\".join(npr.choice([\"0\", \"1\"], size=string_length))\n",
    "\n",
    "oracle = simons_oracle(string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Print the circuits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "T  : |0|    1    |2|3|\n",
      "                      \n",
      "q0 : -H-C---------H---\n",
      "        |             \n",
      "q1 : -H-|-C-------H---\n",
      "        | |           \n",
      "q2 : -H-|-|-C-----H---\n",
      "        | | |         \n",
      "q3 : -H-|-|-|-C---H---\n",
      "        | | | |       \n",
      "q4 : -H-|-|-|-|-C-C-H-\n",
      "        | | | | | |   \n",
      "q5 : ---X-|-|-|-|-|---\n",
      "          | | | | |   \n",
      "q6 : -----X-|-|-|-|---\n",
      "            | | | |   \n",
      "q7 : -------X-|-|-|---\n",
      "              | | |   \n",
      "q8 : ---------X-|-|---\n",
      "                | |   \n",
      "q9 : -----------X-X---\n",
      "\n",
      "T  : |0|    1    |2|3|\n"
     ]
    }
   ],
   "source": [
    "print(simons_algorithm(oracle))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "local_simulator = LocalSimulator()\n",
    "\n",
    "task = run_simons_algorithm(oracle, local_simulator)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result string: 00001\n",
      "Secret string 00001\n"
     ]
    }
   ],
   "source": [
    "processed_results = get_simons_algorithm_results(task)\n",
    "print(\"Secret string\", string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run on a QPU\n",
    "\n",
    "Here we run Simon's algorithm on the Rigetti Aspen M-3 device."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "aspen_m = AwsDevice(\"arn:aws:braket:us-west-1::device/qpu/rigetti/Aspen-M-3\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# run this block to submit the circuit to QPU\n",
    "\n",
    "task = run_simons_algorithm(oracle, aspen_m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result string: 00001\n",
      "Secret string 00001\n"
     ]
    }
   ],
   "source": [
    "# run this block to process the results\n",
    "\n",
    "processed_results = get_simons_algorithm_results(task)\n",
    "print(\"Secret string\", string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Task Summary\n",
      "{'arn:aws:braket:us-west-1::device/qpu/rigetti/Aspen-M-3': {'shots': 20, 'tasks': {'COMPLETED': 1}}} \n",
      "\n",
      "Estimated cost to run this example: 0.31 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.9.6",
   "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.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "625f119d7123628dd79ea6440058f262ec370c9df2643d17cf5bcd61bdf8ba1c"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}