{
"cells": [
{
"cell_type": "markdown",
"id": "7e5d320e",
"metadata": {},
"source": [
"---\n",
"title: \"Algoritmo de Deutsch\"\n",
"description: \"Curso gratuito « IBM » sobre información y computación cuánticas\"\n",
"---\n",
"\n",
"\n",
"\n",
"# Algoritmo de Deutsch\n",
"\n",
"El algoritmo de Deutsch resuelve el problema de paridad para el caso especial de que $n = 1.$ En el contexto de la computación cuántica este problema se denomina a veces *problema de Deutsch*, y seguiremos esa nomenclatura en esta lección.\n",
"\n",
"Para ser precisos, la entrada se representa mediante una función $f:\\Sigma \\rightarrow \\Sigma$ de un bit a un bit.\n",
"Estas funciones son cuatro:\n",
"\n",
"$$\n",
"\\rule[-10mm]{0mm}{10mm}\n",
"\\begin{array}{c|c}\n",
" a & f_1(a)\\\\\n",
" \\hline\n",
" 0 & 0\\\\\n",
" 1 & 0\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_2(a)\\\\\n",
" \\hline\n",
" 0 & 0\\\\\n",
" 1 & 1\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_3(a)\\\\\n",
" \\hline\n",
" 0 & 1\\\\\n",
" 1 & 0\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_4(a)\\\\\n",
" \\hline\n",
" 0 & 1\\\\\n",
" 1 & 1\n",
"\\end{array}\n",
"$$\n",
"\n",
"La primera y la última de estas funciones son *constantes* y las dos centrales están *equilibradas*, lo que significa que los dos posibles valores de salida de la función se producen el mismo número de veces a medida que recorremos las entradas.\n",
"El problema de Deutsch consiste en determinar a cuál de estas dos categorías pertenece la función de entrada: constante o equilibrada.\n",
"\n",
"\n",
" Entrada: una función $f:\\{0,1\\}\\rightarrow\\{0,1\\}$ \\ Salida: $0$ si $f$ es constante, $1$ si $f$ es equilibrado\n",
"\n",
"\n",
"Si consideramos que la función de entrada $f$ del problema de Deutsch representa el acceso aleatorio a una cadena, estamos pensando en una cadena de dos bits: $f(0)f(1).$\n",
"\n",
"$$\n",
"\\begin{array}{cc}\n",
"\\mathsf{function} & \\mathsf{string}\\\\\n",
"\\hline\n",
"f_1 & 00 \\\\\n",
"f_2 & 01 \\\\\n",
"f_3 & 10 \\\\\n",
"f_4 & 11\n",
"\\end{array}\n",
"$$\n",
"\n",
"Visto así, el problema de Deutsch consiste en calcular la paridad (o, lo que es lo mismo, el OR exclusivo) de los dos bits.\n",
"\n",
"Todo algoritmo de consulta clásico que resuelva correctamente este problema debe consultar ambos bits: $f(0)$ y $f(1).$ Si aprendemos que $f(1) = 1,$ por ejemplo, la respuesta podría seguir siendo $0$ o $1,$ dependiendo de si $f(0) = 1$ o $f(0) = 0,$ respectivamente.\n",
"Todos los demás casos son similares; conocer sólo uno de los dos bits no proporciona ninguna información sobre su paridad.\n",
"Por tanto, el circuito booleano descrito en la sección anterior es lo mejor que podemos hacer en cuanto al número de consultas necesarias para resolver este problema.\n",
"\n",
"\n",
"\n",
"## Descripción del circuito cuántico\n",
"\n",
"El algoritmo de Deutsch resuelve el problema de Deutsch utilizando una única consulta, lo que proporciona una ventaja cuantificable de los cálculos cuánticos sobre los clásicos.\n",
"Puede que sea una ventaja modesta -una consulta frente a dos-, pero por algo hay que empezar.\n",
"Los avances científicos tienen a veces orígenes aparentemente humildes.\n",
"\n",
"He aquí un circuito cuántico que describe el algoritmo de Deutsch:\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"## Análisis\n",
"\n",
"Para analizar el algoritmo de Deutsch, recorreremos la acción del circuito anterior e identificaremos los estados de los qubits en los momentos sugeridos por esta figura:\n",
"\n",
"\n",
"\n",
"El estado inicial es $\\vert 1\\rangle \\vert 0 \\rangle,$ y las dos operaciones Hadamard del lado izquierdo del circuito transforman este estado en\n",
"\n",
"$$\n",
"\\vert \\pi_1 \\rangle = \\vert - \\rangle \\vert + \\rangle\n",
"= \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 0\\rangle\n",
"+ \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 1\\rangle.\n",
"$$\n",
"\n",
"(Como siempre, seguimos la convención de ordenación de qubits de Qiskit, que coloca el qubit superior a la derecha y el qubit inferior a la izquierda) Puede parecer poco intuitivo escribir este producto estado parcialmente distribuido (dejando los estados del qubit 1 factorizados), pero esto hará que nuestras expresiones posteriores sean más compactas.\n",
"\n",
"A continuación, se ejecuta la puerta $U_f$.\n",
"Según la definición de la puerta $U_f$, el valor de la función $f$ para el estado clásico del qubit superior/derecho es XORed en el qubit inferior/izquierdo, que transforma $\\vert \\pi_1\\rangle$ en el estado\n",
"\n",
"$$\n",
"\\vert \\pi_2 \\rangle\n",
"= \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(0) \\rangle - \\vert 1 \\oplus f(0) \\rangle \\bigr) \\vert 0 \\rangle\n",
"+ \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(1) \\rangle - \\vert 1 \\oplus f(1) \\rangle \\bigr) \\vert 1 \\rangle.\n",
"$$\n",
"\n",
"Podemos simplificar esta expresión observando que la fórmula\n",
"\n",
"$$\n",
"\\vert 0 \\oplus a\\rangle - \\vert 1 \\oplus a\\rangle = (-1)^a \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n",
"$$\n",
"\n",
"funciona para los dos valores posibles $a\\in\\Sigma.$ Más explícitamente, los dos casos son los siguientes.\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert 0 \\oplus 0\\rangle - \\vert 1 \\oplus 0\\rangle\n",
"& = \\vert 0 \\rangle - \\vert 1 \\rangle\n",
"= (-1)^0 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\\\\\n",
"\\vert 0 \\oplus 1\\rangle - \\vert 1 \\oplus 1\\rangle & = \\vert 1 \\rangle - \\vert 0\\rangle\n",
"= (-1)^1 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Así, podemos expresar alternativamente $\\vert\\pi_2\\rangle$ de la siguiente manera:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert\\pi_2\\rangle\n",
" & = \\frac{1}{2} (-1)^{f(0)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 0 \\rangle\n",
" + \\frac{1}{2} (-1)^{f(1)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 1 \\rangle \\\\\n",
" & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Acaba de ocurrir algo interesante\n",
"Aunque la acción de la puerta $U_f$ en estados base estándar deja el qubit superior/derecho solo y XORs el valor de la función en el qubit inferior/izquierdo, aquí vemos que el estado del qubit superior/derecho ha cambiado (en general) mientras que el estado del qubit inferior/izquierdo permanece igual - específicamente estando en el estado $\\vert - \\rangle$ antes y después de que se realice la puerta $U_f$.\n",
"Este fenómeno se conoce como *contragolpe de fase*, y hablaremos más de él en breve.\n",
"\n",
"Con una última simplificación, que consiste en sacar el factor de $(-1)^{f(0)}$ fuera de la suma, obtenemos esta expresión del estado $\\vert\\pi_2\\rangle$ :\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert\\pi_2\\rangle\n",
" & = (-1)^{f(0)} \\vert - \\rangle\n",
" \\biggl( \\frac{\\vert 0\\rangle + (-1)^{f(0) \\oplus f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr) \\\\\n",
" & = \\begin{cases}\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert + \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert - \\rangle & \\text{if $f(0) \\oplus f(1) = 1$}.\n",
" \\end{cases}\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Nótese que en esta expresión, tenemos $f(0) \\oplus f(1)$ en el exponente de $-1$ en lugar de $f(1) - f(0),$ que es lo que podríamos esperar desde un punto de vista puramente algebraico, pero obtenemos el mismo resultado de cualquier manera.\n",
"Esto se debe a que el valor $(-1)^k$ para cualquier número entero $k$ depende únicamente de si $k$ es par o impar.\n",
"\n",
"La aplicación de la última puerta de Hadamard al qubit superior nos deja con el estado\n",
"\n",
"$$\n",
"\\vert \\pi_3 \\rangle =\n",
"\\begin{cases}\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert 0 \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert 1 \\rangle & \\text{if $f(0) \\oplus f(1) = 1$},\n",
"\\end{cases}\n",
"$$\n",
"\n",
"que conduce al resultado correcto con probabilidad $1$ cuando se mide el qubit derecho/superior.\n",
"\n",
"\n",
"\n",
"## Comentarios adicionales sobre el retroceso de fase\n",
"\n",
"Antes de continuar, veamos el análisis anterior desde un ángulo ligeramente diferente que puede arrojar algo de luz sobre el fenómeno del contragolpe de fase.\n",
"\n",
"En primer lugar, observe que la siguiente fórmula funciona para todas las opciones de bits $b,c\\in\\Sigma.$\n",
"\n",
"$$\n",
"\\vert b \\oplus c\\rangle = X^c \\vert b \\rangle\n",
"$$\n",
"\n",
"Esto puede verificarse comprobándolo para los dos valores posibles $c = 0$ y $c = 1$ :\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert b \\oplus 0 \\rangle & = \\vert b\\rangle = \\mathbb{I} \\vert b \\rangle = X^0 \\vert b \\rangle\\\\\n",
"\\vert b \\oplus 1 \\rangle & = \\vert \\neg b\\rangle = X \\vert b \\rangle = X^1 \\vert b \\rangle.\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Utilizando esta fórmula, vemos que\n",
"\n",
"$$\n",
"U_f \\bigl(\\vert b\\rangle \\vert a \\rangle\\bigr)\n",
"= \\vert b \\oplus f(a) \\rangle \\vert a \\rangle\n",
"= \\bigl(X^{f(a)}\\vert b \\rangle\\bigr) \\vert a \\rangle\n",
"$$\n",
"\n",
"para cada elección de bits $a,b\\in\\Sigma.$ Como esta fórmula es cierta para $b=0$ y $b=1,$ vemos por linealidad que\n",
"\n",
"$$\n",
"U_f \\bigl( \\vert \\psi \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)}\\vert \\psi \\rangle\\bigr) \\vert a \\rangle\n",
"$$\n",
"\n",
"para todos los vectores de estado de los qubits $\\vert \\psi\\rangle,$ y por tanto\n",
"\n",
"$$\n",
"U_f \\bigl( \\vert - \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)} \\vert - \\rangle \\bigr) \\vert a \\rangle\n",
"= (-1)^{f(a)} \\vert - \\rangle \\vert a \\rangle.\n",
"$$\n",
"\n",
"La clave que hace que esto funcione es que $X\\vert - \\rangle = - \\vert - \\rangle.$ En términos matemáticos, el vector $\\vert - \\rangle$ es un *vector propio* de la matriz $X$ que tiene *el valor propio* $-1.$\n",
"\n",
"Hablaremos de los vectores propios y los valores propios con más detalle en la próxima lección sobre *Estimación de fase y factorización,* donde el fenómeno del retroceso de fase se generaliza a otras operaciones unitarias.\n",
"\n",
"Teniendo en cuenta que los escalares flotan libremente a través de productos tensoriales, encontramos una forma alternativa de razonar cómo la operación $U_f$ transforma $\\vert \\pi_1\\rangle$ en $\\vert \\pi_2\\rangle$ en el análisis anterior:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert \\pi_2 \\rangle\n",
" & = U_f \\bigl( \\vert - \\rangle \\vert + \\rangle \\bigr)\\\\\n",
" & = \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 0\\rangle \\bigr)\n",
" + \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 1\\rangle \\bigr)\\\\\n",
" & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n",
"\\end{aligned}\n",
"$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "d0cff57e",
"metadata": {},
"source": [
"\n",
"\n",
"## Implementación en Qiskit\n",
"\n",
"Ahora vamos a ver cómo podemos implementar el algoritmo de Deutsch en Qiskit. Empezaremos con una comprobación de la versión y luego realizaremos las importaciones necesarias únicamente para esta implementación.\n",
"Para las implementaciones de otros algoritmos que siguen, vamos a realizar las importaciones necesarias por separado en aras de una mayor modularidad.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "baa9bc2c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2.1.1\n"
]
}
],
"source": [
"from qiskit import __version__\n",
"\n",
"print(__version__)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "0a706449",
"metadata": {},
"outputs": [],
"source": [
"from qiskit import QuantumCircuit\n",
"from qiskit_aer import AerSimulator"
]
},