Computación Cuántica: febrero 2010

En este post voy a explicar la técnica más popular para la construcción de algoritmos cuánticos conocida como Amplificación de Amplitud (Amplitude Amplification). Mi investigación está principalmente basada en encontrar cotas superiores e inferiores utilizando esta técnica y quantum walks (sobre este punto ya hablaré más adelante). Esta técnica es una generalización del algoritmo de Grover.

Antes que nada, se le llama amplificación de amplitud porque se amplifica o incrementa la amplitud en la ecuación de onda de una partícula. Por ejemplo, sea $|\Psi\rangle$ un estado cuántico definido en un espacio de Hilbert $\mathcal{H}=span\{|i\rangle\quad : \quad 1\leq i \leq n\}$ , donde cada $|i\rangle$ es un vector de la base de $\mathcal{H}$ (siempre $\parallel |\Psi\rangle \parallel=1$ ). En un problema de búsqueda sin información, para encontrar un índice dado $k$ , donde $1\leq k \leq n$ , la técnica de amplificación de amplitud ubica el vector base $|k\rangle$ en $|\Psi\rangle=\alpha_1|1\rangle+\cdots+\alpha_k|k\rangle+\cdots+\alpha_n|n\rangle$ con amplitud $\alpha_k$ , y sustituye ese valor por otro $\alpha_k'$ tal que $\100dpi \inline |\alpha_k'|>|\alpha_k|$ . El resto de las amplitudes son sustituidas por otras amplitudes con valor absoluto menor. Esto ocurre automáticamente porque las transformaciones efectuadas a $|\Psi\rangle$ son unitarias, i.e., preservan el valor del producto interno y por lo tanto las normas. De esta forma al realizar una observación, el algoritmo retorna el valor $k$ con probabilidad $|\alpha_k|^2$ suficientemente alta.

Esa es básicamente la intuición en el algoritmo de amplificación de amplitud. A continuación paso a formalizar esta idea, pero solamente describiendo el caso particular del algoritmo de Grover. Hacia el final de post mencionaré como es el caso general de amplificación sin entrar en detalles.

El algoritmo de Grover funciona aplicando primero al estado $|0\rangle$ un operador que genera el vector

$|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i,j}|i\rangle\langle j|$ ,

i.e., una superposición con la misma amplitud para todos los elementos de la base. Luego, sobre $|\psi\rangle$ se aplica un número $t$ de veces dos operadores unitarios: el oráculo $O$ y el operador de difusión $G$ . Entonces el algoritmo luce algo como $\left(GO\right)^t|\psi\rangle$ . Vamos a probar que $t=O(\sqrt{n})$ , y retorna $k$ con una probabilidad $O(1-1/n)$ .

Primero el oráculo $O$ es un operador de fase (reflexión), y su acción se basa en cambiarle el signo a la amplitud de la base $|k\rangle$ dejando el resto sin alterar. Se define como $O|x\rangle|q\rangle=|x\rangle|q\oplus f(x)\rangle$ , donde $x$ es la entrada a la función del oráculo, y $q$ es el bit del oráculo el cual se invierte si $f(x)=1$ (el operador $\oplus$ representa al OR exclusivo bit a bit si la codificación es binaria, o puede considerarse como adición modulo 2 para números en base mayor a 2). Inicializando $q$ a $(|0\rangle-|1\rangle)/\sqrt{2}$ , la acción del oráculo puede resumirse en

$O|x\rangle=(-1)^{f(x)}|x\rangle$ ,

i.e., el oráculo "marca" el vector buscado inviertiendo su fase. Como escribir el oráculo en esta forma dada la definición anterior es un ejercicio muy entretenido (ref. Quantum Information and Computation. Nielsen and Chuang).

El operador de difusión de Grover (definido aquí) tiene la siguiente forma

$G=\begin{bmatrix}2/n-1 & 2/n & \cdots & 2/n\\2/n & 2n-1 & \cdots & 2/n\\\vdots & & \ddots & \vdots\\ 2/n & 2/n & \cdots & 2/n-1\end{bmatrix}$ ,

o en notación de Dirac

$G=\sum_{i=1}^n (\frac{2}{n}-1) |i\rangle\langle i|+\sum_{i\neq j} \frac{2}{n}|i\rangle\langle j|$ .

Este operador se conoce también con el nombre de reflexión alrededor de la media, porque también puede escribirse de la siguiente forma $G=2|\psi\rangle\langle\psi|-I$ .

Ahora, supongamos que estamos buscando un único elemento $k$ en $[n]$ (esta es una notación más corta para referirse al conjunto $\{1,\dots,n\}$ ). Definamos el estado cuántico

$|\Psi\rangle=\alpha|k\rangle+\sum_{i\neq k}\beta|i\rangle$ .

