{ "cells": [ { "cell_type": "markdown", "id": "0721324a", "metadata": { "id": "0721324a" }, "source": [ "# Quantum Phase Estimation, Order Finding y Shor\n", "\n", "Este notebook acompaña el módulo **QPE, Order Finding y Shor**. Está escrito como material autoexplicativo para estudiar la conexión entre estimación de fase, periodicidad modular y factorización entera. La notación de Dirac se escribe sin macros personalizadas para preservar compatibilidad con JupyterLab, Anaconda y Google Colab; por ejemplo, usamos\n", "\n", "$$\n", "\\left|u\\right\\rangle, \\qquad \\left\\langle u\\right|, \\qquad U\\left|u\\right\\rangle=e^{2\\pi i\\varphi}\\left|u\\right\\rangle.\n", "$$\n", "\n", "El objetivo conceptual es entender cómo una fase cuántica, que no se observa directamente, puede convertirse en una fracción racional y luego en el orden multiplicativo que permite factorizar enteros compuestos." ] }, { "cell_type": "markdown", "id": "90349bbd", "metadata": { "id": "90349bbd" }, "source": [ "## Objetivos de aprendizaje\n", "\n", "Al finalizar el notebook podrás explicar qué estima QPE, por qué el registro de conteo codifica una fase binaria, cómo la inverse QFT transforma una onda de fase en una distribución de medición, por qué el operador de multiplicación modular tiene fases de la forma $s/r$, cómo las fracciones continuas permiten reconstruir candidatos para $r$, y cómo Shor convierte un orden útil en factores no triviales de $N$.\n", "\n", "El notebook no repite la introducción básica a números complejos, qubits o QFT. Esos conceptos se usan como prerrequisitos y se retoman únicamente cuando son necesarios para interpretar QPE, order finding y Shor." ] }, { "cell_type": "code", "execution_count": null, "id": "c9d4699f", "metadata": { "id": "c9d4699f" }, "outputs": [], "source": [ "import math\n", "from math import gcd, pi\n", "from fractions import Fraction\n", "from typing import List, Tuple, Optional, Dict\n", "\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "plt.rcParams[\"figure.figsize\"] = (7, 4.5)\n", "plt.rcParams[\"axes.grid\"] = True" ] }, { "cell_type": "markdown", "id": "7aa0372d", "metadata": { "id": "7aa0372d" }, "source": [ "## 1. Qué significa estimar una fase\n", "\n", "Sea $U$ un operador unitario y sea $\\left|u\\right\\rangle$ un eigenvector:\n", "\n", "$$\n", "U\\left|u\\right\\rangle=e^{2\\pi i\\varphi}\\left|u\\right\\rangle,\n", "\\qquad \\varphi\\in[0,1).\n", "$$\n", "\n", "QPE intenta estimar $\\varphi$. La fase se expresa normalizada: $\\varphi=1/2$ significa una rotación angular de $\\pi$, mientras que $\\varphi=5/8$ significa una rotación de $5\\pi/4$. La clave es que aplicar $U^k$ al eigenvector produce\n", "\n", "$$\n", "U^k\\left|u\\right\\rangle=e^{2\\pi i k\\varphi}\\left|u\\right\\rangle.\n", "$$\n", "\n", "Por eso las potencias controladas de $U$ permiten escribir múltiplos de la fase en el registro de conteo." ] }, { "cell_type": "code", "execution_count": null, "id": "0b6aa834", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 487 }, "id": "0b6aa834", "outputId": "4bb18ef5-9b01-428d-80cd-8e3645c2e06c" }, "outputs": [], "source": [ "def plot_phase_on_unit_circle(phi: float, title: str = \"Fase como punto en el círculo unitario\") -> None:\n", " \"\"\"Visualiza e^{2πiφ} en el círculo unitario.\"\"\"\n", " theta = 2 * np.pi * phi\n", " fig, ax = plt.subplots(figsize=(5, 5))\n", " t = np.linspace(0, 2*np.pi, 400)\n", " ax.plot(np.cos(t), np.sin(t))\n", " ax.axhline(0, linewidth=1)\n", " ax.axvline(0, linewidth=1)\n", " ax.arrow(0, 0, np.cos(theta), np.sin(theta), head_width=0.06, length_includes_head=True)\n", " ax.scatter([np.cos(theta)], [np.sin(theta)])\n", " ax.text(np.cos(theta)*1.12, np.sin(theta)*1.12, f\"φ={phi:.4f}\")\n", " ax.set_aspect(\"equal\")\n", " ax.set_xlabel(\"Re\")\n", " ax.set_ylabel(\"Im\")\n", " ax.set_title(title)\n", " plt.show()\n", "\n", "plot_phase_on_unit_circle(5/8, \"Ejemplo: fase estimada 5/8\")" ] }, { "cell_type": "markdown", "id": "18986380", "metadata": { "id": "18986380" }, "source": [ "## 2. Fases binarias\n", "\n", "Con $t$ qubits de conteo se distinguen $2^t$ posiciones en el intervalo $[0,1)$. Una medición $m$ se interpreta como\n", "\n", "$$\n", "\\widetilde{\\varphi}=\\frac{m}{2^t}.\n", "$$\n", "\n", "Si $t=3$ y la cadena observada es $101_2$, entonces $m=5$ y la estimación es $5/8$. Esta interpretación será esencial cuando el resultado de QPE deba convertirse en una fracción $s/r$." ] }, { "cell_type": "code", "execution_count": null, "id": "867fab96", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "867fab96", "outputId": "82be396f-3383-4548-d674-681f0c27f226" }, "outputs": [], "source": [ "def binary_phase_table(t: int) -> None:\n", " \"\"\"Muestra las fases representables con t qubits de conteo.\"\"\"\n", " rows = []\n", " for m in range(2**t):\n", " rows.append((format(m, f\"0{t}b\"), m, Fraction(m, 2**t)))\n", " for bits, m, frac in rows:\n", " print(f\"{bits} -> {m:2d}/{2**t} = {frac}\")\n", "\n", "binary_phase_table(3)" ] }, { "cell_type": "code", "execution_count": null, "id": "cd8bd5d6", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 282 }, "id": "cd8bd5d6", "outputId": "1f9c9e59-e441-41a3-98c2-d33bbdb017a9" }, "outputs": [], "source": [ "def plot_binary_phase_grid(t: int, highlight: Optional[int] = None) -> None:\n", " \"\"\"Visualiza la malla binaria de fases en [0,1).\"\"\"\n", " xs = np.arange(2**t) / (2**t)\n", " ys = np.zeros_like(xs)\n", " plt.figure(figsize=(9, 1.8))\n", " plt.scatter(xs, ys)\n", " for m, x in enumerate(xs):\n", " plt.text(x, 0.05, format(m, f\"0{t}b\"), ha=\"center\", fontsize=8, rotation=45)\n", " if highlight is not None:\n", " plt.scatter([highlight/2**t], [0], s=180)\n", " plt.text(highlight/2**t, -0.12, f\"m={highlight}\", ha=\"center\")\n", " plt.yticks([])\n", " plt.xlabel(\"fase normalizada\")\n", " plt.title(f\"Malla de fases con t={t} qubits\")\n", " plt.xlim(-0.03, 1.03)\n", " plt.show()\n", "\n", "plot_binary_phase_grid(3, highlight=5)" ] }, { "cell_type": "markdown", "id": "b0c23e53", "metadata": { "id": "b0c23e53" }, "source": [ "## 3. Distribución ideal de QPE\n", "\n", "Cuando la fase exacta no cae en la malla binaria, QPE no devuelve siempre un único entero. La distribución de probabilidad se concentra alrededor de los enteros $m$ cercanos a $2^t\\varphi$. Una forma útil de visualizar la distribución ideal es construir el estado del registro de conteo antes de la inverse QFT y aplicar la transformada inversa discreta." ] }, { "cell_type": "code", "execution_count": null, "id": "4ca52979", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 797 }, "id": "4ca52979", "outputId": "2c9bfcfc-e520-4023-a47d-763e305a7591" }, "outputs": [], "source": [ "def qft_matrix(M: int, inverse: bool = False) -> np.ndarray:\n", " \"\"\"Matriz QFT de dimensión M, con normalización unitaria.\"\"\"\n", " omega = np.exp(2j * np.pi / M)\n", " j, k = np.meshgrid(np.arange(M), np.arange(M), indexing=\"ij\")\n", " F = omega ** (j * k) / np.sqrt(M)\n", " return F.conj().T if inverse else F\n", "\n", "\n", "def qpe_distribution(phi: float, t: int) -> np.ndarray:\n", " \"\"\"Distribución ideal de QPE para una fase φ usando t qubits de conteo.\"\"\"\n", " M = 2**t\n", " k = np.arange(M)\n", " state_before_iqft = np.exp(2j * np.pi * phi * k) / np.sqrt(M)\n", " state_after_iqft = qft_matrix(M, inverse=True) @ state_before_iqft\n", " return np.abs(state_after_iqft) ** 2\n", "\n", "\n", "def plot_qpe_distribution(phi: float, t: int) -> None:\n", " probs = qpe_distribution(phi, t)\n", " labels = [format(i, f\"0{t}b\") for i in range(2**t)]\n", " plt.figure(figsize=(9, 4))\n", " plt.bar(range(2**t), probs)\n", " plt.xticks(range(2**t), labels, rotation=90)\n", " plt.ylabel(\"probabilidad\")\n", " plt.xlabel(\"resultado del registro de conteo\")\n", " plt.title(f\"Distribución ideal de QPE para φ={phi:.5f}, t={t}\")\n", " plt.tight_layout()\n", " plt.show()\n", "\n", "plot_qpe_distribution(5/8, 3)\n", "plot_qpe_distribution(2/7, 4)" ] }, { "cell_type": "markdown", "id": "78a85645", "metadata": { "id": "78a85645" }, "source": [ "## 4. Diagrama conceptual de QPE\n", "\n", "El diagrama siguiente no intenta reemplazar el circuito real. Su función es mostrar el flujo de información: el registro de conteo se prepara en superposición, las potencias controladas escriben fases y la inverse QFT convierte esas fases en una cadena medible." ] }, { "cell_type": "code", "execution_count": null, "id": "c9bb4f21", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 290 }, "id": "c9bb4f21", "outputId": "298c05b4-e4df-437e-d453-4a2a33ccfdaa" }, "outputs": [], "source": [ "def draw_qpe_diagram() -> None:\n", " fig, ax = plt.subplots(figsize=(10, 3))\n", " ax.axis(\"off\")\n", " boxes = [\n", " (0.05, 0.62, \"conteo\\n|0...0>\"),\n", " (0.25, 0.62, \"H en\\nconteo\"),\n", " (0.47, 0.62, \"U^{2^j}\\ncontroladas\"),\n", " (0.70, 0.62, \"inverse\\nQFT\"),\n", " (0.88, 0.62, \"medición\\nm\"),\n", " (0.47, 0.18, \"trabajo\\n|u>\")\n", " ]\n", " for x, y, txt in boxes:\n", " ax.text(x, y, txt, ha=\"center\", va=\"center\", bbox=dict(boxstyle=\"round\", fc=\"white\", ec=\"black\"))\n", " for x1, x2 in [(0.12,0.20),(0.31,0.40),(0.55,0.62),(0.76,0.82)]:\n", " ax.annotate(\"\", xy=(x2,0.62), xytext=(x1,0.62), arrowprops=dict(arrowstyle=\"->\"))\n", " ax.annotate(\"\", xy=(0.47,0.48), xytext=(0.47,0.28), arrowprops=dict(arrowstyle=\"->\"))\n", " ax.set_title(\"Arquitectura conceptual de Quantum Phase Estimation\")\n", " plt.show()\n", "\n", "draw_qpe_diagram()" ] }, { "cell_type": "markdown", "id": "e033d86f", "metadata": { "id": "e033d86f" }, "source": [ "## 5. Potencias controladas\n", "\n", "La razón por la que aparecen potencias $U^{2^j}$ es binaria. El qubit $j$ del registro de conteo decide si la rama correspondiente acumula una fase multiplicada por $2^j$. En una implementación, la sintaxis exacta depende del marco de software, pero la intención matemática es siempre controlar $U^{2^j}$." ] }, { "cell_type": "code", "execution_count": null, "id": "32e3c41b", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "32e3c41b", "outputId": "3d618f35-ab93-49c5-f591-bc9342afa4fa" }, "outputs": [], "source": [ "def controlled_power_table(t: int) -> None:\n", " for j in range(t):\n", " print(f\"qubit de conteo {j}: controla U^{2**j}\")\n", "\n", "controlled_power_table(6)" ] }, { "cell_type": "markdown", "id": "79dbcc1f", "metadata": { "id": "79dbcc1f" }, "source": [ "## 6. Order finding\n", "\n", "Dado $x$ coprimo con $N$, el orden multiplicativo de $x$ módulo $N$ es el menor entero positivo $r$ tal que\n", "\n", "$$\n", "x^r\\equiv 1 \\pmod N.\n", "$$\n", "\n", "La sucesión $x^a\\bmod N$ es periódica con período $r$. Shor usa QPE porque esa periodicidad puede representarse como fase de un operador unitario de multiplicación modular." ] }, { "cell_type": "code", "execution_count": null, "id": "40de37e5", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "40de37e5", "outputId": "f4d2c12f-87be-4a48-9ef6-541b55bd6f29" }, "outputs": [], "source": [ "def order_mod(x: int, N: int, limit: Optional[int] = None) -> Optional[int]:\n", " \"\"\"Devuelve el menor r>0 tal que x^r = 1 mod N, si gcd(x,N)=1.\"\"\"\n", " if gcd(x, N) != 1:\n", " return None\n", " if limit is None:\n", " limit = 4 * N\n", " value = 1\n", " for r in range(1, limit + 1):\n", " value = (value * x) % N\n", " if value == 1:\n", " return r\n", " return None\n", "\n", "print(\"orden de 4 módulo 81:\", order_mod(4, 81))\n", "print(\"orden de 2 módulo 15:\", order_mod(2, 15))\n", "print(\"orden de 2 módulo 21:\", order_mod(2, 21))" ] }, { "cell_type": "code", "execution_count": null, "id": "05225bf8", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 803 }, "id": "05225bf8", "outputId": "4e2a8b5d-bb96-4105-f235-6b24e9db832a" }, "outputs": [], "source": [ "def modular_sequence(x: int, N: int, length: int) -> List[int]:\n", " return [pow(x, a, N) for a in range(length)]\n", "\n", "\n", "def plot_modular_periodicity(x: int, N: int, length: int = 40) -> None:\n", " seq = modular_sequence(x, N, length)\n", " r = order_mod(x, N)\n", " plt.figure(figsize=(10, 4))\n", " plt.plot(range(length), seq, marker=\"o\")\n", " if r is not None:\n", " for k in range(0, length, r):\n", " plt.axvline(k, linestyle=\"--\", alpha=0.4)\n", " plt.xlabel(\"exponente a\")\n", " plt.ylabel(f\"{x}^a mod {N}\")\n", " plt.title(f\"Periodicidad modular: x={x}, N={N}, orden r={r}\")\n", " plt.show()\n", "\n", "plot_modular_periodicity(2, 15, 24)\n", "plot_modular_periodicity(4, 81, 60)" ] }, { "cell_type": "markdown", "id": "9ea224de", "metadata": { "id": "9ea224de" }, "source": [ "## 7. De periodicidad a fase\n", "\n", "El operador\n", "\n", "$$\n", "U_x\\left|y\\right\\rangle=\\left|xy\\bmod N\\right\\rangle\n", "$$\n", "\n", "es una permutación reversible cuando $\\gcd(x,N)=1$. Su estructura cíclica implica que sus eigenvalores relevantes tienen forma\n", "\n", "$$\n", "e^{2\\pi i s/r}, \\qquad s=0,1,\\ldots,r-1.\n", "$$\n", "\n", "Por tanto, QPE aplicada a $U_x$ produce aproximaciones a fracciones $s/r$." ] }, { "cell_type": "code", "execution_count": null, "id": "c9ce097b", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 919 }, "id": "c9ce097b", "outputId": "778c6e29-43e8-4c4d-fe94-27c3f53acedc" }, "outputs": [], "source": [ "def plot_order_phases(r: int) -> None:\n", " \"\"\"Visualiza las fases s/r como puntos en el círculo unitario.\"\"\"\n", " s_vals = np.arange(r)\n", " angles = 2*np.pi*s_vals/r\n", " fig, ax = plt.subplots(figsize=(5, 5))\n", " t = np.linspace(0, 2*np.pi, 400)\n", " ax.plot(np.cos(t), np.sin(t))\n", " ax.scatter(np.cos(angles), np.sin(angles))\n", " for s, a in zip(s_vals, angles):\n", " ax.text(1.15*np.cos(a), 1.15*np.sin(a), f\"{s}/{r}\", ha=\"center\", va=\"center\", fontsize=8)\n", " ax.axhline(0, linewidth=1)\n", " ax.axvline(0, linewidth=1)\n", " ax.set_aspect(\"equal\")\n", " ax.set_title(f\"Fases e^(2π i s/{r}) asociadas a un ciclo de longitud {r}\")\n", " plt.show()\n", "\n", "plot_order_phases(4)\n", "plot_order_phases(7)" ] }, { "cell_type": "markdown", "id": "75ad8493", "metadata": { "id": "75ad8493" }, "source": [ "## 8. Picos esperados tras la inverse QFT\n", "\n", "Si el período es $r$ y el registro de conteo tiene tamaño $M=2^t$, las frecuencias probables se ubican cerca de\n", "\n", "$$\n", "k_s \\approx \\frac{sM}{r}, \\qquad s=0,1,\\ldots,r-1.\n", "$$\n", "\n", "La medición produce enteros cercanos a esos valores. Después se usa $k/M$ como aproximación de $s/r$." ] }, { "cell_type": "code", "execution_count": null, "id": "45e35fba", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "45e35fba", "outputId": "6fea2e85-37c7-4485-945a-f64d90f2ac7c" }, "outputs": [], "source": [ "def expected_peaks(M: int, r: int) -> List[int]:\n", " \"\"\"Enteros cercanos a sM/r.\"\"\"\n", " return sorted(set(int(round(s * M / r)) for s in range(r)))\n", "\n", "for r in [4, 6, 27]:\n", " print(f\"M=512, r={r}: picos aproximados =\", expected_peaks(512, r)[:20])" ] }, { "cell_type": "code", "execution_count": null, "id": "910ed502", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 619 }, "id": "910ed502", "outputId": "0c016d05-ce2b-4228-f1fd-9988042c4488" }, "outputs": [], "source": [ "def plot_expected_peaks(M: int, r: int) -> None:\n", " peaks = expected_peaks(M, r)\n", " y = np.zeros(M)\n", " for p in peaks:\n", " if 0 <= p < M:\n", " y[p] = 1\n", " plt.figure(figsize=(10, 2.8))\n", " plt.stem(range(M), y, basefmt=\" \")\n", " plt.xlabel(\"k\")\n", " plt.ylabel(\"pico ideal\")\n", " plt.title(f\"Ubicación aproximada de picos para M={M}, r={r}\")\n", " plt.xlim(0, M)\n", " plt.show()\n", "\n", "plot_expected_peaks(128, 4)\n", "plot_expected_peaks(128, 6)" ] }, { "cell_type": "markdown", "id": "e8158b3b", "metadata": { "id": "e8158b3b" }, "source": [ "## 9. Fracciones continuas\n", "\n", "QPE devuelve una fracción binaria $m/2^t$. Para extraer el período buscamos una fracción $s/r$ cercana. Las fracciones continuas construyen convergentes que son candidatos racionales especialmente buenos." ] }, { "cell_type": "code", "execution_count": null, "id": "457f3bbb", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "457f3bbb", "outputId": "35a6f444-f856-448d-ce5a-73cb6b2ccf4b" }, "outputs": [], "source": [ "def continued_fraction(x: float, max_terms: int = 12) -> List[int]:\n", " terms = []\n", " y = x\n", " for _ in range(max_terms):\n", " a = math.floor(y)\n", " terms.append(a)\n", " frac = y - a\n", " if abs(frac) < 1e-12:\n", " break\n", " y = 1 / frac\n", " return terms\n", "\n", "\n", "def convergents_from_cf(cf: List[int]) -> List[Fraction]:\n", " convs = []\n", " for i in range(1, len(cf) + 1):\n", " f = Fraction(cf[i-1], 1)\n", " for a in reversed(cf[:i-1]):\n", " f = a + Fraction(1, f)\n", " convs.append(f)\n", " return convs\n", "\n", "cf = [1, 4, 2, 1]\n", "print(\"fracción continua:\", cf)\n", "print(\"convergentes:\", convergents_from_cf(cf))" ] }, { "cell_type": "code", "execution_count": null, "id": "c5873449", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 797 }, "id": "c5873449", "outputId": "d819e790-95a6-4192-d5ec-14a7bf61f6f8" }, "outputs": [], "source": [ "def plot_convergents(x: float, max_terms: int = 10) -> None:\n", " cf = continued_fraction(x, max_terms)\n", " convs = convergents_from_cf(cf)\n", " errors = [abs(float(c) - x) for c in convs]\n", " labels = [f\"{c.numerator}/{c.denominator}\" for c in convs]\n", " plt.figure(figsize=(9, 4))\n", " plt.semilogy(range(1, len(errors)+1), errors, marker=\"o\")\n", " plt.xticks(range(1, len(errors)+1), labels, rotation=45)\n", " plt.ylabel(\"error absoluto\")\n", " plt.xlabel(\"convergente\")\n", " plt.title(f\"Convergentes de {x:.6f}\")\n", " plt.tight_layout()\n", " plt.show()\n", "\n", "plot_convergents(11/9, max_terms=6)\n", "plot_convergents(2/7, max_terms=8)" ] }, { "cell_type": "markdown", "id": "6cfe4fe5", "metadata": { "id": "6cfe4fe5" }, "source": [ "## 10. Reconstrucción de un candidato de orden\n", "\n", "A partir de una medición $m$, se forma $m/M$. Los denominadores de los convergentes son candidatos para $r$. Cada candidato debe verificarse mediante la congruencia\n", "\n", "$$\n", "x^r\\equiv1\\pmod N.\n", "$$\n", "\n", "El algoritmo no acepta un denominador únicamente porque aparece en una aproximación; lo prueba contra la aritmética modular." ] }, { "cell_type": "code", "execution_count": null, "id": "477a8fa7", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "477a8fa7", "outputId": "6942f8a0-8310-4e0b-91b6-114896186973" }, "outputs": [], "source": [ "def order_candidates_from_measurement(m: int, M: int, max_denominator: int = 100) -> List[Fraction]:\n", " x = m / M\n", " cf = continued_fraction(x, max_terms=20)\n", " convs = convergents_from_cf(cf)\n", " return [c for c in convs if c.denominator <= max_denominator]\n", "\n", "\n", "def verify_order_candidates(x: int, N: int, candidates: List[Fraction]) -> List[Tuple[Fraction, bool]]:\n", " results = []\n", " for frac in candidates:\n", " r = frac.denominator\n", " results.append((frac, pow(x, r, N) == 1))\n", " return results\n", "\n", "m = 85\n", "M = 512\n", "cands = order_candidates_from_measurement(m, M, max_denominator=30)\n", "print(\"candidatos desde 85/512:\", cands)\n", "print(\"verificación para x=2, N=15:\", verify_order_candidates(2, 15, cands))" ] }, { "cell_type": "markdown", "id": "6c8b8bc6", "metadata": { "id": "6c8b8bc6" }, "source": [ "## 11. Flujo completo de Shor\n", "\n", "Shor combina piezas clásicas y cuánticas. El subproblema cuántico es order finding; el resto del algoritmo interpreta el orden para obtener factores." ] }, { "cell_type": "code", "execution_count": null, "id": "4997e9a0", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "4997e9a0", "outputId": "fa5bd2bf-7885-48f5-b8d3-4aa9321baa4b" }, "outputs": [], "source": [ "def shor_classical_postprocess(N: int, x: int, r: int) -> Optional[Tuple[int, int]]:\n", " \"\"\"Intenta obtener factores no triviales de N a partir de x y r.\"\"\"\n", " if r is None or r % 2 == 1:\n", " return None\n", " y = pow(x, r // 2, N)\n", " if y == N - 1:\n", " return None\n", " p = gcd(y - 1, N)\n", " q = gcd(y + 1, N)\n", " if p in (1, N) or q in (1, N):\n", " return None\n", " return p, q\n", "\n", "for N, x in [(15, 2), (21, 2), (35, 3)]:\n", " r = order_mod(x, N)\n", " print(f\"N={N}, x={x}, r={r}, factores={shor_classical_postprocess(N, x, r)}\")" ] }, { "cell_type": "code", "execution_count": null, "id": "7b6e9a54", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 290 }, "id": "7b6e9a54", "outputId": "8bbc0f36-8d24-4763-cc49-e197babf276f" }, "outputs": [], "source": [ "def draw_shor_flow() -> None:\n", " \"\"\"Dibuja el flujo conceptual de Shor con separación explícita entre cajas, flechas y ecuaciones.\"\"\"\n", " from matplotlib.patches import FancyBboxPatch\n", "\n", " fig, ax = plt.subplots(figsize=(14, 6), constrained_layout=True)\n", " ax.set_xlim(0, 13)\n", " ax.set_ylim(0, 6)\n", " ax.axis(\"off\")\n", "\n", " box_style = dict(boxstyle=\"round,pad=0.08\", facecolor=\"white\", edgecolor=\"black\", linewidth=1.2)\n", " arrow_style = dict(arrowstyle=\"->\", linewidth=1.5, mutation_scale=16)\n", "\n", " nodes = [\n", " {\"key\": \"x\", \"xy\": (1.45, 4.35), \"w\": 2.15, \"h\": 1.05,\n", " \"label\": \"1. Elegir $x$\\n$1 None:\n", " props = {**arrow_style, \"connectionstyle\": f\"arc3,rad={rad}\"}\n", " ax.annotate(\n", " \"\",\n", " xy=edge_point(end_key, end_side),\n", " xytext=edge_point(start_key, start_side),\n", " arrowprops=props,\n", " )\n", "\n", " arrow(\"x\", \"right\", \"gcd0\", \"left\")\n", " arrow(\"gcd0\", \"right\", \"qpe\", \"left\")\n", " arrow(\"qpe\", \"right\", \"cf\", \"left\")\n", " arrow(\"cf\", \"bottom\", \"r\", \"top\")\n", " arrow(\"r\", \"left\", \"post\", \"right\")\n", " arrow(\"post\", \"left\", \"factors\", \"right\")\n", "\n", " ax.text(5.95, 4.72, \"$d=1$\", ha=\"center\", va=\"bottom\", fontsize=10)\n", " ax.text(4.35, 3.55, \"si $d>1$: factor inmediato\", ha=\"center\", va=\"center\", fontsize=10)\n", "\n", " ax.set_title(\"Flujo conceptual de Shor\", fontsize=15, pad=18)\n", " plt.show()\n", "\n", "\n", "draw_shor_flow()\n" ] }, { "cell_type": "markdown", "id": "5f0ef444", "metadata": { "id": "5f0ef444" }, "source": [ "## 12. Precisión frente a número de qubits\n", "\n", "Cada qubit adicional en el registro de conteo duplica la resolución de fase. Sin embargo, también incrementa el número de potencias controladas y la profundidad del circuito. La siguiente gráfica muestra la escala de cuantización $1/2^t$." ] }, { "cell_type": "code", "execution_count": null, "id": "fd70ce39", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 410 }, "id": "fd70ce39", "outputId": "1f700815-5922-4c22-aa7d-943faf2d1eac" }, "outputs": [], "source": [ "def plot_precision_vs_qubits(tmax: int = 14) -> None:\n", " ts = np.arange(1, tmax + 1)\n", " err = 1 / (2 ** ts)\n", " plt.figure(figsize=(8, 4))\n", " plt.semilogy(ts, err, marker=\"o\")\n", " plt.xlabel(\"qubits de conteo t\")\n", " plt.ylabel(\"tamaño de celda 1/2^t\")\n", " plt.title(\"Resolución binaria de fase\")\n", " plt.xticks(ts)\n", " plt.show()\n", "\n", "plot_precision_vs_qubits()" ] }, { "cell_type": "markdown", "id": "00905aac", "metadata": { "id": "00905aac" }, "source": [ "## 13. Distribuciones aproximadas para distintas precisiones\n", "\n", "La misma fase no exacta se representa mejor conforme aumenta $t$. La gráfica siguiente compara la distribución de QPE para $\\varphi=2/7$ con distintos tamaños de registro." ] }, { "cell_type": "code", "execution_count": null, "id": "18848fa7", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 887 }, "id": "18848fa7", "outputId": "b9f8bfd9-3fbc-45bb-8158-c21baf712f27" }, "outputs": [], "source": [ "def compare_qpe_precisions(phi: float, t_values: List[int]) -> None:\n", " for t in t_values:\n", " probs = qpe_distribution(phi, t)\n", " plt.figure(figsize=(8, 3))\n", " plt.bar(range(2**t), probs)\n", " plt.xlabel(\"m\")\n", " plt.ylabel(\"probabilidad\")\n", " plt.title(f\"QPE para φ={phi:.5f}, t={t}\")\n", " plt.tight_layout()\n", " plt.show()\n", "\n", "compare_qpe_precisions(2/7, [3, 4, 5])" ] }, { "cell_type": "markdown", "id": "74ca76ae", "metadata": { "id": "74ca76ae" }, "source": [ "## 14. Implementación opcional con Qiskit\n", "\n", "Las celdas siguientes intentan importar Qiskit. Si el paquete no está disponible y el entorno permite instalación, se intentará instalarlo. Si no es posible, el notebook continúa con las visualizaciones numéricas y deja la sección de circuito como esquema conceptual." ] }, { "cell_type": "markdown", "id": "d4cd4b5c", "metadata": {}, "source": [ "### Nota de compatibilidad para diagramas de circuitos\n", "\n", "El dibujador Matplotlib de Qiskit requiere la dependencia opcional `pylatexenc`. Para que la opción **Ejecutar todas las celdas** sea estable en JupyterLab, Anaconda y Google Colab, el notebook intenta instalar esa dependencia cuando sea necesario. Si el entorno no permite instalar paquetes, el circuito se muestra automáticamente en formato de texto y la ejecución continúa sin detenerse." ] }, { "cell_type": "code", "execution_count": null, "id": "6ea77700", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "6ea77700", "outputId": "49340dd2-47a1-4bc5-baa5-7a4f59045228" }, "outputs": [], "source": [ "import importlib\n", "import subprocess\n", "import sys\n", "from IPython.display import display\n", "\n", "\n", "def try_import_or_install(import_name: str, pip_name: Optional[str] = None):\n", " \"\"\"Intenta importar un paquete; si falla, intenta instalarlo. Devuelve el módulo o None.\n", "\n", " La función está pensada para JupyterLab, Anaconda y Google Colab. Si el entorno no tiene acceso a\n", " instalación por pip, el notebook continúa ejecutándose y usa rutas numéricas o representaciones de texto.\n", " \"\"\"\n", " try:\n", " return importlib.import_module(import_name)\n", " except Exception:\n", " pass\n", "\n", " try:\n", " subprocess.check_call([sys.executable, \"-m\", \"pip\", \"install\", pip_name or import_name, \"-q\"])\n", " return importlib.import_module(import_name)\n", " except Exception as exc:\n", " print(f\"No se pudo importar o instalar {import_name}: {exc}\")\n", " return None\n", "\n", "\n", "def display_qiskit_circuit(qc):\n", " \"\"\"Muestra un circuito de Qiskit sin detener la ejecución si falta pylatexenc.\n", "\n", " Qiskit usa `pylatexenc` para `qc.draw(\"mpl\")`. Si esa dependencia opcional no está instalada,\n", " se intenta instalar. Si aun así no está disponible, se muestra el circuito en modo texto para que\n", " `Ejecutar todas las celdas` no falle.\n", " \"\"\"\n", " try:\n", " display(qc.draw(output=\"mpl\"))\n", " return\n", " except Exception as exc:\n", " message = str(exc)\n", " if \"pylatexenc\" in message or \"MatplotlibDrawer\" in message:\n", " pylatexenc = try_import_or_install(\"pylatexenc\")\n", " if pylatexenc is not None:\n", " try:\n", " display(qc.draw(output=\"mpl\"))\n", " return\n", " except Exception as exc_retry:\n", " print(f\"No se pudo usar el dibujador Matplotlib después de instalar pylatexenc: {exc_retry}\")\n", " else:\n", " print(f\"No se pudo usar el dibujador Matplotlib de Qiskit: {exc}\")\n", "\n", " print(\"Se muestra el circuito en formato de texto para mantener la ejecución completa del notebook.\")\n", " print(qc.draw(output=\"text\"))\n", "\n", "\n", "qiskit = try_import_or_install(\"qiskit\")\n", "qiskit_aer = try_import_or_install(\"qiskit_aer\", \"qiskit-aer\")\n", "HAS_QISKIT = qiskit is not None\n", "HAS_QISKIT_AER = qiskit_aer is not None\n", "print(\"Qiskit disponible:\", HAS_QISKIT)\n", "print(\"Qiskit Aer disponible:\", HAS_QISKIT_AER)\n" ] }, { "cell_type": "code", "execution_count": null, "id": "b43e75de", "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 529 }, "id": "b43e75de", "outputId": "88750098-f6be-40cb-8bef-d705683a1104" }, "outputs": [], "source": [ "if HAS_QISKIT:\n", " from qiskit import QuantumCircuit, transpile\n", " if HAS_QISKIT_AER:\n", " from qiskit_aer import AerSimulator\n", "\n", " def inverse_qft_qiskit(qc: QuantumCircuit, qubits: List[int]) -> None:\n", " \"\"\"Inverse QFT simple sobre una lista de qubits.\"\"\"\n", " n = len(qubits)\n", " for i in range(n // 2):\n", " qc.swap(qubits[i], qubits[n - 1 - i])\n", " for j in range(n):\n", " for m in range(j):\n", " qc.cp(-np.pi / (2 ** (j - m)), qubits[m], qubits[j])\n", " qc.h(qubits[j])\n", "\n", " def qpe_phase_gate_circuit(phi: float, t: int) -> QuantumCircuit:\n", " \"\"\"QPE para una compuerta U que añade fase e^(2πiφ) al estado |1> del trabajo.\"\"\"\n", " qc = QuantumCircuit(t + 1, t)\n", " work = t\n", " qc.x(work) # prepara |1>, eigenestado de una compuerta de fase\n", " qc.h(range(t))\n", " for j in range(t):\n", " angle = 2 * np.pi * phi * (2 ** j)\n", " qc.cp(angle, j, work)\n", " inverse_qft_qiskit(qc, list(range(t)))\n", " qc.measure(range(t), range(t))\n", " return qc\n", "\n", " qc = qpe_phase_gate_circuit(5/8, 3)\n", " display_qiskit_circuit(qc)\n", "else:\n", " print(\"Se omite el circuito Qiskit porque el paquete no está disponible en este entorno.\")\n" ] }, { "cell_type": "code", "execution_count": null, "id": "e6766335", "metadata": { "id": "e6766335" }, "outputs": [], "source": [ "if HAS_QISKIT and HAS_QISKIT_AER:\n", " sim = AerSimulator()\n", " qc = qpe_phase_gate_circuit(5/8, 3)\n", " tqc = transpile(qc, sim)\n", " result = sim.run(tqc, shots=2048).result()\n", " counts = result.get_counts()\n", " print(counts)\n", "\n", " plt.figure(figsize=(6, 3))\n", " plt.bar(counts.keys(), counts.values())\n", " plt.xlabel(\"resultado\")\n", " plt.ylabel(\"conteos\")\n", " plt.title(\"QPE exacta para φ=5/8\")\n", " plt.show()\n", "elif HAS_QISKIT and not HAS_QISKIT_AER:\n", " print(\"Qiskit está disponible, pero Qiskit Aer no. Se muestra la distribución teórica equivalente.\")\n", " plot_qpe_distribution(5/8, 3)\n", "else:\n", " print(\"Distribución teórica equivalente:\")\n", " plot_qpe_distribution(5/8, 3)\n" ] }, { "cell_type": "markdown", "id": "736a99b7", "metadata": { "id": "736a99b7" }, "source": [ "## 15. Implementación opcional con Cirq\n", "\n", "La sección siguiente construye un esquema de QPE en Cirq cuando el paquete está disponible. Si el entorno no permite instalarlo, las celdas informan la omisión sin detener el notebook." ] }, { "cell_type": "code", "execution_count": null, "id": "21cb0de8", "metadata": { "id": "21cb0de8" }, "outputs": [], "source": [ "cirq = try_import_or_install(\"cirq\")\n", "HAS_CIRQ = cirq is not None\n", "print(\"Cirq disponible:\", HAS_CIRQ)" ] }, { "cell_type": "code", "execution_count": null, "id": "6054b8f8", "metadata": { "id": "6054b8f8" }, "outputs": [], "source": [ "if HAS_CIRQ:\n", " def qpe_cirq_phase_gate(phi: float, t: int):\n", " qubits = cirq.LineQubit.range(t + 1)\n", " work = qubits[-1]\n", " circuit = cirq.Circuit()\n", " circuit.append(cirq.X(work))\n", " circuit.append(cirq.H.on_each(*qubits[:t]))\n", " for j in range(t):\n", " # CZPowGate con exponent e produce fase exp(i*pi*e) sobre |11>.\n", " exponent = 2 * phi * (2 ** j)\n", " circuit.append(cirq.CZPowGate(exponent=exponent).on(qubits[j], work))\n", " circuit.append(cirq.measure(*qubits[:t], key=\"m\"))\n", " return circuit\n", "\n", " c = qpe_cirq_phase_gate(5/8, 3)\n", " print(c)\n", "else:\n", " print(\"Se omite el circuito Cirq porque el paquete no está disponible en este entorno.\")" ] }, { "cell_type": "markdown", "id": "7ad024c1", "metadata": { "id": "7ad024c1" }, "source": [ "## 16. Ejemplo paso a paso: de una medición a un factor\n", "\n", "Supongamos que la subrutina cuántica de order finding para $N=15$ y $x=2$ proporciona evidencia de que el orden es $r=4$. El paso final es clásico:\n", "\n", "$$\n", "2^{r/2}=2^2=4,\\qquad\n", "\\gcd(4-1,15)=3,\\qquad\n", "\\gcd(4+1,15)=5.\n", "$$\n", "\n", "La factorización aparece porque $2^4\\equiv1\\pmod{15}$ implica que $2^4-1$ es múltiplo de $15$, y la factorización algebraica de $2^4-1$ contiene los divisores no triviales." ] }, { "cell_type": "code", "execution_count": null, "id": "f1871e46", "metadata": { "id": "f1871e46" }, "outputs": [], "source": [ "def explain_factor_step(N: int, x: int) -> None:\n", " r = order_mod(x, N)\n", " print(f\"N={N}, x={x}, orden r={r}\")\n", " if r is None:\n", " print(\"x no es coprimo con N; gcd ya da un factor.\")\n", " print(\"gcd(x,N)=\", gcd(x, N))\n", " return\n", " factors = shor_classical_postprocess(N, x, r)\n", " print(\"factores desde r:\", factors)\n", "\n", "explain_factor_step(15, 2)\n", "explain_factor_step(21, 2)" ] }, { "cell_type": "markdown", "id": "2d4bb74f", "metadata": { "id": "2d4bb74f" }, "source": [ "## 17. Ejercicios guiados\n", "\n", "**Ejercicio 1.** Un registro de conteo de cuatro qubits produce la cadena $0110_2$. Interpreta la estimación de fase. \n", "**Desarrollo.** La cadena representa $6$ y la escala es $16$, por lo que $\\widetilde{\\varphi}=6/16=3/8$.\n", "\n", "**Ejercicio 2.** Para $x=4$ y $N=81$, verifica por código que el orden es $27$. \n", "**Desarrollo.** La función `order_mod(4, 81)` recorre potencias sucesivas hasta encontrar el primer regreso a $1$.\n", "\n", "**Ejercicio 3.** Si el candidato de orden es impar, explica por qué no se puede extraer factor mediante $x^{r/2}\\pm1$. \n", "**Desarrollo.** El exponente $r/2$ no es entero, por lo que la identidad usada en el paso de factorización no se aplica." ] }, { "cell_type": "code", "execution_count": null, "id": "3ed64e0e", "metadata": { "id": "3ed64e0e" }, "outputs": [], "source": [ "print(\"Ejercicio 1: 0110 con 4 qubits ->\", Fraction(int(\"0110\", 2), 2**4))\n", "print(\"Ejercicio 2: orden de 4 módulo 81 ->\", order_mod(4, 81))\n", "print(\"Ejercicio 3: r=27 es impar ->\", \"repetir con otra elección\" if 27 % 2 else \"puede continuar\")" ] }, { "cell_type": "markdown", "id": "5c187588", "metadata": { "id": "5c187588" }, "source": [ "## 18. Ejercicios propuestos\n", "\n", "1. Construye la tabla de $2^a\\bmod 21$ para $a=0,1,\\ldots,12$ y localiza el período.\n", "2. Grafica la distribución ideal de QPE para $\\varphi=3/10$ usando $t=4,5,6$.\n", "3. Usa fracciones continuas para aproximar $85/512$ y lista los denominadores candidatos menores que $20$.\n", "4. Para $N=35$ y $x=3$, calcula el orden y verifica si permite obtener factores.\n", "5. Explica en un párrafo por qué la salida de QPE en order finding debe interpretarse como aproximación a $s/r$ y no como el orden directamente." ] }, { "cell_type": "markdown", "id": "ad85cba0", "metadata": { "id": "ad85cba0" }, "source": [ "## 19. Resumen final\n", "\n", "Quantum Phase Estimation extrae una fase asociada a un eigenvalor unitario. Order finding convierte la periodicidad modular en un problema espectral, de modo que las fases medidas tienen forma $s/r$. Las fracciones continuas reconstruyen candidatos racionales a partir de la estimación binaria. Shor combina estas piezas para convertir un orden útil en factores no triviales mediante máximos comunes divisores.\n", "\n", "El mensaje central es que la factorización se vuelve accesible al transformar un problema aritmético en un problema de interferencia y luego regresar al lenguaje de enteros mediante post-procesamiento clásico." ] } ], "metadata": { "colab": { "provenance": [] }, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }