{ "cells": [ { "cell_type": "markdown", "id": "8a972161", "metadata": {}, "source": [ "# Max-Cut y sumadores reversibles\n", "\n", "Este notebook desarrolla de forma autoexplicativa el módulo **Max-Cut and Adders**. El objetivo es entender cómo un problema de optimización en grafos se transforma en un predicado reversible que puede ser usado por búsqueda de Grover.\n", "\n", "La notación de Dirac se escribe sin macros personalizadas para que se visualice correctamente en JupyterLab, Anaconda y Google Colab. Por ejemplo:\n", "\n", "$$\n", "\\left|x\\right\\rangle,\n", "\\qquad\n", "\\left\\langle x\\right|,\n", "\\qquad\n", "\\left|s\\right\\rangle\\left\\langle s\\right|.\n", "$$\n", "\n", "El notebook contiene teoría, ejemplos, código ejecutable, ejercicios guiados y ejercicios propuestos. Las celdas de instalación intentan instalar dependencias solo cuando no están disponibles." ] }, { "cell_type": "markdown", "id": "50ce2c8f", "metadata": {}, "source": [ "## 1. Objetivos de aprendizaje\n", "\n", "Al finalizar este notebook, se espera que puedas:\n", "\n", "1. Formular Max-Cut como un problema de optimización sobre coloraciones binarias.\n", "2. Explicar por qué una arista cortada se detecta mediante XOR.\n", "3. Relacionar vértices con qubits y coloraciones con estados base.\n", "4. Construir indicadores de arista usando CNOT.\n", "5. Explicar por qué la aritmética reversible es necesaria en circuitos cuánticos.\n", "6. Implementar conceptualmente half adders, full adders y acumuladores por acarreo.\n", "7. Determinar cuántos bits se requieren para almacenar una suma de indicadores.\n", "8. Construir comparadores binarios mediante controles positivos y negativos.\n", "9. Explicar cómo un conteo de aristas se convierte en un criterio de marcado.\n", "10. Integrar Max-Cut, adders y Grover en una arquitectura extremo a extremo.\n", "11. Implementar ejemplos en Cirq y Qiskit.\n", "12. Diagnosticar errores de interpretación: orden de bits, auxiliares sin limpiar, conocer soluciones de antemano y confundir verificación con búsqueda.\n", "7. Visualizar grafos, particiones y distribuciones de valores de corte para interpretar el problema más allá de la fórmula.\n", "8. Interpretar una gráfica de probabilidad de éxito de Grover y relacionarla con la elección del número de iteraciones." ] }, { "cell_type": "markdown", "id": "27c11ed3", "metadata": {}, "source": [ "## 2. Problema Max-Cut\n", "\n", "Sea $G=(V,E)$ un grafo no dirigido. Un corte divide los vértices en dos conjuntos disjuntos $S$ y $\\bar S$. Una arista $\\{u,v\\}$ cruza el corte si sus extremos quedan en lados distintos.\n", "\n", "El tamaño del corte es\n", "\n", "$$\n", "\\operatorname{Cut}(S)=\\left|\\{\\{u,v\\}\\in E: u\\in S,\\ v\\in \\bar S\\}\\right|.\n", "$$\n", "\n", "Max-Cut pide encontrar una partición que maximice esa cantidad. El problema es importante porque cada arista aporta una condición local sencilla, pero maximizar simultáneamente muchas condiciones locales puede ser combinatoriamente difícil." ] }, { "cell_type": "markdown", "id": "d77ff1cb", "metadata": {}, "source": [ "## 3. Codificación binaria de coloraciones\n", "\n", "Usaremos un bit por vértice:\n", "\n", "$$\n", "x_i=0 \\quad \\text{un color},\n", "\\qquad\n", "x_i=1 \\quad \\text{el otro color}.\n", "$$\n", "\n", "Una coloración completa se escribe como una cadena\n", "\n", "$$\n", "x=x_0x_1\\cdots x_{n-1}\\in\\{0,1\\}^n.\n", "$$\n", "\n", "En un circuito cuántico, esa cadena etiqueta un estado base:\n", "\n", "$$\n", "\\left|x\\right\\rangle\n", "=\n", "\\left|x_0x_1\\cdots x_{n-1}\\right\\rangle.\n", "$$\n", "\n", "El punto conceptual es que Grover buscará sobre coloraciones completas, no sobre vértices individuales." ] }, { "cell_type": "code", "execution_count": null, "id": "27a3606e", "metadata": {}, "outputs": [], "source": [ "from itertools import product\n", "from math import ceil, log2, pi, sqrt\n", "from typing import Iterable, List, Sequence, Tuple, Dict, Optional\n", "\n", "BitString = str\n", "Edge = Tuple[int, int]\n", "\n", "def all_bitstrings(n: int) -> List[BitString]:\n", " \"\"\"Devuelve todas las cadenas binarias de longitud n en orden lexicográfico.\"\"\"\n", " return [''.join(bits) for bits in product('01', repeat=n)]\n", "\n", "\n", "def cut_value(bitstring: BitString, edges: Sequence[Edge]) -> int:\n", " \"\"\"Calcula el tamaño del corte asociado a una coloración binaria.\n", "\n", " Convención: bitstring[i] es el color del vértice i.\n", " Una arista contribuye si sus extremos tienen bits distintos.\n", " \"\"\"\n", " return sum(bitstring[u] != bitstring[v] for u, v in edges)\n", "\n", "\n", "def max_cuts(n: int, edges: Sequence[Edge]) -> Tuple[int, List[BitString]]:\n", " \"\"\"Calcula por fuerza bruta el valor máximo de corte y las coloraciones que lo alcanzan.\n", "\n", " Esta rutina es clásica y se usa aquí solo para verificar ejemplos pequeños.\n", " En un algoritmo cuántico genuino, el oráculo debe reconocer soluciones sin recibir la lista de óptimos.\n", " \"\"\"\n", " values = {x: cut_value(x, edges) for x in all_bitstrings(n)}\n", " best = max(values.values())\n", " marked = [x for x, v in values.items() if v == best]\n", " return best, marked" ] }, { "cell_type": "code", "execution_count": null, "id": "55fcfaf0", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import networkx as nx\n", "import numpy as np\n", "\n", "\n", "def graph_from_edges(n: int, edges: Sequence[Edge]) -> nx.Graph:\n", " \"\"\"Construye un grafo de NetworkX a partir del número de vértices y la lista de aristas.\"\"\"\n", " G = nx.Graph()\n", " G.add_nodes_from(range(n))\n", " G.add_edges_from(edges)\n", " return G\n", "\n", "\n", "def adjacency_matrix(n: int, edges: Sequence[Edge]) -> np.ndarray:\n", " \"\"\"Matriz de adyacencia simétrica del grafo.\"\"\"\n", " A = np.zeros((n, n), dtype=int)\n", " for u, v in edges:\n", " A[u, v] = 1\n", " A[v, u] = 1\n", " return A\n", "\n", "\n", "def cut_edges(bitstring: BitString, edges: Sequence[Edge]) -> List[Edge]:\n", " \"\"\"Lista las aristas que sí cruzan el corte.\"\"\"\n", " return [(u, v) for (u, v) in edges if bitstring[u] != bitstring[v]]\n", "\n", "\n", "def uncut_edges(bitstring: BitString, edges: Sequence[Edge]) -> List[Edge]:\n", " \"\"\"Lista las aristas cuyos extremos quedan en la misma parte del corte.\"\"\"\n", " return [(u, v) for (u, v) in edges if bitstring[u] == bitstring[v]]\n", "\n", "\n", "def draw_graph_structure(n: int, edges: Sequence[Edge], pos: Optional[Dict[int, Tuple[float, float]]] = None, title: str = \"Estructura del grafo\"):\n", " \"\"\"Dibuja el grafo sin una coloración específica.\"\"\"\n", " G = graph_from_edges(n, edges)\n", " if pos is None:\n", " pos = nx.spring_layout(G, seed=7)\n", " plt.figure(figsize=(7, 4.5))\n", " nx.draw_networkx_nodes(G, pos, node_size=900)\n", " nx.draw_networkx_edges(G, pos, width=2)\n", " nx.draw_networkx_labels(G, pos, font_size=12, font_weight=\"bold\")\n", " plt.title(title)\n", " plt.axis(\"off\")\n", " plt.show()\n", " return pos\n", "\n", "\n", "def draw_graph_partition(bitstring: BitString, edges: Sequence[Edge], pos: Optional[Dict[int, Tuple[float, float]]] = None, title: Optional[str] = None, show_edge_labels: bool = True):\n", " \"\"\"Dibuja una coloración binaria sobre el grafo y resalta las aristas cortadas.\"\"\"\n", " n = len(bitstring)\n", " G = graph_from_edges(n, edges)\n", " if pos is None:\n", " pos = nx.spring_layout(G, seed=7)\n", "\n", " node_colors = [\"tab:blue\" if bit == \"0\" else \"tab:orange\" for bit in bitstring]\n", " crossing = cut_edges(bitstring, edges)\n", " internal = uncut_edges(bitstring, edges)\n", "\n", " plt.figure(figsize=(7, 4.5))\n", " nx.draw_networkx_nodes(G, pos, node_color=node_colors, node_size=950)\n", " nx.draw_networkx_labels(G, pos, font_size=12, font_weight=\"bold\")\n", " if internal:\n", " nx.draw_networkx_edges(G, pos, edgelist=internal, width=2, edge_color=\"0.55\")\n", " if crossing:\n", " nx.draw_networkx_edges(G, pos, edgelist=crossing, width=3, edge_color=\"crimson\")\n", "\n", " if show_edge_labels:\n", " edge_labels = {(u, v): int(bitstring[u] != bitstring[v]) for (u, v) in edges}\n", " nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=10)\n", "\n", " if title is None:\n", " title = f\"Coloración {bitstring} con C(x)={cut_value(bitstring, edges)}\"\n", " plt.title(title)\n", " plt.axis(\"off\")\n", " plt.show()\n", " return crossing\n", "\n", "\n", "def plot_cut_values(n: int, edges: Sequence[Edge]) -> None:\n", " \"\"\"Grafica el valor del corte para todas las coloraciones binarias.\"\"\"\n", " states = all_bitstrings(n)\n", " values = [cut_value(x, edges) for x in states]\n", " plt.figure(figsize=(10, 4.5))\n", " plt.bar(range(len(states)), values)\n", " plt.xticks(range(len(states)), states, rotation=90, fontsize=8)\n", " plt.xlabel(\"Coloración binaria\")\n", " plt.ylabel(\"Tamaño del corte\")\n", " plt.title(\"Valor de C(x) para todas las coloraciones\")\n", " plt.grid(axis=\"y\", alpha=0.3)\n", " plt.tight_layout()\n", " plt.show()\n", "\n", "\n", "def plot_cut_histogram(n: int, edges: Sequence[Edge]) -> None:\n", " \"\"\"Muestra la distribución de tamaños de corte.\"\"\"\n", " values = [cut_value(x, edges) for x in all_bitstrings(n)]\n", " bins = np.arange(min(values) - 0.5, max(values) + 1.5, 1)\n", " plt.figure(figsize=(7, 4.5))\n", " plt.hist(values, bins=bins, rwidth=0.85)\n", " plt.xticks(range(min(values), max(values) + 1))\n", " plt.xlabel(\"Tamaño del corte\")\n", " plt.ylabel(\"Número de coloraciones\")\n", " plt.title(\"Distribución de tamaños de corte\")\n", " plt.grid(axis=\"y\", alpha=0.3)\n", " plt.show()\n" ] }, { "cell_type": "markdown", "id": "fdfe45cf", "metadata": {}, "source": [ "## 4. Ejemplo desarrollado: grafo bipartito $K_{3,2}$\n", "\n", "Consideremos el grafo con vértices $0,1,2$ en una parte y $3,4$ en la otra. Todas las aristas conectan una parte con la otra:\n", "\n", "$$\n", "E=\\{(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)\\}.\n", "$$\n", "\n", "La coloración $00011$ pone los tres primeros vértices de un lado y los dos últimos del otro. Todas las aristas cruzan, por lo que el tamaño máximo del corte es $6$." ] }, { "cell_type": "code", "execution_count": null, "id": "c29fd98d", "metadata": {}, "outputs": [], "source": [ "# Grafo K_{3,2}: vertices 0,1,2 conectados con vertices 3,4.\n", "edges_k32: List[Edge] = [(0, 3), (0, 4), (1, 3), (1, 4), (2, 3), (2, 4)]\n", "n_vertices = 5\n", "\n", "best_value, optimal_colorings = max_cuts(n_vertices, edges_k32)\n", "print(\"Valor máximo del corte:\", best_value)\n", "print(\"Coloraciones óptimas:\", optimal_colorings)\n", "\n", "# Verificación de una coloración no óptima usada en la presentación.\n", "x = \"00111\"\n", "print(f\"C({x}) =\", cut_value(x, edges_k32))" ] }, { "cell_type": "markdown", "id": "3cb2f278", "metadata": {}, "source": [ "### Interpretación del ejemplo\n", "\n", "El cálculo clásico anterior no pretende sustituir al algoritmo cuántico. Sirve para verificar una instancia pequeña y para fijar la intuición. La coloración $00011$ y su complemento $11100$ representan el mismo corte si se intercambian los nombres de los colores. En el espacio de estados, sin embargo, son dos estados base distintos:\n", "\n", "$$\n", "\\left|00011\\right\\rangle,\n", "\\qquad\n", "\\left|11100\\right\\rangle.\n", "$$\n", "\n", "Si ambos estados se marcan, entonces $k=2$ soluciones son amplificadas por Grover." ] }, { "cell_type": "markdown", "id": "20791cef", "metadata": {}, "source": [ "### Visualización del grafo $K_{3,2}$\n", "\n", "Como este módulo trata un problema de optimización en grafos, conviene acompañar la formulación algebraica con representaciones geométricas. En las celdas siguientes usamos `networkx` y `matplotlib` para visualizar tanto la estructura del grafo como una coloración óptima. Las aristas resaltadas en rojo son precisamente las que cruzan el corte, es decir, aquellas para las que el indicador XOR vale $1$." ] }, { "cell_type": "code", "execution_count": null, "id": "c56535eb", "metadata": {}, "outputs": [], "source": [ "# Posiciones fijas para que el bipartito K_{3,2} se vea con claridad.\n", "pos_k32 = {0: (0.0, 2.0), 1: (0.0, 1.0), 2: (0.0, 0.0), 3: (2.0, 1.5), 4: (2.0, 0.5)}\n", "draw_graph_structure(n_vertices, edges_k32, pos=pos_k32, title=\"Estructura del grafo bipartito K_{3,2}\")" ] }, { "cell_type": "markdown", "id": "ad9b85bd", "metadata": {}, "source": [ "### Un corte máximo visto sobre el grafo\n", "\n", "La cadena $00011$ coloca a los vértices $0,1,2$ en una parte y a los vértices $3,4$ en la otra. Como $K_{3,2}$ es bipartito, toda arista conecta un vértice de una parte con uno de la otra, de modo que las seis aristas quedan cortadas. La figura permite reconocer visualmente por qué $C(00011)=6$." ] }, { "cell_type": "code", "execution_count": null, "id": "0af77040", "metadata": {}, "outputs": [], "source": [ "draw_graph_partition(\"00011\", edges_k32, pos=pos_k32, title=\"Corte óptimo para K_{3,2}: coloración 00011\")" ] }, { "cell_type": "markdown", "id": "ad7b8740", "metadata": {}, "source": [ "### Matriz de adyacencia\n", "\n", "La matriz de adyacencia ofrece otra representación del mismo grafo. En Max-Cut resulta útil porque resume la conectividad y, en formulaciones más avanzadas, permite escribir la función objetivo como una suma sobre pares adyacentes. Para grafos pequeños, verla junto con el dibujo ayuda a conectar la descripción combinatoria con la estructura matricial." ] }, { "cell_type": "code", "execution_count": null, "id": "07b04ff1", "metadata": {}, "outputs": [], "source": [ "A_k32 = adjacency_matrix(n_vertices, edges_k32)\n", "plt.figure(figsize=(5, 4.5))\n", "plt.imshow(A_k32, interpolation=\"nearest\")\n", "plt.xticks(range(n_vertices))\n", "plt.yticks(range(n_vertices))\n", "plt.xlabel(\"Vértice\")\n", "plt.ylabel(\"Vértice\")\n", "plt.title(\"Matriz de adyacencia de K_{3,2}\")\n", "for i in range(n_vertices):\n", " for j in range(n_vertices):\n", " plt.text(j, i, str(A_k32[i, j]), ha=\"center\", va=\"center\")\n", "plt.colorbar()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "6398eb5b", "metadata": {}, "source": [ "### Distribución de tamaños de corte\n", "\n", "No todas las coloraciones producen el mismo valor. En esta instancia, la distribución completa de $C(x)$ muestra cuántas soluciones son pobres, intermedias u óptimas. Este tipo de visualización ayuda a entender qué tan selectivo debe ser el oráculo: si muy pocos estados son óptimos, Grover tiene una ventaja más visible al concentrar amplitud sobre ellos." ] }, { "cell_type": "code", "execution_count": null, "id": "e97adeb7", "metadata": {}, "outputs": [], "source": [ "plot_cut_values(n_vertices, edges_k32)\n", "plot_cut_histogram(n_vertices, edges_k32)" ] }, { "cell_type": "markdown", "id": "8eca6d02", "metadata": {}, "source": [ "### Ejemplo adicional: un ciclo impar\n", "\n", "El ciclo $C_5$ ilustra una situación conceptualmente distinta. Si alternamos los colores tanto como sea posible, cuatro aristas quedan cortadas, pero una necesariamente no. La razón es combinatoria: en un ciclo impar no se puede mantener una alternancia perfecta al regresar al vértice inicial. Esta figura sirve para comparar un caso bipartito, donde sí puede cortarse toda arista, con un caso no bipartito, donde aparece una obstrucción estructural." ] }, { "cell_type": "code", "execution_count": null, "id": "2a6dd5b6", "metadata": {}, "outputs": [], "source": [ "edges_c5: List[Edge] = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]\n", "pos_c5 = nx.circular_layout(graph_from_edges(5, edges_c5))\n", "draw_graph_partition(\"01010\", edges_c5, pos=pos_c5, title=\"Ciclo C5 con coloración 01010\")\n", "print(\"Valor del corte en C5 para 01010:\", cut_value(\"01010\", edges_c5))\n", "print(\"Valor máximo del corte en C5:\", max_cuts(5, edges_c5)[0])" ] }, { "cell_type": "markdown", "id": "9e8b8b24", "metadata": {}, "source": [ "## 5. Indicadores de arista y XOR\n", "\n", "Para una arista $\\{i,j\\}$, definimos el indicador\n", "\n", "$$\n", "e_{ij}=x_i\\oplus x_j.\n", "$$\n", "\n", "Si $e_{ij}=1$, los extremos tienen colores distintos y la arista cruza el corte. Si $e_{ij}=0$, no cruza.\n", "\n", "El tamaño del corte se escribe como\n", "\n", "$$\n", "C(x)=\\sum_{\\{i,j\\}\\in E} e_{ij}\n", "=\n", "\\sum_{\\{i,j\\}\\in E}(x_i\\oplus x_j).\n", "$$\n", "\n", "Esta fórmula es la razón por la que CNOT y sumadores aparecen en el módulo: CNOT calcula XOR y los adders suman los indicadores." ] }, { "cell_type": "code", "execution_count": null, "id": "279cf2b9", "metadata": {}, "outputs": [], "source": [ "def edge_indicator(bitstring: BitString, edge: Edge) -> int:\n", " \"\"\"Devuelve 1 si una arista cruza el corte y 0 si no.\"\"\"\n", " u, v = edge\n", " return int(bitstring[u] != bitstring[v])\n", "\n", "x = \"00111\"\n", "print(\"Coloración:\", x)\n", "for edge in edges_k32:\n", " print(edge, \"->\", edge_indicator(x, edge))\n", "print(\"Suma de indicadores:\", sum(edge_indicator(x, e) for e in edges_k32))" ] }, { "cell_type": "markdown", "id": "1d540352", "metadata": {}, "source": [ "## 6. Computación reversible\n", "\n", "Los circuitos cuánticos cerrados son unitarios, y una operación unitaria es reversible. Por eso una función clásica que parece borrar información debe implementarse como una transformación extendida que conserve entradas y use registros auxiliares.\n", "\n", "Para una función booleana $f$, la forma reversible típica es\n", "\n", "$$\n", "\\left|x\\right\\rangle\\left|y\\right\\rangle\n", "\\longmapsto\n", "\\left|x\\right\\rangle\\left|y\\oplus f(x)\\right\\rangle.\n", "$$\n", "\n", "En Max-Cut, los auxiliares almacenan indicadores de arista, bits de suma, acarreos y marcas. Después de aplicar la fase de marcado, esos auxiliares deben limpiarse para no contaminar la difusión de Grover." ] }, { "cell_type": "markdown", "id": "a33c4862", "metadata": {}, "source": [ "## 7. CNOT como operador XOR\n", "\n", "La compuerta CNOT implementa\n", "\n", "$$\n", "\\operatorname{CNOT}\\left|a\\right\\rangle\\left|b\\right\\rangle\n", "=\n", "\\left|a\\right\\rangle\\left|b\\oplus a\\right\\rangle.\n", "$$\n", "\n", "Si el objetivo inicia en $0$, una CNOT copia reversiblemente el valor del control hacia el objetivo. Si aplicamos dos CNOTs con controles $x_i$ y $x_j$ sobre el mismo auxiliar $t$, obtenemos\n", "\n", "$$\n", "t=0 \\longmapsto x_i \\longmapsto x_i\\oplus x_j.\n", "$$" ] }, { "cell_type": "markdown", "id": "e1af1538", "metadata": {}, "source": [ "## 8. Ejercicio guiado: detectar colores distintos\n", "\n", "**Enunciado.** Los qubits $1$ y $2$ contienen los colores de dos vértices. El qubit $0$ inicia en $0$. Se desea que el qubit $0$ almacene $1$ si los colores son distintos y $0$ si son iguales.\n", "\n", "**Desarrollo.** La condición deseada es $x_1\\oplus x_2$. Primero se aplica CNOT desde $q_1$ hacia $q_0$; después se aplica CNOT desde $q_2$ hacia $q_0$:\n", "\n", "$$\n", "q_0:0\\longmapsto x_1\\longmapsto x_1\\oplus x_2.\n", "$$\n", "\n", "**Interpretación.** El circuito no resuelve Max-Cut completo. Resuelve una subpregunta local: si una arista está cortada." ] }, { "cell_type": "markdown", "id": "e90f0d67", "metadata": {}, "source": [ "## 9. Half adder\n", "\n", "El half adder suma dos bits $a$ y $b$ y produce:\n", "\n", "$$\n", "s=a\\oplus b,\n", "\\qquad\n", "c=ab.\n", "$$\n", "\n", "El bit $s$ es la suma módulo $2$ y $c$ es el acarreo. En circuitos reversibles, se usan auxiliares inicializados en cero para almacenar $s$ y $c$ sin modificar $a$ y $b$." ] }, { "cell_type": "code", "execution_count": null, "id": "7a47ee89", "metadata": {}, "outputs": [], "source": [ "def half_adder_classical(a: int, b: int) -> Tuple[int, int]:\n", " \"\"\"Devuelve (suma_mod_2, acarreo).\"\"\"\n", " s = a ^ b\n", " c = a & b\n", " return s, c\n", "\n", "for a, b in product([0, 1], repeat=2):\n", " s, c = half_adder_classical(a, b)\n", " print(f\"a={a}, b={b} -> suma={s}, acarreo={c}, binario={(c, s)}\")" ] }, { "cell_type": "markdown", "id": "e4802b5f", "metadata": {}, "source": [ "## 10. Full adder\n", "\n", "El full adder incluye un acarreo de entrada $c_{in}$:\n", "\n", "$$\n", "s=a\\oplus b\\oplus c_{in},\n", "$$\n", "\n", "$$\n", "c_{out}=ab\\oplus c_{in}(a\\oplus b).\n", "$$\n", "\n", "El segundo término expresa la regla de mayoría: hay acarreo de salida cuando al menos dos entradas valen $1$. En una implementación reversible se calcula un temporal $t=a\\oplus b$, se usa para producir suma y acarreo, y luego se descomputa." ] }, { "cell_type": "code", "execution_count": null, "id": "83f441a7", "metadata": {}, "outputs": [], "source": [ "def full_adder_classical(a: int, b: int, cin: int) -> Tuple[int, int]:\n", " \"\"\"Devuelve (suma_mod_2, acarreo_salida).\"\"\"\n", " s = a ^ b ^ cin\n", " cout = (a & b) ^ (cin & (a ^ b))\n", " return s, cout\n", "\n", "for a, b, cin in product([0, 1], repeat=3):\n", " s, cout = full_adder_classical(a, b, cin)\n", " print(f\"a={a}, b={b}, cin={cin} -> suma={s}, cout={cout}\")" ] }, { "cell_type": "markdown", "id": "02e224b1", "metadata": {}, "source": [ "## 11. ¿Cuántos bits se necesitan para una suma?\n", "\n", "Si se suman $m$ bits, el resultado máximo es $m$ y el mínimo es $0$. Se requieren suficientes bits para representar $m+1$ valores posibles:\n", "\n", "$$\n", "B(m)=\\left\\lceil \\log_2(m+1)\\right\\rceil.\n", "$$\n", "\n", "Para sumar diez bits, el resultado está entre $0$ y $10$. Como $2^3=8<11$ y $2^4=16\\ge 11$, se necesitan $4$ bits." ] }, { "cell_type": "code", "execution_count": null, "id": "7011f837", "metadata": {}, "outputs": [], "source": [ "def bits_required_for_sum(m: int) -> int:\n", " \"\"\"Número de bits necesarios para almacenar una suma entre 0 y m.\"\"\"\n", " if m < 0:\n", " raise ValueError(\"m debe ser no negativo\")\n", " return max(1, ceil(log2(m + 1)))\n", "\n", "for m in [1, 2, 3, 4, 6, 10, 12, 20]:\n", " print(f\"m={m:2d} -> bits necesarios = {bits_required_for_sum(m)}\")" ] }, { "cell_type": "markdown", "id": "7d80cd8e", "metadata": {}, "source": [ "## 12. Comparadores binarios\n", "\n", "Un comparador decide si un registro binario coincide con un patrón o supera un umbral. Para detectar igualdad con un patrón, se usan controles positivos para bits que deben ser $1$ y controles negativos para bits que deben ser $0$.\n", "\n", "Los controles negativos se implementan con la técnica:\n", "\n", "1. Aplicar $X$ sobre los qubits que deberían ser $0$.\n", "2. Aplicar una compuerta multi-controlada que se active cuando todos los controles son $1$.\n", "3. Deshacer las compuertas $X$.\n", "\n", "Así se marca un patrón sin modificar permanentemente el registro de entrada." ] }, { "cell_type": "markdown", "id": "82899f81", "metadata": {}, "source": [ "## 13. Ejercicio guiado: detectar $1011_2$\n", "\n", "**Enunciado.** El registro $q_0,q_1,q_2,q_3$ representa $b_0,b_1,b_2,b_3$. Se desea activar $q_4$ si el número almacenado es $1011_2$.\n", "\n", "**Desarrollo.** El patrón $1011_2$ significa:\n", "\n", "$$\n", "b_3=1,\n", "\\qquad\n", "b_2=0,\n", "\\qquad\n", "b_1=1,\n", "\\qquad\n", "b_0=1.\n", "$$\n", "\n", "Como $b_2$ está en $q_2$, aplicamos $X(q_2)$ antes de la compuerta multi-controlada. Después aplicamos $X(q_4)$ controlada por $q_0,q_1,q_2,q_3$ y finalmente deshacemos $X(q_2)$.\n", "\n", "**Interpretación.** El comparador transforma una condición numérica en un bit de marca reversible." ] }, { "cell_type": "code", "execution_count": null, "id": "dcf64273", "metadata": {}, "outputs": [], "source": [ "def pattern_match(bitstring: BitString, pattern: BitString) -> bool:\n", " \"\"\"Comprueba igualdad entre dos cadenas binarias.\"\"\"\n", " if len(bitstring) != len(pattern):\n", " raise ValueError(\"Las longitudes no coinciden\")\n", " return bitstring == pattern\n", "\n", "for value in [\"1011\", \"1111\", \"0011\", \"1010\"]:\n", " print(value, \"coincide con 1011?\", pattern_match(value, \"1011\"))" ] }, { "cell_type": "markdown", "id": "dc68ba21", "metadata": {}, "source": [ "## 14. Integración: de Max-Cut a oráculo para Grover\n", "\n", "La arquitectura completa es:\n", "\n", "1. Preparar una superposición uniforme de coloraciones.\n", "2. Calcular indicadores de arista $e_{ij}=x_i\\oplus x_j$.\n", "3. Sumar los indicadores para obtener $C(x)$.\n", "4. Comparar $C(x)$ con un criterio, por ejemplo $C(x)=T$.\n", "5. Convertir la marca en una fase.\n", "6. Deshacer comparación, suma e indicadores.\n", "7. Aplicar difusión de Grover.\n", "\n", "El punto más importante es que Grover no calcula Max-Cut por sí solo. Grover amplifica lo que el oráculo es capaz de reconocer." ] }, { "cell_type": "markdown", "id": "f8e65cdf", "metadata": {}, "source": [ "## 15. Qiskit: instalación condicional\n", "\n", "La siguiente celda intenta importar Qiskit. Si no está disponible, intenta instalar `qiskit` y `qiskit-aer`. En Google Colab esto permite ejecutar el notebook sin edición manual." ] }, { "cell_type": "code", "execution_count": null, "id": "b90da43b", "metadata": {}, "outputs": [], "source": [ "import importlib\n", "import subprocess\n", "import sys\n", "\n", "\n", "def ensure_package(import_name: str, pip_name: Optional[str] = None) -> None:\n", " \"\"\"Importa un paquete; si no existe, intenta instalarlo con pip.\"\"\"\n", " try:\n", " importlib.import_module(import_name)\n", " except ImportError:\n", " pkg = pip_name or import_name\n", " print(f\"Instalando {pkg} ...\")\n", " subprocess.check_call([sys.executable, \"-m\", \"pip\", \"install\", \"-q\", pkg])\n", "\n", "# Estas instalaciones solo se ejecutan si faltan los paquetes.\n", "ensure_package(\"qiskit\", \"qiskit\")\n", "ensure_package(\"qiskit_aer\", \"qiskit-aer\")" ] }, { "cell_type": "markdown", "id": "acf2810c", "metadata": {}, "source": [ "## 16. Qiskit: bloques reversibles básicos\n", "\n", "La siguiente celda define tres herramientas:\n", "\n", "- `edge_indicator_qiskit`: calcula el XOR de una arista en un auxiliar.\n", "- `half_adder_qiskit`: construye un half adder reversible.\n", "- `mark_state_phase_qiskit`: aplica una fase negativa a un estado base específico.\n", "\n", "La última función se usa para una demostración compacta de Grover. En un oráculo aritmético completo, el marcado de fase se obtiene a partir del conteo reversible y del comparador." ] }, { "cell_type": "code", "execution_count": null, "id": "b693ccba", "metadata": {}, "outputs": [], "source": [ "from qiskit import QuantumCircuit, transpile\n", "from qiskit_aer import AerSimulator\n", "\n", "\n", "def edge_indicator_qiskit(qc: QuantumCircuit, u: int, v: int, t: int) -> None:\n", " \"\"\"Calcula x_u xor x_v en el auxiliar t.\"\"\"\n", " qc.cx(u, t)\n", " qc.cx(v, t)\n", "\n", "\n", "def half_adder_qiskit(qc: QuantumCircuit, a: int, b: int, s: int, c: int) -> None:\n", " \"\"\"Half adder reversible: s = a xor b, c = a and b.\"\"\"\n", " qc.cx(a, s)\n", " qc.cx(b, s)\n", " qc.ccx(a, b, c)\n", "\n", "\n", "def mark_state_phase_qiskit(qc: QuantumCircuit, qubits: Sequence[int], bitstring: BitString) -> None:\n", " \"\"\"Aplica fase -1 al estado base indicado por bitstring.\n", "\n", " Convención: bitstring[i] corresponde al qubit qubits[i].\n", " \"\"\"\n", " if len(qubits) != len(bitstring):\n", " raise ValueError(\"El número de qubits y bits no coincide\")\n", " for q, b in zip(qubits, bitstring):\n", " if b == '0':\n", " qc.x(q)\n", " qc.h(qubits[-1])\n", " qc.mcx(list(qubits[:-1]), qubits[-1])\n", " qc.h(qubits[-1])\n", " for q, b in reversed(list(zip(qubits, bitstring))):\n", " if b == '0':\n", " qc.x(q)" ] }, { "cell_type": "markdown", "id": "0bebadba", "metadata": {}, "source": [ "## 17. Qiskit: difusión de Grover\n", "\n", "La difusión alrededor del estado uniforme invierte amplitudes respecto a la media. En código se implementa como Hadamards, compuertas $X$, una fase controlada sobre el estado $\\left|0\\cdots 0\\right\\rangle$ y luego la operación inversa." ] }, { "cell_type": "code", "execution_count": null, "id": "25c53653", "metadata": {}, "outputs": [], "source": [ "def diffusion_qiskit(qc: QuantumCircuit, qubits: Sequence[int]) -> None:\n", " \"\"\"Operador de difusión de Grover sobre los qubits indicados.\"\"\"\n", " qc.h(qubits)\n", " qc.x(qubits)\n", " qc.h(qubits[-1])\n", " qc.mcx(list(qubits[:-1]), qubits[-1])\n", " qc.h(qubits[-1])\n", " qc.x(qubits)\n", " qc.h(qubits)\n", "\n", "\n", "def grover_for_marked_states_qiskit(n: int, marked_states: Sequence[BitString], iterations: int) -> QuantumCircuit:\n", " \"\"\"Circuito de Grover que marca directamente una lista de estados.\n", "\n", " Esta versión es demostrativa. Para el oráculo algorítmico completo, la lista de estados se sustituye\n", " por compute -> compare -> phase -> uncompute.\n", " \"\"\"\n", " qc = QuantumCircuit(n, n)\n", " qubits = list(range(n))\n", " qc.h(qubits)\n", " for _ in range(iterations):\n", " for state in marked_states:\n", " mark_state_phase_qiskit(qc, qubits, state)\n", " diffusion_qiskit(qc, qubits)\n", " for i in range(n):\n", " # Medición en orden conceptual: qubit i se imprime en posición i de la cadena final.\n", " qc.measure(i, n - 1 - i)\n", " return qc\n", "\n", "\n", "def run_qiskit_counts(qc: QuantumCircuit, shots: int = 2048) -> Dict[str, int]:\n", " simulator = AerSimulator()\n", " tqc = transpile(qc, simulator)\n", " result = simulator.run(tqc, shots=shots).result()\n", " return dict(result.get_counts())" ] }, { "cell_type": "markdown", "id": "02a1f43b", "metadata": {}, "source": [ "## 18. Qiskit: demostración con el grafo $K_{3,2}$\n", "\n", "Primero calculamos clásicamente el valor óptimo para verificar la instancia pequeña. Después construimos un circuito de Grover que marca las coloraciones óptimas. Esta versión de marcado directo es útil para observar la amplificación; el oráculo reversible completo se obtiene reemplazando la lista de óptimos por el cálculo de indicadores, suma y comparación." ] }, { "cell_type": "code", "execution_count": null, "id": "3095f665", "metadata": {}, "outputs": [], "source": [ "# Max-Cut del grafo K_{3,2}\n", "best_value, marked_states = max_cuts(n_vertices, edges_k32)\n", "iterations = round((pi / 4) * sqrt((2 ** n_vertices) / len(marked_states)))\n", "print(\"Valor máximo:\", best_value)\n", "print(\"Estados marcados:\", marked_states)\n", "print(\"Iteraciones aproximadas:\", iterations)\n", "\n", "qc_grover = grover_for_marked_states_qiskit(n_vertices, marked_states, iterations)\n", "counts = run_qiskit_counts(qc_grover, shots=2048)\n", "print(counts)" ] }, { "cell_type": "markdown", "id": "14f307d5", "metadata": {}, "source": [ "### Probabilidad teórica de éxito frente al número de iteraciones\n", "\n", "La representación gráfica del algoritmo de Grover también es instructiva. Si $N$ es el número total de estados y $M$ el número de estados marcados, la probabilidad ideal de medir una solución tras $k$ iteraciones es\n", "\n", "$$\n", "P_k = \\sin^2\big((2k+1)\theta\big), \\qquad \\sin^2\theta = \f", "rac{M}{N}.\n", "$$\n", "\n", "La curva siguiente permite ver por qué no conviene iterar indefinidamente: la amplitud crece, alcanza un máximo y luego vuelve a disminuir. En la práctica, esta gráfica justifica la elección del número de iteraciones usado en la simulación." ] }, { "cell_type": "code", "execution_count": null, "id": "f948b58e", "metadata": {}, "outputs": [], "source": [ "def grover_success_probability(N: int, M: int, k: int) -> float:\n", " \"\"\"Probabilidad ideal de éxito de Grover tras k iteraciones.\"\"\"\n", " theta = np.arcsin(np.sqrt(M / N))\n", " return float(np.sin((2 * k + 1) * theta) ** 2)\n", "\n", "N = 2 ** n_vertices\n", "M = len(marked_states)\n", "ks = list(range(0, 12))\n", "probs = [grover_success_probability(N, M, k) for k in ks]\n", "\n", "plt.figure(figsize=(7, 4.5))\n", "plt.plot(ks, probs, marker=\"o\")\n", "plt.xlabel(\"Número de iteraciones de Grover\")\n", "plt.ylabel(\"Probabilidad ideal de éxito\")\n", "plt.title(\"Amplificación de amplitud para el ejemplo de K_{3,2}\")\n", "plt.ylim(0, 1.05)\n", "plt.grid(alpha=0.3)\n", "plt.show()\n", "\n", "best_k = ks[int(np.argmax(probs))]\n", "print(f\"Máximo dentro del rango graficado en k={best_k} con P={max(probs):.4f}\")" ] }, { "cell_type": "markdown", "id": "e4ebc394", "metadata": {}, "source": [ "### Interpretación de los conteos\n", "\n", "Si el circuito ideal se comporta como se espera, las cadenas óptimas aparecen con frecuencia dominante. Para el grafo $K_{3,2}$, las coloraciones $00011$ y $11100$ corresponden al corte que separa las dos partes del grafo. Sus complementos representan el mismo corte combinatorio, aunque son estados base diferentes." ] }, { "cell_type": "markdown", "id": "0995cc50", "metadata": {}, "source": [ "## 19. Cirq: instalación condicional\n", "\n", "La siguiente celda intenta importar Cirq. Si no está disponible, intenta instalarlo. En Google Colab puede tardar algunos segundos." ] }, { "cell_type": "code", "execution_count": null, "id": "7d439adb", "metadata": {}, "outputs": [], "source": [ "ensure_package(\"cirq\", \"cirq\")" ] }, { "cell_type": "markdown", "id": "ae783261", "metadata": {}, "source": [ "## 20. Cirq: indicadores y marcado\n", "\n", "Cirq permite expresar controles múltiples con `controlled_by`. La estructura conceptual es la misma que en Qiskit: calcular indicadores, marcar, y descomputar." ] }, { "cell_type": "code", "execution_count": null, "id": "a2991a4c", "metadata": {}, "outputs": [], "source": [ "import cirq\n", "\n", "\n", "def edge_indicator_cirq(circuit: cirq.Circuit, qubits: Sequence[cirq.Qid], u: int, v: int, t: int) -> None:\n", " \"\"\"Calcula x_u xor x_v en el auxiliar t usando dos CNOTs.\"\"\"\n", " circuit.append(cirq.CNOT(qubits[u], qubits[t]))\n", " circuit.append(cirq.CNOT(qubits[v], qubits[t]))\n", "\n", "\n", "def phase_mark_state_cirq(circuit: cirq.Circuit, qubits: Sequence[cirq.Qid], bitstring: BitString) -> None:\n", " \"\"\"Aplica una fase -1 al estado base indicado por bitstring.\"\"\"\n", " if len(qubits) != len(bitstring):\n", " raise ValueError(\"El número de qubits y bits no coincide\")\n", " for q, b in zip(qubits, bitstring):\n", " if b == '0':\n", " circuit.append(cirq.X(q))\n", " circuit.append(cirq.Z(qubits[-1]).controlled_by(*qubits[:-1]))\n", " for q, b in reversed(list(zip(qubits, bitstring))):\n", " if b == '0':\n", " circuit.append(cirq.X(q))\n", "\n", "\n", "def diffusion_cirq(circuit: cirq.Circuit, qubits: Sequence[cirq.Qid]) -> None:\n", " \"\"\"Operador de difusión de Grover en Cirq.\"\"\"\n", " circuit.append(cirq.H.on_each(*qubits))\n", " circuit.append(cirq.X.on_each(*qubits))\n", " circuit.append(cirq.Z(qubits[-1]).controlled_by(*qubits[:-1]))\n", " circuit.append(cirq.X.on_each(*qubits))\n", " circuit.append(cirq.H.on_each(*qubits))" ] }, { "cell_type": "code", "execution_count": null, "id": "32a86409", "metadata": {}, "outputs": [], "source": [ "def grover_for_marked_states_cirq(n: int, marked_states: Sequence[BitString], iterations: int) -> cirq.Circuit:\n", " \"\"\"Circuito de Grover en Cirq para una lista demostrativa de estados marcados.\"\"\"\n", " qubits = cirq.LineQubit.range(n)\n", " circuit = cirq.Circuit()\n", " circuit.append(cirq.H.on_each(*qubits))\n", " for _ in range(iterations):\n", " for state in marked_states:\n", " phase_mark_state_cirq(circuit, qubits, state)\n", " diffusion_cirq(circuit, qubits)\n", " circuit.append(cirq.measure(*qubits, key='z'))\n", " return circuit\n", "\n", "cirq_circuit = grover_for_marked_states_cirq(n_vertices, marked_states, iterations)\n", "print(cirq_circuit)\n", "\n", "sim = cirq.Simulator()\n", "result = sim.run(cirq_circuit, repetitions=1024)\n", "print(result.histogram(key='z'))" ] }, { "cell_type": "markdown", "id": "b7716ae5", "metadata": {}, "source": [ "## 21. Ejercicios guiados\n", "\n", "### Ejercicio 1: estado de coloración\n", "\n", "Tres vértices se codifican con tres qubits. Si $x_0=1$, $x_1=0$ y $x_2=0$, entonces la cadena es $100$ y el estado base es\n", "\n", "$$\n", "\\left|100\\right\\rangle.\n", "$$\n", "\n", "### Ejercicio 2: indicador de arista\n", "\n", "Si una arista conecta colores $x_i=1$ y $x_j=0$, entonces\n", "\n", "$$\n", "e_{ij}=1\\oplus 0=1.\n", "$$\n", "\n", "La arista cruza el corte.\n", "\n", "### Ejercicio 3: bits para sumar diez indicadores\n", "\n", "La suma está entre $0$ y $10$, por lo que se necesitan $4$ bits." ] }, { "cell_type": "markdown", "id": "c6a4823b", "metadata": {}, "source": [ "## 22. Ejercicios guiados con desarrollo paso a paso\n", "\n", "### Ejercicio 4: comparador para $1011_2$\n", "\n", "El patrón $1011_2$ tiene un cero en la posición $b_2$. Si $b_2$ está en $q_2$, se aplica $X(q_2)$ antes de la multi-controlada y se deshace después. La marca queda condicionada a que todos los bits transformados sean $1$.\n", "\n", "### Ejercicio 5: suma módulo 2 en un objetivo\n", "\n", "Para almacenar $a\\oplus b$ en un objetivo $t$ inicializado en $0$, se aplican dos CNOTs:\n", "\n", "$$\n", "t:0\\longmapsto a\\longmapsto a\\oplus b.\n", "$$\n", "\n", "Si el objetivo inicia en $c$, el resultado es $c\\oplus a\\oplus b$." ] }, { "cell_type": "markdown", "id": "6610b3aa", "metadata": {}, "source": [ "## 23. Ejercicios propuestos\n", "\n", "1. Para un ciclo de cinco vértices, propón una coloración y calcula cuántas aristas cruzan. Explica por qué no pueden cruzar las cinco aristas simultáneamente.\n", "2. Determina cuántos bits se necesitan para almacenar la suma de $12$ indicadores y de $20$ indicadores.\n", "3. Diseña el esquema reversible para marcar un registro de conteo igual a $0110_2$.\n", "4. Para el grafo $K_{3,2}$, verifica que las coloraciones $00011$ y $11100$ tienen el mismo corte.\n", "5. Explica por qué un oráculo que deja auxiliares sin limpiar puede afectar la difusión de Grover." ] }, { "cell_type": "markdown", "id": "33ba91d8", "metadata": {}, "source": [ "## 24. Resumen final\n", "\n", "Max-Cut aporta el problema combinatorio: elegir una partición que maximice aristas cruzadas. La codificación binaria convierte cada partición en una cadena de bits y cada arista cortada en una XOR.\n", "\n", "Los adders aportan el mecanismo reversible que permite sumar indicadores de arista. Half adders, full adders y ripple carry adders hacen posible construir registros de conteo sin destruir información.\n", "\n", "Los comparadores convierten el conteo en una marca lógica. Después, esa marca puede transformarse en fase y usarse dentro de Grover.\n", "\n", "La integración completa es:\n", "\n", "$$\n", "\\text{coloración}\n", "\\longrightarrow\n", "\\text{indicadores}\n", "\\longrightarrow\n", "\\text{conteo reversible}\n", "\\longrightarrow\n", "\\text{comparador}\n", "\\longrightarrow\n", "\\text{fase}\n", "\\longrightarrow\n", "\\text{Grover}.\n", "$$\n", "\n", "La conclusión conceptual es que Grover no reemplaza la construcción del oráculo. La parte central del módulo es aprender a convertir una función objetivo clásica en un predicado reversible compatible con interferencia cuántica." ] } ], "metadata": { "colab": { "provenance": [] }, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }