{ "cells": [ { "cell_type": "markdown", "id": "bfa8f443", "metadata": {}, "source": [ "---\n", "title: \"El algoritmo Deutsch-Jozsa\"\n", "description: \"Descubra cómo el algoritmo Deutsch-Jozsa utiliza el paralelismo cuántico y la interferencia para lograr una aceleración exponencial con respecto a los algoritmos clásicos.\"\n", "---\n", "\n", "{/* cspell:ignore blackbox Hadamards */}\n", "\n" ] }, { "cell_type": "markdown", "id": "e761a401-3dd0-4c3c-9333-0d89da48fb34", "metadata": {}, "source": [ "\n", "\n", "# El algoritmo Deutsch-Jozsa\n", "\n", "Para este módulo de Qiskit en las aulas, los estudiantes deben tener un entorno Python en funcionamiento con los siguientes paquetes instalados:\n", "\n", "* `qiskit` v2.1.0 o más reciente\n", "* `qiskit-ibm-runtime` v0.40.1 o más reciente\n", "* `qiskit-aer` v0.17.0 o más reciente\n", "* `qiskit.visualization`\n", "* `numpy`\n", "* `pylatexenc`\n", "\n", "Para configurar e instalar los paquetes anteriores, consulta la guía [Instalar Qiskit](/docs/guides/install-qiskit).\n", "Para ejecutar trabajos en ordenadores cuánticos reales, los estudiantes deberán crear una cuenta en IBM Quantum® siguiendo los pasos de la guía [Configure su cuenta IBM Cloud](/docs/guides/cloud-setup).\n", "\n", "Este módulo fue probado y utilizó cuatro segundos de tiempo QPU. Esto es sólo una estimación. Su uso real puede variar.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "24a83c6d", "metadata": {}, "outputs": [], "source": [ "# Uncomment and modify this line as needed to install dependencies\n", "#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'" ] }, { "cell_type": "markdown", "id": "026f7f82-ac54-413d-8158-e58461bc2afd", "metadata": {}, "source": [ "Vea el tutorial del módulo de la Dra. Katie McCormick a continuación, o haga clic [aquí](https://youtu.be/QcK0GK7DUh8?si=8e0Lmjgylxmgl2y7) para verlo en YouTube.\n", "\n", "***\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "34b2aac3-848f-46b4-8c95-8236b6ad7f8e", "metadata": {}, "source": [ "\n", "\n", "## Introducción\n", "\n", "A principios de los años 80, los físicos cuánticos y los informáticos tenían la vaga idea de que la mecánica cuántica podía aprovecharse para realizar cálculos mucho más potentes que los de los ordenadores clásicos. Su razonamiento era el siguiente: es difícil para un ordenador clásico simular sistemas cuánticos, pero un ordenador *cuántico* debería ser capaz de hacerlo de forma más eficiente. Y si un ordenador cuántico podía simular sistemas cuánticos de forma más eficiente, quizá hubiera otras tareas que pudiera realizar de forma más eficiente que un ordenador clásico.\n", "\n", "La lógica era sólida, pero quedaban por concretar los detalles. Esto empezó en 1985, cuando David Deutsch describió el primer \"ordenador cuántico universal\" En este mismo artículo, proporcionó el primer ejemplo de problema para el que un ordenador cuántico podía resolver algo de forma más eficiente que un ordenador clásico. Este primer ejemplo de juguete se conoce ahora como \"algoritmo de Deutsch\" La mejora del algoritmo de Deutsch fue modesta, pero Deutsch trabajó con Richard Jozsa unos años más tarde para ampliar aún más la brecha entre los ordenadores clásicos y los cuánticos.\n", "\n", "Estos algoritmos -el de Deutsch y la extensión Deutsch-Jozsa- no son especialmente útiles, pero siguen siendo muy importantes por varias razones:\n", "\n", "1. Históricamente, fueron algunos de los primeros algoritmos cuánticos que demostraron superar a sus homólogos clásicos. Comprenderlos puede ayudarnos a entender cómo ha evolucionado el pensamiento de la comunidad sobre la computación cuántica a lo largo del tiempo.\n", "2. Pueden ayudarnos a comprender algunos aspectos de la respuesta a una pregunta sorprendentemente sutil: ¿Qué confiere a la informática cuántica su potencia? A veces, los ordenadores cuánticos se comparan con procesadores paralelos gigantes de escala exponencial. Pero esto no es del todo correcto. Aunque una parte de la respuesta a esta pregunta reside en el llamado \"paralelismo cuántico\", extraer la máxima información posible en una sola ejecución es un arte sutil. Los algoritmos Deutsch y Deutsch-Jozsa muestran cómo hacerlo.\n", "\n", "En este módulo aprenderemos sobre el algoritmo de Deutsch, el algoritmo de Deutsch-Jozsa y lo que nos enseñan sobre el poder de la computación cuántica.\n", "\n" ] }, { "cell_type": "markdown", "id": "096da154-5663-4f46-8d9e-b6f163260706", "metadata": {}, "source": [ "\n", "\n", "## El paralelismo cuántico y sus límites\n", "\n", "Parte de la potencia de la computación cuántica se deriva del \"paralelismo cuántico\" que es esencialmente la capacidad de realizar operaciones en múltiples entradas al mismo tiempo, ya que los estados de entrada del qubit podrían estar en una superposición de múltiples estados permitidos clásicamente. SIN EMBARGO, aunque un circuito cuántico podría ser capaz de evaluar múltiples estados de entrada a la vez, extraer toda esa información de una sola vez es imposible.\n", "\n", "Para ver a qué me refiero, supongamos que tenemos un bit, $x$ y una función aplicada a ese bit, $f(x)$. Hay cuatro posibles funciones binarias que llevan un único bit a otro único bit:\n", "\n", "| $x$ | $f_1(x)$ | $f_2(x)$ | $f_3(x)$ | $f_4(x)$ |\n", "| --- | -------- | -------- | -------- | -------- |\n", "| 0 | 0 | 0 | 1 | 1 |\n", "| 1 | 0 | 1 | 0 | 1 |\n", "\n", "Nos gustaría saber cuál de estas funciones (1-4) es nuestra $f(x)$. Clásicamente, tendríamos que ejecutar la función dos veces - una para $x=0$, otra para $x=1$. Pero veamos si podemos hacerlo mejor con un circuito cuántico. Podemos conocer la función con la siguiente puerta:\n", "\n", "![quantum\\_parallelism](https://eu-de.quantum.cloud.ibm.com/learning/images/modules/computer-science/deutsch-jozsa/quantum-parallelism.avif)\n", "\n", "Aquí, la puerta $U_f$ calcula $f(x)$, donde $x$ es el estado del qubit 0, y lo aplica al qubit 1. Así, el estado resultante, $|x\\rangle|y\\oplus f(x)\\rangle$, simplemente se convierte en $|x\\rangle|f(x)\\rangle$ cuando $|y\\rangle = |0\\rangle$. Esto contiene toda la información que necesitamos para conocer la función $f(x)$ : el qubit 0 nos dice qué es $x$, y el qubit 1 nos dice qué es $f(x)$. Así, si inicializamos $|x\\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$, entonces el estado final de ambos qubits será: $|y\\rangle|x\\rangle = \\frac{1}{\\sqrt{2}}(|f(0)\\rangle|0\\rangle+|f(1)\\rangle|1\\rangle)$. Pero, ¿cómo accedemos a esa información?\n", "\n", "\n", "\n", "### 2.1. Pruébal en Qiskit:\n", "\n", "Utilizando Qiskit seleccionaremos al azar una de las cuatro funciones posibles anteriores y ejecutaremos el circuito. A continuación, su tarea consiste en utilizar las mediciones del circuito cuántico para aprender la función en el menor número de ejecuciones posible.\n", "\n", "En este primer experimento y a lo largo de todo el módulo, utilizaremos un marco para la computación cuántica conocido como \"patrones Qiskit\", que divide los flujos de trabajo en los siguientes pasos:\n", "\n", "* Paso 1: Asignar entradas clásicas a un problema cuántico\n", "* Paso 2: Optimizar el problema para la ejecución cuántica\n", "* Paso 3: Ejecutar utilizando Qiskit Runtime Primitives\n", "* Etapa 4: Tratamiento posterior y análisis clásico\n", "\n", "Empecemos cargando algunos paquetes necesarios, incluidas las primitivas Qiskit Runtime. También seleccionaremos el ordenador cuántico menos ocupado de que dispongamos.\n", "\n", "A continuación encontrará un código para guardar sus credenciales la primera vez que las utilice. Asegúrate de borrar esta información del cuaderno después de guardarlo en tu entorno, para que tus credenciales no se compartan accidentalmente cuando compartas el cuaderno. Consulte [Configurar su cuenta IBM Cloud](/docs/guides/initialize-account) e [Inicializar el servicio en un entorno no](/docs/guides/cloud-setup-untrusted) fiable para obtener más orientación.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "6ccc7364-7b6b-45f5-94b8-b1274006ee2f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ibm_brisbane\n" ] } ], "source": [ "# Load the Qiskit Runtime service\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "\n", "# Load the Runtime primitive and session\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler\n", "\n", "# Syntax for first saving your token. Delete these lines after saving your credentials.\n", "\n", "# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',\n", "# instance = '', token='', overwrite=True, set_as_default=True)\n", "# service = QiskitRuntimeService(channel='ibm_quantum_platform')\n", "\n", "# Load saved credentials\n", "service = QiskitRuntimeService()\n", "\n", "# Use the least busy backend, or uncomment the loading of a specific backend like \"ibm_brisbane\".\n", "# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)\n", "backend = service.backend(\"ibm_brisbane\")\n", "print(backend.name)\n", "\n", "\n", "sampler = Sampler(mode=backend)" ] }, { "cell_type": "markdown", "id": "9912a7c5-ce2b-4eaa-abe7-82ebd4e494c8", "metadata": {}, "source": [ "La celda de abajo te permitirá cambiar entre usar el simulador o el hardware real a lo largo del cuaderno. Recomendamos ejecutarlo ahora:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "29468e63-ce36-4eb7-95b4-176788a97e54", "metadata": {}, "outputs": [], "source": [ "# Load the backend sampler\n", "from qiskit.primitives import BackendSamplerV2\n", "\n", "# Load the Aer simulator and generate a noise model based on the currently-selected backend.\n", "from qiskit_aer import AerSimulator\n", "from qiskit_aer.noise import NoiseModel\n", "\n", "# Alternatively, load a fake backend with generic properties and define a simulator.\n", "\n", "\n", "noise_model = NoiseModel.from_backend(backend)\n", "\n", "# Define a simulator using Aer, and use it in Sampler.\n", "backend_sim = AerSimulator(noise_model=noise_model)\n", "sampler_sim = BackendSamplerV2(backend=backend_sim)\n", "\n", "# You could also define a simulator-based sampler using a generic backend:\n", "# backend_gen = GenericBackendV2(num_qubits=18)\n", "# sampler_gen = BackendSamplerV2(backend=backend_gen)" ] }, { "cell_type": "markdown", "id": "19e9b62f-6e1c-43a1-bdda-75766b1ff7d3", "metadata": {}, "source": [ "Ahora que hemos cargado los paquetes necesarios, podemos proceder con el flujo de trabajo de los patrones Qiskit. En el siguiente paso de mapeo, primero hacemos una función que selecciona entre las cuatro posibles funciones que llevan un único bit a otro único bit.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "5e67183b-42b9-44c2-bd4b-b5e2d192a796", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Step 1: Map\n", "\n", "from qiskit import QuantumCircuit\n", "\n", "qc = QuantumCircuit(2)\n", "\n", "\n", "def twobit_function(case: int):\n", " \"\"\"\n", " Generate a valid two-bit function as a `QuantumCircuit`.\n", " \"\"\"\n", " if case not in [1, 2, 3, 4]:\n", " raise ValueError(\"`case` must be 1, 2, 3, or 4.\")\n", "\n", " f = QuantumCircuit(2)\n", " if case in [2, 3]:\n", " f.cx(0, 1)\n", " if case in [3, 4]:\n", " f.x(1)\n", " return f\n", "\n", "\n", "# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the\n", "# circuit is too large to display\n", "\n", "# you may edit the number inside \"twobit_function()\" to select among the four valid functions:\n", "# blackbox = twobit_function(2).to_gate()\n", "\n", "# blackbox.label = \"$U_f$\"\n", "\n", "qc.h(0)\n", "qc.barrier()\n", "qc.compose(twobit_function(2), inplace=True)\n", "qc.measure_all()\n", "\n", "\n", "qc.draw(\"mpl\")" ] }, { "cell_type": "markdown", "id": "5cf08592-f32e-4ae8-ad69-afb160e43ab4", "metadata": {}, "source": [ "En el circuito anterior, la puerta Hadamard \"H\" lleva el qubit 0, que se encuentra inicialmente en el estado $|0\\rangle$, al estado de superposición $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$. A continuación, $U_f$ evalúa la función $f(x)$ y la aplica al qubit 1.\n", "\n", "A continuación tenemos que optimizar y transpilar el circuito para que funcione en el ordenador cuántico:\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "d8d77417-0295-4f20-aff6-b2a007d5d02f", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc)" ] }, { "cell_type": "markdown", "id": "51e7b705-a4b8-460a-aa5a-6122c84f9b2f", "metadata": {}, "source": [ "Por último, ejecutamos nuestro circuito transpilado en el ordenador cuántico y visualizamos nuestros resultados:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "0495256b-2a80-422e-9adf-2fef1c039a6d", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.meas.get_counts()" ] }, { "cell_type": "code", "execution_count": 6, "id": "6d2904cc-c730-4dca-a167-438018230299", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "from qiskit.visualization import plot_histogram\n", "\n", "plot_histogram(counts)" ] }, { "cell_type": "markdown", "id": "47710bb8-372c-4949-9468-bd2480c4ae5b", "metadata": {}, "source": [ "Arriba se muestra un histograma de nuestros resultados. Dependiendo del número de disparos que elijas para ejecutar el circuito en el paso 3 anterior, podrías ver una o dos barras, representando los estados medidos de los dos qubits en cada disparo. Como siempre con Qiskit y en este cuaderno, utilizamos notación \"little endian\", lo que significa que los estados de los qubits 0 a n se escriben en orden ascendente de derecha a izquierda, por lo que el qubit 0 siempre está más a la derecha.\n", "\n", "Así, como el qubit 0 estaba en un estado de superposición, el circuito evaluó la función *tanto* para $x=0$ como para $x=1$ *al mismo tiempo*, ¡algo que los ordenadores clásicos no pueden hacer! Pero la trampa viene cuando queremos aprender sobre la función $f(x)$ - cuando medimos los qubits, colapsamos su estado. Si selecciona \"disparos = 1\" para ejecutar el circuito una sola vez, sólo verá una barra en el histograma de arriba, y su información sobre la función estará incompleta.\n", "\n", "\n", "\n", "#### Comprueba tu comprensión\n", "\n", "¿Cuántas veces debemos ejecutar el algoritmo anterior para aprender la función $f(x)$? ¿Es esto mejor que en el caso clásico? ¿Preferiría un ordenador clásico o cuántico para resolver este problema?\n", "\n", "\n", " \n", " Dado que la medición colapsará la superposición y devolverá sólo un valor, necesitamos ejecutar el circuito *al menos* dos veces para devolver ambas salidas de la función $f(0)$ y $f(1)$. En el mejor de los casos, esto funciona tan bien como en el caso clásico, en el que calculamos tanto $f(0)$ como $f(1)$ en las dos primeras consultas. Pero existe la posibilidad de que tengamos que ejecutarlo más de dos veces, ya que la medición final es probabilística y podría devolver el mismo valor $f(x)$ las dos primeras veces. En este caso preferiría un ordenador clásico.\n", " \n", "\n", "\n", "Así pues, aunque el paralelismo cuántico puede ser potente si se utiliza de la forma adecuada, no es correcto afirmar que un ordenador cuántico funciona igual que un procesador paralelo masivo clásico. El acto de medir colapsa los estados cuánticos, por lo que sólo podemos acceder a un único resultado del cálculo.\n", "\n" ] }, { "cell_type": "markdown", "id": "cda50fdf-c354-4021-9b5a-c8cde5cc5edd", "metadata": {}, "source": [ "\n", "\n", "## Algoritmo de Deutsch\n", "\n", "Aunque el paralelismo cuántico por sí solo no nos da ventaja sobre los ordenadores clásicos, podemos combinarlo con otro fenómeno cuántico, la interferencia, para conseguir una mayor velocidad. El algoritmo ahora conocido como \"algoritmo de Deutsch\" es el primer ejemplo de un algoritmo que logra esto.\n", "\n", "\n", "\n", "### El problema\n", "\n", "Aquí estaba el problema:\n", "\n", "Dado un bit de entrada, $x = \\{0,1\\}$, y una función de entrada $f(x) = \\{0,1\\}$, determine si la función es *equilibrada* o *constante*. Es decir, si está equilibrada, la salida de la función es 0 la mitad del tiempo y 1 la otra mitad. Si es constante, entonces la salida de la función es siempre 0 o siempre 1. Recordemos la tabla de las cuatro funciones posibles que llevan un único bit a otro único bit:\n", "\n", "| $x$ | $f_1(x)$ | $f_2(x)$ | $f_3(x)$ | $f_4(x)$ |\n", "| --- | -------- | -------- | -------- | -------- |\n", "| 0 | 0 | 0 | 1 | 1 |\n", "| 1 | 0 | 1 | 0 | 1 |\n", "\n", "La primera y la última función, $f_1(x)$ y $f_4(x)$, son constantes, mientras que las dos del medio, $f_2(x)$ y $f_3(x)$, están equilibradas.\n", "\n" ] }, { "cell_type": "markdown", "id": "a34f1c24-0ed5-4458-8d4e-5957c691cadb", "metadata": {}, "source": [ "\n", "\n", "### El algoritmo\n", "\n", "La forma en que Deutsch abordó este problema fue a través del \"modelo de consulta\" En el modelo de consulta, la función de entrada ( $f_i(x)$ arriba) está contenida en una \"caja negra\" - no tenemos acceso directo a su contenido, pero podemos consultar la caja negra y nos dará la salida de la función. A veces decimos que un \"oráculo\" proporciona esta información. Ver [Lección 1: Algoritmos Cuánticos de Consulta](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/introduction) del curso Fundamentos de Algoritmos Cuánticos para más información sobre el modelo de consulta.\n", "\n", "Para determinar si un algoritmo cuántico es más eficiente que un algoritmo clásico en el modelo de consulta, podemos simplemente comparar el número de consultas que necesitamos hacer a la caja negra en cada caso. En el caso clásico, para saber si la función contenida en la caja negra era equilibrada o constante, tendríamos que consultar la caja dos veces para obtener tanto $f(0)$ como $f(1)$.\n", "\n", "Sin embargo, el algoritmo cuántico de Deutsch encontró la forma de obtener la información con una sola consulta Hizo un ajuste en el circuito de \"paralelismo cuántico\" anterior, de modo que preparó un estado de superposición en *ambos* qubits, en lugar de sólo en el qubit 0. Entonces las dos salidas de la función, $f(0)$ y $f(1)$ interferían para devolver 0 si eran ambas 0 o ambas 1 (la función era constante), y devolvían 1 si eran diferentes (la función era equilibrada). De este modo, Deutsch podía diferenciar entre una constante y una función equilibrada con una sola consulta.\n", "\n", "Aquí tienes un esquema del algoritmo de Deutsch:\n", "\n", "![Esquema del algoritmo de Deutsch](https://eu-de.quantum.cloud.ibm.com/learning/images/modules/computer-science/deutsch-jozsa/Deutsch_algo.avif)\n", "\n", "Para entender cómo funciona este algoritmo, observemos los estados cuánticos de los qubits en los tres puntos señalados en el diagrama anterior. Intenta resolver los estados por ti mismo antes de hacer clic para ver las respuestas:\n", "\n", "\n", "\n", "#### Comprueba tu comprensión\n", "\n", "¿Cuál es el estado $|\\pi_1\\rangle$?\n", "\n", "\n", " \n", " Aplicando una transformación de Hadamard, el estado $|0\\rangle$ pasa a ser $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$ y el estado $|1\\rangle$ pasa a ser $\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$. Así, el estado completo pasa a ser $|\\pi_1\\rangle = [\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}][\\frac{|0\\rangle+|1\\rangle}{\\sqrt{2}}]$\n", " \n", "\n", "\n", "¿Cuál es el estado $|\\pi_2\\rangle$?\n", "\n", "\n", " \n", " Antes de aplicar $U_f$, recuerde lo que hace. Cambiará el estado del qubit 1 en función del estado del qubit 0. Por lo tanto, tiene sentido factorizar el estado del qubit 0: $|\\pi_1\\rangle = \\frac{1}{2} (|0\\rangle-|1\\rangle)|0\\rangle+\\frac{1}{2}(|0\\rangle-|1\\rangle)|1\\rangle$. Entonces, si $f(0)=f(1)$, los dos términos se transformarán de la misma manera y el signo relativo entre los dos términos seguirá siendo positivo, pero si $f(0)\\neq f(1)$, entonces eso significa que el segundo término recogerá un signo menos relativo al primer término, cambiando el estado del qubit 0 de $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$ a $\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$. Entonces:\n", "\n", " $$\n", " |\\pi_2\\rangle = \\begin{cases}\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}][\\frac{|0\\rangle+|1\\rangle}{\\sqrt{2}}] & \\text{if} & f(0) = f(1) \\\\\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}][\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}] &\\text{if} & f(0) \\neq f(1) \\\\\n", " \\end{cases}\n", " $$\n", " \n", "\n", "\n", "¿Cuál es el estado $|\\pi_3\\rangle$?\n", "\n", "\n", " \n", " Ahora, el estado del qubit 0 es $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$ o $\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$, dependiendo de la función. Aplicando el Hadamard se obtendrá $|0\\rangle$ o $|1\\rangle$, respectivamente.\n", "\n", " $$\n", " |\\pi_3\\rangle = \\begin{cases}\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}]|0\\rangle & \\text{if} & f(0) = f(1) \\\\\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}]|1\\rangle &\\text{if} & f(0) \\neq f(1) \\\\\n", " \\end{cases}\n", " $$\n", " \n", "\n", "\n", "Al repasar tus respuestas a las preguntas anteriores, observa que ocurre algo un poco sorprendente. Aunque $U_f$ no hace nada explícitamente al estado del qubit 0, debido a que cambia el qubit 1 basándose en el estado del qubit 0, puede ocurrir que esto provoque un desplazamiento de fase en el qubit 0. Esto se conoce como el fenómeno de \"retroceso de fase\" y se analiza con más detalle en [la Lección 1: Algoritmos de consulta cuántica](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/introduction) del curso Fundamentos de algoritmos cuánticos.\n", "\n", "Ahora que entendemos cómo funciona este algoritmo, vamos a implementarlo con Qiskit.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "4d9129df-f2ef-4f94-9508-21ed986fd823", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "## Deutsch's algorithm:\n", "\n", "## Step 1: Map the problem\n", "\n", "# first, convert oracle circuit (above) to a single gate for drawing purposes.\n", "# otherwise, the circuit is too large to display\n", "blackbox = twobit_function(\n", " 3\n", " # you may edit the number (1-4) inside \"twobit_function()\" to select among the four valid functions\n", ").to_gate()\n", "blackbox.label = \"$U_f$\"\n", "\n", "\n", "qc_deutsch = QuantumCircuit(2, 1)\n", "\n", "qc_deutsch.x(1)\n", "qc_deutsch.h(range(2))\n", "\n", "qc_deutsch.barrier()\n", "qc_deutsch.compose(twobit_function(2), inplace=True)\n", "qc_deutsch.barrier()\n", "\n", "qc_deutsch.h(0)\n", "qc_deutsch.measure(0, 0)\n", "\n", "qc_deutsch.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 8, "id": "ef0196b4-d4f0-4581-96f8-97893e652ee8", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc_deutsch)" ] }, { "cell_type": "code", "execution_count": null, "id": "51ad01d0-fa90-4e80-a55d-e55e146e2065", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.c.get_counts()" ] }, { "cell_type": "code", "execution_count": 10, "id": "5465d833-49e0-4779-94a3-0adb18f6aa76", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'1': 1}\n", "balanced\n" ] } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "print(counts)\n", "if \"1\" in counts:\n", " print(\"balanced\")\n", "else:\n", " print(\"constant\")" ] }, { "cell_type": "markdown", "id": "82f6da25-0f9c-47b3-aa24-02482f008383", "metadata": {}, "source": [ "\n", "\n", "## El algoritmo Deutsch-Jozsa\n", "\n", "El algoritmo de Deutsch fue un primer paso importante para demostrar cómo un ordenador cuántico podría ser más eficiente que uno clásico, pero sólo supuso una modesta mejora: sólo requería una consulta, frente a las dos del caso clásico. En 1992, Deutsch y su colega Richard Jozsa ampliaron el algoritmo original de dos qubits a más qubits. El problema seguía siendo el mismo: determinar si una función es *equilibrada* o *constante*. Pero esta vez, la función pasa de $n$ bits a un solo bit. O bien la función devuelve 0 y 1 el mismo número de veces (es *equilibrada* ) o bien la función devuelve siempre 1 o siempre 0 (es *constante* ).\n", "\n", "Aquí tienes un esquema del algoritmo:\n", "\n", "![DJ\\_algo.png](https://eu-de.quantum.cloud.ibm.com/learning/images/modules/computer-science/deutsch-jozsa/DJ_algo.avif)\n", "\n", "Este algoritmo funciona de la misma manera que el algoritmo de Deutsch: el retroceso de fase permite leer el estado del qubit 0 para determinar si la función es constante o equilibrada. Es un poco más complicado de ver que en el caso del algoritmo de Deutsch de dos qubits, ya que los estados incluirán sumas sobre los $n$ qubits, por lo que la resolución de esos estados se dejará como ejercicio opcional al final del módulo. El algoritmo devolverá una cadena de bits con todos 0 si la función es constante, y una cadena de bits que contiene al menos un 1 si la función es equilibrada.\n", "\n", "Para ver cómo funciona el algoritmo en Qiskit, primero, necesitamos generar nuestro oráculo: la función aleatoria que está garantizada para ser constante o equilibrada. El código siguiente generará una función equilibrada el 50% de las veces, y una función constante el 50% de las veces. No se preocupe si no sigue completamente el código: es complicado y no es necesario para nuestra comprensión del algoritmo cuántico.\n", "\n" ] }, { "cell_type": "code", "execution_count": 11, "id": "ca2a51c0-3e62-4536-b891-0834e325a3d6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from qiskit import QuantumCircuit\n", "import numpy as np\n", "\n", "\n", "def dj_function(num_qubits):\n", " \"\"\"\n", " Create a random Deutsch-Jozsa function.\n", " \"\"\"\n", "\n", " qc_dj = QuantumCircuit(num_qubits + 1)\n", " if np.random.randint(0, 2):\n", " # Flip output qubits with 50% chance\n", " qc_dj.x(num_qubits)\n", " if np.random.randint(0, 2):\n", " # return constant circuit with 50% chance.\n", " return qc_dj\n", "\n", " # If the \"if\" statement above was \"TRUE\" then we've returned the constant\n", " # function and the function is complete. If not, we proceed in creating our\n", " # balanced function. Everything below is to produce the balanced function:\n", "\n", " # select half of all possible states at random:\n", " on_states = np.random.choice(\n", " range(2**num_qubits), # numbers to sample from\n", " 2**num_qubits // 2, # number of samples\n", " replace=False, # makes sure states are only sampled once\n", " )\n", "\n", " def add_cx(qc_dj, bit_string):\n", " for qubit, bit in enumerate(reversed(bit_string)):\n", " if bit == \"1\":\n", " qc_dj.x(qubit)\n", " return qc_dj\n", "\n", " for state in on_states:\n", " # qc_dj.barrier() # Barriers are added to help visualize how the functions are created.\n", " # They can safely be removed.\n", " qc_dj = add_cx(qc_dj, f\"{state:0b}\")\n", " qc_dj.mcx(list(range(num_qubits)), num_qubits)\n", " qc_dj = add_cx(qc_dj, f\"{state:0b}\")\n", "\n", " # qc_dj.barrier()\n", "\n", " return qc_dj\n", "\n", "\n", "n = 3 # number of input qubits\n", "\n", "oracle = dj_function(n)\n", "\n", "display(oracle.draw(\"mpl\"))" ] }, { "cell_type": "markdown", "id": "78096e00-a29b-418c-a620-726675c2a792", "metadata": {}, "source": [ "Se trata de la función oráculo, que puede ser equilibrada o constante. ¿Puedes ver si la salida en el último qubit depende de los valores introducidos en los primeros $n$ qubits? Si la salida del último qubit depende de los primeros $n$ qubits, ¿se puede saber si esa salida dependiente está equilibrada o no?\n", "\n", "Podemos saber si la función es equilibrada o constante observando el circuito anterior, pero recuerda que, para este problema, pensamos en esta función como una \"caja negra\" No podemos asomarnos a la caja para ver el esquema del circuito. En su lugar, tenemos que consultar la caja.\n", "\n", "Para consultar la caja, utilizamos el algoritmo Deutsch-Jozsa y determinamos si la función es constante o equilibrada:\n", "\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "fe7ee688-f052-4a7e-bcc7-a14bea57e5c6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "blackbox = oracle.to_gate()\n", "blackbox.label = \"$U_f$\"\n", "\n", "\n", "qc_dj = QuantumCircuit(n + 1, n)\n", "qc_dj.x(n)\n", "qc_dj.h(range(n + 1))\n", "qc_dj.barrier()\n", "qc_dj.compose(blackbox, inplace=True)\n", "qc_dj.barrier()\n", "qc_dj.h(range(n))\n", "qc_dj.measure(range(n), range(n))\n", "\n", "qc_dj.decompose().decompose()\n", "\n", "\n", "qc_dj.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 13, "id": "bf3aedfa-7454-424e-85cb-c446a8918417", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Step 1: Map the problem\n", "\n", "qc_dj = QuantumCircuit(n + 1, n)\n", "qc_dj.x(n)\n", "qc_dj.h(range(n + 1))\n", "qc_dj.barrier()\n", "qc_dj.compose(oracle, inplace=True)\n", "qc_dj.barrier()\n", "qc_dj.h(range(n))\n", "qc_dj.measure(range(n), range(n))\n", "\n", "qc_dj.decompose().decompose()\n", "\n", "\n", "qc_dj.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 14, "id": "5497c1aa-c427-419b-b22c-a0c2fa0c4028", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc_dj)" ] }, { "cell_type": "code", "execution_count": null, "id": "974f3db9-1b55-414c-9fe4-d891cf22f78f", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.c.get_counts()" ] }, { "cell_type": "code", "execution_count": 16, "id": "39af76b4-f380-4a61-82a4-1e9203c20408", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'110': 1}\n", "balanced\n" ] } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "print(counts)\n", "\n", "if (\n", " \"0\" * n in counts\n", "): # The D-J algorithm returns all zeroes if the function was constant\n", " print(\"constant\")\n", "else:\n", " print(\"balanced\") # anything other than all zeroes means the function is balanced." ] }, { "cell_type": "markdown", "id": "c601a252-d1d4-4def-b9a4-d05494d34899", "metadata": {}, "source": [ "Arriba, la primera línea de la salida es la cadena de bits de los resultados de la medición. La segunda línea muestra si la cadena de bits implica que la función era equilibrada o constante. Si la cadena de bits contenía todos ceros, era constante; si no, estaba equilibrada. Así pues, con una sola ejecución del circuito cuántico anterior, ¡podemos determinar si la función es constante o equilibrada!\n", "\n", "\n", "\n", "#### Comprueba tu comprensión\n", "\n", "¿Cuántas consultas necesitaría un ordenador clásico para determinar con un 100% de certeza si una función es constante o equilibrada? Recuerde que, clásicamente, una única consulta sólo permite aplicar la función a una única cadena de bits.\n", "\n", "\n", " \n", " Hay $2^n$ posibles cadenas de bits que comprobar y, en el peor de los casos, tendría que comprobar $2^n/2+1$ de ellas. Por ejemplo, si la función fuera constante y siguieras midiendo \"1\" como salida de la función, no podrías estar seguro de que fuera realmente constante hasta que comprobaras más de la mitad de los resultados. Antes de eso, puede que tuvieras muy mala suerte si seguías midiendo \"1\" en una función equilibrada. Es como lanzar una moneda al aire una y otra vez y que siempre salga cara. Es poco probable, pero no imposible.\n", " \n", "\n", "\n", "¿Cómo cambiaría tu respuesta anterior si sólo tuvieras que medir hasta que un resultado (equilibrado o constante) fuera más probable que el otro? ¿Cuántas consultas serían necesarias en este caso?\n", "\n", "\n", " \n", " En este caso, basta con medir dos veces. Si las dos medidas son diferentes, sabrás que la función está equilibrada. Si las dos mediciones son iguales, entonces podría estar equilibrado, o podría ser constante. La probabilidad de que esté equilibrada con este conjunto de medidas es: $\\frac{1}{2}\\frac{2^n /2 - 1}{2^n-1}$. Esto es menos de 1/2, por lo que es más probable que la función sea constante en este caso.\n", " \n", "\n", "\n", "Así, el algoritmo Deutsch-Jozsa demostró un aumento exponencial de la velocidad con respecto a un algoritmo *determinista* clásico (que devuelve la respuesta con un 100% de certeza), pero no un aumento significativo de la velocidad con respecto a uno *probabilista* (que devuelve un resultado que *probablemente* sea la respuesta correcta).\n", "\n" ] }, { "cell_type": "markdown", "id": "37d8d1b5-1593-480e-afb9-cdae1debb8ea", "metadata": {}, "source": [ "\n", "\n", "### El problema de Bernstein-Vazirani\n", "\n", "En 1997, Ethan Bernstein y Umesh Vazirani utilizaron el algoritmo Deutsch-Jozsa para resolver un problema más específico y restringido que el problema Deutsch-Jozsa. En lugar de tratar simplemente de distinguir entre dos clases diferentes de funciones, como en el caso D-J, Bernstein y Vazirani utilizaron el algoritmo Deutsch-Jozsa para aprender realmente una cadena codificada en una función. He aquí el problema:\n", "\n", "La función $f:\\{0,1\\}^n \\rightarrow \\{0,1\\}$ sigue tomando una cadena $n$ -bit y emite un único bit. Pero ahora, en lugar de prometer que la función es equilibrada o constante, se nos promete que la función es el producto punto entre la cadena de entrada $x$ y alguna cadena secreta de $n$ -bit $s$, módulo 2. (Este producto punto módulo 2 se denomina \"producto punto binario\") El problema es averiguar cuál es la cadena secreta, $n$ -bit.\n", "\n", "Dicho de otro modo, nos dan una función de caja negra $f: {0,1}^n \\rightarrow {0,1}$ que satisface $f(x) = s \\cdot x$ para alguna cadena $s$, y queremos aprender la cadena $s$.\n", "\n", "Veamos cómo resuelve este problema el algoritmo D-J:\n", "\n", "1. En primer lugar, se aplica una puerta Hadamard a los qubits de entrada $n$, y una puerta NOT más una Hadamard al qubit de salida, formando el estado:\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle_{n} \\otimes |+\\rangle_{n-1} \\otimes |+\\rangle_{n-2} \\otimes ... \\otimes |+\\rangle_0\n", "$$\n", "\n", "El estado de los qubits 1 a $n$ puede escribirse más sencillamente como una suma sobre todos $2^n$ los estados base $n$ -qubit $|00...00\\rangle, |00...01\\rangle, |000...11\\rangle, ..., |111...11\\rangle$. Llamamos al conjunto de estos estados base $\\Sigma^n$. (Para más detalles, véase [Fundamentos de los algoritmos cuánticos](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/deutsch-jozsa-algorithm) )\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle \\otimes \\frac{1}{\\sqrt{2^n}}\\sum\\limits_{x \\in \\Sigma^n}{|x\\rangle}\n", "$$\n", "\n", "2. A continuación, se aplica la puerta $U_f$ a los qubits. Esta puerta tomará los primeros n qubits como entrada (que ahora están en una superposición igual de todas las posibles cadenas de n bits) y aplica la función $f(x)=s \\cdot x$ al qubit de salida, de modo que este qubit está ahora en el estado: $ |- \\oplus f(x)\\rangle$. Gracias al mecanismo de retroceso de fase, el estado de este qubit permanece inalterado, pero algunos de los términos del estado del qubit de entrada adquieren un signo menos:\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle \\otimes \\frac{1}{\\sqrt{2^n}}\\sum\\limits_{x \\in \\Sigma^n}{(-1)^{f(x)}|x\\rangle}\n", "$$\n", "\n", "3. Ahora, el siguiente conjunto de Hadamards se aplica a los qubits 0 a $n-1$. No perder de vista los signos menos en este caso puede ser complicado. Es útil saber que la aplicación de una capa de Hadamards a $n$ qubits en un estado de base estándar $|x\\rangle$ se puede escribir como:\n", "\n", "$$\n", "H^{\\otimes n} |x\\rangle = \\frac{1}{\\sqrt{2^n}}\\sum\\limits_{y \\in \\Sigma^n}{(-1)^{x \\cdot y}|y\\rangle}\n", "$$\n", "\n", "Así que el estado se convierte:\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle \\otimes \\frac{1}{2^n}\\sum\\limits_{x \\in \\Sigma^n}\\sum\\limits_{y \\in \\Sigma^n}{(-1)^{(s \\cdot x) + (x \\cdot y)}|y\\rangle}\n", "$$\n", "\n", "4. El siguiente paso es medir los primeros $n$ bits. Pero, ¿qué mediremos? Resulta que el estado anterior se simplifica a: $|\\Psi\\rangle = |-\\rangle \\otimes |s\\rangle$, pero eso está lejos de ser obvio. Si quieres seguir las matemáticas, consulta el curso [Fundamentos de los algoritmos cuánticos](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/deutsch-jozsa-algorithm#the-bernstein-vazirani-problem) de John Watrous. La cuestión es, sin embargo, que el mecanismo de contragolpe de fase lleva a que los qubits de entrada estén en el estado $|s\\rangle$. Por tanto, para averiguar cuál era la cadena secreta $s$, basta con medir los qubits\n", "\n", "\n", "\n", "#### Comprueba tu comprensión\n", "\n", "Verifique que el estado del paso 3 anterior es efectivamente el estado $|s\\rangle$ para el caso especial de $n=1$.\n", "\n", "\n", " \n", " Cuando escribes explícitamente las dos sumas, deberías obtener un estado con cuatro términos (vamos a omitir el estado de salida $|-\\rangle$ para esto):\n", "\n", " $$\n", " |\\Psi\\rangle = \\frac{1}{2}[|0\\rangle + (-1)^s |0\\rangle + |1\\rangle + (-1)^{(s+1)} |1\\rangle]\n", " $$\n", "\n", " Si $s=0$, entonces los dos primeros términos se suman constructivamente y los dos últimos se cancelan, lo que nos deja $|\\Psi\\rangle = |0\\rangle$. Si $s=1$, entonces los dos últimos términos se suman constructivamente y los dos primeros se cancelan, lo que nos deja $|\\Psi\\rangle = |1\\rangle$. Por tanto, en cualquier caso, $|\\Psi\\rangle = |s\\rangle$. Esperemos que este caso más simple te dé una idea de cómo funciona el caso general con qubits $n$ : todos los términos que no son $|s\\rangle$ interfieren, dejando sólo el estado $|s\\rangle$.\n", " \n", "\n", "\n", "¿Cómo puede el mismo algoritmo resolver los problemas de Bernstein-Vazirani y Deutsch-Jozsa? Para entender esto, piense en las funciones Bernstein-Vazirani, que son de la forma $f(x) = s \\cdot x$. ¿Son también funciones de Deutsch-Jozsa? Es decir, determinar si las funciones de esta forma satisfacen la promesa del problema de Deutsch-Jozsa: que sean *constantes* o *equilibradas*. ¿Cómo nos ayuda esto a entender cómo el mismo algoritmo resuelve dos problemas diferentes?\n", "\n", "\n", " \n", " Toda función Bernstein-Vazirani de la forma $f(x) = s \\cdot x$ también satisface la promesa del problema Deutsch-Jozsa: si s=00...00, entonces la función es constante (siempre devuelve 0 para cada cadena x). Si s es cualquier otra cadena, la función se equilibra. Así, aplicando el algoritmo Deutsch-Jozsa a una de estas funciones, se resuelven simultáneamente ambos problemas Devuelve la cadena, y si esa cadena es 00...00 entonces sabemos que es constante; si hay al menos un \"1\" en la cadena, sabemos que está equilibrada.\n", " \n", "\n", "\n", "También podemos verificar que este algoritmo resuelve con éxito el problema Bernstein-Vazirani probándolo experimentalmente. En primer lugar, creamos la función B-V que vive dentro de la caja negra:\n", "\n" ] }, { "cell_type": "code", "execution_count": 17, "id": "45449a26-0bd0-4244-87be-3309937955b9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Step 1: Map the problem\n", "\n", "\n", "def bv_function(s):\n", " \"\"\"\n", " Create a Bernstein-Vazirani function from a string of 1s and 0s.\n", " \"\"\"\n", " qc = QuantumCircuit(len(s) + 1)\n", " for index, bit in enumerate(reversed(s)):\n", " if bit == \"1\":\n", " qc.cx(index, len(s))\n", " return qc\n", "\n", "\n", "display(bv_function(\"1000\").draw(\"mpl\"))" ] }, { "cell_type": "code", "execution_count": 18, "id": "0cf6f2bc-3b5e-46d2-ab82-1a190e77c42b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "string = \"1000\" # secret string that we'll pretend we don't know or have access to\n", "n = len(string)\n", "\n", "qc = QuantumCircuit(n + 1, n)\n", "qc.x(n)\n", "qc.h(range(n + 1))\n", "qc.barrier()\n", "# qc.compose(oracle, inplace = True)\n", "qc.compose(bv_function(string), inplace=True)\n", "qc.barrier()\n", "qc.h(range(n))\n", "qc.measure(range(n), range(n))\n", "\n", "qc.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 19, "id": "5d225a6e-e3d0-4c08-8aeb-f03337bfffc4", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc)" ] }, { "cell_type": "code", "execution_count": null, "id": "8fef6a65-227a-4f27-af3e-348513e1cd33", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.c.get_counts()" ] }, { "cell_type": "code", "execution_count": 21, "id": "ec576787-d9ba-4406-b799-9c0de21a8088", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'0000': 1}\n" ] } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "print(counts)" ] }, { "cell_type": "markdown", "id": "46ff0418-570d-4e78-be36-f403aeccc392", "metadata": {}, "source": [ "Así, con una sola consulta, el algoritmo Deutsch-Jozsa devolverá la cadena $s$ utilizada en la función: $f(x)=x \\cdot s$ cuando lo apliquemos al problema Bernstein-Vazirani. Con un algoritmo clásico, se necesitarían $n$ consultas para resolver el mismo problema.\n", "\n", "\n", "\n", "## Conclusión\n", "\n", "Esperamos que el examen de estos sencillos ejemplos le haya dado una mejor intuición de cómo los ordenadores cuánticos son capaces de aprovechar la superposición, el entrelazamiento y la interferencia para lograr su poder sobre los ordenadores clásicos.\n", "\n", "El algoritmo de Deutsch-Jozsa tiene una enorme importancia histórica porque fue el primero en demostrar un aumento de velocidad con respecto a un algoritmo clásico, pero sólo fue un aumento de velocidad polinómico. El algoritmo Deutsch-Jozsa es sólo el principio de la historia.\n", "\n", "Después de utilizar el algoritmo para resolver su problema, Bernstein y Vazirani lo utilizaron como base para un problema más complicado y recursivo denominado *problema recursivo de muestreo de Fourier*. Su solución ofrecía una velocidad superpolinómica con respecto a los algoritmos clásicos. E incluso antes que Bernstein y Vazirani, Peter Shor ya había ideado su famoso algoritmo que permitía a los ordenadores cuánticos factorizar grandes números exponencialmente más rápido de lo que podría hacerlo cualquier algoritmo clásico. Estos resultados, en conjunto, mostraron la emocionante promesa de un futuro ordenador cuántico, y espolearon a físicos e ingenieros para hacer realidad este futuro.\n", "\n" ] }, { "cell_type": "markdown", "id": "c76273ac-ad3c-4c82-94e8-213e887dc7b7", "metadata": {}, "source": [ "\n", "\n", "## Preguntas\n", "\n", "Los profesores pueden solicitar versiones de estos cuadernos con claves de respuestas y orientaciones sobre su colocación en planes de estudios comunes rellenando esta [rápida encuesta](https://ibm.biz/classrooms_instructor_key_request) sobre cómo se están utilizando los cuadernos.\n", "\n", "\n", "\n", "### Conceptos fundamentales\n", "\n", "* los algoritmos Deutsch y Deutsch-Jozsa utilizan el paralelismo cuántico combinado con la interferencia para encontrar una respuesta a un problema más rápido de lo que puede hacerlo un ordenador clásico.\n", "* el mecanismo de retroceso de fase es un fenómeno cuántico contraintuitivo que transfiere las operaciones de un qubit a la fase de otro qubit. Los algoritmos Deutsch y Deutsch-Jozsa utilizan este mecanismo.\n", "* El algoritmo Deutsch-Jozsa ofrece una velocidad polinómica superior a la de cualquier algoritmo clásico determinista.\n", "* El algoritmo Deutsch-Jozsa puede aplicarse a un problema diferente, llamado problema Bernstein-Vazirani, para encontrar una cadena oculta codificada en una función.\n", "\n", "\n", "\n", "### True/False\n", "\n", "1. T/F El algoritmo de Deutsch es un caso especial del algoritmo de Deutsch-Jozsa en el que la entrada es un único qubit.\n", "2. T/F Los algoritmos Deutsch y Deutsch-Jozsa utilizan la superposición cuántica y la interferencia para lograr su eficacia.\n", "3. T/F El algoritmo Deutsch-Jozsa requiere múltiples evaluaciones de funciones para determinar si una función es constante o equilibrada.\n", "4. T/F El \"algoritmo Bernstein-Vazirani\" es en realidad el mismo que el algoritmo Deutsch-Jozsa, aplicado a un problema diferente.\n", "5. T/F El algoritmo Bernstein-Vazirani puede encontrar múltiples cadenas secretas simultáneamente.\n", "\n", "\n", "\n", "### Respuesta breve\n", "\n", "1. ¿Cuánto tardaría un algoritmo clásico en resolver el problema Deutsch-Jozsa en el peor de los casos?\n", "\n", "2. ¿Cuánto tardaría un algoritmo clásico en resolver el problema de Bernstein-Vazirani? ¿Qué aumento de velocidad ofrece el algoritmo DJ en este caso?\n", "\n", "3. Describa el mecanismo de retroceso de fase y cómo funciona para resolver los problemas Deutsch-Jozsa y Bernstein-Vazirani.\n", "\n", "\n", "\n", "### Problema desafiante\n", "\n", "1. El algoritmo de Deutsch-Jozsa: Recuerda que tenías una pregunta más arriba en la que se te pedía que calcularas los estados intermedios de los qubits $\\pi_1$, y $\\pi_2$ del algoritmo de Deutsch. Haga lo mismo para los estados intermedios $n+1$ -qubit $\\pi_1$, y $\\pi_2$ del algoritmo Deutsch-Jozsa, para el caso específico de que $n=2$. A continuación, verifique que $\\pi_3 = |-\\rangle \\otimes \\sum\\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\\rangle$, de nuevo, para el caso específico de que $n=2$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "in_page_toc_max_heading_level": 2, "in_page_toc_min_heading_level": 2, "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" }, "widgets": { "application/vnd.jupyter.widget-state+json": { "state": {}, "version_major": 2, "version_minor": 0 } } }, "nbformat": 4, "nbformat_minor": 5 }