El algoritmo (cuántico) de Deutsch

Los ordenadores cuánticos serán una tremenda revolución, en caso de construirse, no sólo porque nos abrirán las puertas del análisis de muchos sistemas fascinantes, sino porque nos permitirán realizar cómputos que ahora no podemos ni imaginar. Varios ejemplos se encuentran en el anterior post sobre computación cuántica. En este post, sin embargo, no profundizamos en los algoritmos en si y eso es lo que vamos a empezar a hacer ahora. Esto no es una tarea sencilla, sobre todo si se intenta llegar a todo el mundo ya que la nomenclatura es bastante difícil de seguir. Así pues este post está dirigido sólo a gente que ya tenga algo de conocimiento sobre álgebra, estudiantes de física o físicos de otras ramas sobre todo. 

Notación y Definiciones 

Estados

Como ya explicamos en el post anterior en computación cuántica en vez de trabajar con bits trabajamos con qubits. Para representarlos usamos la conocida notación de Dirac.

Ejemplo: Las secuencias de bits 000, 001 se denotan como los estados de qubits $\left| 000 \right>$, $\left| 001\right>$.

Podéis pensar que es una tontería simplemente encajar los bits en una cajita, pero ahora vamos más allá. No olvidemos que la física cuántica dice que si tenemos un estado $\left| A\right>$ y otro $\left| B\right>$ también será legítimo un estado formado por combinaciones lineales (que se forman multiplicando los estados por números complejos y sumándolos o restándolos entre si) de $A$ y $B$.

Ejemplo: Con las dos secuencias anteriores nos podemos también crear el estado $\frac{1}{\sqrt{2}} \left(  \left| 000 \right>+\left| 001 \right>\right)$, o el estado $\frac{1}{\sqrt{2}} \left(  \left| 000 \right>+ i \left| 001 \right>\right)$, donde $i=\sqrt{-1}$.


Producto escalar


Como los estados son vectores podemos definir también el producto escalar de los vectores $\left| A\right>$ y $\left| B\right>$, esto se denota como $\left< A|B\right>$.

En el caso que nos concierne, los qubits. el producto escalar de un qubit consigo mismo es 1, $\left< 0|0\right>$=$\left< 1|1\right>=1$ y los qubits diferentes tienen producto cero (son ortogonales) $\left< 0|1\right>=\left< 1|0\right>=0$.

Esto es extensible al caso de más qubits, multiplicando siempre el primero por el primero, el segundo por el segundo y así sucesivamente.

Ejemplo: $\left< 10|11\right>=0$ (tienen el segundo qubit diferente), $\left< 11|11\right>=1$ (son los dos iguales).
 $\left<10\right|  \left(\frac{\left|10\right>+ \left|01\right>}{\sqrt{2}} \right)=\frac{1}{\sqrt{2}}$ (Uno igual, uno diferente).

Una propiedad importante de nuestros estados es que al calcular el producto de cualquier estado por si mismo nos debe dar 1.

Ejemplo: El estado $\left|0\right>+ \left|1\right>$ no es un estado válido, porque su producto escalar vale:
$\left(\left<0\right|+ \left<1\right|\right) \left(\left|0\right>+ \left|1\right>\right)=\left< 0 | 0\right>+\left< 0 | 1\right>+\left< 1 | 0\right>+\left< 1 | 1\right>=2$. El estado correspondiente correcto es  $\frac{\left|10\right>+ \left|01\right>}{\sqrt{2}}$ (podéis comprobar que este sí es válido).

Operadores

Un operador es una transformación sobre nuestros estados de qubits en otros estados. Igual que en con los bits podemos sumarlos, restarlos, conjugarlos y demás, con los qubits también podemos hacer muchas operaciones. En general, ya que los qubits son vectores, los operadores serán matrices que transforman esos vectores en otros. En la notación de Dirac, y para lo que queremos hacer aquí nos bastará con definir los operadores de la siguiente manera (estos se denominan técnicamente operadores de proyección). 

$O=\left| A\right> \left<A\right|$.

Esto significa lo siguiente. Si aplicamos el operador $O$ a un vector cualquiera $\left| B \right>$ lo convertimos en $O\left| B\right>=\left<A|B\right> \left| A \right>$. Asi pues, lo hemos proyectado al estado $\left| A\right>$.

