Transformada cuántica de Fourier: Encontrar periodos ocultos

En 1807 Joseph Fourier afirmó, estudiando la propagación del calor, que cualquier función se puede escribir como una suma de senos y cosenos. Dos siglos después la versión discreta de su idea está en todas partes: comprimir imágenes, filtrar audio, multiplicar números grandes. En 1965 James Cooley y John Tukey redescubrieron la transformada rápida de Fourier (FFT), que calcula la transformada de $N$ números en $O (N \log N)$ operaciones. La versión cuántica es todavía exponencialmente más rápida, con una pega que tendremos que aprender a sortear.

La transformada discreta y la cuántica

Sean $N = 2^{n}$ y $ω = e^{2 π i / N}$ , una raíz $N$ -ésima primitiva de la unidad. La transformada cuántica de Fourier es la aplicación lineal definida sobre la base computacional por

QFT | j ⟩ = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} ω^{j k} | k ⟩, j = 0, \dots, N - 1 .

Aplicada a un estado $\sum_{j} x_{j} | j ⟩$ , produce la transformada discreta de Fourier de las amplitudes, $\sum_{k} y_{k} | k ⟩$ con $y_{k} = \frac{1}{\sqrt{N}} \sum_{j} ω^{j k} x_{j}$ .

Proposición (la QFT es unitaria)

Las columnas de la matriz de la QFT son ortonormales, así que es una puerta cuántica válida.

Demostración

El producto interior de las columnas $j$ y $j^{'}$ es $\frac{1}{N} \sum_{k = 0}^{N - 1} ω^{(j^{'} - j) k}$ . Si $j = j^{'}$ vale 1. Si no, $q = ω^{j^{'} - j} \neq 1$ es una raíz $N$ -ésima de la unidad y la suma geométrica $\sum_{k} q^{k} = \frac{q^{N} - 1}{q - 1} = 0$ .

Para $N = 2$ , la QFT es exactamente la puerta de Hadamard. Y aplicar $H$ a cada uno de $n$ qubits es la transformada de Fourier sobre el grupo $(ℤ_{2})^{n}$ : el algoritmo de Deutsch-Jozsa ya era una transformada de Fourier disfrazada.

Un circuito exponencialmente pequeño

La clave de su eficiencia es que la QFT de un estado de la base no crea entrelazamiento: se factoriza en $n$ qubits separados. Escribamos $j$ en binario como $j = j_{1} j_{2} \dots j_{n}$ , y $0 . j_{l} j_{l + 1} \dots j_{n}$ para la fracción binaria $\sum_{m \geq l} j_{m} 2^{l - m - 1}$ .

Teorema (representación como producto)

QFT | j_{1} \dots j_{n} ⟩ = \frac{(| 0 ⟩ + e^{2 π i 0 . j_{n}} | 1 ⟩) \otimes (| 0 ⟩ + e^{2 π i 0 . j_{n - 1} j_{n}} | 1 ⟩) \otimes \dots \otimes (| 0 ⟩ + e^{2 π i 0 . j_{1} j_{2} \dots j_{n}} | 1 ⟩)}{2^{n / 2}} .

Esbozo de la demostración

Escribamos $k = \sum_{l = 1}^{n} k_{l} 2^{n - l}$ . Entonces $ω^{j k} = \prod_{l} e^{2 π i j k_{l} / 2^{l}}$ , y la suma sobre $k$ se factoriza en un producto de sumas sobre cada bit $k_{l} \in {0, 1}$ . En $e^{2 π i j / 2^{l}}$ solo importan los últimos $l$ bits de $j$ , porque los demás aportan múltiplos enteros de $2 π i$ .

Cada factor se prepara con una puerta de Hadamard y unas cuantas rotaciones de fase controladas, $R_{k} = diag (1, e^{2 π i / 2^{k}})$ . En total $n (n + 1) / 2$ puertas, más una inversión del orden de los qubits: $O (n^{2})$ operaciones para transformar $2^{n}$ amplitudes, frente a las $O (n 2^{n})$ de la FFT. Coppersmith (1994) mostró además que las rotaciones más pequeñas se pueden omitir sin pérdida apreciable, lo que deja $O (n \log n)$ puertas.

La periodicidad se convierte en picos

Eso es exactamente lo que ocurre con los estados periódicos, la situación que importa para el algoritmo de Shor.

Teorema (transformada de un estado periódico)

Sea $r$ un divisor de $N$ y $m = N / r$ . El estado uniforme sobre una progresión aritmética de paso $r$ ,

| ψ ⟩ = \frac{1}{\sqrt{m}} \sum_{s = 0}^{m - 1} | x_{0} + s r ⟩,

se transforma en una superposición uniforme sobre los múltiplos de $m$ : al medir tras la QFT se obtiene $k = ℓ N / r$ con $ℓ$ uniforme en ${0, \dots, r - 1}$ , sea cual sea el desplazamiento $x_{0}$ .

Demostración

