{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fa561b79",
   "metadata": {},
   "source": [
    "# Búsqueda de Grover\n",
    "\n",
    "Este notebook acompaña el material académico integrado sobre **Grover's Search**. El objetivo es estudiar el algoritmo como una técnica de búsqueda no estructurada basada en cuatro ideas: preparación de una superposición uniforme, marcado de soluciones por fase, difusión como inversión respecto a la media y amplificación de amplitud.\n",
    "\n",
    "El notebook es autoexplicativo. Las secciones matemáticas siguen el mismo orden temático de la presentación integrada y desarrollan los ejemplos y ejercicios con pasos intermedios suficientes para verificar formalmente cada conclusión."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c08858a7",
   "metadata": {},
   "source": [
    "## Convención de notación de Dirac\n",
    "\n",
    "Para evitar que la notación se rompa entre JupyterLab, Anaconda y Google Colab, este notebook escribe los kets y bras con LaTeX nativo expandido, sin depender de comandos abreviados externos. En particular:\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",
    "Esta convención mantiene clara la diferencia entre un vector de estado, su dual y un proyector. Todas las fórmulas posteriores usan esta misma codificación."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ea2206e",
   "metadata": {},
   "source": [
    "## Objetivos de aprendizaje\n",
    "\n",
    "Al finalizar, se espera que puedas:\n",
    "\n",
    "1. Formular la búsqueda no estructurada como un problema de consulta con un predicado booleano.\n",
    "2. Relacionar el número de qubits $n$ con el tamaño del espacio de búsqueda $N=2^n$.\n",
    "3. Explicar por qué una búsqueda clásica sin estructura requiere escala lineal en el número de candidatos.\n",
    "4. Construir el estado uniforme $\\left|s\\right\\rangle=N^{-1/2}\\sum_x\\left|x\\right\\rangle$.\n",
    "5. Interpretar el oráculo de fase $O_f\\left|x\\right\\rangle=(-1)^{f(x)}\\left|x\\right\\rangle$.\n",
    "6. Explicar la difusión como reflexión alrededor de $\\left|s\\right\\rangle$ y como inversión respecto a la media.\n",
    "7. Describir una iteración de Grover como composición de dos reflexiones.\n",
    "8. Justificar conceptualmente el número aproximado de iteraciones $r\\approx \\frac{\\pi}{4}\\sqrt{N/k}$.\n",
    "9. Implementar ejemplos en Cirq y Qiskit.\n",
    "10. Diagnosticar errores frecuentes en oráculos, difusión, número de iteraciones y orden de bits."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44da7d49",
   "metadata": {},
   "source": [
    "## 1. Problema de búsqueda no estructurada\n",
    "\n",
    "Sea $N=2^n$ el número de candidatos. Cada candidato se etiqueta mediante una cadena binaria $x\\in\\{0,1\\}^n$. La información sobre las soluciones se entrega mediante un predicado booleano\n",
    "\n",
    "$$\n",
    "f:\\{0,1\\}^n\\to\\{0,1\\},\n",
    "$$\n",
    "\n",
    "donde $f(x)=1$ significa que $x$ es solución y $f(x)=0$ significa que no lo es. El conjunto marcado es\n",
    "\n",
    "$$\n",
    "M=\\{x:f(x)=1\\},\\qquad k=|M|.\n",
    "$$\n",
    "\n",
    "El problema no consiste en calcular todos los valores de $f$. El objetivo es encontrar algún $x\\in M$ usando el menor número posible de consultas al predicado. En ausencia de estructura, un algoritmo clásico que consulta candidatos individuales necesita escala $O(N/k)$ para obtener una solución con probabilidad constante. Grover reduce esa escala a $O(\\sqrt{N/k})$ consultas en el modelo ideal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a0b6b24",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instalación condicional para JupyterLab, Anaconda o Google Colab.\n",
    "# Si los paquetes ya existen, esta celda no modifica el entorno.\n",
    "import importlib.util\n",
    "import subprocess\n",
    "import sys\n",
    "\n",
    "\n",
    "def ensure_package(import_name, pip_name=None):\n",
    "    \"\"\"Instala un paquete solo si no puede importarse.\"\"\"\n",
    "    if importlib.util.find_spec(import_name) is None:\n",
    "        pkg = pip_name or import_name\n",
    "        print(f\"Instalando {pkg} ...\")\n",
    "        subprocess.check_call([sys.executable, \"-m\", \"pip\", \"install\", \"-q\", pkg])\n",
    "    else:\n",
    "        print(f\"{import_name} disponible\")\n",
    "\n",
    "ensure_package(\"numpy\")\n",
    "ensure_package(\"matplotlib\")\n",
    "ensure_package(\"qiskit\")\n",
    "ensure_package(\"qiskit_aer\", \"qiskit-aer\")\n",
    "ensure_package(\"cirq\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "762979ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from collections import Counter\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import cirq\n",
    "from qiskit import QuantumCircuit, transpile\n",
    "from qiskit_aer import AerSimulator\n",
    "\n",
    "# Para que los ejemplos sean reproducibles.\n",
    "np.random.seed(7)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22d8f25b",
   "metadata": {},
   "source": [
    "## 2. Estado uniforme\n",
    "\n",
    "El algoritmo comienza sin preferir ningún candidato. Por ello prepara el estado uniforme\n",
    "\n",
    "$$\n",
    "\\left|s\\right\\rangle=\\frac{1}{\\sqrt{N}}\\sum_{x=0}^{N-1}\\left|x\\right\\rangle.\n",
    "$$\n",
    "\n",
    "Si $N=2^n$, este estado se obtiene aplicando Hadamard a cada qubit inicializado en $\\left|0\\right\\rangle$:\n",
    "\n",
    "$$\n",
    "H^{\\otimes n}\\left|0^n\\right\\rangle\n",
    "=\\left(\\frac{\\left|0\\right\\rangle+\\left|1\\right\\rangle}{\\sqrt{2}}\\right)^{\\otimes n}\n",
    "=\\frac{1}{\\sqrt{2^n}}\\sum_{x\\in\\{0,1\\}^n}\\left|x\\right\\rangle.\n",
    "$$\n",
    "\n",
    "La superposición uniforme no entrega todas las respuestas al medir. Si se mide inmediatamente, el resultado es casi uniforme. Su función es preparar caminos coherentes para que el oráculo y la difusión puedan modificar amplitudes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7fbb0b0",
   "metadata": {},
   "source": [
    "\n",
    "### Desarrollo paso a paso: por qué $64$ candidatos requieren $6$ qubits\n",
    "\n",
    "El registro de búsqueda de $n$ qubits tiene $2^n$ estados base. Para representar una lista de $64$ candidatos se busca $n$ tal que\n",
    "\n",
    "$$\n",
    "2^n=64.\n",
    "$$\n",
    "\n",
    "Calculamos las potencias relevantes:\n",
    "\n",
    "$$\n",
    "2^1=2,\n",
    "\\qquad\n",
    "2^2=4,\n",
    "\\qquad\n",
    "2^3=8,\n",
    "\\qquad\n",
    "2^4=16,\n",
    "\\qquad\n",
    "2^5=32,\n",
    "\\qquad\n",
    "2^6=64.\n",
    "$$\n",
    "\n",
    "Por tanto, se requieren $6$ qubits. La inicialización coherente es\n",
    "\n",
    "$$\n",
    "H^{\\otimes 6}\\left|000000\\right\\rangle\n",
    "=\n",
    "\\frac{1}{\\sqrt{64}}\n",
    "\\sum_{x=0}^{63}\\left|x\\right\\rangle.\n",
    "$$\n",
    "\n",
    "La conclusión conceptual es que los seis qubits no almacenan sesenta y cuatro respuestas clásicas accesibles por lectura directa. Preparan sesenta y cuatro caminos coherentes con igual amplitud inicial para que el oráculo pueda introducir una diferencia de fase y la difusión pueda convertir esa diferencia en un sesgo observable de probabilidad.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8775f903",
   "metadata": {},
   "outputs": [],
   "source": [
    "def uniform_state(n):\n",
    "    \"\"\"Devuelve el vector de estado uniforme para n qubits.\"\"\"\n",
    "    N = 2 ** n\n",
    "    return np.ones(N, dtype=complex) / np.sqrt(N)\n",
    "\n",
    "n = 6\n",
    "state = uniform_state(n)\n",
    "print(\"Número de qubits:\", n)\n",
    "print(\"Número de candidatos N:\", 2**n)\n",
    "print(\"Norma del estado uniforme:\", np.linalg.norm(state))\n",
    "print(\"Probabilidad inicial de un candidato específico:\", abs(state[0])**2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "601a6c68",
   "metadata": {},
   "source": [
    "## 3. Oráculo de fase\n",
    "\n",
    "El oráculo de Grover marca soluciones mediante una fase:\n",
    "\n",
    "$$\n",
    "O_f\\left|x\\right\\rangle=(-1)^{f(x)}\\left|x\\right\\rangle.\n",
    "$$\n",
    "\n",
    "Si $x$ es solución, $f(x)=1$ y el estado base cambia de signo. Si no lo es, $f(x)=0$ y queda igual. Este cambio de signo no aumenta todavía la probabilidad de medir la solución, porque $|a|^2=|-a|^2$. Su papel es crear un contraste de fase que la difusión puede convertir en amplitud.\n",
    "\n",
    "En muchas implementaciones, este oráculo de fase se obtiene desde un oráculo reversible con auxiliar:\n",
    "\n",
    "$$\n",
    "U_f\\left|x\\right\\rangle\\left|y\\right\\rangle=\\left|x\\right\\rangle\\left|y\\oplus f(x)\\right\\rangle.\n",
    "$$\n",
    "\n",
    "Si el auxiliar está en $\\left|-\\right\\rangle$, entonces\n",
    "\n",
    "$$\n",
    "U_f\\left|x\\right\\rangle\\left|-\\right\\rangle=(-1)^{f(x)}\\left|x\\right\\rangle\\left|-\\right\\rangle.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eaccadd4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def phase_oracle_statevector(state, marked_indices):\n",
    "    \"\"\"Aplica un oráculo de fase a un vector de estado.\n",
    "\n",
    "    Los índices marcados reciben un factor -1.\n",
    "    \"\"\"\n",
    "    new_state = state.copy()\n",
    "    for idx in marked_indices:\n",
    "        new_state[idx] *= -1\n",
    "    return new_state\n",
    "\n",
    "n = 3\n",
    "marked = [int(\"101\", 2)]\n",
    "psi = uniform_state(n)\n",
    "psi_after_oracle = phase_oracle_statevector(psi, marked)\n",
    "\n",
    "print(\"Estado marcado:\", format(marked[0], \"03b\"))\n",
    "print(\"Amplitud antes del oráculo:\", psi[marked[0]])\n",
    "print(\"Amplitud después del oráculo:\", psi_after_oracle[marked[0]])\n",
    "print(\"Probabilidad antes:\", abs(psi[marked[0]])**2)\n",
    "print(\"Probabilidad después:\", abs(psi_after_oracle[marked[0]])**2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "722a7b13",
   "metadata": {},
   "source": [
    "## 4. Difusión como inversión respecto a la media\n",
    "\n",
    "Sea\n",
    "\n",
    "$$\n",
    "\\left|\\psi\\right\\rangle=\\sum_x a_x\\left|x\\right\\rangle.\n",
    "$$\n",
    "\n",
    "La media de las amplitudes es\n",
    "\n",
    "$$\n",
    "\\bar a=\\frac{1}{N}\\sum_x a_x.\n",
    "$$\n",
    "\n",
    "El operador de difusión\n",
    "\n",
    "$$\n",
    "D=2\\left|s\\right\\rangle\\left\\langle s\\right|-I\n",
    "$$\n",
    "\n",
    "actúa sobre las amplitudes como\n",
    "\n",
    "$$\n",
    "a_x\\longmapsto 2\\bar a-a_x.\n",
    "$$\n",
    "\n",
    "Esta es una inversión respecto a la media. Después del oráculo, las amplitudes de los estados marcados quedan por debajo de la media debido al cambio de signo; al reflejarlas respecto a la media, pasan a ser mayores que las demás. Así se convierte una diferencia de fase en una diferencia de probabilidad."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46ab58fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def diffusion_statevector(state):\n",
    "    \"\"\"Aplica inversión respecto a la media a un vector de amplitudes.\"\"\"\n",
    "    mean = np.mean(state)\n",
    "    return 2 * mean - state\n",
    "\n",
    "n = 3\n",
    "marked = [int(\"101\", 2)]\n",
    "psi = uniform_state(n)\n",
    "psi_oracle = phase_oracle_statevector(psi, marked)\n",
    "psi_diffused = diffusion_statevector(psi_oracle)\n",
    "\n",
    "labels = [format(i, \"03b\") for i in range(2**n)]\n",
    "print(\"Amplitudes después del oráculo:\")\n",
    "for label, amp in zip(labels, psi_oracle):\n",
    "    print(label, np.round(amp.real, 4))\n",
    "\n",
    "print(\"\\nAmplitudes después de la difusión:\")\n",
    "for label, amp in zip(labels, psi_diffused):\n",
    "    print(label, np.round(amp.real, 4))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c641611",
   "metadata": {},
   "source": [
    "\n",
    "### Desarrollo paso a paso: una iteración con $N=8$ y una solución marcada\n",
    "\n",
    "Supongamos un registro de tres qubits, por lo que $N=2^3=8$. Si hay una única solución marcada, la amplitud inicial de cada estado base en la superposición uniforme es\n",
    "\n",
    "$$\n",
    "a=\\frac{1}{\\sqrt{8}}.\n",
    "$$\n",
    "\n",
    "Después del oráculo, la solución marcada tiene amplitud $-a$, mientras que los siete estados no marcados conservan amplitud $a$. La media de las amplitudes queda\n",
    "\n",
    "$$\n",
    "\\bar a\n",
    "=\n",
    "\\frac{7a+(-a)}{8}\n",
    "=\n",
    "\\frac{6a}{8}\n",
    "=\n",
    "\\frac{3a}{4}.\n",
    "$$\n",
    "\n",
    "La difusión aplica la regla\n",
    "\n",
    "$$\n",
    "a_x \\longmapsto 2\\bar a-a_x.\n",
    "$$\n",
    "\n",
    "Para el estado marcado:\n",
    "\n",
    "$$\n",
    "-a\n",
    "\\longmapsto\n",
    "2\\left(\\frac{3a}{4}\\right)-(-a)\n",
    "=\n",
    "\\frac{3a}{2}+a\n",
    "=\n",
    "\\frac{5a}{2}.\n",
    "$$\n",
    "\n",
    "Para cada estado no marcado:\n",
    "\n",
    "$$\n",
    "a\n",
    "\\longmapsto\n",
    "2\\left(\\frac{3a}{4}\\right)-a\n",
    "=\n",
    "\\frac{3a}{2}-a\n",
    "=\n",
    "\\frac{a}{2}.\n",
    "$$\n",
    "\n",
    "La probabilidad de la solución marcada después de esta iteración es\n",
    "\n",
    "$$\n",
    "\\left|\\frac{5a}{2}\\right|^2\n",
    "=\n",
    "\\frac{25}{4}|a|^2\n",
    "=\n",
    "\\frac{25}{4}\\cdot\\frac{1}{8}\n",
    "=\n",
    "\\frac{25}{32}.\n",
    "$$\n",
    "\n",
    "El cálculo muestra el propósito de la difusión: convertir un signo introducido por el oráculo en una amplificación real de probabilidad. El oráculo solo crea contraste de fase; la difusión transforma ese contraste en una distribución medible favorable a la solución.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23c7a250",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Visualización sencilla de amplitudes reales antes y después de la difusión.\n",
    "plt.figure(figsize=(8, 4))\n",
    "plt.bar(labels, psi_diffused.real)\n",
    "plt.xlabel(\"Estado base\")\n",
    "plt.ylabel(\"Amplitud real\")\n",
    "plt.title(\"Después de una iteración parcial: oráculo + difusión\")\n",
    "plt.xticks(rotation=45)\n",
    "plt.tight_layout()\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c554a84",
   "metadata": {},
   "source": [
    "## 5. Iteración de Grover y número de repeticiones\n",
    "\n",
    "Una iteración de Grover es la composición\n",
    "\n",
    "$$\n",
    "G=DO_f.\n",
    "$$\n",
    "\n",
    "El oráculo invierte la fase del subespacio marcado y la difusión refleja alrededor del estado uniforme. La composición de dos reflexiones es una rotación. Si hay $k$ soluciones en $N$ candidatos, se define\n",
    "\n",
    "$$\n",
    "\\sin^2\\theta=\\frac{k}{N}.\n",
    "$$\n",
    "\n",
    "Después de $r$ iteraciones, la probabilidad total de medir una solución idealmente es\n",
    "\n",
    "$$\n",
    "P_r=\\sin^2((2r+1)\\theta).\n",
    "$$\n",
    "\n",
    "El máximo ocurre cuando $(2r+1)\\theta$ queda cerca de $\\pi/2$. Para $k\\ll N$ se usa la regla aproximada\n",
    "\n",
    "$$\n",
    "r\\approx \\frac{\\pi}{4}\\sqrt{\\frac{N}{k}}.\n",
    "$$\n",
    "\n",
    "Esta regla explica por qué hay sobrerotación: si se sigue iterando después del máximo, la probabilidad de éxito puede disminuir."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f040b32b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recommended_iterations(N, k):\n",
    "    \"\"\"Número entero recomendado de iteraciones para Grover básico.\"\"\"\n",
    "    if k <= 0 or k > N:\n",
    "        raise ValueError(\"Se requiere 1 <= k <= N\")\n",
    "    return max(1, int(round((math.pi / 4) * math.sqrt(N / k))))\n",
    "\n",
    "for k in [1, 2, 4, 8]:\n",
    "    print(f\"N=64, k={k}: iteraciones recomendadas = {recommended_iterations(64, k)}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e71d113d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def grover_statevector(n, marked_bitstrings, iterations=None):\n",
    "    \"\"\"Simulación vectorial básica de Grover.\n",
    "\n",
    "    Esta función no usa Qiskit ni Cirq; sirve para observar la dinámica matemática.\n",
    "    \"\"\"\n",
    "    N = 2 ** n\n",
    "    marked_indices = [int(b, 2) for b in marked_bitstrings]\n",
    "    if iterations is None:\n",
    "        iterations = recommended_iterations(N, len(marked_indices))\n",
    "    state = uniform_state(n)\n",
    "    history = [state.copy()]\n",
    "    for _ in range(iterations):\n",
    "        state = phase_oracle_statevector(state, marked_indices)\n",
    "        state = diffusion_statevector(state)\n",
    "        history.append(state.copy())\n",
    "    return state, history\n",
    "\n",
    "final_state, history = grover_statevector(3, [\"101\"], iterations=2)\n",
    "probs = np.abs(final_state)**2\n",
    "for i, p in enumerate(probs):\n",
    "    print(format(i, \"03b\"), round(float(p), 4))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "194e1675",
   "metadata": {},
   "source": [
    "\n",
    "## 6. Ejemplo desarrollado: marcar $\\left|101\\right\\rangle$\n",
    "\n",
    "**Problema.** Queremos encontrar la cadena $101$ dentro de un registro de tres qubits. El oráculo debe implementar\n",
    "\n",
    "$$\n",
    "O\\left|101\\right\\rangle=-\\left|101\\right\\rangle,\n",
    "\\qquad\n",
    "O\\left|x\\right\\rangle=\\left|x\\right\\rangle\\quad (x\\neq 101).\n",
    "$$\n",
    "\n",
    "**Idea cuántica.** El oráculo no revela la solución como un dato clásico. Cambia el signo de la amplitud asociada con la solución. Esa diferencia de fase será útil solo después de aplicar difusión.\n",
    "\n",
    "**Desarrollo paso a paso del marcado.** La fase multi-controlada estándar se activa naturalmente sobre el patrón $111$. Como queremos marcar $101$, convertimos temporalmente el cero de la segunda posición en un uno:\n",
    "\n",
    "$$\n",
    "\\left|101\\right\\rangle\n",
    "\\xrightarrow{X\\text{ en el segundo qubit}}\n",
    "\\left|111\\right\\rangle.\n",
    "$$\n",
    "\n",
    "Ahora la fase multi-controlada sí se activa:\n",
    "\n",
    "$$\n",
    "\\left|111\\right\\rangle\\longmapsto -\\left|111\\right\\rangle.\n",
    "$$\n",
    "\n",
    "Finalmente se deshace la traducción temporal:\n",
    "\n",
    "$$\n",
    "-\\left|111\\right\\rangle\n",
    "\\xrightarrow{X\\text{ en el segundo qubit}}\n",
    "-\\left|101\\right\\rangle.\n",
    "$$\n",
    "\n",
    "**Justificación.** Los $X$ antes y después no son parte del predicado final; son una herramienta para implementar controles negativos. El paso de deshacer es indispensable porque un oráculo de búsqueda debe marcar la etiqueta sin cambiarla.\n",
    "\n",
    "**Interpretación.** El resultado final no significa que el circuito haya leído una lista de ocho valores. Significa que la solución definida por el predicado quedó distinguida por fase y lista para ser amplificada por la difusión.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa9b89d2",
   "metadata": {},
   "source": [
    "\n",
    "### Variación desarrollada: marcar $\\left|101\\right\\rangle$ y $\\left|111\\right\\rangle$\n",
    "\n",
    "Ahora el conjunto marcado es\n",
    "\n",
    "$$\n",
    "M=\\{101,111\\}.\n",
    "$$\n",
    "\n",
    "Las dos cadenas comparten el primer y el tercer bit igual a $1$; el segundo bit puede ser $0$ o $1$. Por tanto, el predicado puede escribirse como\n",
    "\n",
    "$$\n",
    "f(x_1x_2x_3)=1\n",
    "\\quad\\Longleftrightarrow\\quad\n",
    "x_1=1\\ \\text{y}\\ x_3=1.\n",
    "$$\n",
    "\n",
    "El segundo qubit no debe usarse como control, porque exigirlo eliminaría una de las dos soluciones. La acción deseada es\n",
    "\n",
    "$$\n",
    "\\left|101\\right\\rangle\\mapsto -\\left|101\\right\\rangle,\n",
    "\\qquad\n",
    "\\left|111\\right\\rangle\\mapsto -\\left|111\\right\\rangle,\n",
    "$$\n",
    "\n",
    "mientras que los demás estados deben quedar sin cambio de signo. Esta variación ilustra una diferencia central entre conocer una solución y conocer un predicado: el circuito implementa una condición lógica sobre bits, no necesariamente una lista explícita de estados escritos uno por uno.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "467ff39d",
   "metadata": {},
   "source": [
    "## 7. Implementación en Cirq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05fa6d67",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mcz_cirq(qubits):\n",
    "    \"\"\"Compuerta Z multi-controlada sobre el último qubit.\"\"\"\n",
    "    if len(qubits) == 1:\n",
    "        return cirq.Z(qubits[0])\n",
    "    return cirq.Z(qubits[-1]).controlled_by(*qubits[:-1])\n",
    "\n",
    "\n",
    "def mark_state_cirq_ops(qubits, bitstring):\n",
    "    \"\"\"Operaciones de Cirq que marcan una cadena con fase negativa.\"\"\"\n",
    "    ops = []\n",
    "    for q, bit in zip(qubits, bitstring):\n",
    "        if bit == \"0\":\n",
    "            ops.append(cirq.X(q))\n",
    "    ops.append(mcz_cirq(qubits))\n",
    "    for q, bit in zip(qubits, bitstring):\n",
    "        if bit == \"0\":\n",
    "            ops.append(cirq.X(q))\n",
    "    return ops\n",
    "\n",
    "\n",
    "def diffusion_cirq_ops(qubits):\n",
    "    \"\"\"Difusión de Grover sobre el registro de búsqueda.\"\"\"\n",
    "    ops = []\n",
    "    ops.extend(cirq.H.on_each(*qubits))\n",
    "    ops.extend(cirq.X.on_each(*qubits))\n",
    "    ops.append(mcz_cirq(qubits))\n",
    "    ops.extend(cirq.X.on_each(*qubits))\n",
    "    ops.extend(cirq.H.on_each(*qubits))\n",
    "    return ops\n",
    "\n",
    "\n",
    "def grover_cirq_circuit(marked_bitstrings, n, iterations=None):\n",
    "    \"\"\"Construye un circuito de Grover en Cirq.\"\"\"\n",
    "    qubits = cirq.LineQubit.range(n)\n",
    "    N = 2 ** n\n",
    "    if iterations is None:\n",
    "        iterations = recommended_iterations(N, len(marked_bitstrings))\n",
    "    circuit = cirq.Circuit()\n",
    "    circuit.append(cirq.H.on_each(*qubits))\n",
    "    for _ in range(iterations):\n",
    "        for bitstring in marked_bitstrings:\n",
    "            circuit.append(mark_state_cirq_ops(qubits, bitstring))\n",
    "        circuit.append(diffusion_cirq_ops(qubits))\n",
    "    circuit.append(cirq.measure(*qubits, key=\"x\"))\n",
    "    return circuit\n",
    "\n",
    "\n",
    "def run_cirq_counts(circuit, n, repetitions=1000):\n",
    "    \"\"\"Ejecuta un circuito Cirq y devuelve conteos como cadenas binarias.\"\"\"\n",
    "    simulator = cirq.Simulator(seed=7)\n",
    "    result = simulator.run(circuit, repetitions=repetitions)\n",
    "    rows = result.measurements[\"x\"]\n",
    "    strings = [\"\".join(str(int(bit)) for bit in row) for row in rows]\n",
    "    return Counter(strings)\n",
    "\n",
    "circuit_cirq = grover_cirq_circuit([\"101\"], n=3, iterations=2)\n",
    "print(circuit_cirq)\n",
    "counts_cirq = run_cirq_counts(circuit_cirq, n=3, repetitions=1000)\n",
    "counts_cirq\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf339761",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Caso con dos soluciones: 101 y 111.\n",
    "circuit_cirq_two = grover_cirq_circuit([\"101\", \"111\"], n=3, iterations=1)\n",
    "counts_cirq_two = run_cirq_counts(circuit_cirq_two, n=3, repetitions=1000)\n",
    "counts_cirq_two\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31d8b409",
   "metadata": {},
   "source": [
    "## 8. Implementación en Qiskit\n",
    "\n",
    "La implementación en Qiskit sigue la misma lógica. Se define una fase multi-controlada, un marcador para cadenas concretas, el operador de difusión y el circuito completo. La medición se realiza con un orden explícito para que la cadena impresa coincida con el orden conceptual usado al escribir las soluciones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5ff6601",
   "metadata": {},
   "outputs": [],
   "source": [
    "def apply_mcz_qiskit(qc, qubits):\n",
    "    \"\"\"Aplica una Z multi-controlada sobre el último qubit de la lista.\"\"\"\n",
    "    if len(qubits) == 1:\n",
    "        qc.z(qubits[0])\n",
    "    else:\n",
    "        qc.h(qubits[-1])\n",
    "        qc.mcx(qubits[:-1], qubits[-1])\n",
    "        qc.h(qubits[-1])\n",
    "\n",
    "\n",
    "def mark_state_qiskit(qc, bitstring):\n",
    "    \"\"\"Marca una cadena con fase negativa en Qiskit.\n",
    "\n",
    "    Convención: bitstring[0] corresponde al qubit 0.\n",
    "    \"\"\"\n",
    "    n = len(bitstring)\n",
    "    qubits = list(range(n))\n",
    "    for i, bit in enumerate(bitstring):\n",
    "        if bit == \"0\":\n",
    "            qc.x(i)\n",
    "    apply_mcz_qiskit(qc, qubits)\n",
    "    for i, bit in enumerate(bitstring):\n",
    "        if bit == \"0\":\n",
    "            qc.x(i)\n",
    "\n",
    "\n",
    "def diffusion_qiskit(qc, n):\n",
    "    \"\"\"Difusión de Grover sobre n qubits de búsqueda.\"\"\"\n",
    "    qc.h(range(n))\n",
    "    qc.x(range(n))\n",
    "    apply_mcz_qiskit(qc, list(range(n)))\n",
    "    qc.x(range(n))\n",
    "    qc.h(range(n))\n",
    "\n",
    "\n",
    "def grover_qiskit_circuit(marked_bitstrings, n, iterations=None):\n",
    "    \"\"\"Construye el circuito completo de Grover en Qiskit.\"\"\"\n",
    "    N = 2 ** n\n",
    "    if iterations is None:\n",
    "        iterations = recommended_iterations(N, len(marked_bitstrings))\n",
    "    qc = QuantumCircuit(n, n)\n",
    "    qc.h(range(n))\n",
    "    for _ in range(iterations):\n",
    "        for bitstring in marked_bitstrings:\n",
    "            mark_state_qiskit(qc, bitstring)\n",
    "        diffusion_qiskit(qc, n)\n",
    "    for i in range(n):\n",
    "        qc.measure(i, n - 1 - i)\n",
    "    return qc\n",
    "\n",
    "\n",
    "def run_qiskit_counts(qc, shots=1000):\n",
    "    \"\"\"Ejecuta un circuito Qiskit con AerSimulator y devuelve conteos.\"\"\"\n",
    "    simulator = AerSimulator(seed_simulator=7)\n",
    "    tqc = transpile(qc, simulator)\n",
    "    result = simulator.run(tqc, shots=shots).result()\n",
    "    return result.get_counts()\n",
    "\n",
    "qc = grover_qiskit_circuit([\"101\"], n=3, iterations=2)\n",
    "print(qc)\n",
    "counts_qiskit = run_qiskit_counts(qc, shots=1000)\n",
    "counts_qiskit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0973faf1",
   "metadata": {},
   "outputs": [],
   "source": [
    "qc_two = grover_qiskit_circuit([\"101\", \"111\"], n=3, iterations=1)\n",
    "counts_qiskit_two = run_qiskit_counts(qc_two, shots=1000)\n",
    "counts_qiskit_two\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d3e9036",
   "metadata": {},
   "source": [
    "\n",
    "## 9. Ejercicio guiado 1: controles negativos\n",
    "\n",
    "**Enunciado.** En un registro de tres qubits se desea marcar $010$. ¿Qué qubits requieren controles negativos?\n",
    "\n",
    "**Desarrollo paso a paso.** La fase multi-controlada estándar reconoce el patrón $111$. Para que el patrón $010$ active esa fase, se deben convertir temporalmente sus ceros en unos. La cadena objetivo es\n",
    "\n",
    "$$\n",
    "010.\n",
    "$$\n",
    "\n",
    "Los ceros están en la primera y tercera posiciones, por lo que se aplican $X$ en esos qubits:\n",
    "\n",
    "$$\n",
    "\\left|010\\right\\rangle\n",
    "\\xrightarrow{X_1X_3}\n",
    "\\left|111\\right\\rangle.\n",
    "$$\n",
    "\n",
    "Después se aplica la fase multi-controlada:\n",
    "\n",
    "$$\n",
    "\\left|111\\right\\rangle\\longmapsto -\\left|111\\right\\rangle.\n",
    "$$\n",
    "\n",
    "Luego se deshacen los $X$:\n",
    "\n",
    "$$\n",
    "-\\left|111\\right\\rangle\n",
    "\\xrightarrow{X_1X_3}\n",
    "-\\left|010\\right\\rangle.\n",
    "$$\n",
    "\n",
    "**Justificación.** La fase multi-controlada no sabe reconocer ceros. Los $X$ convierten temporalmente controles negativos en controles positivos. La inversión final restaura la etiqueta original.\n",
    "\n",
    "**Interpretación.** El oráculo debe marcar exactamente el predicado deseado. Si se omite un control negativo, Grover amplificará el estado que realmente fue marcado, no el estado que se pretendía marcar.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d7a5c2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "qc_010 = grover_qiskit_circuit([\"010\"], n=3, iterations=2)\n",
    "run_qiskit_counts(qc_010, shots=1000)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58e80f98",
   "metadata": {},
   "source": [
    "\n",
    "## 10. Ejercicio guiado 2: estimar iteraciones\n",
    "\n",
    "**Enunciado.** Para $N=64$ y $k=4$, estima el número de iteraciones de Grover.\n",
    "\n",
    "**Desarrollo paso a paso.** La regla aproximada es\n",
    "\n",
    "$$\n",
    "r\\approx \\frac{\\pi}{4}\\sqrt{\\frac{N}{k}}.\n",
    "$$\n",
    "\n",
    "Sustituimos $N=64$ y $k=4$:\n",
    "\n",
    "$$\n",
    "r\\approx \\frac{\\pi}{4}\\sqrt{\\frac{64}{4}}.\n",
    "$$\n",
    "\n",
    "Primero se simplifica el cociente:\n",
    "\n",
    "$$\n",
    "\\frac{64}{4}=16.\n",
    "$$\n",
    "\n",
    "Después se calcula la raíz:\n",
    "\n",
    "$$\n",
    "\\sqrt{16}=4.\n",
    "$$\n",
    "\n",
    "Por tanto,\n",
    "\n",
    "$$\n",
    "r\\approx \\frac{\\pi}{4}\\cdot 4=\\pi\\approx 3.14.\n",
    "$$\n",
    "\n",
    "Como el circuito solo puede aplicar un número entero de iteraciones, se elige un entero cercano, típicamente $3$.\n",
    "\n",
    "**Interpretación.** Con cuatro soluciones, el subespacio marcado ocupa una fracción mayor del espacio que cuando $k=1$. Por eso se necesitan menos iteraciones: el estado inicial ya tiene una componente marcada más grande y requiere una rotación menor para acercarse al máximo de probabilidad.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76edad2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Iteraciones recomendadas para N=64, k=4:\", recommended_iterations(64, 4))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a218bf5",
   "metadata": {},
   "source": [
    "\n",
    "## 11. Ejercicio guiado 3: sobrerrotación\n",
    "\n",
    "**Enunciado.** Para $N=8$ y una solución marcada, compara la probabilidad de éxito al usar una, dos, tres y cuatro iteraciones.\n",
    "\n",
    "**Desarrollo matemático.** Con $N=8$ y $k=1$,\n",
    "\n",
    "$$\n",
    "\\sin^2\\theta=\\frac{k}{N}=\\frac{1}{8},\n",
    "\\qquad\n",
    "\\theta=\\arcsin\\left(\\frac{1}{\\sqrt{8}}\\right).\n",
    "$$\n",
    "\n",
    "Después de $r$ iteraciones, la probabilidad total de medir una solución es\n",
    "\n",
    "$$\n",
    "P_r=\\sin^2((2r+1)\\theta).\n",
    "$$\n",
    "\n",
    "Los valores aproximados son:\n",
    "\n",
    "$$\n",
    "P_0=\\frac{1}{8},\n",
    "\\qquad\n",
    "P_1\\approx 0.781,\n",
    "\\qquad\n",
    "P_2\\approx 0.945,\n",
    "\\qquad\n",
    "P_3\\approx 0.330.\n",
    "$$\n",
    "\n",
    "**Justificación.** La composición oráculo-difusión es una rotación en el plano marcado/no marcado. Al principio la rotación acerca el estado al subespacio marcado. Después de pasar el punto óptimo, seguir rotando lo aleja.\n",
    "\n",
    "**Interpretación.** Si una simulación empeora al aumentar iteraciones, no necesariamente hay un error de programación. Puede estar ocurriendo sobrerrotación. Grover no acumula probabilidad de forma irreversible; redistribuye amplitudes mediante operaciones unitarias.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9100a29e",
   "metadata": {},
   "outputs": [],
   "source": [
    "marked = [\"101\"]\n",
    "for r in [1, 2, 3, 4]:\n",
    "    final_state, _ = grover_statevector(3, marked, iterations=r)\n",
    "    prob_success = abs(final_state[int(marked[0], 2)])**2\n",
    "    print(f\"iteraciones={r}, probabilidad de éxito={prob_success:.4f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c893948f",
   "metadata": {},
   "source": [
    "\n",
    "## 12. Ejercicios propuestos con orientación matemática\n",
    "\n",
    "1. **Construye un oráculo que marque $011$.** Identifica primero los ceros de la cadena objetivo. En $011$ solo la primera posición es cero, por lo que se aplica $X$ en el primer qubit, después la fase multi-controlada y finalmente se deshace ese $X$.\n",
    "\n",
    "2. **Para $N=128$ y $k=2$, estima el número de iteraciones recomendado.** Usa\n",
    "\n",
    "   $$\n",
    "   r\\approx \\frac{\\pi}{4}\\sqrt{\\frac{N}{k}}\n",
    "   =\\frac{\\pi}{4}\\sqrt{\\frac{128}{2}}\n",
    "   =\\frac{\\pi}{4}\\sqrt{64}\n",
    "   =2\\pi\\approx 6.28.\n",
    "   $$\n",
    "\n",
    "   Un entero cercano es $6$.\n",
    "\n",
    "3. **Simula en Qiskit un caso con soluciones $001$ y $110$.** La interpretación correcta del histograma no es que el circuito haya probado todas las entradas una por una. El histograma debe concentrarse en las cadenas que el oráculo marcó porque la difusión amplifica el subespacio marcado.\n",
    "\n",
    "4. **Modifica deliberadamente un oráculo para marcar un estado equivocado.** Si el histograma amplifica otro estado, la conclusión no es que Grover falló. La conclusión es que el predicado implementado no coincide con el predicado deseado.\n",
    "\n",
    "5. **Explica por qué medir después del oráculo destruye la ventaja.** El oráculo cambia $a_x$ por $(-1)^{f(x)}a_x$, pero la probabilidad sigue siendo\n",
    "\n",
    "   $$\n",
    "   |(-1)^{f(x)}a_x|^2=|a_x|^2.\n",
    "   $$\n",
    "\n",
    "   La información todavía está en fase. Medir en ese punto elimina la coherencia antes de que la difusión convierta esa fase en probabilidad.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb37f381",
   "metadata": {},
   "source": [
    "## 13. Resumen final\n",
    "\n",
    "Grover resuelve búsqueda no estructurada por predicado. El algoritmo no inspecciona todos los candidatos como datos clásicos; prepara una superposición uniforme, marca soluciones por fase, aplica difusión para convertir fase en amplitud y repite ese proceso un número cuidadosamente elegido de veces.\n",
    "\n",
    "Las fórmulas esenciales son\n",
    "\n",
    "$$\n",
    "\\left|s\\right\\rangle=\\frac{1}{\\sqrt{N}}\\sum_x\\left|x\\right\\rangle,\n",
    "\\qquad\n",
    "O_f\\left|x\\right\\rangle=(-1)^{f(x)}\\left|x\\right\\rangle,\n",
    "\\qquad\n",
    "D=2\\left|s\\right\\rangle\\left\\langle s\\right|-I,\n",
    "\\qquad\n",
    "r\\approx\\frac{\\pi}{4}\\sqrt{\\frac{N}{k}}.\n",
    "$$\n",
    "\n",
    "La interpretación profunda es geométrica: el oráculo y la difusión son reflexiones, y su composición produce una rotación hacia el subespacio marcado. La ventaja frente a búsqueda clásica no estructurada es cuadrática en número de consultas."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}