qualtran/bloqs/factoring/mod_exp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5947b041",
   "metadata": {
    "cq.autogen": "title_cell"
   },
   "source": [
    "# Modular Exponentiation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce6b0d51",
   "metadata": {
    "cq.autogen": "top_imports"
   },
   "outputs": [],
   "source": [
    "from qualtran import Bloq, CompositeBloq, BloqBuilder, Signature, Register\n",
    "from qualtran import QBit, QInt, QUInt, QAny\n",
    "from qualtran.drawing import show_bloq, show_call_graph, show_counts_sigma\n",
    "from typing import *\n",
    "import numpy as np\n",
    "import sympy\n",
    "import cirq"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f68374c",
   "metadata": {
    "cq.autogen": "ModExp.bloq_doc.md"
   },
   "source": [
    "## `ModExp`\n",
    "Perform $b^e \\mod{m}$ for constant `base` $b$, `mod` $m$, and quantum `exponent` $e$.\n",
    "\n",
    "Modular exponentiation is the main computational primitive for quantum factoring algorithms.\n",
    "We follow [GE2019]'s \"reference implementation\" for factoring. See `ModExp.make_for_shor`\n",
    "to set the class attributes for a factoring run.\n",
    "\n",
    "This bloq decomposes into controlled modular exponentiation for each exponent bit.\n",
    "\n",
    "#### Parameters\n",
    " - `base`: The integer base of the exponentiation\n",
    " - `mod`: The integer modulus\n",
    " - `exp_bitsize`: The size of the `exponent` thru-register\n",
    " - `x_bitsize`: The size of the `x` right-register \n",
    "\n",
    "#### Registers\n",
    " - `exponent`: The exponent\n",
    " - `x [right]`: The output register containing the result of the exponentiation \n",
    "\n",
    "#### References\n",
    " - [How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits](https://arxiv.org/abs/1905.09749). Gidney and Ekerå. 2019.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4a1b8a2a",
   "metadata": {
    "cq.autogen": "ModExp.bloq_doc.py"
   },
   "outputs": [],
   "source": [
    "from qualtran.bloqs.factoring import ModExp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "902ec939",
   "metadata": {
    "cq.autogen": "ModExp.example_instances.md"
   },
   "source": [
    "### Example Instances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c5aac47",
   "metadata": {
    "cq.autogen": "ModExp.modexp_small"
   },
   "outputs": [],
   "source": [
    "modexp_small = ModExp(base=4, mod=15, exp_bitsize=3, x_bitsize=2048)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41d94c81",
   "metadata": {
    "cq.autogen": "ModExp.modexp"
   },
   "outputs": [],
   "source": [
    "modexp = ModExp.make_for_shor(big_n=13 * 17, g=9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5c0c6c06",
   "metadata": {
    "cq.autogen": "ModExp.modexp_symb"
   },
   "outputs": [],
   "source": [
    "g, N, n_e, n_x = sympy.symbols('g N n_e, n_x')\n",
    "modexp_symb = ModExp(base=g, mod=N, exp_bitsize=n_e, x_bitsize=n_x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a55a51df",
   "metadata": {
    "cq.autogen": "ModExp.graphical_signature.md"
   },
   "source": [
    "#### Graphical Signature"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce953a6d",
   "metadata": {
    "cq.autogen": "ModExp.graphical_signature.py"
   },
   "outputs": [],
   "source": [
    "from qualtran.drawing import show_bloqs\n",
    "show_bloqs([modexp_symb, modexp_small, modexp],\n",
    "           ['`modexp_symb`', '`modexp_small`', '`modexp`'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83ba4b54",
   "metadata": {},
   "source": [
    "### Decomposition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0e53334",
   "metadata": {},
   "outputs": [],
   "source": [
    "show_bloq(modexp_small.decompose_bloq())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8662fa01",
   "metadata": {
    "cq.autogen": "ModExp.call_graph.md"
   },
   "source": [
    "### Call Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9a7d9f5a",
   "metadata": {
    "cq.autogen": "ModExp.call_graph.py"
   },
   "outputs": [],
   "source": [
    "from qualtran.resource_counting.generalizers import ignore_split_join\n",
    "modexp_symb_g, modexp_symb_sigma = modexp_symb.call_graph(max_depth=1, generalizer=ignore_split_join)\n",
    "show_call_graph(modexp_symb_g)\n",
    "show_counts_sigma(modexp_symb_sigma)"
   ]
  }
 ],
 "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}