Transformada cuántica de Fourier

En computación cuántica, la 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 Hadamard y puertas de desplazamiento de fase controladas, donde

$n$

es el número de qubits. Esto puede ser comparado con la transformada de Fourier discreta, que utiliza

$O(n{2}^n)$

puertas (donde

$n$

es el número de bits), lo cual es exponencialmente mayor 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

${ℂ}^N$

, (x₀,..., x_N−1) y lo mapea al vector (y₀,..., y_N−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 N^th 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⟩$ y lo mapea a un estado cuántico $\sum _{i=0}^{N-1}{y}_i|i⟩$ 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⟩\mapsto \frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{\omega }^{jk}|k⟩.$

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}}\left[\begin{array}{cccccc}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)}\\ ⋮& ⋮& ⋮& ⋮& & ⋮\\ 1& {\omega }^{N-1}& {\omega }^{2(N-1)}& {\omega }^{3(N-1)}& \cdots & {\omega }^{(N-1)(N-1)}\end{array}\right].$

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 $F{F}^{†}=F^{†}F=I$, donde $F^{†}$ es la Hermitica adjunta de $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í $F^{-1}=F^{†}$. 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

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.

Transformada cuántica de Fourier implementada en circuito cuántico

Cambio de notación.

Sea el número 123456. Dicho número realmente puede ser descrito por

$123456=1\cdot 10^6+2\cdot 10^5+3\cdot 10^4..+6\cdot 10^0={\sum }_{i=0}^n{j}_{i}10^{n-i}$

donde $n$ es el número de término que describe dicho número. Cabe destacar que $j_i$ puede tomar valores entre 0 y 9 ya que se están haciendo operaciones módulo 10.

Se puede definir también para fracciones. Por ejemplo, el número

$0.2345678$

puede ser visto como

$0.2345678=2\cdot 10^{-1}+3\cdot 10^{-2}+4\cdot 10^{-3}+5\cdot 10^{-4}+6\cdot 10^{-5}...={\sum }_{i=0}^n{j}_{i}10^{-i}$

Es posible definir el mismo tipo de notación en binario. Este tipo de notación es conocida como notación binaria o representación binaria

Supongamos N = 2ⁿ. Tenemos la base ortogonal consistente en los vectores

$|0⟩,\dots ,|2^n-1⟩.$

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

$|x⟩=|x_1{x}_2\dots x_n⟩=|x_1⟩\otimes |x_2⟩\otimes \cdots \otimes |x_n⟩$

donde, con la notación producto tensorial $\otimes$, $|x_j⟩$ indica que el qubit $j$ está en el estado $x_j$, con $x_j$ entre 0 y 1 ya que estamos haciendo módulo 2. 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.$

La acción de la puerta de Hadamard es $H|x_j⟩=\left(\frac{1}{\sqrt{2}}\right)(|0⟩+e^{2\pi i{x}_j{2}^{-1}}|1⟩)$, donde el signo depende de $x_i$.

La transformada cuántica de Fourier se puede escribir como el producto tensorial de una serie de términos, conocido como tensotorio:

$\text{QFT}(|x⟩)=\frac{1}{\sqrt{N}}\underset{j=1}{\overset{n}{⨂}}(|0⟩+{\omega }_N^{x{2}^{n-j}}|1⟩).$

Esto también es útil para la notación binaria fraccionaria:

