Transformada cuántica de Fourier

En computación cuántica , la transformada cuántica de Fourier (TCF) es una transformación lineal sobre bits cuánticos y es el análogo cuántico de la transformada discreta de Fourier . La transformada cuántica de Fourier forma parte de muchos algoritmos cuánticos , en particular el algoritmo de Shor para factorizar y calcular el logaritmo discreto , el algoritmo de estimación de fase cuántica para estimar los autovalores de un operador unitario y algoritmos para el problema del subgrupo oculto . La transformada cuántica de Fourier fue descubierta por Don Coppersmith . ^{[ 1 ]} Con pequeñas modificaciones a la TCF, también se puede utilizar para realizar operaciones aritméticas de enteros rápidas , como la suma y la multiplicación. ^{[ 2 ] [ 3 ] [ 4 ]}

La transformada cuántica de Fourier se puede realizar de manera eficiente en una computadora cuántica con una descomposición en el producto de matrices unitarias más simples . La transformada discreta de Fourier en${\displaystyle 2^{n}}$Las amplitudes se pueden implementar como un circuito cuántico que consta únicamente de${\displaystyle O(n^{2})}$Compuertas de Hadamard y compuertas de desplazamiento de fase controlado , donde${\displaystyle n}$es el número de cúbits. ^{[ 5 ]} Esto se puede comparar con la transformada discreta de Fourier clásica, que toma${\displaystyle O(n2^{n})}$puertas (donde${\displaystyle n}$es el número de bits), que es exponencialmente mayor que${\displaystyle O(n^{2})}$.

La transformada de Fourier cuántica actúa sobre un vector de estado cuántico (un registro cuántico ), y la transformada discreta de Fourier clásica actúa sobre un vector. Ambos tipos de vectores pueden escribirse como listas de números complejos. En el caso clásico, el vector puede representarse, por ejemplo, con una matriz de números de punto flotante , y en el caso cuántico es una secuencia de amplitudes de probabilidad para todos los resultados posibles tras la medición (los resultados son los estados base o autoestados ). Dado que la medición colapsa el estado cuántico a un único estado base, no todas las tareas que utilizan la transformada de Fourier clásica pueden aprovechar la aceleración exponencial de la transformada de Fourier cuántica.

Los mejores algoritmos de transformada de Fourier cuántica conocidos (a finales del año 2000) solo requieren${\displaystyle O(n\log n)}$puertas para lograr una aproximación eficiente, siempre que se implemente una puerta de fase controlada como una operación nativa. ^{[ 6 ]}

La transformada cuántica de Fourier es la transformada discreta clásica de Fourier aplicada al vector de amplitudes de un estado cuántico, que tiene longitud${\displaystyle N=2^{n}}$si se aplica a un registro de${\displaystyle n}$cúbits.

La transformada clásica de Fourier actúa sobre un vector.${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}}$y lo mapea al vector ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}}$Según la fórmula

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

dónde${\displaystyle \omega _ {N}=e^{\frac {2\pi i}{N}}}$es una raíz N - ésima de la unidad .

De manera similar, la transformada cuántica de Fourier actúa sobre un estado cuántico.${\textstyle |x\rangle =\sum _ {j=0}^{N-1}x_ {j}|j\rangle }$y lo mapea a un estado cuántico${\textstyle \sum _{j=0}^{N-1}y_{j}|j\rangle }$Según la fórmula

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

(Las convenciones para el signo del exponente del factor de fase varían; aquí la transformada cuántica de Fourier tiene el mismo efecto que la transformada discreta de Fourier inversa, y viceversa).

Desde${\displaystyle \omega _ {N}^{l}}$es una rotación, la transformada cuántica inversa de Fourier actúa de manera similar pero con

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

En caso de eso${\displaystyle |x\rangle }$es un estado base, la transformada cuántica de Fourier también se puede expresar como el mapa

${\displaystyle \operatorname {QFT}$ :|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .}

De forma equivalente, la transformada cuántica de Fourier puede verse como una matriz unitaria (o puerta cuántica ) que actúa sobre vectores de estado cuántico, donde la matriz unitaria${\displaystyle F_{N}}$es la matriz DFT

