{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a506218f",
   "metadata": {},
   "source": [
    "# Deutsch--Jozsa y Bernstein--Vazirani\n",
    "\n",
    "Este notebook es el material complementario ejecutable para el módulo. Contiene las derivaciones matemáticas completas, ejemplos desarrollados paso a paso y simulaciones en Qiskit. La presentación principal prioriza intuición e interpretación; aquí se conservan los detalles algebraicos y computacionales para estudio individual, verificación formal y práctica en JupyterLab, Anaconda o Google Colab.\n",
    "\n",
    "La idea unificadora es que el oráculo transforma información sobre una función booleana en fases relativas; Hadamard convierte esas fases en una salida medible. Deutsch--Jozsa usa este mecanismo para decidir si una función prometida es constante o balanceada. Bernstein--Vazirani lo usa para recuperar una cadena secreta $s$ que define una función lineal booleana."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3569f1db",
   "metadata": {},
   "source": [
    "## Objetivos de aprendizaje\n",
    "\n",
    "Al finalizar este notebook deberías poder:\n",
    "\n",
    "1. Formular el problema de Deutsch--Jozsa para $f:\\{0,1\\}^n\\to\\{0,1\\}$ bajo la promesa constante/balanceada.\n",
    "2. Explicar por qué el modelo clásico determinista requiere $2^{n-1}+1$ consultas en el peor caso para Deutsch--Jozsa.\n",
    "3. Derivar la identidad\n",
    "   $$\n",
    "   H^{\\otimes n}|x\\rangle=\\frac{1}{\\sqrt{2^n}}\\sum_{z\\in\\{0,1\\}^n}(-1)^{x\\cdot z}|z\\rangle.\n",
    "   $$\n",
    "4. Demostrar el *phase kickback*\n",
    "   $$\n",
    "   U_f|x\\rangle|-\\rangle=(-1)^{f(x)}|x\\rangle|-\\rangle.\n",
    "   $$\n",
    "5. Derivar la amplitud final de Deutsch--Jozsa.\n",
    "6. Formular Bernstein--Vazirani como recuperación de $s$ en $f_s(x)=x\\cdot s\\pmod 2$.\n",
    "7. Demostrar que Bernstein--Vazirani devuelve $|s\\rangle$ con probabilidad $1$ en el modelo ideal.\n",
    "8. Implementar oráculos y circuitos completos en Qiskit."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c4f6115",
   "metadata": {},
   "source": [
    "## 1. Fundamentos matemáticos\n",
    "\n",
    "Usaremos cadenas binarias $x=x_1x_2\\cdots x_n\\in\\{0,1\\}^n$ para etiquetar estados base:\n",
    "\n",
    "$$\n",
    "|x\\rangle=|x_1\\rangle\\otimes |x_2\\rangle\\otimes\\cdots\\otimes |x_n\\rangle.\n",
    "$$\n",
    "\n",
    "El producto interno módulo $2$ se define como\n",
    "\n",
    "$$\n",
    "x\\cdot z=x_1z_1\\oplus x_2z_2\\oplus\\cdots\\oplus x_nz_n.\n",
    "$$\n",
    "\n",
    "Este producto no mide ángulos geométricos usuales; cuenta la paridad de las posiciones en las que ambos vectores tienen un $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6c83a2c",
   "metadata": {},
   "source": [
    "### 1.1 Hadamard multidimensional\n",
    "\n",
    "Para un qubit,\n",
    "\n",
    "$$\n",
    "H|0\\rangle=\\frac{|0\\rangle+|1\\rangle}{\\sqrt 2},\\qquad\n",
    "H|1\\rangle=\\frac{|0\\rangle-|1\\rangle}{\\sqrt 2}.\n",
    "$$\n",
    "\n",
    "Ambos casos se escriben de forma compacta como\n",
    "\n",
    "$$\n",
    "H|x_i\\rangle=\\frac{1}{\\sqrt2}\\sum_{z_i\\in\\{0,1\\}}(-1)^{x_i z_i}|z_i\\rangle.\n",
    "$$\n",
    "\n",
    "Si $x_i=0$, el exponente $x_i z_i$ siempre es $0$, por lo que ambos signos son positivos. Si $x_i=1$, el término con $z_i=1$ recibe signo negativo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "034d021e",
   "metadata": {},
   "source": [
    "Para $n$ qubits:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "H^{\\otimes n}|x\\rangle\n",
    "&=\\bigotimes_{i=1}^{n}H|x_i\\rangle\\\\\n",
    "&=\\bigotimes_{i=1}^{n}\\left(\\frac{1}{\\sqrt2}\\sum_{z_i\\in\\{0,1\\}}(-1)^{x_i z_i}|z_i\\rangle\\right)\\\\\n",
    "&=\\frac{1}{\\sqrt{2^n}}\\sum_{z_1,\\ldots,z_n\\in\\{0,1\\}}(-1)^{x_1z_1+\\cdots+x_nz_n}|z_1\\cdots z_n\\rangle\\\\\n",
    "&=\\frac{1}{\\sqrt{2^n}}\\sum_{z\\in\\{0,1\\}^n}(-1)^{x\\cdot z}|z\\rangle.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Interpretación: $H^{\\otimes n}$ convierte una etiqueta $x$ en un patrón de signos sobre todas las etiquetas $z$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8356b57d",
   "metadata": {},
   "source": [
    "### 1.2 Oráculos reversibles y *phase kickback*\n",
    "\n",
    "Un oráculo booleano reversible se define por\n",
    "\n",
    "$$\n",
    "U_f|x\\rangle|y\\rangle=|x\\rangle|y\\oplus f(x)\\rangle.\n",
    "$$\n",
    "\n",
    "El segundo registro es necesario porque la transformación $|x\\rangle\\mapsto |f(x)\\rangle$ puede no ser reversible: muchas entradas distintas podrían tener el mismo valor de salida.\n",
    "\n",
    "El estado auxiliar clave es\n",
    "\n",
    "$$\n",
    "|-\\rangle=\\frac{|0\\rangle-|1\\rangle}{\\sqrt2}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05f00e53",
   "metadata": {},
   "source": [
    "Demostración completa del *phase kickback*:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U_f|x\\rangle|-\\rangle\n",
    "&=U_f|x\\rangle\\left(\\frac{|0\\rangle-|1\\rangle}{\\sqrt2}\\right)\\\\\n",
    "&=\\frac{1}{\\sqrt2}\\left(U_f|x\\rangle|0\\rangle-U_f|x\\rangle|1\\rangle\\right)\\\\\n",
    "&=\\frac{1}{\\sqrt2}\\left(|x\\rangle|0\\oplus f(x)\\rangle-|x\\rangle|1\\oplus f(x)\\rangle\\right).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Si $f(x)=0$:\n",
    "\n",
    "$$\n",
    "U_f|x\\rangle|-\\rangle=\\frac{|x\\rangle|0\\rangle-|x\\rangle|1\\rangle}{\\sqrt2}=|x\\rangle|-\\rangle.\n",
    "$$\n",
    "\n",
    "Si $f(x)=1$:\n",
    "\n",
    "$$\n",
    "U_f|x\\rangle|-\\rangle=\\frac{|x\\rangle|1\\rangle-|x\\rangle|0\\rangle}{\\sqrt2}=-|x\\rangle|-\\rangle.\n",
    "$$\n",
    "\n",
    "Por tanto,\n",
    "\n",
    "$$\n",
    "U_f|x\\rangle|-\\rangle=(-1)^{f(x)}|x\\rangle|-\\rangle.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22276001",
   "metadata": {},
   "source": [
    "## 2. Configuración de Qiskit\n",
    "\n",
    "El siguiente bloque instala Qiskit y Qiskit Aer si no están disponibles. En Google Colab esto normalmente descarga los paquetes. En JupyterLab o Anaconda, si ya están instalados, el bloque solo los importa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "39a273c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instalación/importación robusta para JupyterLab, Anaconda y Google Colab.\n",
    "import sys\n",
    "import subprocess\n",
    "\n",
    "try:\n",
    "    from qiskit import QuantumCircuit, transpile\n",
    "    from qiskit_aer import AerSimulator\n",
    "except ImportError:\n",
    "    subprocess.check_call([sys.executable, \"-m\", \"pip\", \"install\", \"qiskit\", \"qiskit-aer\"])\n",
    "    from qiskit import QuantumCircuit, transpile\n",
    "    from qiskit_aer import AerSimulator\n",
    "\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13477b7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_counts(circuit, shots=1024):\n",
    "    \"\"\"Ejecuta un circuito medido usando AerSimulator y devuelve conteos.\"\"\"\n",
    "    simulator = AerSimulator()\n",
    "    compiled = transpile(circuit, simulator)\n",
    "    result = simulator.run(compiled, shots=shots).result()\n",
    "    return result.get_counts(compiled)\n",
    "\n",
    "\n",
    "def print_counts(title, counts):\n",
    "    \"\"\"Imprime conteos ordenados para facilitar lectura.\"\"\"\n",
    "    print(title)\n",
    "    for bitstring, count in sorted(counts.items()):\n",
    "        print(f\"  {bitstring}: {count}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1e07770",
   "metadata": {},
   "source": [
    "## 3. Deutsch--Jozsa\n",
    "\n",
    "### 3.1 Problema\n",
    "\n",
    "Dada una función\n",
    "\n",
    "$$\n",
    "f:\\{0,1\\}^n\\to\\{0,1\\},\n",
    "$$\n",
    "\n",
    "se promete que ocurre exactamente uno de estos casos:\n",
    "\n",
    "1. **Constante:** $f(x)=c$ para todo $x$.\n",
    "2. **Balanceada:** $f(x)=0$ en exactamente $2^{n-1}$ entradas y $f(x)=1$ en exactamente $2^{n-1}$ entradas.\n",
    "\n",
    "El objetivo es decidir cuál caso ocurre.\n",
    "\n",
    "La pregunta no es: “¿cuáles son todos los valores de $f$?”. La pregunta es: “¿qué propiedad global tiene $f$?”."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a5c93ec",
   "metadata": {},
   "source": [
    "### 3.2 Costo clásico determinista\n",
    "\n",
    "Un algoritmo clásico determinista que requiere certeza debe considerar el peor caso.\n",
    "\n",
    "Si consulta $2^{n-1}$ entradas y todas producen el mismo valor, todavía existen dos posibilidades compatibles:\n",
    "\n",
    "- la función es constante;\n",
    "- la función es balanceada y todas las entradas consultadas pertenecen a la mitad con el mismo valor.\n",
    "\n",
    "Por eso se necesita una consulta adicional:\n",
    "\n",
    "$$\n",
    "2^{n-1}+1.\n",
    "$$\n",
    "\n",
    "El algoritmo cuántico usa una sola consulta porque no busca un valor opuesto por inspección; busca cancelación de amplitudes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee152677",
   "metadata": {},
   "source": [
    "### 3.3 Derivación del algoritmo Deutsch--Jozsa\n",
    "\n",
    "Estado inicial:\n",
    "\n",
    "$$\n",
    "|\\psi_0\\rangle=|0^n\\rangle|1\\rangle.\n",
    "$$\n",
    "\n",
    "Aplicamos Hadamard al registro de entrada y al auxiliar:\n",
    "\n",
    "$$\n",
    "|\\psi_1\\rangle=\\left(\\frac{1}{\\sqrt{2^n}}\\sum_{x\\in\\{0,1\\}^n}|x\\rangle\\right)|-\\rangle.\n",
    "$$\n",
    "\n",
    "Aplicamos el oráculo y usamos *phase kickback*:\n",
    "\n",
    "$$\n",
    "|\\psi_2\\rangle=\\frac{1}{\\sqrt{2^n}}\\sum_x(-1)^{f(x)}|x\\rangle|-\\rangle.\n",
    "$$\n",
    "\n",
    "El auxiliar ya no contiene la respuesta útil; permanece factorizado como $|-\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64184076",
   "metadata": {},
   "source": [
    "Aplicamos $H^{\\otimes n}$ al registro de entrada:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "|\\psi_3\\rangle\n",
    "&=\\frac{1}{\\sqrt{2^n}}\\sum_x(-1)^{f(x)}H^{\\otimes n}|x\\rangle|-\\rangle\\\\\n",
    "&=\\frac{1}{\\sqrt{2^n}}\\sum_x(-1)^{f(x)}\n",
    "\\left(\\frac{1}{\\sqrt{2^n}}\\sum_z(-1)^{x\\cdot z}|z\\rangle\\right)|-\\rangle\\\\\n",
    "&=\\sum_z\\left[\\frac{1}{2^n}\\sum_x(-1)^{f(x)+x\\cdot z}\\right]|z\\rangle|-\\rangle.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "La amplitud final de $|z\\rangle$ es\n",
    "\n",
    "$$\n",
    "\\alpha_z=\\frac{1}{2^n}\\sum_x(-1)^{f(x)+x\\cdot z}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f6248be",
   "metadata": {},
   "source": [
    "### 3.4 Interpretación de la amplitud\n",
    "\n",
    "La fórmula\n",
    "\n",
    "$$\n",
    "\\alpha_z=\\frac{1}{2^n}\\sum_x(-1)^{f(x)+x\\cdot z}\n",
    "$$\n",
    "\n",
    "puede leerse así:\n",
    "\n",
    "- cada entrada $x$ aporta un voto $+1$ o $-1$;\n",
    "- el valor $f(x)$ decide el signo escrito por el oráculo;\n",
    "- el término $x\\cdot z$ decide el signo del detector Hadamard;\n",
    "- la amplitud mide correlación entre ambos patrones.\n",
    "\n",
    "Para $z=0^n$:\n",
    "\n",
    "$$\n",
    "\\alpha_{0^n}=\\frac{1}{2^n}\\sum_x(-1)^{f(x)}.\n",
    "$$\n",
    "\n",
    "Si $f$ es constante, todos los signos son iguales y $|\\alpha_{0^n}|=1$. Si $f$ es balanceada, la mitad de signos son positivos y la mitad negativos, por lo que $\\alpha_{0^n}=0$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a0eb151",
   "metadata": {},
   "source": [
    "### 3.5 Regla de decisión\n",
    "\n",
    "En el modelo ideal:\n",
    "\n",
    "$$\n",
    "\\boxed{\\text{medir }0^n\\Rightarrow \\text{función constante}}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\boxed{\\text{medir algo distinto de }0^n\\Rightarrow \\text{función balanceada}}\n",
    "$$\n",
    "\n",
    "Esta regla solo es válida bajo la promesa constante/balanceada."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0661a98",
   "metadata": {},
   "source": [
    "### 3.6 Implementación de Deutsch--Jozsa en Qiskit\n",
    "\n",
    "Para mantener coherencia con la notación del texto, usaremos la convención: la cadena mostrada por Qiskit debe leerse en el mismo orden conceptual que los qubits de entrada. Por eso medimos el qubit $i$ en el bit clásico $n-1-i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "93295e51",
   "metadata": {},
   "outputs": [],
   "source": [
    "def constant_oracle(n, c=0):\n",
    "    \"\"\"Oráculo para f(x)=c. El qubit n es el auxiliar/salida.\"\"\"\n",
    "    qc = QuantumCircuit(n + 1, name=f\"const_{c}\")\n",
    "    if c == 1:\n",
    "        qc.x(n)\n",
    "    return qc\n",
    "\n",
    "\n",
    "def linear_balanced_oracle(mask):\n",
    "    \"\"\"Oráculo para f(x)=x·mask mod 2. Si mask no es cero, es balanceado.\"\"\"\n",
    "    n = len(mask)\n",
    "    qc = QuantumCircuit(n + 1, name=f\"balanced_{mask}\")\n",
    "    for i, bit in enumerate(mask):\n",
    "        if bit == \"1\":\n",
    "            qc.cx(i, n)\n",
    "    return qc\n",
    "\n",
    "\n",
    "def deutsch_jozsa_circuit(n, oracle):\n",
    "    \"\"\"Circuito completo de Deutsch--Jozsa.\"\"\"\n",
    "    qc = QuantumCircuit(n + 1, n)\n",
    "\n",
    "    # Prepara el auxiliar en |->.\n",
    "    qc.x(n)\n",
    "    qc.h(n)\n",
    "\n",
    "    # Superposición uniforme en el registro de entrada.\n",
    "    qc.h(range(n))\n",
    "\n",
    "    # Consulta al oráculo.\n",
    "    qc.compose(oracle, inplace=True)\n",
    "\n",
    "    # Interferencia final.\n",
    "    qc.h(range(n))\n",
    "\n",
    "    # Medición con orden legible de izquierda a derecha.\n",
    "    for i in range(n):\n",
    "        qc.measure(i, n - 1 - i)\n",
    "    return qc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ecf394e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ejemplo 1: función constante cero.\n",
    "n = 4\n",
    "oracle_c0 = constant_oracle(n, c=0)\n",
    "circuit_c0 = deutsch_jozsa_circuit(n, oracle_c0)\n",
    "counts_c0 = run_counts(circuit_c0)\n",
    "print_counts(\"Deutsch--Jozsa con función constante cero\", counts_c0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57758a6c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ejemplo 2: función balanceada f(x)=x_1 xor x_3, representada por mask=\"1010\".\n",
    "mask = \"1010\"\n",
    "oracle_bal = linear_balanced_oracle(mask)\n",
    "circuit_bal = deutsch_jozsa_circuit(len(mask), oracle_bal)\n",
    "counts_bal = run_counts(circuit_bal)\n",
    "print_counts(f\"Deutsch--Jozsa con función balanceada mask={mask}\", counts_bal)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec446f51",
   "metadata": {},
   "source": [
    "Interpretación de los resultados:\n",
    "\n",
    "- En el caso constante, los conteos deben concentrarse en `0000`.\n",
    "- En el caso balanceado lineal, los conteos deben concentrarse en una cadena distinta de `0000`.\n",
    "\n",
    "El punto conceptual no es que hayamos recuperado toda la tabla de verdad, sino que la interferencia final detectó si el paisaje de fase tenía componente uniforme."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f55c92c6",
   "metadata": {},
   "source": [
    "### 3.7 Ejercicio guiado Deutsch--Jozsa\n",
    "\n",
    "**Enunciado.** Para $n=2$, considere\n",
    "\n",
    "$$\n",
    "f(00)=0,\n",
    "\\quad f(01)=1,\n",
    "\\quad f(10)=1,\n",
    "\\quad f(11)=0.\n",
    "$$\n",
    "\n",
    "1. Clasifica la función.\n",
    "2. Predice si el resultado puede ser $00$.\n",
    "3. Explica qué significa físicamente la predicción.\n",
    "\n",
    "**Solución.** Hay dos ceros y dos unos; por tanto la función es balanceada. En Deutsch--Jozsa, las funciones balanceadas cancelan la amplitud de $|00\\rangle$. Por tanto, el resultado ideal no puede ser $00$.\n",
    "\n",
    "Físicamente, los caminos con signo positivo y negativo llegan al detector uniforme con amplitudes opuestas y se cancelan."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "faa1d215",
   "metadata": {},
   "source": [
    "## 4. Bernstein--Vazirani\n",
    "\n",
    "### 4.1 Problema\n",
    "\n",
    "Existe una cadena secreta $s\\in\\{0,1\\}^n$ tal que\n",
    "\n",
    "$$\n",
    "f_s(x)=x\\cdot s\\pmod 2.\n",
    "$$\n",
    "\n",
    "El objetivo es recuperar $s$.\n",
    "\n",
    "Si $s_i=1$, el bit $x_i$ participa en la paridad. Si $s_i=0$, el bit $x_i$ no afecta el valor de la función."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee405470",
   "metadata": {},
   "source": [
    "### 4.2 Estrategia clásica\n",
    "\n",
    "Sea $e_i$ el vector unitario con un único $1$ en la posición $i$. Entonces\n",
    "\n",
    "$$\n",
    "f_s(e_i)=e_i\\cdot s=s_i.\n",
    "$$\n",
    "\n",
    "Por tanto, un algoritmo clásico determinista puede recuperar $s$ con $n$ consultas:\n",
    "\n",
    "$$\n",
    "f_s(e_1)=s_1,\\quad f_s(e_2)=s_2,\\quad\\ldots,\\quad f_s(e_n)=s_n.\n",
    "$$\n",
    "\n",
    "El algoritmo cuántico recupera toda la cadena con una sola consulta, porque consulta en una base que convierte la regla lineal completa en un patrón de fase."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2682e2c0",
   "metadata": {},
   "source": [
    "### 4.3 Derivación cuántica\n",
    "\n",
    "Preparamos\n",
    "\n",
    "$$\n",
    "\\frac{1}{\\sqrt{2^n}}\\sum_x|x\\rangle|-\\rangle.\n",
    "$$\n",
    "\n",
    "Aplicamos el oráculo de $f_s$:\n",
    "\n",
    "$$\n",
    "\\frac{1}{\\sqrt{2^n}}\\sum_x|x\\rangle|-\\rangle\n",
    "\\longmapsto\n",
    "\\frac{1}{\\sqrt{2^n}}\\sum_x(-1)^{x\\cdot s}|x\\rangle|-\\rangle.\n",
    "$$\n",
    "\n",
    "Pero por la identidad de Hadamard:\n",
    "\n",
    "$$\n",
    "H^{\\otimes n}|s\\rangle=\\frac{1}{\\sqrt{2^n}}\\sum_x(-1)^{s\\cdot x}|x\\rangle.\n",
    "$$\n",
    "\n",
    "Como $s\\cdot x=x\\cdot s$, el registro de entrada está en $H^{\\otimes n}|s\\rangle$.\n",
    "\n",
    "Aplicamos Hadamard otra vez:\n",
    "\n",
    "$$\n",
    "H^{\\otimes n}H^{\\otimes n}|s\\rangle=|s\\rangle.\n",
    "$$\n",
    "\n",
    "La medición devuelve $s$ con probabilidad $1$ en el modelo ideal."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47f9fa7d",
   "metadata": {},
   "source": [
    "### 4.4 Implementación de Bernstein--Vazirani en Qiskit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fca385b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bv_oracle(s):\n",
    "    \"\"\"Oráculo de Bernstein--Vazirani para f_s(x)=x·s mod 2.\"\"\"\n",
    "    n = len(s)\n",
    "    qc = QuantumCircuit(n + 1, name=f\"bv_{s}\")\n",
    "    for i, bit in enumerate(s):\n",
    "        if bit == \"1\":\n",
    "            qc.cx(i, n)\n",
    "    return qc\n",
    "\n",
    "\n",
    "def bernstein_vazirani_circuit(s):\n",
    "    \"\"\"Circuito completo de Bernstein--Vazirani.\"\"\"\n",
    "    n = len(s)\n",
    "    qc = QuantumCircuit(n + 1, n)\n",
    "\n",
    "    # Auxiliar en |->.\n",
    "    qc.x(n)\n",
    "    qc.h(n)\n",
    "\n",
    "    # Entrada uniforme.\n",
    "    qc.h(range(n))\n",
    "\n",
    "    # Oráculo lineal.\n",
    "    qc.compose(bv_oracle(s), inplace=True)\n",
    "\n",
    "    # Decodificación por Hadamard.\n",
    "    qc.h(range(n))\n",
    "\n",
    "    # Medición con orden conceptual legible.\n",
    "    for i in range(n):\n",
    "        qc.measure(i, n - 1 - i)\n",
    "    return qc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a2ad183",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ejemplo BV: recuperar s = \"0110\".\n",
    "s = \"0110\"\n",
    "bv_circ = bernstein_vazirani_circuit(s)\n",
    "bv_counts = run_counts(bv_circ)\n",
    "print_counts(f\"Bernstein--Vazirani con s={s}\", bv_counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "767dc3b6",
   "metadata": {},
   "source": [
    "Interpretación: si los conteos se concentran en `0110`, el simulador confirma que la interferencia final reconstruyó la cadena secreta. La salida no es un valor $f(x)$, sino el parámetro estructural que define la función."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99f26e6e",
   "metadata": {},
   "source": [
    "### 4.5 Ejercicio guiado Bernstein--Vazirani\n",
    "\n",
    "**Enunciado.** Supón que una función prometida satisface\n",
    "\n",
    "$$\n",
    "f(100)=1,\n",
    "\\qquad f(010)=1,\n",
    "\\qquad f(001)=0.\n",
    "$$\n",
    "\n",
    "Si $f(x)=x\\cdot s$, recupera $s$.\n",
    "\n",
    "**Desarrollo.** Cada consulta a un vector unitario revela un bit de $s$:\n",
    "\n",
    "$$\n",
    "f(100)=s_1=1,\n",
    "$$\n",
    "\n",
    "$$\n",
    "f(010)=s_2=1,\n",
    "$$\n",
    "\n",
    "$$\n",
    "f(001)=s_3=0.\n",
    "$$\n",
    "\n",
    "Por tanto,\n",
    "\n",
    "$$\n",
    "s=110.\n",
    "$$\n",
    "\n",
    "**Interpretación.** La función depende de los dos primeros bits y no depende del tercero. El algoritmo cuántico obtendría `110` en una sola consulta coherente."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91ff20b2",
   "metadata": {},
   "source": [
    "## 5. Comparación conceptual\n",
    "\n",
    "| Aspecto | Deutsch--Jozsa | Bernstein--Vazirani |\n",
    "|---|---|---|\n",
    "| Promesa | constante o balanceada | lineal $x\\cdot s$ |\n",
    "| Pregunta | ¿qué categoria tiene $f$? | ¿cuál es $s$? |\n",
    "| Salida ideal | $0^n$ o distinto de $0^n$ | $s$ |\n",
    "| Papel del oráculo | crear un paisaje de fase | crear el paisaje de fase de una máscara lineal |\n",
    "| Papel de Hadamard | detectar componente uniforme | invertir el cambio de base y recuperar $s$ |\n",
    "\n",
    "La lección principal es que el circuito no debe interpretarse aislado. La promesa del problema determina qué significa la medición."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c77a6d9",
   "metadata": {},
   "source": [
    "## 6. Ejercicios propuestos\n",
    "\n",
    "### Ejercicio 1: Deutsch--Jozsa conceptual\n",
    "\n",
    "Para $n=3$, una función prometida tiene cuatro entradas con salida $0$ y cuatro con salida $1$.\n",
    "\n",
    "1. ¿Qué tipo de función es?\n",
    "2. ¿Puede el algoritmo devolver `000` en el modelo ideal?\n",
    "3. ¿Qué fenómeno físico explica tu respuesta?\n",
    "\n",
    "**Respuesta esperada.** Es balanceada. No debe devolver `000`. El fenómeno físico es interferencia destructiva en la amplitud del componente uniforme.\n",
    "\n",
    "### Ejercicio 2: Bernstein--Vazirani conceptual\n",
    "\n",
    "Si el resultado ideal del algoritmo BV es `1001`, explica qué bits de entrada afectan la función.\n",
    "\n",
    "**Respuesta esperada.** Participan el primer y el cuarto bit; los bits intermedios no afectan la paridad.\n",
    "\n",
    "### Ejercicio 3: condición alterada\n",
    "\n",
    "¿Qué falla si en lugar de preparar el auxiliar en $|-\\rangle$ se prepara en $|+\\rangle$?\n",
    "\n",
    "**Respuesta esperada.** Como $X|+\\rangle=|+\\rangle$, el oráculo no produce el signo dependiente de $f(x)$. Sin el paisaje de fase, la interferencia final no codifica la propiedad buscada."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "431e4314",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Verificación programática de varios casos BV.\n",
    "for secret in [\"0000\", \"1001\", \"1111\", \"0101\"]:\n",
    "    circ = bernstein_vazirani_circuit(secret)\n",
    "    counts = run_counts(circ, shots=256)\n",
    "    print_counts(f\"s={secret}\", counts)\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e74623e",
   "metadata": {},
   "source": [
    "## 7. Resumen final\n",
    "\n",
    "Deutsch--Jozsa y Bernstein--Vazirani comparten una estructura:\n",
    "\n",
    "$$\n",
    "|0^n\\rangle|1\\rangle\n",
    "\\longrightarrow\n",
    "\\frac{1}{\\sqrt{2^n}}\\sum_x|x\\rangle|-\\rangle\n",
    "\\longrightarrow\n",
    "\\frac{1}{\\sqrt{2^n}}\\sum_x(-1)^{f(x)}|x\\rangle|-\\rangle\n",
    "\\longrightarrow\n",
    "\\text{medición informativa}.\n",
    "$$\n",
    "\n",
    "La diferencia está en la promesa:\n",
    "\n",
    "- En Deutsch--Jozsa, la promesa permite decidir constante frente a balanceada.\n",
    "- En Bernstein--Vazirani, la promesa lineal permite recuperar la cadena secreta $s$.\n",
    "\n",
    "El concepto que debes conservar es: los oráculos no solo devuelven valores; usados coherentemente, pueden escribir fases. La interferencia convierte esas fases en información computacional observable."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}