$[0.x_1\dots 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\dots x_n⟩\mapsto \frac{1}{\sqrt{N}}(|0⟩+e^{2\pi i[0.x_n]}|1⟩)\otimes (|0⟩+e^{2\pi i[0.x_{n-1}{x}_n]}|1⟩)\otimes \cdots \otimes (|0⟩+e^{2\pi i[0.x_1{x}_2\dots x_n]}|1⟩),$

donde la salida del qubit 1 es una superposición del estado $|0⟩$ y $e^{2\pi i[0.x_n]}|1⟩$, y así en los otros qubits.

Demostración

Se parte de la demostración de transformada discreta de Fourier cuántica dada por

$|x⟩\to \frac{1}{\sqrt{N}}{\sum }_{k=0}^{N-1}{e}^{i2\pi xk/N}|k⟩$

Ahora se especifica la dimensión de nuestro espacio dada por $N=2^n$llegando a

$|x⟩\to \frac{1}{\sqrt{2^n}}{\sum }_{k=0}^{2^n-1}{e}^{i2\pi xk/2^n}|k⟩$.

Aplicando notación binaria sobre $k$ de tal forma que $\frac{k}{2^n}=0.k_1{k}_2..k_n=\sum _{l=0}^n{k}_l{2}^{-l}$ . Luego separando, la sumatoria en $k$ en $n$ sumatorias sobre los distintos valores $k_l$.

$|x⟩⟶\frac{1}{2^{n/2}}\sum _{k_1=0}^1..\sum _{k_n=0}^1{e}^{i2\pi x\sum _{l=0}^n{2}^{-l}{k}_l}|k_1..k_n⟩$

Utilizando propiedades de la exponencial puedo llegar a

$|x⟩⟶\frac{1}{2^{n/2}}\sum _{k_1=0}^1..\sum _{k_n=0}^1\underset{l=1}{\overset{n}{\otimes }}{e}^{i2\pi x{k}_l{2}^{-l}}|k_l⟩$

Cambiando el productorio por el sumatorio puedo llegar a

$|x⟩⟶\frac{1}{2^{n/2}}\underset{l=1}{\overset{n}{\otimes }}\sum _{k_l=0}^1{e}^{i2\pi x{k}_l{2}^{-l}}|k_l⟩$

Aplicando la sumatoria:

$|x⟩⟶\frac{1}{2^{n/2}}\underset{l=1}{\overset{n}{\otimes }}[|0⟩+e^{i2\pi x{2}^{-l}}|1⟩]$

La cuestión ahora es poner $x$ en notación binaria como $x=x_1{x}_2...x_n$. Realizando un par de términos. Por ejemplo, para $l=1$:

$x/2=x_1{x}_2...x_{n-1}.x_n$.

Ahora bien,

$e^{2\pi i{x}_1{x}_2...x_{n-1}.x_n}=e^{2\pi i{x}_1{x}_2...x_{n-1}}\times e^{2\pi i0.x_n}=e^{2\pi i0.x_n}$

donde se ha utilizado que $x_1{x}_2...x_{n-1}$ es un número entero ya que es ${\sum }_{i=0}^n{x}_i{2}^{n-i}$ con $x_i\in \{0,1\}$.

Aplicando el mismo razonamiento para $l=2$:

Se tiene:

$\frac{x}{2^2}=x_1{x}_2...x_{n-2}.x_{n-1}{x}_n$

y se llega a que

$e^{2\pi i{x}_1{x}_2....x_{n-2}.x_{n-1}{x}_n}=e^{2\pi i{x}_1{x}_2...x_{n-2}}\times e^{2\pi i0.x_{n-1}{x}_n}=e^{2\pi i0.x_{n-1}{x}_n}$

Si se aplica en general se puede llegar al resultado donde falta por introducir puertas lógicas swap que cambien el qubit 1 con el $n$, el 2 con el $n-1$ y así llegando a:

$|x⟩⟶\frac{(|0⟩+e^{2\pi i0.x_n}|1⟩)\otimes (|0⟩+e^{2\pi i0.x_{n-1}{x}_n}|1⟩)\otimes ..\otimes (|0⟩+e^{2\pi i0.x_1{x}_2..x_n}|1⟩)}{2^{n/2}}$

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 $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⟩\mapsto \frac{1}{\sqrt{2^3}}\sum _{k=0}^{2^3-1}{\omega }^{jk}|k⟩,$

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}}\left[\begin{array}{cccccccc}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{array}\right]=\frac{1}{\sqrt{2^3}}\left[\begin{array}{cccccccc}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{array}\right].$

La transformada de Fourier cuántica de 3-qubit es las siguiente operación:

$|x_1,x_2,x_3⟩\mapsto \frac{1}{\sqrt{2^3}}(|0⟩+e^{2\pi i[0.x_3]}|1⟩)\otimes (|0⟩+e^{2\pi i[0.x_2{x}_3]}|1⟩)\otimes (|0⟩+e^{2\pi i[0.x_1{x}_2{x}_3]}|1⟩).$

Este circuito cuántico implementa la transformada cuántica de Fourier sobre el estado cuántico $|x_1,x_2,x_3⟩$.

Las puertas cuánticas usadas en el circuito de arriba son la puerta Hadamard 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.