El algoritmo de Deutsch

El algoritmo de Deutsch resuelve el problema de la paridad para el caso especial en que $n = 1.$ En el contexto de la computación cuántica, este problema a veces se denomina problema de Deutsch, y seguiremos esa nomenclatura en esta lección.

Para ser precisos, la entrada se representa mediante una función $f:\Sigma \rightarrow \Sigma$ de un bit a un bit. Existen cuatro funciones de este tipo:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

La primera y la última de estas funciones son constantes, mientras que las dos del medio son balanceadas, lo que significa que los dos posibles valores de salida de la función aparecen el mismo número de veces al recorrer las entradas. El problema de Deutsch consiste en determinar a cuál de estas dos categorías pertenece la función de entrada: constante o balanceada.

El problema de Deutsch

Entrada: una función $f:\{0,1\}\rightarrow\{0,1\}$
Salida: $0$ si $f$ es constante, $1$ si $f$ es balanceada

Si vemos la función de entrada $f$ del problema de Deutsch como un acceso aleatorio a una cadena, estamos pensando en una cadena de dos bits: $f(0)f(1).$

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

Visto de esta manera, el problema de Deutsch consiste en calcular la paridad (o, de forma equivalente, el OR exclusivo) de los dos bits.

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. Todos los demás casos son similares; conocer solo uno de los dos bits no proporciona ninguna información sobre su paridad. Por lo tanto, el circuito booleano descrito en la sección anterior es lo mejor que podemos hacer en términos del número de consultas necesarias para resolver este problema.

Descripción del circuito cuántico

El algoritmo de Deutsch resuelve el problema de Deutsch con una sola consulta, lo que proporciona una ventaja cuantificable de la computación cuántica sobre la clásica. Puede parecer una ventaja modesta —una consulta en vez de dos— pero hay que empezar por algún sitio. Los avances científicos a veces tienen orígenes aparentemente humildes.

Aquí se muestra un circuito cuántico que describe el algoritmo de Deutsch:

Análisis

Para analizar el algoritmo de Deutsch, recorreremos la acción del circuito anterior e identificaremos los estados de los qubits en los momentos indicados por esta figura:

El estado inicial es $\vert 1\rangle \vert 0 \rangle,$ y las dos operaciones Hadamard en el lado izquierdo del circuito transforman este estado en

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(Como siempre, seguimos la convención de ordenamiento de qubits de Qiskit, que coloca el qubit superior a la derecha y el qubit inferior a la izquierda.) Puede resultar poco intuitivo escribir este estado producto parcialmente distribuido (dejando los estados del qubit 1 factorizados), pero esto hará que nuestras expresiones posteriores sean más compactas.

A continuación, se aplica la compuerta $U_f$. De acuerdo con la definición de la compuerta $U_f$, el valor de la función $f$ para el estado clásico del qubit superior/más a la derecha se aplica con XOR al qubit inferior/más a la izquierda, lo que transforma $\vert \pi_1\rangle$ en el estado

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

Podemos simplificar esta expresión observando que la fórmula

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

es válida para ambos valores posibles $a\in\Sigma.$ Más explícitamente, los dos casos son los siguientes.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

Así, podemos expresar $\vert\pi_2\rangle$ de forma alternativa de la siguiente manera:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

¡Algo interesante acaba de ocurrir! Aunque la acción de la compuerta $U_f$ sobre los estados de la base estándar deja intacto el qubit superior/más a la derecha y aplica el XOR del valor de la función al qubit inferior/más a la izquierda, aquí vemos que el estado del qubit superior/más a la derecha ha cambiado (en general) mientras que el estado del qubit inferior/más a la izquierda permanece igual, estando específicamente en el estado $\vert - \rangle$ antes y después de que se aplique la compuerta $U_f$. Este fenómeno se conoce como phase kickback (retroceso de fase), y hablaremos más sobre él en breve.

Con una última simplificación, que consiste en extraer el factor $(-1)^{f(0)}$ fuera de la suma, obtenemos esta expresión del estado $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Observa 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 forma. Esto se debe a que el valor $(-1)^k$ para cualquier entero $k$ depende únicamente de si $k$ es par o impar.

Aplicar la compuerta Hadamard final al qubit superior nos deja con el estado

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}$$

lo que conduce al resultado correcto con probabilidad $1$ cuando se mide el qubit de la derecha/superior.

Observaciones adicionales sobre el phase kickback

Antes de continuar, veamos el análisis anterior desde un ángulo ligeramente diferente que puede arrojar luz sobre el fenómeno del phase kickback.

Primero, observa que la siguiente fórmula es válida para toda elección de bits $b,c\in\Sigma.$

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

Esto puede verificarse comprobándolo para los dos valores posibles $c = 0$ y $c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

Usando esta fórmula, vemos que

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

para toda elección de bits $a,b\in\Sigma.$ Como esta fórmula es válida para $b=0$ y $b=1$, vemos por linealidad que

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

para todos los vectores de estado de qubit $\vert \psi\rangle,$ y por lo tanto

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

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$ con valor propio $-1.$

Discutiremos los vectores propios y valores propios con mayor detalle en la próxima lección sobre Estimación de fase y factorización, donde el fenómeno del phase kickback se generaliza a otras operaciones unitarias.

Teniendo en cuenta que los escalares se propagan libremente a través de los 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:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Implementación en Qiskit

Ahora veamos cómo podemos implementar el algoritmo de Deutsch en Qiskit. Comenzaremos con una verificación de versión y luego realizaremos las importaciones necesarias únicamente para esta implementación. Para las implementaciones de otros algoritmos que siguen, realizaremos las importaciones necesarias por separado en aras de una mayor modularidad.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Primero definiremos un circuito cuántico que implemente una compuerta de consulta para una de las cuatro funciones $f_1,$ $f_2,$ $f_3,$ o $f_4$ de un bit a un bit descritas anteriormente. Como ya mencionamos, la implementación de las compuertas de consulta no es realmente parte del propio algoritmo de Deutsch; aquí esencialmente solo mostramos una forma de preparar la entrada, en la forma de una implementación en circuito de una compuerta de consulta.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

Podemos ver cómo luce cada circuito usando el método draw. Aquí está el circuito para la función $f_3.$

display(deutsch_function(3).draw(output="mpl"))

A continuación crearemos el circuito cuántico real para el algoritmo de Deutsch, sustituyendo la compuerta de consulta por una implementación en circuito cuántico dada como argumento. En breve conectaremos uno de los cuatro circuitos definidos por la función deutsch_function que definimos antes. Se incluyen barreras para mostrar la separación visual entre la implementación de la compuerta de consulta y el resto del circuito.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

De nuevo podemos ver cómo luce el circuito usando el método draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Finalmente, crearemos una función que ejecute el circuito definido anteriormente una sola vez y devuelva el resultado apropiado: "constant" o "balanced."

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

Ahora podemos ejecutar el algoritmo de Deutsch en cualquiera de las cuatro funciones definidas anteriormente.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'