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 ${\displaystyle O(n^{2})}$ puertas Hadamard y puertas de desplazamiento de fase controladas, donde ${\displaystyle n}$ es el número de qubits.¹ Esto puede ser comparado con la transformada de Fourier discreta, que utiliza ${\displaystyle O(n2^{n})}$ puertas (donde ${\displaystyle n}$ es el número de bits), lo cual es exponencialmente mejor que ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \mathbb {C} ^{N}}$, (x₀,..., x_N−1) y lo mapea al vector (y₀,..., y_N−1) de acuerdo con la fórmula:

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega ^{jk}}$

Donde ${\displaystyle \omega =e^{\frac {2\pi i}{N}}}$ es una raíz de la unidad N^th primitiva.

De forma similar, la transformada cuántica de Fourier actúa sobre un estado cuántico ${\displaystyle \sum _{i=0}^{N-1}x_{i}|i\rangle }$ y lo mapea a un estado cuántico ${\displaystyle \sum _{i=0}^{N-1}y_{i}|i\rangle }$ de acuerdo con la fórmula:

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega ^{jk}.}$

Esto puede ser expresado como la aplicación

${\displaystyle |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 ${\displaystyle F_{N}}$ está dada por

${\displaystyle 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 ${\displaystyle FF^{\dagger }=F^{\dagger }F=I}$, donde ${\displaystyle F^{\dagger }}$ es la Hermitica adjunta de ${\displaystyle F}$. Alternativamente, podemos comprobar que los vectores de norma 1 son transformados a su vez en vectores de norma 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í ${\displaystyle 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 = 2ⁿ. Tenemos la base ortogonal consistente en los vectores

${\displaystyle |0\rangle ,\ldots ,|2^{n}-1\rangle .}$

La base de todos los posibles estados de los qubits es:

${\displaystyle |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 ${\displaystyle \otimes }$, ${\displaystyle |x_{j}\rangle }$ indica que el qubit ${\displaystyle j}$ está en el estado ${\displaystyle x_{j}}$, con ${\displaystyle x_{j}}$ entre 0 y 1. Por convención, el índice de la base de estados ${\displaystyle 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.:

${\displaystyle 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:

${\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.}$

Por tanto, ${\displaystyle [0.x_{1}]={\frac {x_{1}}{2}}}$ and ${\displaystyle [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:

${\displaystyle |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 ${\displaystyle |0\rangle }$ y ${\displaystyle 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 Hadamard y puertas controladas de desplazamiento de fase. El primer término requiere una puerta Hadamard, el siguiente requiere una puerta Hadamard 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 ${\displaystyle 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:

${\displaystyle |j\rangle \mapsto {\frac {1}{\sqrt {2^{3}}}}\sum _{k=0}^{2^{3}-1}\omega ^{jk}|k\rangle ,}$

donde ${\displaystyle \omega }$ satisface ${\displaystyle \omega ^{8}=\left(e^{\frac {2\pi i}{8}}\right)^{8}=1}$ (ya que ${\displaystyle N=2^{3}=8}$).

La matriz que representa esta transformación es

${\displaystyle 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:

${\displaystyle |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 ${\displaystyle |x_{1},x_{2},x_{3}\rangle }$.

Las puertas cuánticas usadas en el circuito de arriba son la puerta Hadamard y la puerta controlada de desplazamiento de fase ${\displaystyle R_{\theta }}$.

Como se calculó antes, el número de puertas usadas es ${\displaystyle 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  y lo transforma en un estado  tal que

donde los  son los coeficientes de la transformada de Fourier de . Como los estados cuánticos deben estar normalizados, la transformada de Fourier cuántica cumple con la siguiente ecuación

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

(3.5)

También sabemos que el coeficiente  multiplica al ket base  asi que

(3.6)

Y como  es el coeficiente del vector base , entonces por linealidad la ecuación 3.5 es equivalente a decir que

(3.7)

ya que