
{
"cell_type": "markdown",
"id": "0af39df9",
"metadata": {},
"source": [
"Primero definiremos un circuito cuántico que implemente una puerta de consulta para una de las cuatro funciones $f_1,$ $f_2,$ $f_3,$ o $f_4$ de un bit a otro bit descritas anteriormente. Como ya hemos mencionado, la implementación de puertas de consulta no es realmente una parte del algoritmo de Deutsch en sí; aquí estamos esencialmente mostrando una forma de preparar la entrada, en la forma de un circuito de implementación de una puerta de consulta.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "ba5a708f",
"metadata": {},
"outputs": [],
"source": [
"def deutsch_function(case: int):\n",
" # This function generates a quantum circuit for one of the 4 functions\n",
" # from one bit to one bit\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"
]
},
{
"cell_type": "markdown",
"id": "46eccf09",
"metadata": {},
"source": [
"Podemos ver el aspecto de cada circuito utilizando el método `draw` . Este es el circuito para la función $f_3.$\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "787e3c81",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(deutsch_function(3).draw(output=\"mpl\"))"
]
},
{
"cell_type": "markdown",
"id": "b6fa5b7b",
"metadata": {},
"source": [
"A continuación crearemos el circuito cuántico real para el algoritmo de Deutsch, sustituyendo la puerta de consulta por una implementación de circuito cuántico dada como argumento. En breve conectaremos uno de los cuatro circuitos definidos por la función `deutsch_function` que definimos anteriormente.\n",
"Se incluyen barreras para mostrar la separación visual entre la implementación de la puerta de consulta y el resto del circuito.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "379aac92",
"metadata": {},
"outputs": [],
"source": [
"def compile_circuit(function: QuantumCircuit):\n",
" # Compiles a circuit for use in Deutsch's algorithm.\n",
"\n",
" n = function.num_qubits - 1\n",
" qc = QuantumCircuit(n + 1, n)\n",
"\n",
" qc.x(n)\n",
" qc.h(range(n + 1))\n",
"\n",
" qc.barrier()\n",
" qc.compose(function, inplace=True)\n",
" qc.barrier()\n",
"\n",
" qc.h(range(n))\n",
" qc.measure(range(n), range(n))\n",
"\n",
" return qc"
]
},