qft.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# QFT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This article follows the convention of qiskit of qubits ordering, i.e. \n",
    "$|x_{n-1}x_{n-2}\\cdots x_1x_0\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definition\n",
    "\n",
    "For n qubits (with N possible states) $\\sum_{j=0}^{N-1} \\alpha_j|j\\rangle$, the quantum Fourier transform $\\sum_{k=0}^{N-1} \\beta_k |k\\rangle$ is defined as,\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "\\sum_{k=0}^{N-1} \\beta_k |k\\rangle &= QFT \\sum_{j=0}^{N-1} \\alpha_j|j\\rangle \\tag 1\\\\\n",
    "\\beta_k &= \\frac{1}{\\sqrt{N}} \\sum_{j=0}^{N-1} \\alpha_j e^{\\frac{2\\pi i}{N}jk} \n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That is,\n",
    "\n",
    "$$\n",
    "QFT \\sum_{j=0}^{N-1} \\alpha_j|j\\rangle = \\frac{1}{\\sqrt{N}} \\sum_{k=0}^{N-1} \\sum_{j=0}^{N-1} \\alpha_j e^{\\frac{2\\pi i}{N}jk} |k\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The quantum Fourier transform transforms between computational basis (Z) and the Fourier basis.\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "|\\text{State in Fourier Basis}\\rangle &= QFT |\\text{State in Computational Basis}\\rangle \\\\\n",
    "|\\tilde{x}\\rangle &= QFT |x\\rangle \n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Take Computational basis $|x\\rangle = |x_{n-1} x_{n-2}\\cdots x_1 x_0 \\rangle$, that is $\\alpha_j = 1$ for $j=x$ and $\\alpha_j = 0$ for $j \\neq x$.\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "QFT|x\\rangle &= \\frac{1}{\\sqrt{2^n}} \\sum_{y=0}^{2^n-1} e^{\\frac{2\\pi i}{2^n}xy} |y\\rangle \\\\  \n",
    "&= \\frac{1}{\\sqrt{2^n}} \\sum_{y_{n-1}=0}^1 \\sum_{y_{n-2}=0}^1 \\cdots \\sum_{y_1=0}^1 \\sum_{y_0=0}^1 e^{\\frac{2\\pi i}{2^n}(\\sum_{k=0}^{n-1}2^{k}y_k) x} |y_{n-1} y_{n-2} \\cdots y_1 y_0 \\rangle \\\\\n",
    "&= \\frac{1}{\\sqrt{2^n}} \\sum_{y_{n-1}=0}^1 \\sum_{y_{n-2}=0}^1 \\cdots \\sum_{y_1=0}^1 \\sum_{y_0=0}^1 e^{2\\pi i(\\sum_{k=0}^{n-1} \\frac{y_k}{2^{n-k}}) x} |y_{n-1} y_{n-2} \\cdots y_1 y_0 \\rangle \\\\\n",
    "&= \\frac{1}{\\sqrt{2^n}} \\sum_{y_{n-1}=0}^1 \\sum_{y_{n-2}=0}^1 \\cdots \\sum_{y_1=0}^1 \\sum_{y_0=0}^1 \\prod_{k=0}^{n-1} e^{2\\pi i \\frac{y_k}{2^{n-k}} x } |y_{n-1} y_{n-2} \\cdots y_1 y_0 \\rangle \\\\\n",
    "&= \\frac{1}{\\sqrt{2^n}} \\sum_{y_{n-1}=0}^1 \\sum_{y_{n-2}=0}^1 \\cdots \\sum_{y_1=0}^1 \\sum_{y_0=0}^1 \n",
    "e^{2\\pi i \\frac{y_{n-1}}{2^1} x} |y_{n-1}\\rangle \\otimes\n",
    "e^{2\\pi i \\frac{y_{n-2}}{2^2} x} |y_{n-2}\\rangle \\otimes\n",
    "\\cdots \\otimes \n",
    "e^{2\\pi i \\frac{y_1}{2^{n-1}} x} |y_{1}\\rangle \\otimes\n",
    "e^{2\\pi i \\frac{y_0}{2^{n}} x} |y_{0}\\rangle \\\\\n",
    "&= \\frac{1}{\\sqrt{2^n}} \n",
    "\\sum_{y_{n-1}=0}^1 e^{2\\pi i \\frac{y_{n-1}}{2^1} x} |y_{n-1}\\rangle \\otimes\n",
    "\\sum_{y_{n-2}=0}^1 e^{2\\pi i \\frac{y_{n-2}}{2^2} x} |y_{n-2}\\rangle \\otimes\n",
    "\\cdots \\otimes \n",
    "\\sum_{y_1=0}^1 e^{2\\pi i \\frac{y_1}{2^{n-1}} x} |y_{1}\\rangle \\otimes\n",
    "\\sum_{y_0=0}^1 e^{2\\pi i \\frac{y_0}{2^{n}} x} |y_{0}\\rangle \\\\\n",
    "&= \\frac{1}{\\sqrt{2^n}} \n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^1} x} |1\\rangle \\right] \\otimes\n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^2} x} |1\\rangle \\right] \\otimes\n",
    "\\cdots \\otimes \n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-1}} x} |1\\rangle \\right] \\otimes\n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n}} x} |1\\rangle \\right] \n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![n qubits qft](./images/n_qubits_qft1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The circuit operates as below,\n",
    "\n",
    "### 1. H gate on most significant qubits $x_{n-1}$\n",
    "\n",
    "$H_{n-1}|x_{n-1}x_{n-2}x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "$ = \\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2}x_{n-1}}|1\\rangle\\right] \n",
    "\\otimes |x_{n-2}x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "### 2. Apply controlled $UROT_2$ on $x_{n-1}$\n",
    "\n",
    "$\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2}x_{n-1} + \\frac{2\\pi i}{2^2}x_{n-2}}|1\\rangle\\right] \n",
    "\\otimes |x_{n-2}x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "### 5. Apply a series of controlled $UROT_*$ gates on $x_{n-1}$\n",
    "\n",
    "$\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2}x_{n-1} + \\frac{2\\pi i}{2^2}x_{n-2} + \\frac{2\\pi i}{2^3}x_{n-3} + \\cdots + \\frac{2\\pi i}{2^{n-1}}x_1 + \\frac{2\\pi i}{2^n}x_0}|1\\rangle\\right] \n",
    "\\otimes |x_{n-2}x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "$ = \\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}(2^{n-1}x_{n-1} + 2^{n-2}x_{n-2} + 2^n-{3}x_{n-3} + \\cdots + 2^1x_1 + 2^0x_0)}|1\\rangle\\right] \n",
    "\\otimes |x_{n-2}x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "$ = \\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right] \n",
    "\\otimes |x_{n-2}x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "### 6. Apply H gate on $x_{n-2}$\n",
    "\n",
    "$ = \\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2}x_{n-2}}|1\\rangle\\right]\n",
    "\\otimes |x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "### 9. Apply a series of controlled $UROT_*$ gates on $x_{n-2}$\n",
    "\n",
    "$\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2}x_{n-2} + \\frac{2\\pi i}{2^2}x_{n-3} + \\cdots + \\frac{2\\pi i}{2^{n-2}}x_1 + \\frac{2\\pi i}{2^{n-1}}x_0}|1\\rangle\\right]\n",
    "\\otimes |x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "$ = \\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\n",
    "\\frac{2\\pi i}{2^{n-1}}(2^{n-2}x_{n-2} + 2^n-{3}x_{n-3} + \\cdots + 2^1x_1 + 2^0x_0)\n",
    "}|1\\rangle\\right]\n",
    "\\otimes |x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "$ = \\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\n",
    "\\frac{2\\pi i}{2^{n-1}}({\\color{red}{2^{n-1}x_{n-1}}} + 2^{n-2}x_{n-2} + 2^n-{3}x_{n-3} + \\cdots + 2^1x_1 + 2^0x_0)\n",
    "}|1\\rangle\\right]\n",
    "\\otimes |x_{n-3}\\cdots x_1x_0\\rangle $ the red term does not change the value of the exponent while simplify the equation\n",
    "\n",
    "$ = \\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\n",
    "\\frac{2\\pi i}{2^{n-1}}x\n",
    "}|1\\rangle\\right]\n",
    "\\otimes |x_{n-3}\\cdots x_1x_0\\rangle $\n",
    "\n",
    "### 12. Similarly for $x_{n-3}$\n",
    "\n",
    "$\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-1}}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-2}}x}|1\\rangle\\right]\n",
    "\\otimes |x_{n-4} \\cdots x_1x_0\\rangle $\n",
    "\n",
    "### 15. Repeat until $x_{0}$\n",
    "\n",
    "$\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-1}}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-2}}x}|1\\rangle\\right]\n",
    "\\cdots\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^2}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^1}x}|1\\rangle\\right]\n",
    "$\n",
    "\n",
    "### 16. After all swap gates\n",
    "\n",
    "$\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^1}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^2}x}|1\\rangle\\right]\n",
    "\\cdots\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-2}}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-1}}x}|1\\rangle\\right]\n",
    "\\frac{1}{\\sqrt{2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "$\n",
    "\n",
    "$ = \n",
    "\\frac{1}{2^{n/2}}\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^1}x}|1\\rangle\\right]\n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^2}x}|1\\rangle\\right]\n",
    "\\cdots\n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-2}}x}|1\\rangle\\right]\n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^{n-1}}x}|1\\rangle\\right]\n",
    "\\left[ |0\\rangle + e^{\\frac{2\\pi i}{2^n}x}|1\\rangle\\right]\n",
    "$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from numpy import pi\n",
    "from qiskit import QuantumCircuit, Aer, transpile\n",
    "from qiskit.visualization import plot_histogram, plot_bloch_multivector\n",
    "from qiskit.circuit import QuantumRegister, ClassicalRegister"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "sim = Aer.get_backend('statevector_simulator')\n",
    "qc = QuantumCircuit(3)\n",
    "\n",
    "init_state = '101'\n",
    "qc.initialize(init_state)\n",
    "qc.barrier()\n",
    "\n",
    "qc.h(2)\n",
    "qc.cp(pi/2, 1, 2)\n",
    "qc.cp(pi/4, 0, 2)\n",
    "\n",
    "qc.h(1)\n",
    "qc.cp(pi/2, 0, 1)\n",
    "\n",
    "qc.h(0)\n",
    "\n",
    "qc.swap(0, 2)\n",
    "\n",
    "display(qc.draw())\n",
    "\n",
    "sv = sim.run(qc).result().get_statevector()\n",
    "plot_bloch_multivector(sv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "from qiskit.circuit.library import QFT\n",
    "\n",
    "qc2 = QuantumCircuit(3)\n",
    "qc2.initialize(init_state)\n",
    "qc2.append(QFT(num_qubits=3), [0, 1, 2])\n",
    "display(qc2.draw())\n",
    "sv2 = sim.run(transpile(qc2, sim)).result().get_statevector()\n",
    "plot_bloch_multivector(sv2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "# implement general QFT\n",
    "\n",
    "def myqft(n):\n",
    "    qc = QuantumCircuit(n)\n",
    "    for i in reversed(range(n)):\n",
    "        qc.h(i)\n",
    "        for e, j in enumerate(reversed(range(i))):\n",
    "            qc.cp(pi/2**(e+1), j, i)\n",
    "    for i in range(n//2):\n",
    "        qc.swap(i, n-i-1)\n",
    "    return qc.to_gate(label='myqft{}'.format(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "qc3 = QuantumCircuit(3)\n",
    "qc3.initialize(init_state)\n",
    "qc3.append(myqft(3), [0, 1, 2])\n",
    "display(qc3.draw())\n",
    "sv3 = sim.run(transpile(qc3, sim)).result().get_statevector()\n",
    "plot_bloch_multivector(sv3)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create Exponentiation Modulo N circuit\n",
    "Refer to Vlatko Vedral, Adriano Barenco and Artur Ekert, Quantum Networks for Elementary Arithmetic Operations, create the support functions to generate the circuit for $a^x mod \\, N$.\n",
    "\n",
    "Also refer to the quantum circuits in https://quantumcomputing.stackexchange.com/questions/6842/is-there-a-simple-formulaic-way-to-construct-a-modular-exponentiation-circuit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "def create_carrier(name=None):\n",
    "    qc = QuantumCircuit(4)\n",
    "    qc.toffoli(1, 2, 3)\n",
    "    qc.cx(1, 2)\n",
    "    qc.toffoli(0, 2, 3)\n",
    "    return qc.to_gate(label=name or 'carrier')\n",
    "\n",
    "def create_carrier_inv(name=None):\n",
    "    qc = QuantumCircuit(4)\n",
    "    qc.append(create_carrier().inverse(), range(4))\n",
    "    return qc.to_gate(label=name or 'carrier_inv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "def create_sum(name=None):\n",
    "    qc = QuantumCircuit(3)\n",
    "    qc.cx(1, 2)\n",
    "    qc.cx(0, 2)\n",
    "    return qc.to_gate(label=name or 'sum')\n",
    "\n",
    "def create_sum_inv(name=None):\n",
    "    qc = QuantumCircuit(3)\n",
    "    qc.append(create_sum().inverse(), range(3))\n",
    "    return qc.to_gate(label=name or 'sum_inv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "a = QuantumRegister(3, 'a')\n",
    "b = QuantumRegister(4, 'b')\n",
    "c = QuantumRegister(3, 'c')\n",
    "creg = ClassicalRegister(4, 'creg')\n",
    "qc = QuantumCircuit(a, b, c, creg)\n",
    "qc.x(a[0])\n",
    "qc.x(a[1])\n",
    "qc.x(b[1])\n",
    "qc.x(b[2])\n",
    "qc.append(create_carrier(), [c[0], a[0], b[0], c[1]])\n",
    "qc.append(create_carrier(), [c[1], a[1], b[1], c[2]])\n",
    "qc.append(create_carrier(), [c[2], a[2], b[2], b[3]])\n",
    "qc.cx(a[2], b[2])\n",
    "qc.append(create_sum(), [c[2], a[2], b[2]])\n",
    "qc.append(create_carrier_inv(), [c[1], a[1], b[1], c[2]])\n",
    "qc.append(create_sum(), [c[1], a[1], b[1]])\n",
    "qc.append(create_carrier_inv(), [c[0], a[0], b[0], c[1]])\n",
    "qc.append(create_sum(), [c[0], a[0], b[0]])\n",
    "qc.barrier()\n",
    "qc.measure(b, creg)\n",
    "display(qc.draw())\n",
    "backend = Aer.get_backend('qasm_simulator')\n",
    "job = backend.run(transpile(qc, backend), shots=1024)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "def create_adder(n):\n",
    "    \"\"\"create adder with n bits a, n+1 bits b and n bits carrier\"\"\"\n",
    "    a = QuantumRegister(n, 'a')\n",
    "    b = QuantumRegister(n+1, 'b')\n",
    "    c = QuantumRegister(n, 'c')\n",
    "    qc = QuantumCircuit(a, b, c)\n",
    "    for i in range(n-1):\n",
    "        qc.append(create_carrier(), [c[i], a[i], b[i], c[i+1]])\n",
    "    qc.append(create_carrier(), [c[n-1], a[n-1], b[n-1], b[n]])\n",
    "    qc.cx(a[n-1], b[n-1])\n",
    "    qc.append(create_sum(), [c[n-1], a[n-1], b[n-1]])\n",
    "    for i in reversed(range(n-1)):\n",
    "        qc.append(create_carrier_inv(), [c[i], a[i], b[i], c[i+1]])\n",
    "        qc.append(create_sum(), [c[i], a[i], b[i]])\n",
    "    return qc.to_gate(label='adder')\n",
    "\n",
    "def create_adder_inv(n):\n",
    "    qc = QuantumCircuit(3*n+1)\n",
    "    qc.append(create_adder(n).inverse(), range(3*n+1))\n",
    "    return qc.to_gate(label='adder_inv')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "qc = QuantumCircuit(10, 4)\n",
    "qc.x(0)\n",
    "qc.x(1)\n",
    "qc.x(4)\n",
    "qc.x(5)\n",
    "qc.append(create_adder(3), range(10))\n",
    "qc.measure([3, 4, 5, 6], range(4))\n",
    "display(qc.draw())\n",
    "backend = Aer.get_backend('qasm_simulator')\n",
    "job = backend.run(transpile(qc, backend), shots=1024)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "def create_adder_mod(n, bigN):\n",
    "    \"\"\"\n",
    "    :param n: number of bits for a, c and bigN; b has n+1 bits\n",
    "    :param bigN: mod number\n",
    "    :return: Gate of 4n+2 qubits\n",
    "        0-2 qubits for a\n",
    "        3-6 qubits for b\n",
    "        7-9 qubits for c (init to 0)\n",
    "        10-12 qubits for bigN (init to bigN when use)\n",
    "        13 qubit for temp (init to 0)\n",
    "    \"\"\"\n",
    "    a = QuantumRegister(n, 'a')\n",
    "    b = QuantumRegister(n+1, 'b')\n",
    "    c = QuantumRegister(n, 'c')\n",
    "    bN = QuantumRegister(n, 'bigN')\n",
    "    t = QuantumRegister(1, 't')\n",
    "    qc = QuantumCircuit(a, b, c, bN, t)\n",
    "    # block 1\n",
    "    qc.append(create_adder(n), list(a)+list(b)+list(c))\n",
    "    for i in range(n):\n",
    "        qc.swap(a[i], bN[i])\n",
    "    qc.append(create_adder_inv(n), list(a)+list(b)+list(c))\n",
    "    qc.x(b[n])\n",
    "    qc.cx(b[n], t[0])\n",
    "    qc.x(b[n])\n",
    "    tempN = bigN\n",
    "    i = 0\n",
    "    while tempN != 0:\n",
    "        if tempN % 2 != 0:\n",
    "            qc.cx(t[0], a[i])\n",
    "        i = i + 1\n",
    "        tempN = tempN // 2\n",
    "    qc.append(create_adder(n), list(a)+list(b)+list(c))\n",
    "    tempN = bigN\n",
    "    i = 0\n",
    "    while tempN != 0:\n",
    "        if tempN % 2 != 0:\n",
    "            qc.cx(t[0], a[i])\n",
    "        i = i + 1\n",
    "        tempN = tempN // 2\n",
    "    for i in range(n):\n",
    "        qc.swap(a[i], bN[i])\n",
    "    # block 2\n",
    "    qc.append(create_adder_inv(n), list(a)+list(b)+list(c))\n",
    "    qc.cx(b[n], t[0])\n",
    "    qc.append(create_adder(n), list(a)+list(b)+list(c))\n",
    "    #display(qc.draw())\n",
    "    return qc.to_gate(label='adder_mod')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "n = 3\n",
    "bigN = 5\n",
    "#qc = QuantumCircuit(4*n+2)\n",
    "a = QuantumRegister(n, 'a')\n",
    "b = QuantumRegister(n+1, 'b')\n",
    "c = QuantumRegister(n, 'c')\n",
    "bN = QuantumRegister(n, 'bigN')\n",
    "t = QuantumRegister(1, 't')\n",
    "creg = ClassicalRegister(4, 'creg')\n",
    "qc = QuantumCircuit(a, b, c, bN, t, creg)\n",
    "# qc.x(a[0]) # a = 3\n",
    "# qc.x(a[1])\n",
    "qc.x(a[2]) # a = 4\n",
    "qc.x(b[2]) # b = 4\n",
    "qc.x(bN[0])\n",
    "qc.x(bN[2]) # bN = 5\n",
    "qc.append(create_adder_mod(n, bigN), list(a) + list(b) + list(c) + list(bN) + list(t))\n",
    "qc.measure(b, creg)\n",
    "display(qc.draw())\n",
    "backend = Aer.get_backend('qasm_simulator')\n",
    "job = backend.run(transpile(qc, backend), shots=1024)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "def create_ctrl_mult_mod(n, bigN, m):\n",
    "    \"\"\"\n",
    "    Calculate zm mod N and output to b\n",
    "\n",
    "    :param n: number of bits for a, c and bigN; b has n+1 bits\n",
    "    :param bigN: mod number\n",
    "    :param m: multiplier\n",
    "    :return: Gate of 4n+2 qubits\n",
    "        0 (1 qubit) for x\n",
    "        1 to n (n qubits) for z\n",
    "        n+1 to 2n (n qubits) for a\n",
    "        2n+1 to 3n+1 (n+1 qubits) for b\n",
    "        3n+2 to 4n+1 (n qubits) for c (init to 0)\n",
    "        4n+2 to 5n+1 (n qubits) for bigN (init to bigN when use)\n",
    "        5n+2 (1 qubit) for temp (init to 0)\n",
    "    \"\"\"\n",
    "    x = QuantumRegister(1, 'x')\n",
    "    z = QuantumRegister(n, 'z')\n",
    "    a = QuantumRegister(n, 'a')\n",
    "    b = QuantumRegister(n+1, 'b')\n",
    "    c = QuantumRegister(n, 'c')\n",
    "    bN = QuantumRegister(n, 'bN')\n",
    "    t = QuantumRegister(1, 't')\n",
    "    qc = QuantumCircuit(x, z, a, b, c, bN, t)\n",
    "    next_mod = m # m 2^0 mod N\n",
    "    for j in range(n):\n",
    "        temp_mod = next_mod\n",
    "        i = 0\n",
    "        while temp_mod != 0:\n",
    "            if temp_mod % 2 != 0:\n",
    "                qc.ccx(x[0], z[j], a[i])\n",
    "            i = i + 1\n",
    "            temp_mod = temp_mod // 2\n",
    "\n",
    "        qc.append(create_adder_mod(n, bigN), list(a) + list(b) + list(c) + list(bN) + list(t))\n",
    "\n",
    "        temp_mod = next_mod\n",
    "        i = 0\n",
    "        while temp_mod != 0:\n",
    "            if temp_mod % 2 != 0:\n",
    "                qc.ccx(x[0], z[j], a[i])\n",
    "            i = i + 1\n",
    "            temp_mod = temp_mod // 2\n",
    "    \n",
    "        next_mod = (next_mod * 2) % bigN # update for m 2^i+1 mod N \n",
    "    \n",
    "    qc.x(x[0])\n",
    "    for j in range(n):\n",
    "        qc.ccx(x[0], z[j], b[j])\n",
    "    qc.x(x[0])\n",
    "\n",
    "    # display(qc.draw())\n",
    "    return qc.to_gate(label='ctrl_mult_mod')\n",
    "\n",
    "def create_ctrl_mult_mod_inv(n, bigN, m):\n",
    "    qc = QuantumCircuit(5*n+3)\n",
    "    qc.append(create_ctrl_mult_mod(n, bigN, m).inverse(), range(5*n+3))\n",
    "    return qc.to_gate(label='ctrl_mult_mod_inv')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "n = 3\n",
    "bigN = 5\n",
    "m = 3\n",
    "x = QuantumRegister(1, 'x')\n",
    "z = QuantumRegister(n, 'z')\n",
    "a = QuantumRegister(n, 'a')\n",
    "b = QuantumRegister(n+1, 'b')\n",
    "c = QuantumRegister(n, 'c')\n",
    "bN = QuantumRegister(n, 'bN')\n",
    "t = QuantumRegister(1, 't')\n",
    "creg = ClassicalRegister(n, 'creg')\n",
    "qc = QuantumCircuit(x, z, a, b, c, bN, t, creg)\n",
    "qc.x(x[0]) # x = 1\n",
    "qc.x(z[0]) # z = 3\n",
    "qc.x(z[1])\n",
    "qc.x(bN[0]) # bN = 5\n",
    "qc.x(bN[2])\n",
    "qc.append(create_ctrl_mult_mod(n, bigN, m), list(x) + z[:] + list(a) + list(b) + list(c) + list(bN) + list(t))\n",
    "# for i in range(n):\n",
    "#     qc.measure(b[i], creg[i])\n",
    "qc.measure(b[0:n], creg)\n",
    "display(qc.draw())\n",
    "backend = Aer.get_backend('qasm_simulator')\n",
    "job = backend.run(transpile(qc, backend), shots=1024)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "from sympy import mod_inverse\n",
    "\n",
    "def create_mod_exp(n, bigN, y, nx):\n",
    "    \"\"\"\n",
    "    Calculate y^x mod N and output to z\n",
    "\n",
    "    :param n: number of bits for z, a, c and bigN; b has n+1 bits\n",
    "    :param bigN: mod number\n",
    "    :param y: multiplier\n",
    "    :param nx: number of bits for x\n",
    "    :return: Gate of 4n+2 qubits\n",
    "        0 to nx-1 (n qubit) for x\n",
    "        nx to nx+n-1 (n qubits) for z (init to 1 when use)\n",
    "        nx+n to nx+2n-1 (n qubits) for a (init to 0)\n",
    "        nx+2n to nx+3n (n+1 qubits) for b (init to 0)\n",
    "        nx+3n+1 to nx+4n (n qubits) for c (init to 0)\n",
    "        nx+4n+1 to nx+5n (n qubits) for bigN (init to bigN when use)\n",
    "        nx+5n+1 (1 qubit) for temp (init to 0)\n",
    "    \"\"\"\n",
    "    x = QuantumRegister(nx, 'x')\n",
    "    z = QuantumRegister(n, 'z')\n",
    "    a = QuantumRegister(n, 'a')\n",
    "    b = QuantumRegister(n+1, 'b')\n",
    "    c = QuantumRegister(n, 'c')\n",
    "    bN = QuantumRegister(n, 'bN')\n",
    "    t = QuantumRegister(1, 't')\n",
    "    qc = QuantumCircuit(x, z, a, b, c, bN, t)\n",
    "    m = y\n",
    "    for i in range(nx):\n",
    "        qc.append(create_ctrl_mult_mod(n, bigN, m), \n",
    "            [x[i]] + z[:] + a[:] + b[:] + c[:] + bN[:] + list(t))\n",
    "        for j in range(n):\n",
    "            qc.cswap(x[i], z[j], b[j])\n",
    "        m_inv = mod_inverse(m, bigN)\n",
    "        qc.append(create_ctrl_mult_mod_inv(n, bigN, m_inv), \n",
    "            [x[i]] + z[:] + a[:] + b[:] + c[:] + bN[:] + list(t))\n",
    "        m = (m * m) % bigN # update for next cycle\n",
    "    # display(qc.draw())\n",
    "    return qc.to_gate(label='mod_exp')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mJupyter cannot be started. Error attempting to locate Jupyter: Select an Interpreter to start Jupyter\n",
      "\u001b[1;31mRun the following command to install 'jupyter and notebook' into the Python environment. \n",
      "\u001b[1;31mCommand: 'python -m pip install jupyter notebook -U\n",
      "\u001b[1;31mor\n",
      "\u001b[1;31mconda install jupyter notebook -U'\n",
      "\u001b[1;31mClick <a href='https://aka.ms/installJupyterForVSCode'>here</a> for more info."
     ]
    }
   ],
   "source": [
    "n = 3\n",
    "bigN = 5\n",
    "y = 3\n",
    "nx = 6\n",
    "x = QuantumRegister(nx, 'x')\n",
    "z = QuantumRegister(n, 'z')\n",
    "a = QuantumRegister(n, 'a')\n",
    "b = QuantumRegister(n+1, 'b')\n",
    "c = QuantumRegister(n, 'c')\n",
    "bN = QuantumRegister(n, 'bN')\n",
    "t = QuantumRegister(1, 't')\n",
    "creg = ClassicalRegister(n, 'creg')\n",
    "qc = QuantumCircuit(x, z, a, b, c, bN, t, creg)\n",
    "#qc.x(x[2]) # x = 4\n",
    "# qc.x(x[0]) # x = 3\n",
    "# qc.x(x[1])\n",
    "qc.x(x[1]) # x = 42\n",
    "qc.x(x[3])\n",
    "qc.x(x[5])\n",
    "qc.x(z[0]) # z = 1 init\n",
    "qc.x(bN[0]) # bN = 5\n",
    "qc.x(bN[2])\n",
    "qc.append(create_mod_exp(n, bigN, y, nx), x[:] + z[:] + a[:] + b[:] + c[:] + bN[:] + list(t))\n",
    "qc.measure(z, creg)\n",
    "display(qc.draw())\n",
    "backend = Aer.get_backend('qasm_simulator')\n",
    "job = backend.run(transpile(qc, backend), shots=1024)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">          ┌───┐┌───────────┐┌─────────────────────┐┌─┐                        »\n",
       "     x_0: ┤ H ├┤0          ├┤0                    ├┤M├────────────────────────»\n",
       "          ├───┤│           ││                     │└╥┘┌─┐                     »\n",
       "     x_1: ┤ H ├┤1          ├┤1                    ├─╫─┤M├─────────────────────»\n",
       "          ├───┤│           ││                     │ ║ └╥┘┌─┐                  »\n",
       "     x_2: ┤ H ├┤2          ├┤2                    ├─╫──╫─┤M├──────────────────»\n",
       "          ├───┤│           ││                     │ ║  ║ └╥┘┌─┐               »\n",
       "     x_3: ┤ H ├┤3          ├┤3                    ├─╫──╫──╫─┤M├───────────────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║ └╥┘┌─┐            »\n",
       "     x_4: ┤ H ├┤4          ├┤4                    ├─╫──╫──╫──╫─┤M├────────────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║ └╥┘┌─┐         »\n",
       "     x_5: ┤ H ├┤5          ├┤5                    ├─╫──╫──╫──╫──╫─┤M├─────────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║ └╥┘┌─┐      »\n",
       "     x_6: ┤ H ├┤6          ├┤6                    ├─╫──╫──╫──╫──╫──╫─┤M├──────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║ └╥┘┌─┐   »\n",
       "     x_7: ┤ H ├┤7          ├┤7                    ├─╫──╫──╫──╫──╫──╫──╫─┤M├───»\n",
       "          ├───┤│           ││   circuit-406237_dg │ ║  ║  ║  ║  ║  ║  ║ └╥┘┌─┐»\n",
       "     x_8: ┤ H ├┤8          ├┤8                    ├─╫──╫──╫──╫──╫──╫──╫──╫─┤M├»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║ └╥┘»\n",
       "     x_9: ┤ H ├┤9          ├┤9                    ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_10: ┤ H ├┤10         ├┤10                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_11: ┤ H ├┤11         ├┤11                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_12: ┤ H ├┤12         ├┤12                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_13: ┤ H ├┤13         ├┤13                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_14: ┤ H ├┤14         ├┤14                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_15: ┤ H ├┤15         ├┤15                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │└─────────────────────┘ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_0: ┤ X ├┤16         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_1: ─────┤17         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_2: ─────┤18         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_3: ─────┤19         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_4: ─────┤20         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_5: ─────┤21         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_6: ─────┤22         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_7: ─────┤23         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_0: ─────┤24         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_1: ─────┤25         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_2: ─────┤26         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_3: ─────┤27         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_4: ─────┤28         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │   mod_exp │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_5: ─────┤29         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_6: ─────┤30         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_7: ─────┤31         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_0: ─────┤32         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_1: ─────┤33         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_2: ─────┤34         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_3: ─────┤35         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_4: ─────┤36         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_5: ─────┤37         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_6: ─────┤38         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_7: ─────┤39         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_8: ─────┤40         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_0: ─────┤41         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_1: ─────┤42         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_2: ─────┤43         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_3: ─────┤44         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_4: ─────┤45         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_5: ─────┤46         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_6: ─────┤47         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_7: ─────┤48         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ┌───┐│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_0: ┤ X ├┤49         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_1: ─────┤50         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ┌───┐│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_2: ┤ X ├┤51         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_3: ┤ X ├┤52         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_4: ┤ X ├┤53         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_5: ─────┤54         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ┌───┐│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_6: ┤ X ├┤55         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_7: ┤ X ├┤56         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "       t: ─────┤57         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               └───────────┘                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "cregx: 16/══════════════════════════════════════════╩══╩══╩══╩══╩══╩══╩══╩══╩═»\n",
       "                                                    0  1  2  3  4  5  6  7  8 »\n",
       "«                               \n",
       "«     x_0: ─────────────────────\n",
       "«                               \n",
       "«     x_1: ─────────────────────\n",
       "«                               \n",
       "«     x_2: ─────────────────────\n",
       "«                               \n",
       "«     x_3: ─────────────────────\n",
       "«                               \n",
       "«     x_4: ─────────────────────\n",
       "«                               \n",
       "«     x_5: ─────────────────────\n",
       "«                               \n",
       "«     x_6: ─────────────────────\n",
       "«                               \n",
       "«     x_7: ─────────────────────\n",
       "«                               \n",
       "«     x_8: ─────────────────────\n",
       "«          ┌─┐                  \n",
       "«     x_9: ┤M├──────────────────\n",
       "«          └╥┘┌─┐               \n",
       "«    x_10: ─╫─┤M├───────────────\n",
       "«           ║ └╥┘┌─┐            \n",
       "«    x_11: ─╫──╫─┤M├────────────\n",
       "«           ║  ║ └╥┘┌─┐         \n",
       "«    x_12: ─╫──╫──╫─┤M├─────────\n",
       "«           ║  ║  ║ └╥┘┌─┐      \n",
       "«    x_13: ─╫──╫──╫──╫─┤M├──────\n",
       "«           ║  ║  ║  ║ └╥┘┌─┐   \n",
       "«    x_14: ─╫──╫──╫──╫──╫─┤M├───\n",
       "«           ║  ║  ║  ║  ║ └╥┘┌─┐\n",
       "«    x_15: ─╫──╫──╫──╫──╫──╫─┤M├\n",
       "«           ║  ║  ║  ║  ║  ║ └╥┘\n",
       "«     z_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_8: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«       t: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«cregx: 16/═╩══╩══╩══╩══╩══╩══╩═\n",
       "«           9  10 11 12 13 14 15</pre>"
      ],
      "text/plain": [
       "          ┌───┐┌───────────┐┌─────────────────────┐┌─┐                        »\n",
       "     x_0: ┤ H ├┤0          ├┤0                    ├┤M├────────────────────────»\n",
       "          ├───┤│           ││                     │└╥┘┌─┐                     »\n",
       "     x_1: ┤ H ├┤1          ├┤1                    ├─╫─┤M├─────────────────────»\n",
       "          ├───┤│           ││                     │ ║ └╥┘┌─┐                  »\n",
       "     x_2: ┤ H ├┤2          ├┤2                    ├─╫──╫─┤M├──────────────────»\n",
       "          ├───┤│           ││                     │ ║  ║ └╥┘┌─┐               »\n",
       "     x_3: ┤ H ├┤3          ├┤3                    ├─╫──╫──╫─┤M├───────────────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║ └╥┘┌─┐            »\n",
       "     x_4: ┤ H ├┤4          ├┤4                    ├─╫──╫──╫──╫─┤M├────────────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║ └╥┘┌─┐         »\n",
       "     x_5: ┤ H ├┤5          ├┤5                    ├─╫──╫──╫──╫──╫─┤M├─────────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║ └╥┘┌─┐      »\n",
       "     x_6: ┤ H ├┤6          ├┤6                    ├─╫──╫──╫──╫──╫──╫─┤M├──────»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║ └╥┘┌─┐   »\n",
       "     x_7: ┤ H ├┤7          ├┤7                    ├─╫──╫──╫──╫──╫──╫──╫─┤M├───»\n",
       "          ├───┤│           ││   circuit-406237_dg │ ║  ║  ║  ║  ║  ║  ║ └╥┘┌─┐»\n",
       "     x_8: ┤ H ├┤8          ├┤8                    ├─╫──╫──╫──╫──╫──╫──╫──╫─┤M├»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║ └╥┘»\n",
       "     x_9: ┤ H ├┤9          ├┤9                    ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_10: ┤ H ├┤10         ├┤10                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_11: ┤ H ├┤11         ├┤11                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_12: ┤ H ├┤12         ├┤12                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_13: ┤ H ├┤13         ├┤13                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_14: ┤ H ├┤14         ├┤14                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           ││                     │ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    x_15: ┤ H ├┤15         ├┤15                   ├─╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │└─────────────────────┘ ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_0: ┤ X ├┤16         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_1: ─────┤17         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_2: ─────┤18         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_3: ─────┤19         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_4: ─────┤20         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_5: ─────┤21         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_6: ─────┤22         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     z_7: ─────┤23         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_0: ─────┤24         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_1: ─────┤25         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_2: ─────┤26         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_3: ─────┤27         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_4: ─────┤28         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │   mod_exp │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_5: ─────┤29         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_6: ─────┤30         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     a_7: ─────┤31         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_0: ─────┤32         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_1: ─────┤33         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_2: ─────┤34         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_3: ─────┤35         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_4: ─────┤36         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_5: ─────┤37         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_6: ─────┤38         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_7: ─────┤39         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     b_8: ─────┤40         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_0: ─────┤41         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_1: ─────┤42         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_2: ─────┤43         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_3: ─────┤44         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_4: ─────┤45         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_5: ─────┤46         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_6: ─────┤47         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               │           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "     c_7: ─────┤48         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ┌───┐│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_0: ┤ X ├┤49         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_1: ─────┤50         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ┌───┐│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_2: ┤ X ├┤51         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_3: ┤ X ├┤52         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_4: ┤ X ├┤53         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_5: ─────┤54         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ┌───┐│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_6: ┤ X ├┤55         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          ├───┤│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "    bN_7: ┤ X ├┤56         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "          └───┘│           │                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "       t: ─────┤57         ├────────────────────────╫──╫──╫──╫──╫──╫──╫──╫──╫─»\n",
       "               └───────────┘                        ║  ║  ║  ║  ║  ║  ║  ║  ║ »\n",
       "cregx: 16/══════════════════════════════════════════╩══╩══╩══╩══╩══╩══╩══╩══╩═»\n",
       "                                                    0  1  2  3  4  5  6  7  8 »\n",
       "«                               \n",
       "«     x_0: ─────────────────────\n",
       "«                               \n",
       "«     x_1: ─────────────────────\n",
       "«                               \n",
       "«     x_2: ─────────────────────\n",
       "«                               \n",
       "«     x_3: ─────────────────────\n",
       "«                               \n",
       "«     x_4: ─────────────────────\n",
       "«                               \n",
       "«     x_5: ─────────────────────\n",
       "«                               \n",
       "«     x_6: ─────────────────────\n",
       "«                               \n",
       "«     x_7: ─────────────────────\n",
       "«                               \n",
       "«     x_8: ─────────────────────\n",
       "«          ┌─┐                  \n",
       "«     x_9: ┤M├──────────────────\n",
       "«          └╥┘┌─┐               \n",
       "«    x_10: ─╫─┤M├───────────────\n",
       "«           ║ └╥┘┌─┐            \n",
       "«    x_11: ─╫──╫─┤M├────────────\n",
       "«           ║  ║ └╥┘┌─┐         \n",
       "«    x_12: ─╫──╫──╫─┤M├─────────\n",
       "«           ║  ║  ║ └╥┘┌─┐      \n",
       "«    x_13: ─╫──╫──╫──╫─┤M├──────\n",
       "«           ║  ║  ║  ║ └╥┘┌─┐   \n",
       "«    x_14: ─╫──╫──╫──╫──╫─┤M├───\n",
       "«           ║  ║  ║  ║  ║ └╥┘┌─┐\n",
       "«    x_15: ─╫──╫──╫──╫──╫──╫─┤M├\n",
       "«           ║  ║  ║  ║  ║  ║ └╥┘\n",
       "«     z_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     z_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     a_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     b_8: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«     c_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_0: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_1: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_2: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_3: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_4: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_5: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_6: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«    bN_7: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«       t: ─╫──╫──╫──╫──╫──╫──╫─\n",
       "«           ║  ║  ║  ║  ║  ║  ║ \n",
       "«cregx: 16/═╩══╩══╩══╩══╩══╩══╩═\n",
       "«           9  10 11 12 13 14 15"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'1011010101010101': 1}\n"
     ]
    }
   ],
   "source": [
    "n = 8\n",
    "bigN = 221\n",
    "y = 3\n",
    "nx = 16\n",
    "x = QuantumRegister(nx, 'x')\n",
    "z = QuantumRegister(n, 'z')\n",
    "a = QuantumRegister(n, 'a')\n",
    "b = QuantumRegister(n+1, 'b')\n",
    "c = QuantumRegister(n, 'c')\n",
    "bN = QuantumRegister(n, 'bN')\n",
    "t = QuantumRegister(1, 't')\n",
    "# cregz = ClassicalRegister(n, 'cregz')\n",
    "cregx = ClassicalRegister(nx, 'cregx')\n",
    "# qc = QuantumCircuit(x, z, a, b, c, bN, t, cregz, cregx)\n",
    "qc = QuantumCircuit(x, z, a, b, c, bN, t, cregx)\n",
    "qc.h(x)\n",
    "qc.x(z[0]) # z = 1 init\n",
    "qc.x(bN[0]) # bN = 221 = 11011101(2)\n",
    "qc.x(bN[2])\n",
    "qc.x(bN[3])\n",
    "qc.x(bN[4])\n",
    "qc.x(bN[6])\n",
    "qc.x(bN[7])\n",
    "\n",
    "qc.append(create_mod_exp(n, bigN, y, nx), x[:] + z[:] + a[:] + b[:] + c[:] + bN[:] + list(t))\n",
    "qc.append(myqft(nx).inverse(), x)\n",
    "# qc.measure(z, cregz)\n",
    "qc.measure(x, cregx)\n",
    "display(qc.draw())\n",
    "backend = Aer.get_backend('qasm_simulator')\n",
    "job = backend.run(transpile(qc, backend), shots=1)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(17, 24)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fractions import Fraction\n",
    "Fraction(46421/2**16).limit_denominator(221)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "print(math.gcd(3**12+1, 221))\n",
    "print(math.gcd(3**12-1, 221))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "221"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "17*13"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "qiskit_env",
   "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": "b7b4ead5d24734c2a41540018ab7aa4f2247bd7b68de855b6b65f9bc6ebaaee2"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}