Ejemplo: Si $O=\left| 1\right> \left<1\right|$ y lo aplicamos al vector $\frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}$ tendremos $O\left(\frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}\right)=\frac{1}{\sqrt{2}} \left| 1\right> $.

En general hay operadores más complicados, nos basta saber que un operador es cualquier cosa que transforma un vector en otro vector.


Medidas

Ahora está la espinosa cuestión de obtener información de nuestros estados. Una cuestión que hay que asumir es que no podemos ver los estados en sí. Así si tenemos nuestro querido estado $\frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}$, no podemos en principio saber cual es. Para obtener información debemos medir estos estados.

Para medir lo que necesitamos es una colección de operadores que sumados nos den todo el espacio. Mirándolo de otra manera lo que necesitamos es una base de nuestro espacio, es decir, un conjunto de vectores ortogonales entre si de modo que cualquier otro vector se pueda escribir como combinación lineal de estos.

Ejemplo: La base más usual para un sólo qubit es la "base computacional": $\left\{ \left| 0\right>,\left| 1\right>\right\}$. Otra base que es muy común son los vectores $\left\{\frac{\left|0\right>+ \left|1\right>}{\sqrt{2}},\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\right\}$.

Cuando medimos un vector $\left| A\right>$ en una base compuesta por los vectores $\left\{ \left| B_i\right>\right\}$, obtendremos el resultado asociado a $B_i$ con una probabilidad $\left| \left<A|B_i \right> \right|^2$. (Nota: El Símbolo $| |$ representa el módulo, no olvidemos que en general trabajamos con números complejos. Para nuestro caso se puede tomar como el valor absoluto.)

Ejemplo: Si tenemos el vector $\frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}$ y lo medimos en la base $\left\{ \left| 0\right>,\left| 1\right>\right\}$ ¿qué obtendremos? Pues con una probabilidad $\frac{1}{2}$ 0 y con la misma probabilidad 1.

Algoritmo

Vamos ya al jaleo, el algoritmo de Deutsch. El problema que queremos resolver es bastante sencillo: 

- Tenemos una caja negra ("oráculo" a partir de ahora) que calcula una función que recibe un bit, 0 ó 1 y devuelve otro bit 0 ó 1.
- No conocemos la función, pero sólo nos interesa un detalle. Queremos saber si el resultado que da para 0 es el mismo que da para 1.
- La solución clásica es simple, introducimos en el oráculo 0 y vemos que sale, luego hacemos lo mismo con 1, comparamos los resultados y a casita.
- El problema es que nuestro oráculo sólo funciona una vez. Tenemos que extraer la información sólo con una llamada. Complicado ¿no?

Aquí el oráculo al que vamos a preguntarle la pregunta definitiva ¿f(0)=f(1)? Vía Wikipedia

La cuestión es que con un oráculo cuántico sí que podemos averiguar esta propiedad usándolo una vez. Sólo tenemos que manipularlo un poco de modo que el resultado salga de una manera particular. En vez de tener un resultado que miremos tal cual el oráculo transformará el estado $\left| x \right> \rightarrow (-1)^{f(x)} \left| x \right>$.

Entonces para resolverlo le introduciremos el estado $\frac{\left| 0\right>+ \left|1\right>}{\sqrt{2}}$, vamos a ver que pasará en los 4 casos posibles:


1.- f(0)=f(1)=0 $\qquad \frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}\to\frac{\left|0\right> + \left|1\right>}{\sqrt{2}}$


2.- f(0)=f(1)=1 $\qquad \frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}\to -\frac{\left|0\right> + \left|1\right>}{\sqrt{2}}$


3.- f(0)=0, f(1)=1 $\qquad \frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}\to \frac{\left|0\right> - \left|1\right>}{\sqrt{2}}$

4.- f(0)=1, f(1)=0 $\qquad \frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}\to -\frac{\left|0\right> - \left|1\right>}{\sqrt{2}}$

