{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Shor's Algorithm\n",
    "\n",
    "This example provides an implementation of the Shor's algorithm using the Amazon Braket SDK. Shor's algorithm is used to find prime factors of an integer. On a quantum computer, Shor's algorithm runs in polynomial time and is almost exponentially faster than the most efficient known classical factoring algorithm. The efficiency of Shor's algorithm is due to the efficiency of the Quantum Fourier transform, Quantum Phase estimation and modular exponentiation by repeated squarings. In this notebook, you implement the Shor's algorithm in code using the Amazon Braket SDK and run a simple example of factoring 15."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References \n",
    "\n",
    "[1] Wikipedia: https://en.wikipedia.org/wiki/Shor%27s_algorithm\n",
    "\n",
    "[2] Nielsen, Michael A., Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from braket.devices import LocalSimulator\n",
    "from braket.aws import AwsDevice\n",
    "from braket.experimental.algorithms.shors.shors import (\n",
    "    shors_algorithm,\n",
    "    run_shors_algorithm,\n",
    "    get_factors_from_results\n",
    ")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Prepare inputs for Shor's Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 15 # Integer to factor (currently 15, 21, 35 work)\n",
    "a = 7  # Any integer that satisfies 1 < a < N and gcd(a, N) = 1.\n",
    "\n",
    "\n",
    "shors_circuit = shors_algorithm(N, a)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run on a local simulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of Measured phases (s/r) : 4\n",
      "\n",
      "For phase 0.25 :\n",
      "Estimate for r is : 4\n",
      "Factors are : 3 and 5\n",
      "\n",
      "For phase 0.75 :\n",
      "Estimate for r is : 4\n",
      "Factors are : 3 and 5\n",
      "\n",
      "For phase 0.0 :\n",
      "Estimate for r is : 1\n",
      "Factors are : 15 and 1\n",
      "\n",
      "For phase 0.5 :\n",
      "Estimate for r is : 2\n",
      "Factors are : 3 and 1\n",
      "\n",
      "\n",
      "Non-trivial factors found are : {3, 5}\n"
     ]
    }
   ],
   "source": [
    "local_simulator = LocalSimulator()\n",
    "\n",
    "output = run_shors_algorithm(shors_circuit, local_simulator)\n",
    "\n",
    "guessed_factors = get_factors_from_results(output, N, a)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run on a managed simulator\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use Braket SDK Cost Tracking to estimate the cost to run this example\n",
    "from braket.tracking import Tracker\n",
    "tracker = Tracker().start()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of Measured phases (s/r) : 4\n",
      "\n",
      "For phase 0.25 :\n",
      "Estimate for r is : 4\n",
      "Factors are : 3 and 5\n",
      "\n",
      "For phase 0.75 :\n",
      "Estimate for r is : 4\n",
      "Factors are : 3 and 5\n",
      "\n",
      "For phase 0.0 :\n",
      "Estimate for r is : 1\n",
      "Factors are : 15 and 1\n",
      "\n",
      "For phase 0.5 :\n",
      "Estimate for r is : 2\n",
      "Factors are : 3 and 1\n",
      "\n",
      "\n",
      "Non-trivial factors found are : {3, 5}\n"
     ]
    }
   ],
   "source": [
    "managed_sim = AwsDevice(\"arn:aws:braket:::device/quantum-simulator/amazon/sv1\")\n",
    "output = run_shors_algorithm(shors_circuit, managed_sim)\n",
    "\n",
    "guessed_factors = get_factors_from_results(output, N, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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=15000), '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.10.8"
  },
  "vscode": {
   "interpreter": {
    "hash": "5904cb9a2089448a2e1aeb5d493d227c9de33e591d7c07e4016fb81e71061a5d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}