${\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 &\ddots &\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}},}$

dónde${\displaystyle \omega =\omega _{N}}$. Por ejemplo, en el caso de${\displaystyle N=4=2^{2}}$y fase${\displaystyle \omega =i}$La matriz de transformación es

${\displaystyle F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}}$

Las puertas cuánticas utilizadas en el circuito de${\displaystyle n}$Los cúbits son la puerta de Hadamard y la puerta de fase racional diádica.${\displaystyle R_{k}}$:

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{and}}\qquad R_{k}={\begin{pmatrix}1&0\\0&e^{i2\pi /2^{k}}\end{pmatrix}}}$

El circuito está compuesto por${\displaystyle H}$puertas y la versión controlada de${\displaystyle R_{k}}$:

Una base ortonormal${\displaystyle S}$está compuesto por estados base

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

Estos estados base abarcan todos los estados posibles de los cúbits. Es decir, cada uno${\displaystyle |x\rangle \in S}$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 notación de producto tensorial${\displaystyle \otimes }$,${\displaystyle |x_{j}\rangle }$indica que el cúbit${\displaystyle j}$está en estado${\displaystyle x_{j}}$, con${\displaystyle x_{j}}$ya sea 0 o 1. Por convención, el índice del estado base${\displaystyle x}$es el número binario codificado por el${\displaystyle x_{j}}$, con${\displaystyle x_{1}}$la parte más importante.

La acción de la puerta Hadamard es${\displaystyle H|x_{j}\rangle =\left({\frac {1}{\sqrt {2}}}\right)\left(|0\rangle +e^{2\pi ix_{j}2^{-1}}|1\rangle \right)}$donde el signo depende de${\displaystyle x_{j}}$.

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

${\displaystyle {\text{QFT}}(|x\rangle )={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{N}^{x2^{n-j}}|1\rangle \right).}$

Utilizando la notación binaria fraccionaria

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

La acción de la transformada cuántica de Fourier se puede expresar de forma compacta:

${\displaystyle {\text{QFT}}(|x_{1}x_{2}\ldots x_{n}\rangle )={\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).}$

Para obtener este estado del circuito representado anteriormente, se debe realizar una operación de intercambio de los cúbits para invertir su orden. Como máximo${\displaystyle n/2}$Se requieren intercambios. ^{[ 5 ]}

Debido a que la transformada discreta de Fourier, una operación en n cúbits, se puede factorizar en el producto tensorial de n operaciones de un solo cúbit, se puede representar fácilmente como un circuito cuántico (salvo una inversión de orden de la salida). Cada una de esas operaciones de un solo cúbit se puede implementar de manera eficiente utilizando una puerta Hadamard y un número lineal de puertas de fase controlada . El primer término requiere una puerta Hadamard y${\displaystyle (n-1)}$compuertas de fase controladas, el siguiente término requiere una compuerta Hadamard y${\displaystyle (n-2)}$compuerta de fase controlada, y cada término siguiente requiere una compuerta de fase controlada menos. Sumando el número de compuertas, excluyendo las necesarias para la inversión de la salida, se obtiene${\displaystyle n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})}$puertas, que es un polinomio cuadrático en el número de cúbits. Este valor es mucho menor que para la transformada de Fourier clásica. ^{[ 7 ]}

La implementación a nivel de circuito de la transformada cuántica de Fourier en una arquitectura lineal de vecinos más cercanos se ha estudiado anteriormente. ^{[ 8 ] [ 9 ]} La profundidad del circuito es lineal en el número de cúbits.

La transformada cuántica de Fourier en tres cúbits,${\displaystyle F_{8}}$con${\displaystyle n=3,N=8=2^{3}}$, se representa mediante la siguiente transformación:

${\displaystyle {\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {8}}}\sum _{k=0}^{7}\omega ^{xk}|k\rangle ,}$

dónde${\displaystyle \omega =\omega _{8}}$es una octava raíz de la unidad que satisface${\displaystyle \omega ^{8}=\left(e^{\frac {i2\pi }{8}}\right)^{8}=1}$.

