{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ba3ae4c9",
   "metadata": {},
   "source": [
    "# Exponentiator\n",
    "\n",
    "**Download Notebook** - {nb-download}`exponentiator.ipynb`\n",
    "\n",
    "This notebook demonstrates the modulo-$2^n$ exponentiator implemented in `guppyalgos.primitives.arithmetic`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ae679e47",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import no_type_check\n",
    "\n",
    "from guppylang import guppy\n",
    "\n",
    "from guppyalgos.primitives.arithmetic import exponentiator_ripple_gidney_mod\n",
    "\n",
    "from guppylang.std.builtins import output\n",
    "from guppylang.std.quantum import collect_measurements, measure_array\n",
    "\n",
    "from guppyalgos.utils import apply_bitstring, bits_to_int, int_to_bits, qarray"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7026476c",
   "metadata": {},
   "source": [
    "# Math and Circuit Structure\n",
    "\n",
    "For a given $n$-bit classical constant $b$, the target operation for the exponentiator is\n",
    "$$\n",
    "    |x\\rangle |1\\rangle \\mapsto |x\\rangle |b^x \\mod 2^n \\rangle.\n",
    "$$\n",
    "Since this operation is generally not reversible for even bases, $b$ must be odd for this implementation.\n",
    "\n",
    "The exponentiation is decomposed into the standard sequence of controlled modular multiplications as follows. For a little-endian exponent $x = x_0 x_1 \\dots x_{m-1}$, we can write the exponential as\n",
    "$$\n",
    "    b^x \\mod 2^n = \\prod_{i=0}^{m-1} \\left( b^{2^i} \\mod 2^n \\right)^{x_i}.\n",
    "$$\n",
    "The multiplicand $b^{2^i} \\mod 2^n$ can be efficiently classically precomputed via repeated squaring, so in total the exponentiator requires $m$ controlled multipliers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "2da059c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected output: 3\n"
     ]
    }
   ],
   "source": [
    "n = 2\n",
    "exponent = 5\n",
    "base = 3\n",
    "\n",
    "expected = base ** exponent % (2 ** n)\n",
    "print(f\"Expected output: {expected}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8b4fe9d8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exponent register measurement result: 5\n",
      "Output register measurement result: 3\n"
     ]
    }
   ],
   "source": [
    "exponent_reg_size = exponent.bit_length()\n",
    "exponent_bits = int_to_bits(exponent, exponent_reg_size)\n",
    "initial_state_bits = int_to_bits(1, n)\n",
    "\n",
    "@guppy\n",
    "@no_type_check\n",
    "def main() -> None:\n",
    "    exponent_reg = qarray(exponent_reg_size)\n",
    "    apply_bitstring(exponent_reg, exponent_bits)\n",
    "    output_reg = qarray(n)\n",
    "    apply_bitstring(output_reg, initial_state_bits)\n",
    "\n",
    "    exponentiator_ripple_gidney_mod(exponent_reg, output_reg, base)\n",
    "\n",
    "    output(\"exponent_meas\", collect_measurements(measure_array(exponent_reg)))\n",
    "    output(\"output_meas\", collect_measurements(measure_array(output_reg)))\n",
    "\n",
    "required_qubits = exponent_reg_size + 5 * n\n",
    "result = main.emulator(n_qubits=required_qubits).run().results[0].as_dict()\n",
    "exponent_reg_measurement_result = bits_to_int(result[\"exponent_meas\"])\n",
    "output_reg_measurement_result = bits_to_int(result[\"output_meas\"])\n",
    "\n",
    "print(f\"Exponent register measurement result: {exponent_reg_measurement_result}\")\n",
    "print(f\"Output register measurement result: {output_reg_measurement_result}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "guppyalgos (3.12.x)",
   "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.12.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}