La norma de los vectores debe de ser siempre 1, por lo tanto $\alpha^2+(n-1)\beta^2=1$ (tenemos un solo $\alpha$ porque solo hay un único vector objetivo, y $(n-1)\beta$ porque esos vectores no representan una solución al problema). Denotemos por $|\Psi\rangle^{(t)}$ el estado del algoritmo en el tiempo $t$ . Vamos a calcular cual es la realción entre $|\Psi\rangle^{(t)}$ y $|\Psi\rangle^{(t+1)}$ . Primero aplicamos el oráculo

$O|\Psi\rangle^{(t)}=-\alpha|k\rangle+\sum_{k\neq i}\beta|i\rangle$ .

A continuación aplicamos el operador $G$ , y obtenemos

$\begin{array}{ll}G\left(-\alpha|k\rangle+\sum_{k \neq i}\beta|i\rangle\right) &=-\alpha(\frac{2}{n}-1)|k\rangle-\sum_{i\neq k}^n \alpha \frac{2}{n}|i\rangle+\left(\sum_{i=1}^n (\frac{2}{n}-1)|i\rangle\langle i|\right)\left(\sum_{i \neq k}\beta|i\rangle\right)\\&=\alpha\frac{(n-2)}{n}|k\rangle-\alpha\sum_{i\neq k}^n\frac{2}{n}|i\rangle+\sum_{i\neq k}^n(\frac{2}{n}-1)\beta|i\rangle+\beta\frac{2}{n}\sum_{i\neq k}^n(n-2)|i\rangle+\beta\frac{2}{n}(n-1)|k\rangle\end{array}$ .

El último término requiere un poco de trabajo, pero es simple algebra. Por último, factorizamos los vectores y

$|\Psi\rangle^{(t+1)}=\left[\frac{(n-2)}{n}\alpha+2\frac{(n-1)}{n}\beta\right]|k\rangle+\left[\frac{(n-2)}{n}\beta-\frac{2}{n}\alpha\right]\sum_{i=1}^n|i\rangle$ .

A partir de esta ecuación podemos escribir el estado como

$|\Psi\rangle^{(t)}=\sin((2t+1)\theta)|k\rangle+\sum_i\frac{1}{\sqrt{n-1}}\cos((2j+1)\theta)|i\rangle$

donde $\sin^2\theta=1/n$ . Esto lo escribo sin demostrar, debido a que la prueba es larga y bastante laboriosa, pero puede obtenerse con simple algebra.

Ahora necesitamos que la amplitud de $|k\rangle$ sea cercana a 1, y el resto sea cercano a 0. Si $t=(\pi-2\theta)4\theta$ el coseno se vuelve 0, pero el problema es que ese número no es necesariamente un entero. Entonces elijamos un entero $\tilde{t}=\lfloor\pi/4\theta\rfloor$ . Tenemos que $|(2\tilde{t}+1)\theta-(2t+1)\theta| \leq \theta$ y $\cos((2t+1)\theta)=\pi/2$ implican $\cos((2\tilde{t}+1)\theta)\leq\sin\theta$ . Por lo tanto, para un ángulo pequeño $\theta$ , $\cos^2((2\tilde{t}+1)\theta) \leq \sin^2\theta=1/n$ . De esta forma la probabilidad de éxito, i.e., la probabilidad de obtener el vector $|k\rangle$ es $1-1/n$ .

El algoritmo original de Grover realizaba este procedimiento con 50% de probabilidades de éxito, aquí (utilizando una técnica presentada en este paper) probamos que la probabilidad de éxito está muy cercana a 1 si se elige apropiadamente el número de iteraciones. En este caso $\tilde{t}=\lfloor\pi/4\theta\rfloor=O(\sqrt{n})$ . Si hacemos más iteraciones, debido a la oscilación del estado, la probabilidad de éxito disminuye. Por lo tanto debemos hacer exactamente esa cantidad de iteraciones o un número cercano.

De similar manera podemos demostrar que si tenemos $K$ objetos marcados, podemos encontrar uno de esos objetos en $O(\sqrt{n/K})$ con $1-K/n$ probabilidades de éxito.

En el caso general nuestra iteración principal $\left(GO\right)^t|\psi\rangle$ la podemos escribir de la siguiente forma

$-AS_0A^{-1}S_k$

donde $A$ es un operador unitario, $S_0$ cambia el signo de la amplitud si es el vector 0, y $S_k$ es el oráculo que cambia el signo al vector $|k\rangle$ . Para los detalles de las demostraciones para el caso general consultar el paper Quantum Amplitude Amplification and Estimation. Para el caso del algoritmo de Grover tenemos que $A=W$ .

Otro problema es intentar encontrar todos los objetos marcados, para ello se requiere $O(\sqrt{Kn})$ con una probabilidad de éxito de $2^{-\Omega(K)}$ .

Se puede demostrar también que esta cota superior es óptima, i.e., existe una cota inferior del mismo orden. Pero esa demostración queda para otro día.

23 de febrero de 2010

AQIS 2010

16 de febrero de 2010

Amplificación de Amplitud