{ "cells": [ { "cell_type": "markdown", "id": "76d7b924", "metadata": {}, "source": [ "---\n", "title: \"Algoritmo de Grover\"\n", "description: \"Utiliza el algoritmo de Grover para realizar búsquedas en una base de datos no estructurada con una aceleración cuadrática.\"\n", "---\n", "\n", "{/* cspell:ignore fontsize */}\n", "\n", "\n", "\n", "# Algoritmo de Grover\n", "\n", "*Tiempo estimado de ejecución: menos de un minuto en un procesador Eagle r3 (NOTA: Se trata únicamente de una estimación). (El tiempo de ejecución puede variar.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "88aa4204", "metadata": {}, "source": [ "\n", "\n", "## Resultados del aprendizaje\n", "\n", "Una vez completado este tutorial, habrás adquirido los siguientes conocimientos:\n", "\n", "* Cómo construir oráculos de Grover que marquen uno o más estados de la base computacional\n", "* Cómo utilizar la `grover_operator()` función de la biblioteca de circuitos de Qiskit\n", "* Cómo determinar el número óptimo de iteraciones de Grover para un problema determinado\n", "* Cómo ejecutar el algoritmo de Grover utilizando la primitiva « Qiskit Runtime » del sampler\n", "\n", "\n", "\n", "## Requisitos previos\n", "\n", "Se recomienda que te familiarices con estos temas:\n", "\n", "* [Fundamentos de los algoritmos cuánticos: el algoritmo de Grover](/learning/courses/fundamentals-of-quantum-algorithms/grover-algorithm/introduction)\n", "* [Fundamentos de la información cuántica](/learning/courses/basics-of-quantum-information)\n", "\n", "\n", "\n", "## En segundo plano\n", "\n", "La amplificación de amplitud es un algoritmo cuántico de uso general, o subrutina, que puede utilizarse para obtener una aceleración cuadrática con respecto a varios algoritmos clásicos. [El algoritmo de Grover](https://arxiv.org/abs/quant-ph/9605043) fue el primero en demostrar esta mejora en la velocidad en problemas de búsqueda no estructurados. Para formular un problema de búsqueda de Grover se necesita una función oráculo que marque uno o varios estados de la base computacional como los estados que nos interesa encontrar, y un circuito de amplificación que aumente la amplitud de los estados marcados, suprimiendo así los estados restantes.\n", "\n", "Aquí, demostramos cómo construir oráculos de Grover y utilizar el [`grover_operator()`](/docs/api/qiskit/qiskit.circuit.library.grover_operator) de la biblioteca de circuitos Qiskit para configurar fácilmente una instancia de búsqueda de Grover. La primitiva de ejecución `Sampler` permite ejecutar circuitos Grover sin problemas.\n", "\n" ] }, { "cell_type": "markdown", "id": "5bbba268", "metadata": {}, "source": [ "\n", "\n", "## Requisitos\n", "\n", "Antes de comenzar este tutorial, asegúrate de tener instalado lo siguiente:\n", "\n", "* Qiskit SDK v2.0 o posterior, con soporte [para visualización](/docs/api/qiskit/visualization)\n", "* Qiskit Runtime v0.22 o posterior (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "bfccad15", "metadata": {}, "source": [ "\n", "\n", "## Configuración\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "e2cb0472", "metadata": {}, "outputs": [], "source": [ "# Built-in modules\n", "import math\n", "\n", "# Imports from Qiskit\n", "from qiskit import QuantumCircuit\n", "from qiskit.circuit.library import grover_operator, MCMTGate, ZGate\n", "from qiskit.visualization import plot_distribution\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "# Imports from Qiskit Runtime\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler\n", "\n", "\n", "def grover_oracle(marked_states):\n", " \"\"\"Build a Grover oracle for multiple marked states\n", "\n", " Here we assume all input marked states have the same number of bits\n", "\n", " Parameters:\n", " marked_states (str or list): Marked states of oracle\n", "\n", " Returns:\n", " QuantumCircuit: Quantum circuit representing Grover oracle\n", " \"\"\"\n", " if not isinstance(marked_states, list):\n", " marked_states = [marked_states]\n", " # Compute the number of qubits in circuit\n", " num_qubits = len(marked_states[0])\n", "\n", " qc = QuantumCircuit(num_qubits)\n", " # Mark each target state in the input list\n", " for target in marked_states:\n", " # Flip target bit-string to match Qiskit bit-ordering\n", " rev_target = target[::-1]\n", " # Find the indices of all the '0' elements in bit-string\n", " zero_inds = [\n", " ind\n", " for ind in range(num_qubits)\n", " if rev_target.startswith(\"0\", ind)\n", " ]\n", " # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)\n", " # where the target bit-string has a '0' entry\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " return qc" ] }, { "cell_type": "markdown", "id": "77e41aba", "metadata": {}, "source": [ "\n", "\n", "## Ejemplo de simulador a pequeña escala\n", "\n", "En esta sección, repasamos cada paso del algoritmo de Grover a pequeña escala utilizando un simulador local, antes de ejecutar el mismo problema en hardware cuántico real.\n", "\n" ] }, { "cell_type": "markdown", "id": "0c0fb667", "metadata": {}, "source": [ "\n", "\n", "### Paso 1: Asignar entradas clásicas a un problema cuántico\n", "\n", "El algoritmo de Grover requiere un [oráculo](/learning/modules/computer-science/grovers#introduction) que especifique uno o más estados de base computacional «marcados», donde «marcado» significa un estado con una fase de -1. Una puerta de Z controlada, o su generalización multiconrolada sobre qubits de tipo « $N$ », define el estado « $2^{N}-1$ » (`'1'`\\*cadena de bits $N$ ). Para marcar los estados de base con uno o más `'0'` en la representación binaria, es necesario aplicar puertas X a los qubits correspondientes antes y después de la puerta Z controlada, lo que equivale a aplicar una puerta de control abierto a ese qubit. En el siguiente código, definimos un oráculo que identifica uno o varios estados de base de entrada definidos mediante su representación en cadena de bits. La `MCMT` puerta se utiliza para implementar la puerta Z multicontrolada.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "bca14740", "metadata": {}, "source": [ "\n", "\n", "### Instancia específica de Grover\n", "\n", "Ahora que tenemos la función oráculo, podemos definir una instancia específica de búsqueda Grover. En este ejemplo marcaremos dos estados computacionales de los ocho disponibles en un espacio computacional de tres qubits:\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "c150298f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "oracle.draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "25487b93", "metadata": {}, "source": [ "\n", "\n", "### Operador Grover\n", "\n", "El built-in Qiskit `grover_operator()` toma un circuito de oráculo y devuelve un circuito que se compone del propio circuito de oráculo y un circuito que amplifica los estados marcados por el oráculo. Aquí, utilizamos el método `decompose()` el circuito para ver las puertas dentro del operador:\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "283d5265", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grover_op = grover_operator(oracle)\n", "grover_op.decompose().draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "83c34dc9", "metadata": {}, "source": [ "Las aplicaciones repetidas de este circuito `grover_op` amplifican los estados marcados, convirtiéndolos en las cadenas de bits más probables en la distribución de salida del circuito. Existe un número óptimo de estas aplicaciones que viene determinado por la relación entre los estados marcados y el número total de estados computacionales posibles:\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "f4c3d4b5", "metadata": {}, "outputs": [], "source": [ "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "e06c8238", "metadata": {}, "source": [ "\n", "\n", "### Circuito Grover completo\n", "\n", "Un experimento Grover completo comienza con una puerta Hadamard en cada qubit; creando una superposición par de todos los estados base computacionales, seguido del operador Grover (`grover_op`) repetido el número óptimo de veces. Aquí utilizamos el método `QuantumCircuit.power(INT)` para aplicar repetidamente el operador Grover.\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "4933ae44", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "qc = QuantumCircuit(grover_op.num_qubits)\n", "# Create even superposition of all basis states\n", "qc.h(range(grover_op.num_qubits))\n", "# Apply Grover operator the optimal number of times\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "# Measure all qubits\n", "qc.measure_all()\n", "qc.draw(output=\"mpl\", style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "0649c854", "metadata": {}, "source": [ "\n", "\n", "### Paso 2: Optimizar el problema para la ejecución en hardware cuántico\n", "\n", "Para la simulación a pequeña escala, compilamos el circuito sin orientarlo a un hardware concreto.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "c4f67f35", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pm = generate_preset_pass_manager(optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "circuit_isa.draw(output=\"mpl\", idle_wires=False, style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "4e0d4d90", "metadata": {}, "source": [ "\n", "\n", "### Paso 3: Ejecutar utilizando Qiskit primitives\n", "\n", "La amplificación de amplitud es un problema de muestreo que se presta a ser resuelto mediante la [`SamplerV2`](/docs/api/qiskit-ibm-runtime/sampler-v2) primitiva. Aquí utilizamos el `StatevectorSampler` de `qiskit.primitives` para la simulación local.\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "7666ad7c", "metadata": {}, "outputs": [], "source": [ "from qiskit.primitives import StatevectorSampler\n", "\n", "sampler = StatevectorSampler()\n", "result = sampler.run([circuit_isa], shots=10_000).result()\n", "dist = result[0].data.meas.get_counts()" ] }, { "cell_type": "markdown", "id": "5c8263c7", "metadata": {}, "source": [ "\n", "\n", "### Paso 4: Procesamiento posterior y devolución del resultado en el formato clásico deseado\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "a5ef9913", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "2b45b2ee", "metadata": {}, "source": [ "\n", "\n", "## Ejemplo de hardware\n", "\n" ] }, { "cell_type": "markdown", "id": "5fb22680", "metadata": {}, "source": [ "\n", "\n", "### Pasos 1 a 4\n", "\n", "El algoritmo de Grover es, en esencia, un algoritmo tolerante a fallos: las puertas Z multicontroladas que constituyen el núcleo del oráculo y del operador de difusión dan lugar a profundidades de puerta de dos qubits que aumentan muy rápidamente con el número de qubits (como demostraremos en la siguiente sección). Esto significa que el algoritmo no se adapta bien al hardware actual, que suele presentar interferencias. Por este motivo, mostramos la ejecución en hardware a la misma escala reducida que el ejemplo del simulador anterior, en lugar de intentar abordar un problema de mayor envergadura.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "be3c3d9e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# -------------------------Step 1-------------------------\n", "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "grover_op = grover_operator(oracle)\n", "\n", "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")\n", "\n", "qc = QuantumCircuit(grover_op.num_qubits)\n", "qc.h(range(grover_op.num_qubits))\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "qc.measure_all()\n", "\n", "# -------------------------Step 2-------------------------\n", "service = QiskitRuntimeService()\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "\n", "# -------------------------Step 3-------------------------\n", "sampler = Sampler(mode=backend)\n", "sampler.options.default_shots = 10_000\n", "sampler.options.environment.job_tags = [\"TUT-GA\"]\n", "result = sampler.run([circuit_isa]).result()\n", "dist = result[0].data.meas.get_counts()\n", "\n", "# -------------------------Step 4-------------------------\n", "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "12e72eab", "metadata": {}, "source": [ "\n", "\n", "## Debate: Escalabilidad de la profundidad de las puertas de dos qubits\n", "\n", "Una de las razones principales por las que el algoritmo de Grover se considera un algoritmo tolerante a fallos es el rápido aumento de la profundidad de las puertas de dos qubits del circuito a medida que aumenta el número de qubits. La puerta Z multicontrolada, que constituye el núcleo tanto del oráculo como del operador de difusión, se descompone en una serie de puertas de dos qubits cuyo número crece exponencialmente con el número de qubits de control. Si a esto le sumamos que el número óptimo de iteraciones de Grover crece a un ritmo de $O(\\sqrt{2^n})$, la profundidad total de dos qubits pronto resulta inviable para un hardware con ruido.\n", "\n", "A continuación, construimos circuitos de Grover para un número creciente de qubits, los transpilamos y representamos gráficamente la profundidad de las puertas de dos qubits resultante para ilustrar esta escalabilidad.\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "abc6b43c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=3: optimal_iters=2, 2Q depth=39\n", "n=4: optimal_iters=3, 2Q depth=111\n", "n=5: optimal_iters=4, 2Q depth=466\n", "n=6: optimal_iters=6, 2Q depth=1646\n", "n=7: optimal_iters=8, 2Q depth=3550\n", "n=8: optimal_iters=12, 2Q depth=7989\n", "n=9: optimal_iters=17, 2Q depth=14824\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "num_qubits_list = list(range(3, 10))\n", "two_q_depths = []\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "for n in num_qubits_list:\n", " # Mark a single state for simplicity\n", " marked = [\"1\" * n]\n", " oracle_n = grover_oracle(marked)\n", " grover_op_n = grover_operator(oracle_n)\n", "\n", " # Optimal number of iterations\n", " num_iters = math.floor(\n", " math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))\n", " )\n", "\n", " # Build the full Grover circuit\n", " qc_n = QuantumCircuit(n)\n", " qc_n.h(range(n))\n", " qc_n.compose(grover_op_n.power(num_iters), inplace=True)\n", " qc_n.measure_all()\n", "\n", " # Transpile to a basis gate set and count 2Q depth\n", " pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)\n", " qc_transpiled = pm_n.run(qc_n)\n", "\n", " # Compute depth restricted to 2-qubit operations\n", " depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)\n", "\n", " two_q_depths.append(depth_2q)\n", " print(f\"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}\")\n", "\n", "# Plot\n", "fig, ax = plt.subplots(figsize=(8, 5))\n", "ax.plot(\n", " num_qubits_list,\n", " two_q_depths,\n", " \"o-\",\n", " linewidth=2,\n", " markersize=8,\n", " color=\"#6929C4\",\n", ")\n", "ax.set_xlabel(\"Number of qubits\", fontsize=13)\n", "ax.set_ylabel(\"Two-qubit gate depth\", fontsize=13)\n", "ax.set_title(\"Grover's algorithm: 2Q depth scaling\", fontsize=14)\n", "ax.set_yscale(\"log\")\n", "ax.grid(True, alpha=0.3)\n", "ax.set_xticks(num_qubits_list)\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "f3ddda55", "metadata": {}, "source": [ "Como muestra el gráfico, la profundidad de las puertas de dos qubits aumenta muy rápidamente con el número de qubits, más o menos de forma exponencial. Esto hace que el algoritmo de Grover resulte poco práctico en el hardware cuántico actual, que adolece de ruido, salvo en el caso de problemas de tamaño muy reducido. El algoritmo sigue siendo un objetivo importante para los futuros ordenadores cuánticos tolerantes a fallos, en los que la corrección de errores permitirá ejecutar circuitos profundos de forma fiable.\n", "\n" ] }, { "cell_type": "markdown", "id": "cf6e8fe6", "metadata": {}, "source": [ "\n", "\n", "## Próximos pasos\n", "\n", "\n", " Si te ha parecido interesante este trabajo, quizá te interese el siguiente material:\n", "\n", " * [Biblioteca de circuitos de Qiskit: `grover_operator()` Referencia de la API](/docs/api/qiskit/qiskit.circuit.library.grover_operator)\n", " * [El tutorial](/docs/tutorials/quantum-approximate-optimization-algorithm) sobre QAOA y [la lección sobre QAOA a escala industrial](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa) ofrecen ejemplos recientes de optimización con ordenadores cuánticos\n", " * Para obtener información más detallada sobre los algoritmos a corto plazo, consulta el curso [«La computación cuántica en la práctica».](/learning/courses/quantum-computing-in-practice)\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" }, "hours": 1, "qpuSeconds": 60 }, "nbformat": 4, "nbformat_minor": 5 }