
{
"cell_type": "markdown",
"id": "e5112614",
"metadata": {},
"source": [
"De nuevo podemos ver cómo queda el circuito utilizando el método `draw` .\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "27b41067",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(compile_circuit(deutsch_function(3)).draw(output=\"mpl\"))"
]
},
{
"cell_type": "markdown",
"id": "d24d14eb",
"metadata": {},
"source": [
"Por último, crearemos una función que ejecute el circuito previamente definido una vez y emita el resultado apropiado: \"constante\" o \"equilibrado\"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "5b31e311",
"metadata": {},
"outputs": [],
"source": [
"def deutsch_algorithm(function: QuantumCircuit):\n",
" # Determine if a one-bit function is constant or balanced.\n",
"\n",
" qc = compile_circuit(function)\n",
"\n",
" result = AerSimulator().run(qc, shots=1, memory=True).result()\n",
" measurements = result.get_memory()\n",
" if measurements[0] == \"0\":\n",
" return \"constant\"\n",
" return \"balanced\""
]
},
{
"cell_type": "markdown",
"id": "3d0868ed",
"metadata": {},
"source": [
"Ahora podemos ejecutar el algoritmo de Deutsch en cualquiera de las cuatro funciones definidas anteriormente.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "33b8355d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'balanced'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"f = deutsch_function(3)\n",
"display(deutsch_algorithm(f))"
]
},
{
"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"
}
},
"nbformat": 4,
"nbformat_minor": 5
}