La representación matricial de la transformada de Fourier en tres cúbits es:

${\displaystyle F_{8}={\frac {1}{\sqrt {8}}}{\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 cuántica de Fourier de 3 cúbits se puede reescribir como:

${\displaystyle {\text{QFT}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {8}}}\ \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).}$

El siguiente esquema muestra el circuito respectivo para${\displaystyle n=3}$(con el orden invertido de los cúbits de salida con respecto a la QFT propia):

Como se calculó anteriormente, el número de compuertas utilizadas es${\displaystyle n(n+1)/2}$lo cual es igual a${\displaystyle 6}$, para${\displaystyle n=3}$.

Utilizando la transformada de Fourier generalizada en grupos finitos (abelianos) , existen dos formas naturales de definir una transformada de Fourier cuántica en un registro cuántico de n cúbits . La QFT, tal como se definió anteriormente, es equivalente a la DFT, que considera estos n cúbits indexados por el grupo cíclico.${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$Sin embargo, también tiene sentido considerar los cúbits como indexados por el grupo booleano.${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$y en este caso la transformada de Fourier es la transformada de Hadamard . Esto se logra aplicando una puerta de Hadamard a cada uno de los n cúbits en paralelo. ^{[ 10 ] [ 11 ]} El algoritmo de Shor utiliza ambos tipos de transformadas de Fourier, una transformada de Hadamard inicial y una QFT.

La transformada de Fourier puede formularse para grupos distintos del grupo cíclico y extenderse al contexto cuántico. ^{[ 12 ]} Por ejemplo, considérese el grupo simétrico.${\displaystyle S_{n}}$[ ^{13 ] [ 14 ]} La transformada de Fourier puede expresarse en forma matricial ^.

${\displaystyle {\mathfrak {F}}_{n}=\sum _{\lambda \in \Lambda _{n}}\sum _{p,q\in {\mathcal {P}}(\lambda )}\sum _{g\in S_{n}}{\sqrt {\frac {d_{\lambda }}{n!}}}[\lambda (g)]_{q,p}|\lambda ,p,q\rangle \langle g|,}$

dónde${\displaystyle [\lambda (g)]_{q,p}}$es el${\displaystyle (q,p)}$elemento de la representación matricial de${\displaystyle \lambda (g)}$,${\displaystyle {\mathcal {P}}(\lambda )}$es el conjunto de rutas desde el nodo raíz hasta${\displaystyle \lambda }$en el diagrama de Brattelli de${\displaystyle S_{n}}$,${\displaystyle \Lambda _{n}}$es el conjunto de representaciones de${\displaystyle S_{n}}$indexados por diagramas de Young y${\displaystyle g}$es una permutación.

La transformada discreta de Fourier también puede formularse sobre un campo finito.${\displaystyle F_{q}}$y se puede definir una versión cuántica. ^{[ 15 ]} Considere${\displaystyle N=q=p^{n}}$. Dejar${\displaystyle \phi :GF(q)\to GF(p)}$Sea un mapa lineal arbitrario (traza, por ejemplo). Entonces, para cada${\displaystyle x\in GF(q)}$definir

${\displaystyle F_{q,\phi }:|x\rangle \mapsto {\frac {1}{\sqrt {q}}}\sum _{y\in GF(q)}\omega ^{\phi (xy)}|y\rangle }$

para${\displaystyle \omega =e^{2\pi i/p}}$y extender${\displaystyle F_{q,\phi }}$linealmente.

• Parthasarathy, KR (2006). Lecciones sobre computación cuántica, códigos de corrección de errores cuánticos y teoría de la información . Instituto Tata de Investigación Fundamental. ISBN 978-81-7319-688-1.
• Preskill, John (septiembre de 1998). "Apuntes de clase para Física 229: Información cuántica y computación" (PDF) .

• Proyecto de demostración de Wolfram: Circuito cuántico que implementa el algoritmo de búsqueda de Grover.
• Proyecto de demostración de Wolfram: Circuito cuántico que implementa la transformada cuántica de Fourier
• Transformada cuántica de Fourier de la vida en línea de Quirk