viernes, 30 de octubre de 2015

Algoritmos

Algoritmos cuánticos

transformada cuántica de Fourier es una transformación sobre bits cuánticos, y es la analogía cuántica de la transformada de Fourier discreta. La transformada de Fourier es una parte de muchos algoritmos cuánticos, el algoritmo de factorización de Shor y el cálculo del logaritmo discreto, el algoritmo de estimación de fase para estimar los eigenvalores de un operador unitario, y logaritmos para HSP hidden subgroup problem.
La transformada de Fourier puede ser realizada eficientemente en un ordenador cuántico, con una particular descomposición en un producto de matrices unitarias simples. Usando una descomposición simple, la trasformación discreta de Fourier puede ser implementada como un circuito cuántico que tiene solo O(n^2) puertas Hadamar y puertas de desplazamiento de fase controladas, donde n es el número de qubits.1 Esto puede ser comparado con la transformada de Fourier discreta, que utiliza O(n2^n) puertas (donde n es el número de bits), lo cual es exponencialmente mejor que O(n^2). Sin embargo, la transformada cuántica de Fourier actúa sobre un estado cuántico, mientras que la trasformada de Fourier clásica actúa sobre un vector, así que no todas las tareas que usan la transformada de Fourier clásica pueden utilizar la ventaja de esta aceleración exponencial.
Los mejores algoritmos cuánticos de transformada de Fourier conocidos actualmente requieren solo O(n \log n) puertas para alcanzar una aproximación eficiente.

Definición

La transformada de Fourier cuántica es la transformada de Fourier discreta clásica aplicada al vector de amplitudes de un estado cuántico. La transformada de Fourier clásica (unitaria) actúa sobre un vector en \mathbb{C}^N, (x0,..., xN−1) y lo mapea al vector (y0,..., yN−1) de acuerdo con la fórmula:
y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega^{jk}
Donde \omega = e^{\frac{2 \pi i}{N}} es una raíz de la unidad Nth primitiva.
De forma similar, la transformada cuántica de Fourier actúa sobre un estado cuántico \sum_{i=0}^{N-1} x_i |i\rangle y lo mapea a un estado cuántico \sum_{i=0}^{N-1} y_i |i\rangle de acuerdo con la fórmula:
y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega^{jk}.
Esto puede ser expresado como la aplicación
|j\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \omega^{jk} |k\rangle.
De forma equivalente, la transformada de Fourier cuántica puede ser vista como una matriz unitaria actuando sobre vectores estado cuántico, donde la matriz unitaria F_N está dada por
F_N = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(N-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(N-1)}\\ \vdots&\vdots&\vdots&\vdots&&\vdots\\ 1&\omega^{N-1}&\omega^{2(N-1)}&\omega^{3(N-1)}&\cdots&\omega^{(N-1)(N-1)} \end{bmatrix}.

Propiedades

Unitaria

Muchas de las propiedades de la transformada de Fourier surgen del hecho de que es una transformación unitaria. Esto puede ser comprobado realizando la multiplicación de matrices y verificando la relación FF^{\dagger}=F^{\dagger}F=I, donde F^\dagger es la Hermitica adjunta de F. Alternativamente, podemos comprobar que los vectores de norm 1 obtienen relación con los vectores de 1.
De las propiedades unitarias surge que la inversa de la transformada cuántica de Fourier es la hermítica adjunta de la matriz de Fourier, así F^{-1}=F^{\dagger}. Existe un circuito cuántico eficiente que implementa la transformada inversa cuántica de Fourier. Así que ambas transformaciones pueden ser realizadas en un ordenador cuántico.

Implementación del Circuito

