Transformada cuántica de Fourier

En general, la suma es una operación más sencilla que la multiplicación. Es por ello que en ocasiones buscamos transformaciones que conviertan los productos en sumas. Mediante esta transformación, nos “movemos” a un espacio en el que la operación, compuesta por productos en el espacio origen, que deseamos realizar se puede efectuar con sumas y una vez que obtuvimos el resultado regresamos al espacio original mediante la trasformación inversa obteniendo así el resultado de la operación. Un ejemplo de esto son los logaritmos. Digamos que queremos realizar la operación a \cdot b, si aplicamos el logaritmo entonces tenemos \ln (a \cdot b) = \ln a + \ln b, por las propiedades de los logaritmos. Ahora, digamos que el resultado de la suma de logaritmos es c entonces el resultado de a \cdot b se obtiene aplicando la operación inversa del logaritmo a c, entonces a \cdot b = e^c. Esto puede parecer un método poco práctico, sin embargo, la idea subyacente es de mucha importancia en la computación cuántica. La transformación cuántica de Fourier es un ejemplo de ello+-.

Introducción

De manera análoga a cómo la transformada discreta de Fourier convierte una función en el dominio del tiempo a otra función en el dominio de frecuencia, la transformada cuántica de Fourier, al ser una transformada de Fourier discreta aplicada al vector de amplitudes del estado cuántico, transforma un estado cuántico

    \[\sum_{i=0}^{N-1} x_i |i\rangle\]

al estado cuántico

    \[\sum_{i=0}^{N-1} y_i |i\rangle\]

donde los y_k para k = 0, 1, \ldots, N-1 están dados por

    \[y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j w^{jk}\]

donde

    \[w = e^{2 \pi i / N}\]

La transformación cuántica de Fourier

La transformada cuántica de Fourier está dada por

    \[ \sum_{x = 0}^{N-1} f(x) |x \rangle = \sum_{y=0}^{N-1} \tilde{f}(y) | y \rangle \]

donde

    \[\tilde{f} (y) = \frac{1}{\sqrt{N}} \sum_{x = 0} ^{N-1} e^{2 \pi i xy /N} f(x)\]

De acuerdo a las expresión anteriores, sobre los vectores base se aplica la trasformación unitaria N \times N:

    \[U_{F_N} |x\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0} ^{N-1} e^{2 \pi i xy /N} | y \rangle\]

Para el caso de la computación cuántica, utilizamos el caso binario (N = 2^n) y sustituimos en la última expresión la expansión binaria:

    \[y = y_{n-1}y_{n-2} \cdots y_{0} = y_{n-1} \cdot 2^{n-1} + \cdots + y_0 2^0\]

con y_i \in \{ 0,1 \}. Obtenemos así

    \[U_{F_{2^n}} = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}=0}^{1} \cdots \sum_{y_0 = 0}^{1} e^{2\pi ix \sum_{l=1}^{n} y_{n-l} / 2^{l}} | y_{n-1} \cdots y_{0} \rangle\]

Utilizando la propiedad de que la exponencial de una suma es el producto de exponenciales, e^{a+b} = e^a e^b, resulta

    \[U_{F_{2^n}} =  \frac{1}{\sqrt{2^n}} \bigotimes_{l=1}^{n} \left [  \sum_{y_{n-l}=0}^{1} e^{2\pi i x y_{n-l}/ 2^l}   | y_{n-l}  \rangle \right ]\]

Entonces, la transformada cuántica de Fourier transforma la base computacional en otra base con vectores factorizables, esto es, sin entrelazamiento. Ahora, teniendo en consideración la representación en fracciones binarias:

    \[\frac{x}{2} = x_{n-1} 2^{n-2} + \cdots + x_1 + x_0 2^{-1} = x_{n-1} \cdots x_1 . x_0\]

    \[\frac{x}{2^2} = x_{n-1} 2^{n-3} + \cdots + x_2 + x_1 2^{-1} + x_0 2^{-2} = x_{n-1} \cdots x_2 . x_1 x_0\]

dado que el exponencial e^{2\pi i k} = 1 cuando k es entero, despreciamos la parte entera en las representaciones en fracciones binarias, por lo que

    \[U_{F_{2^n}}  = \frac{1}{\sqrt{2^n}} ( | 0 \rangle + e^{2\pi i 0.x_0} | 1  \rangle ) \otimes ( | 0 \rangle + e^{2\pi i 0.x_1x_0} | 1 \rangle ) \otimes \cdots \otimes ( | 0 \rangle + e^{2\pi i 0.x_{n-1} \cdots x_0} | 1 \rangle )\]

Expresado de forma compacta

    \[U_{F_{2^n}}  = \frac{1}{\sqrt{2^n}} \bigotimes_{l=1}^{n} ( | 0 \rangle + e^{2\pi i 0.x_{l-1} \cdots x_0} | 1 \rangle )\]

La transformada cuántica de Fourier puede implementarse en una computadora cuántica mediante un circuito cuántico. Para el caso de n qubits el circuito general sería de la forma:

Imagen extraída de: Moret, V. Principios fundamentales de computación cuántica. (2013) Universidad de la Coruña, Departamento de Computación. Facultad de Informática

Ahora que conocemos la transformada cuántica de Fourier. estamos en condiciones de discutir el algoritmo de Shor, el cual es un algoritmo cuántico para descomponer en factores un número N. Sobre este hablaremos en un próximo artículo.

Referencias

Moret, V. Principios fundamentales de computación cuántica. (2013) Universidad de la Coruña, Departamento de Computación. Facultad de Informática

Algoritmo de Shor. (2021, 27 de junio). Wikipedia, La enciclopedia libre. Fecha de consulta: 00:15 UTC, mayo 30, 2022 desde https://es.wikipedia.org/w/index.php?title=Algoritmo_de_Shor&oldid=136629689.