La amplitud de $| k ⟩$ es $\frac{1}{\sqrt{N m}} ω^{x_{0} k} \sum_{s = 0}^{m - 1} {(ω^{r k})}^{s}$ . Ahora $ω^{r k} = e^{2 π i k / m}$ es una raíz $m$ -ésima de la unidad. Si $m$ divide a $k$ vale 1 y la suma vale $m$ , lo que da probabilidad $\frac{m^{2}}{N m} = \frac{1}{r}$ . Si no, la suma geométrica vale 0. El desplazamiento solo aporta la fase $ω^{x_{0} k}$ , que no cambia las probabilidades.

Un estado de 6 qubits (

N = 64

) uniforme sobre una progresión de periodo

r

(arriba) y su transformada cuántica de Fourier (abajo, colores = fase). Cuando

r

divide a 64 la salida es un peine perfecto de

r

picos separados por

64 / r

. Cuando no lo divide, los picos se difuminan un poco pero siguen cerca de los múltiplos de

64 / r

, lo suficiente para recuperar

r

, como hará el algoritmo de Shor. Mover el desplazamiento solo cambia las fases.

Estructura oculta en una sola consulta

La misma idea dio las primeras separaciones entre la computación cuántica y la clásica, en el modelo en que una función $f$ solo se puede consultar como una caja negra.

Bernstein-Vazirani (1993). Sea $f (x) = s \cdot x mod 2$ para una cadena secreta $s \in {0, 1}^{n}$ . Clásicamente, cada consulta revela como mucho un bit de información sobre $s$ , así que hacen falta $n$ consultas. Cuánticamente basta una: se prepara $H^{\otimes n} | 0 ⟩$ , se aplica el oráculo como una fase $(- 1)^{s \cdot x}$ y se vuelve a aplicar $H^{\otimes n}$ . Como $H^{\otimes n} \sum_{x} (- 1)^{s \cdot x} | x ⟩ = 2^{n / 2} | s ⟩$ , al medir se obtiene $s$ con certeza.

El problema de Bernstein-Vazirani. Elige una cadena secreta. La estrategia clásica consulta

f

e_{1}, e_{2}, \dots

, un bit por consulta; el circuito cuántico pregunta una vez, con todas las entradas en superposición, y la interferencia de las fases

(- 1)^{s \cdot x}

deja exactamente

| s ⟩

Simon (1994). Si $f (x) = f (y)$ exactamente cuando $y = x$ o $y = x \oplus s$ , encontrar $s$ requiere $Ω (2^{n / 2})$ consultas para cualquier algoritmo clásico, incluso aleatorio, y $O (n)$ para uno cuántico: la primera separación exponencial frente a algoritmos aleatorios. El artículo de Daniel Simon fue el que inspiró a Peter Shor.

Estimación de fase

Alexei Kitaev (1995) reformuló estas ideas en una herramienta general. Supongamos un unitario $U$ y uno de sus vectores propios $| u ⟩$ con $U | u ⟩ = e^{2 π i φ} | u ⟩$ . Con $t$ qubits auxiliares, las puertas $U^{2^{j}}$ controladas escriben la fase $φ$ en las amplitudes como $\frac{1}{2^{t / 2}} \sum_{y} e^{2 π i φ y} | y ⟩$ , y una QFT inversa la convierte en un número binario.

Teorema (estimación de fase)

Con $t$ qubits, la medida devuelve la mejor aproximación de $φ$ con $t$ bits con probabilidad al menos $4 / π^{2} \approx 0, 405$ ; con $t + O (\log (1 / ε))$ qubits, una aproximación con $t$ bits con probabilidad al menos $1 - ε$ . Si $φ$ tiene un desarrollo exacto con $t$ bits, el resultado es seguro.

La estimación de fase está en el corazón del algoritmo de Shor, de la química cuántica (estimar energías, los valores propios de un hamiltoniano) y de los algoritmos para sistemas lineales. El siguiente capítulo la pone a trabajar en el problema que hizo famosa a la computación cuántica.

Referencias

J. W. Cooley y J. W. Tukey (1965). «An Algorithm for the Machine Calculation of Complex Fourier Series». Mathematics of Computation, 19(90).
E. Bernstein y U. Vazirani (1993). «Quantum complexity theory». STOC.
D. R. Simon (1994). «On the power of quantum computation». FOCS (versión de revista: SIAM J. Computing, 1997).
D. Coppersmith (1994). «An approximate Fourier transform useful in quantum factoring». IBM Research Report RC19642.
A. Y. Kitaev (1995). «Quantum measurements and the Abelian Stabilizer Problem». arXiv:quant-ph/9511026.
R. Cleve, A. Ekert, C. Macchiavello y M. Mosca (1998). «Quantum algorithms revisited». Proceedings of the Royal Society A, 454.

§La transformada discreta y la cuántica

§Un circuito exponencialmente pequeño

§La periodicidad se convierte en picos

§Estructura oculta en una sola consulta

§Estimación de fase