Quantum circuit representation of the quantum Fourier transform
La transformada de Fourier puede ser implementada aproximadamente para cualquier N, sin embargo, la implementación para el caso en el que N es una potencia de 2 es mucho más simple. Supongamos N = 2n. Tenemos la base ortogonal consistente en los vectores
|0\rangle, \ldots , |2^n - 1\rangle.
La base de todos los posibles estados de los qubits es:
| x \rangle = | x_1 x_2 \ldots x_n \rangle = | x_1 \rangle \otimes | x_2 \rangle \otimes \cdots \otimes | x_n \rangle
donde, con la notación producto tensorial \otimes, |x_j\rangle indica que el qubit j está en el estado x_j, con x_j entre 0 y 1. Por convención, el índice de la base de estados x ordena los posibles estados de los qubits lexicográficamente, por ejemplo, por convención el paso de binario a decimal es de la forma.:
x = x_1 2^{n-1} + x_2 2^{n-2} +\cdots + x_n 2^0.\quad
Esto también es útil para la notación binaria fraccionaria:
[0. x_1 \ldots x_m] = \sum_{k = 1}^m x_k 2^{-k}.
Por tanto, [0.x_1] = \frac{x_1}{2} and [0.x_1 x_2] = \frac{x_1}{2}+\frac{x_2}{2^2}.
Con esta notación, la acción de la transformada de Fourier cuántica puede ser expresada por:
|x_1 x_2 \ldots x_n \rangle \mapsto \frac{1}{\sqrt{N}} \ \left(|0\rangle + e^{2 \pi i \, [0.x_n] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_{n-1} x_n] }|1\rangle\right) \otimes \cdots \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_1 x_2 \ldots x_n] }|1\rangle\right),
donde la salida del qubit 1 es una superposición del estado |0\rangle y e^{2 \pi i \, [0.x_n] }|1\rangle, y así en los otros qubits.
En otras palabras, la operación de la transformada de Fourier discreta sobre n-qubits, puede ser factorizada dentro del producto tensor de n qubits-únicos, sugiriendo que es fácil de representar en un circuito cuántico. De hecho, cada una de las operaciones de los qubits-únicos puede ser implementada eficientemente usando una puerta Hadamar y puertas controladas de desplazamiento de fase. El primer término requiere una puerta Hadamar, el siguiente requiere una puerta Hadamar y una puerta controlada de desplazamiento de fase y cada siguiente término requiere una puerta adicional de desplazamiento de fase. Sumando el número de puertas da 1 + 2 + \cdots + n = n(n+1)/2 = O(n^2) puertas, el cual es proporcional al número de qubits.

Ejemplo

Considerar la transformada cuántica de Fourier sobre 3 qubits. Es la siguiente transformación:
|j\rangle \mapsto \frac{1}{\sqrt{2^3}} \sum_{k=0}^{2^3-1} \omega^{jk} |k\rangle,
donde \omega satisface \omega^8=\left(e^{\frac{2\pi i}{8}}\right)^8=1 (ya que N = 2^3 = 8).
La matriz que representa esta transformación es
F_{2^3} = \frac{1}{\sqrt{2^3}} \begin{bmatrix} 1&1&1&1&1&1&1&1 \\ 1&\omega&\omega^2&\omega^3&\omega^4&\omega^5&\omega^6&\omega^7 \\ 1&\omega^2&\omega^4&\omega^6&\omega^8&\omega^{10}&\omega^{12}&\omega^{14} \\ 1&\omega^3&\omega^6&\omega^9&\omega^{12}&\omega^{15}&\omega^{18}&\omega^{21} \\ 1&\omega^4&\omega^8&\omega^{12}&\omega^{16}&\omega^{20}&\omega^{24}&\omega^{28} \\ 1&\omega^5&\omega^{10}&\omega^{15}&\omega^{20}&\omega^{25}&\omega^{30}&\omega^{35} \\ 1&\omega^6&\omega^{12}&\omega^{18}&\omega^{24}&\omega^{30}&\omega^{36}&\omega^{42} \\ 1&\omega^7&\omega^{14}&\omega^{21}&\omega^{28}&\omega^{35}&\omega^{42}&\omega^{49} \\ \end{bmatrix} = \frac{1}{\sqrt{2^3}} \begin{bmatrix} 1&1&1&1&1&1&1&1 \\ 1&\omega&\omega^2&\omega^3&\omega^4&\omega^5&\omega^6&\omega^7 \\ 1&\omega^2&\omega^4&\omega^6&1&\omega^2&\omega^4&\omega^6 \\ 1&\omega^3&\omega^6&\omega&\omega^4&\omega^7&\omega^2&\omega^5 \\ 1&\omega^4&1&\omega^4&1&\omega^4&1&\omega^4 \\ 1&\omega^5&\omega^2&\omega^7&\omega^4&\omega&\omega^6&\omega^3 \\ 1&\omega^6&\omega^4&\omega^2&1&\omega^6&\omega^4&\omega^2 \\ 1&\omega^7&\omega^6&\omega^5&\omega^4&\omega^3&\omega^2&\omega \\ \end{bmatrix}.
La transformada de Fourier cuántica de 3-qubit es las siguiente operación:
|x_1, x_2, x_3 \rangle \mapsto \frac{1}{\sqrt{2^3}} \ \left(|0\rangle + e^{2 \pi i \, [0.x_3] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_2 x_3] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_1 x_2 x_3] }|1\rangle\right).
Este circuito cuántico implementa la transformada cuántica de Fourier sobre el estado cuántico |x_1,x_2,x_3\rangle.
Quantum Fourier transform on three qubits.svg
Las puertas cuánticas usadas en el circuito de arriba son la puerta Hadamar y la puerta controlada de desplazamiento de fase R_\theta.
Como se calculó antes, el número de puertas usadas es n(n+1)/2 lo cual es igual a 6, para  n = 3.

La Transformada de Fourier Cuántica (QFT)

La transformada de Fourier cuántica toma un estado $ \vert\varphi\rangle$ y lo transforma en un estado $ \vert\phi\rangle$ tal que

