{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b16d9e47-0888-4e50-ae5e-4da79314e6b4",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Importing standard Qiskit libraries\n",
    "from qiskit import QuantumCircuit, transpile\n",
    "from qiskit import QuantumRegister, ClassicalRegister\n",
    "from qiskit.visualization import *\n",
    "from ibm_quantum_widgets import *\n",
    "from qiskit.visualization import plot_histogram\n",
    "\n",
    "from qiskit_aer import Aer\n",
    "\n",
    "# Import the Quantum Fourier Transform (QFT) circuit implementation from the Qiskit circuit library\n",
    "from qiskit.circuit.library import QFT\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "137d5e49-b218-4697-b581-bf71a0d7ec4e",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def c_amod15(a):\n",
    "    \"\"\"\n",
    "    Controlled multiplication by a mod 15.\n",
    "    This is hard-coded for simplicity.\n",
    "    \"\"\"\n",
    "    if a not in [2, 4, 7, 8, 11, 13]:\n",
    "        raise ValueError(\"'a' must not have common factors with 15\")\n",
    "    U = QuantumCircuit(4)\n",
    "    if a in [2, 13]:\n",
    "        U.swap(2, 3)\n",
    "        U.swap(1, 2)\n",
    "        U.swap(0, 1)\n",
    "    if a in [7, 8]:\n",
    "        U.swap(0, 1)\n",
    "        U.swap(1, 2)\n",
    "        U.swap(2, 3)\n",
    "    if a in [4, 11]:\n",
    "        U.swap(1, 3)\n",
    "        U.swap(0, 2)\n",
    "    if a in [7, 11, 13]:\n",
    "        for q in range(4):\n",
    "            U.x(q)\n",
    "    U = U.to_gate()\n",
    "    U.name = f\"{a} mod 15\"\n",
    "    c_U = U.control()\n",
    "    return c_U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1bc8f4c5-08c7-4e63-9874-046a1f369a26",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def phase_estimation(\n",
    "        controlled_operation: QuantumCircuit,\n",
    "        psi_prep: QuantumCircuit,\n",
    "        precision: int\n",
    "    ):\n",
    "    \"\"\"\n",
    "    Carry out phase estimation on a simulator.\n",
    "    Args:\n",
    "        controlled_operation: The operation to perform phase estimation on,\n",
    "                              controlled by one qubit.\n",
    "        psi_prep: Circuit to prepare |ψ>\n",
    "        precision: Number of counting qubits to use\n",
    "    Returns:\n",
    "        float: Best guess for phase of U|ψ>\n",
    "    \"\"\"\n",
    "    control_register = QuantumRegister(precision)\n",
    "    output_register = ClassicalRegister(precision)\n",
    "\n",
    "    target_register = QuantumRegister(psi_prep.num_qubits)\n",
    "    qc = QuantumCircuit(control_register, target_register, output_register)\n",
    "\n",
    "    # Prepare |ψ>\n",
    "    qc.compose(psi_prep,\n",
    "               qubits=target_register,\n",
    "               inplace=True)\n",
    "\n",
    "    # Do phase estimation\n",
    "    for index, qubit in enumerate(control_register):\n",
    "        qc.h(qubit)\n",
    "        for _ in range(2**index):\n",
    "            qc.compose(\n",
    "                controlled_operation,\n",
    "                qubits=[qubit] + list(target_register),\n",
    "                inplace=True,\n",
    "            )\n",
    "\n",
    "    qc.compose(\n",
    "        QFT(precision, inverse=True),\n",
    "        qubits=control_register,\n",
    "        inplace=True\n",
    "    )\n",
    "\n",
    "    qc.measure(control_register, output_register)\n",
    "\n",
    "    measurement = Sampler().run(qc, shots=1).result().quasi_dists[0].popitem()[0]\n",
    "    return measurement / 2**precision"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "50df0aad-bac1-4548-a194-84979586cd0e",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "psi_prep = QuantumCircuit(4)\n",
    "psi_prep.x(0)\n",
    "display(psi_prep.draw())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b308836-ad15-4fee-ac35-c53812b2fd8b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from fractions import Fraction\n",
    "from math import gcd\n",
    "from qiskit.primitives import Sampler\n",
    "\n",
    "a = 8\n",
    "N = 15\n",
    "\n",
    "FACTOR_FOUND = False\n",
    "ATTEMPT = 0\n",
    "while not FACTOR_FOUND:\n",
    "    ATTEMPT += 1\n",
    "    print(f\"\\nAttempt {ATTEMPT}\")\n",
    "\n",
    "    phase = phase_estimation(\n",
    "        c_amod15(a),\n",
    "        psi_prep,\n",
    "        precision=8\n",
    "    )\n",
    "    frac = Fraction(phase).limit_denominator(N)\n",
    "    r = frac.denominator\n",
    "    if phase != 0:\n",
    "        # Guess for a factor is gcd(x^{r/2} - 1 , 15)\n",
    "        guess = gcd(a ** (r // 2) - 1, N)\n",
    "        if guess not in [1, N] and (N % guess) == 0:\n",
    "            # Guess is a factor!\n",
    "            print(f\"Non-trivial factor found: {guess}\")\n",
    "            FACTOR_FOUND = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "123b1165-ba96-40aa-8143-68d1edd2eabc",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Qiskit v1.0.2 (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"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}