Se puede ver que el efecto de las dos posibles funciones constantes es el mismo salvo por un factor "-". Lo mismo ocurre con las dos funciones no-constantes. ¿Qué haremos ahora? Ahora, como es evidente, toca medir el resultado.

Para medir el resultado está claro que no debemos usar la base computacional $0,1$, porque cualquier medida nos dará $0$ o $1$ con un 50% de probabilidad. Lo que haremos será medir en la base $\left\{\frac{\left|0\right>+ \left|1\right>}{\sqrt{2}},\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\right\}$.

Imaginemos que tenemos el caso 1. Las probabilidades de las dos medidas son:

$\left| \left( \frac{\left<0\right|+ \left<1\right|}{\sqrt{2}}\right)\left( \frac{\left|0\right> + \left|1\right>}{\sqrt{2}}\right)\right|^2=1$

$\left| \left( \frac{\left<0\right|- \left<1\right|}{\sqrt{2}}\right)\left( \frac{\left|0\right> + \left|1\right>}{\sqrt{2}}\right)\right|^2=0$

Y para el caso 2:

$\left| \left( \frac{\left<0\right|+ \left<1\right|}{\sqrt{2}}\right)\left( -\frac{\left|0\right> + \left|1\right>}{\sqrt{2}}\right)\right|^2=1$

$\left| \left( \frac{\left<0\right|- \left<1\right|}{\sqrt{2}}\right)\left(- \frac{\left|0\right> + \left|1\right>}{\sqrt{2}}\right)\right|^2=0$

Es decir son idénticas, siempre detectaremos el estado $\frac{\left|0\right>+ \left|1\right>}{\sqrt{2}}$. Veamos ahora que pasa en los casos de $f(x)$ no constante.

Caso 3:

$\left| \left( \frac{\left<0\right|+ \left<1\right|}{\sqrt{2}}\right)\left( \frac{\left|0\right> - \left|1\right>}{\sqrt{2}}\right)\right|^2=0$

$\left| \left( \frac{\left<0\right|- \left<1\right|}{\sqrt{2}}\right)\left( \frac{\left|0\right> - \left|1\right>}{\sqrt{2}}\right)\right|^2=1$

Caso 4: 

$\left| \left( \frac{\left<0\right|+ \left<1\right|}{\sqrt{2}}\right)\left( -\frac{\left|0\right> - \left|1\right>}{\sqrt{2}}\right)\right|^2=0$

$\left| \left( \frac{\left<0\right|- \left<1\right|}{\sqrt{2}}\right)\left( -\frac{\left|0\right> - \left|1\right>}{\sqrt{2}}\right)\right|^2=1$

Siempre detectamos el caso $\frac{\left|0\right>- \left|1\right>}{\sqrt{2}}$. De esta manera podemos distinguir si la función es constante o no, dado que si es constante o no siempre obtendremos resultados diferentes. 

Extensión y conclusiones

El algoritmo de Deutsch puede extenderse a un caso algo más completo. El problema ahora es el siguiente: 

- Tenemos un oráculo que calcula una función que recibe N bits.

- No conocemos la función pero sí sabemos algo de ella. O bien la función es constante o bien da como resultado 1 la mitad de veces y 0 la otra mitad. 

-  Queremos saber si es constante o no.

- La solución clásica es simple, en el peor caso tenemos que introducir la mitad de las posibles combinaciones más una, para asegurar que la función es constante. Esto da una complejidad del problema de orden N/2.  

- El problema es que nuestro oráculo sólo funciona una vez, again. 

La solución es muy similar al caso de un sólo bity se llama el algoritmo de Deutsch-Jozsa. Por no aburrir derivo a los curiosos a la Wikipedia y si tenéis dudas podéis comentar. 

Aquí el "circuito cuántico" que da lugar al algoritmo de Deutsch-Jozsa

Mencionar también que este es un algoritmo que se puede realizar experimentalmente en sistemas fotónicos[1]. Ciertamente no es un algoritmo muy útil, pero sí que sirvió para demostrar que con física cuántica, incluso de la más simple, se pueden reducir problemas a algo mucho más sencillo. 

Más adelante si me veo con ganas escribiré sobre otros algoritmos que sí resuelven problemas útiles como buscar en una base de datos o factorizar números.