$\displaystyle \vert\varphi\rangle = \left(\begin{array}{c} f_0 f_1 \vdots... ...eft(\begin{array}{c} F_0 F_1 \vdots F_{N-1} \end{array}\right), \quad $


$\displaystyle \vert\varphi\rangle \stackrel{\emph{QFT}}{\longrightarrow} \vert\phi\rangle $

donde los $ F_k$ son los coeficientes de la transformada de Fourier de $ f_0, \ldots, f_{N-1}$. Como los estados cuánticos deben estar normalizados, la transformada de Fourier cuántica cumple con la siguiente ecuación

$\displaystyle F_k = \frac 1 {\sqrt{N}}\sum_{j=0}^{N-1}f_j\omega^{jk} $

Si el estado cuántico además corresponde a una secuencia de qubits podemos decir que $ N = 2^n$ y la expresión se traduce a

$\displaystyle F_k = \frac 1 {\sqrt{2^n}}\sum_{j=0}^{2^n-1}f_j\omega^{jk}$(3.5)


También sabemos que el coeficiente $ F_k$ multiplica al ket base $ \vert k\rangle$ asi que

$\displaystyle \emph{QFT}\vert\varphi\rangle = \sum_{k=0}^{2^n-1}F_k\vert k\rangle = $


$\displaystyle \sum_{k=0}^{2^n-1}\left(\frac 1 {\sqrt{2^n}}\sum_{j=0}^{2^n-1}f_j\omega^{jk}\right)\vert k\rangle = $


$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{j=0}^{2^n-1}f_j\sum_{k=0}^{2^n-1}\omega^{jk}\vert k\rangle$(3.6)


Y como $ f_j$ es el coeficiente del vector base $ \vert j\rangle$, entonces por linealidad la ecuación 3.5 es equivalente a decir que

$\displaystyle \emph{QFT}\vert j\rangle = \frac 1 {\sqrt{2^n}}\sum_{k=0}^{2^n-1}w^{jk}\vert k\rangle$(3.7)


ya que

$\displaystyle \emph{QFT}\vert\varphi\rangle = \emph{QFT}\sum_{j=0}^{2^n-1}f_j\vert j\rangle = $


$\displaystyle \sum_{j=0}^{2^n-1}f_jQFT\vert j\rangle = $


$\displaystyle \sum_{j=0}^{2^n-1}f_j \frac 1 {\sqrt{2^n}}\sum_{k=0}^{2^n-1}\omega^{jk}\vert k\rangle = $


% latex2html id marker 7597 $\displaystyle \frac 1 {\sqrt{2^n}}\sum_{j=0}^{2^n-... ...m_{k=0}^{2^n-1}\omega^{jk}\vert k\rangle = \emph{ecuaci\'on}\; \ref{eq-igual} $












El algoritmo del temple cuántico (en inglés, quantum annealing), también llamado aleación, cristalización o recocido, es análogo al temple simulado pero sustituyendo la activación térmica por el efecto túnel.
QA es una clase algorítmica parecida al temple simulado (“Simulated Annealing” o 'SA' de Kirkpatrick y otros) que consiste en una adaptación del algoritmo clásico deMetropolis-Hastings. Sin embargo, QA emplea un campo cuántico en lugar de ungradiente térmico. Para explorar el paisaje del problema de optimización, SA y sus variantes (como el Temple Paralelo) aprovechan las fluctuaciones “térmicas” correspondientes a gradientes de temperatura, mientras que QA utiliza para ello fluctuaciones “cuánticas”. Una fluctuación cuántica es un cambio en la cantidad de energía de un punto del espacio durante brevísimos lapsos de tiempo, como resultado del principio de incertidumbre enunciado por Heisemberg.
En cierto modo, los métodos de temple, cristalización o 'annealing' son una metáfora de la naturaleza que trata de imitar la forma en que se ordenan las moléculas de un metal al magnetizarse, o de un cristal durante la transición de fase, que ocurre por ejemplo, al enfriarse el agua o el dióxido de silicio tras haber sido previamente calentados: si el enfriamiento fuese lento, habitualmente el cristal así generado tendrá pocas imperfecciones (es decir, se encontrará en un metaestado de baja energía) que si se enfriara demasiado rápido (metaestado de alta energía). Este modelo físico natural se basa en la propensión a minimizar su energía libre (en el sentido de Helmholtz) de un sistema ergódico, tal como un sistema termodinámico cerrado en que todos los estados configuracionales sean equiprobables.
Los métodos de temple se basan por lo general en el algoritmo de Monte Carlo, que repite una gran cantidad de muestreos aleatorios sobre un hipercubo de dimensión 'N' (espacio de soluciones del problema), a fin de generar estados muestrales y permitiendo reducir mucho la complejidad de cómputo a costa de perder algo de precisión estadística.

Quant-annl.jpg


Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)