Transformada de Fourier cuántica

Para este módulo de Qiskit en el aula, los estudiantes deben tener un entorno de Python funcional con los siguientes paquetes instalados:

• qiskit v2.1.0 o más reciente
• qiskit-ibm-runtime v0.40.1 o más reciente
• qiskit-aer v0.17.0 o más reciente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar los paquetes anteriores, consulta la guía Instalar Qiskit. Para poder ejecutar trabajos en computadoras cuánticas reales, los estudiantes necesitarán crear una cuenta en IBM Quantum® siguiendo los pasos de la guía Configura tu cuenta de IBM Cloud.

Este módulo fue probado y utilizó 13 segundos de tiempo de QPU. Esta es una estimación de buena fe; tu uso real puede variar.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introducción

La transformada de Fourier es una herramienta omnipresente con aplicaciones en matemáticas, física, procesamiento de señales, compresión de datos y un sinfín de otros campos. Una versión cuántica de la transformada de Fourier, acertadamente llamada transformada de Fourier cuántica, constituye la base de algunos de los algoritmos cuánticos más importantes.

Hoy, tras repasar brevemente la transformada de Fourier clásica, hablaremos de cómo implementamos la transformada de Fourier cuántica en una computadora cuántica. Luego, analizaremos una de las aplicaciones de la transformada de Fourier cuántica a un algoritmo llamado algoritmo de estimación de fase. La estimación de fase cuántica es una subrutina del famoso algoritmo de factorización de Shor, que a veces se describe como la "joya de la corona" de la computación cuántica. Este módulo sirve de preparación para otro módulo dedicado por completo al algoritmo de Shor, aunque también está pensado para ser independiente. ¡La transformada de Fourier cuántica es un algoritmo fascinante y útil por derecho propio!

La transformada de Fourier clásica

Antes de adentrarnos en la transformada de Fourier cuántica, recordemos la versión clásica. La transformada de Fourier es un método para pasar de una llamada "base" a otra. Puedes pensar en dos bases como dos perspectivas diferentes del mismo problema: ambas son formas válidas de expresar una función, pero una u otra puede resultar más esclarecedora según el problema en cuestión. Algunos ejemplos de pares de bases relacionadas por la transformada de Fourier son posición y momento, y tiempo y frecuencia.

Veamos un ejemplo de cómo la transformada de Fourier puede ayudarnos a determinar qué nota está tocando un instrumento a partir de su forma de onda de audio. Normalmente, vemos las formas de onda representadas en la base temporal, es decir, la amplitud de la onda se expresa como función del tiempo.

Podemos aplicar la transformada de Fourier a esta forma de onda para pasar de la base temporal a la base de frecuencias:

En la base de frecuencias, podemos ver claramente un pico en torno a 260 Hz. ¡Es un Do central!

Ahora bien, quizás habrías podido determinar que se estaba tocando un Do central sin necesidad de la transformada de Fourier, pero ¿qué ocurre si se tocan varias notas a la vez? Entonces la forma de onda se vuelve más complicada cuando la representamos en la base temporal:

Pero el espectro de frecuencias identifica claramente tres picos:

Ese era un acorde de Do mayor, tocando las notas Do, Mi y Sol.

Este tipo de análisis de Fourier puede ayudarnos a extraer los componentes de frecuencia de cualquier tipo de señal complicada.

Transformada de Fourier discreta

La transformada de Fourier es útil para multitud de aplicaciones de procesamiento de señales. Pero en la mayoría de estas aplicaciones del mundo real (incluido el ejemplo musical que utilizamos anteriormente), queremos transformar un conjunto discreto de $N$ puntos de datos, no una función continua. En este caso, usamos la transformada de Fourier discreta. La transformada de Fourier discreta (DFT) actúa sobre un vector $(x_0, ..., x_{N-1})$ y lo asigna al vector $(y_0, ..., y_{N-1})$ según la fórmula:

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

donde tomamos $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Ten en cuenta que existen otras convenciones que incluyen un signo negativo en el exponente, así que presta atención cuando veas la DFT en otros contextos.) Recuerda que $e^{2\pi i \frac{jk}{N}}$ es una función periódica con periodo $\frac{N}{k}$. Por tanto, al multiplicar por esta función, la transformada de Fourier es esencialmente una forma de descomponer la función (discreta) $\{x_{j}\}$ en una combinación lineal de sus funciones periódicas constituyentes, cada una con periodo $\frac{N}{k}$.

La transformada de Fourier cuántica

Así pues, hemos visto cómo la transformada de Fourier se utiliza para representar una función como combinación lineal de un nuevo conjunto de llamadas "funciones de base". Las transformaciones de base también se aplican regularmente a estados de qubits. Por ejemplo, el estado de un único qubit $|\psi\rangle$ puede expresarse en la base computacional $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, con estados base $|0\rangle$ y $|1\rangle$, o en la base $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ con estados base $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ y $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Ambas son igualmente válidas, pero una puede resultar más natural que la otra según el tipo de problema que estés tratando de resolver.

Los estados de qubit también pueden expresarse en la base de Fourier, donde un estado se expresa en términos de una combinación lineal de los estados base de Fourier $|\phi_y\rangle$, en lugar de los estados base computacionales habituales $|x\rangle$. Para ello, debes aplicar una transformada de Fourier cuántica (QFT):

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

con $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ como antes, y $N$ es el número de estados base en tu sistema cuántico. Ten en cuenta que, como ahora trabajamos con qubits, $m$ qubits te proporcionan $2^m$ estados base, por lo que $N=2^m$. Aquí, los estados base se escriben como un único número $|x\rangle$ donde $x$ va de $0$ a $N-1$, aunque es más habitual ver los estados base expresados como $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, donde cada dígito binario representa el estado del qubit 0 al $m-1$, de derecha a izquierda. Hay una forma sencilla de convertir estos estados binarios a un único número: ¡simplemente trátalos como números binarios! Así, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, y así sucesivamente hasta $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Desarrolla la intuición sobre los estados base de Fourier

Acabamos de repasar qué son los estados base computacionales y cómo se ordenan: son el conjunto de estados donde cada qubit está en $0$ o $1$, y los ordenamos desde el estado en que todos los qubits son $0$, $|00...00\rangle$, hasta el estado en que todos son $1$, $|11...11\rangle$.

¿Pero cómo podemos interpretar los estados base de Fourier? Todos los estados base de Fourier son superposiciones iguales de todos los estados base computacionales, pero cada estado difiere de los demás en la periodicidad de la fase de sus componentes. Para entenderlo de forma más concreta, examinemos los cuatro estados base de Fourier de un sistema de dos qubits. El estado de Fourier más bajo es aquel cuya fase no varía en absoluto:

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

Podemos visualizar este estado representando la amplitud compleja de cada uno de los términos. La línea roja sirve de guía visual para mostrar cómo la fase de esta amplitud gira alrededor del plano complejo en función del estado base computacional. Para $|\phi_0\rangle$, la fase permanece constante:

El siguiente estado base de Fourier es aquel cuyas fases de los componentes giran desde $0$ hasta $2\pi$ exactamente una vez:

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

Y podemos ver este giro en el gráfico de amplitud compleja frente al estado base computacional:

Así, cada estado tiene una fase $2\pi/4$ radianes mayor que el estado anterior cuando se ordenan de la forma estándar, ya que en este ejemplo tenemos cuatro estados base ($N=4$). El siguiente estado base gira de 0 a $2\pi$ dos veces:

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

Por último, el componente de Fourier más alto es el que tiene la fase de variación más rápida. En nuestro ejemplo con dos qubits, es el cuyas fases giran de 0 a $2\pi$ tres veces:

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

En general, para un estado de $m$ qubits, habrá $2^m$ estados base de Fourier, cuya frecuencia de variación de fase va desde constante, para $|\phi_0\rangle$, hasta de variación rápida para $|\phi_{2^m-1}\rangle$, completando $2^m-1$ vueltas alrededor de $2\pi$ a lo largo de la superposición de estados. Por tanto, cuando aplicamos la QFT a un estado cuántico, en esencia estamos haciendo el mismo análisis básico que hicimos con la forma de onda musical en la introducción: determinamos los componentes de frecuencia de Fourier que contribuyen a crear el estado cuántico de interés.

Prueba algunos ejemplos de QFT

Continuemos desarrollando nuestra intuición sobre la transformada de Fourier cuántica preparando un estado en la base computacional y observando qué ocurre cuando le aplicamos la QFT. Por ahora, trataremos la QFT como una caja negra que aplicamos usando QFTGate de la biblioteca de circuitos de Qiskit. Más adelante, echaremos un vistazo bajo el capó para ver cómo está implementada.

Empezamos cargando los paquetes necesarios y seleccionando un dispositivo en el que ejecutar nuestro circuito:

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

ibm_pinguino2

Si no tienes tiempo disponible en tu cuenta o quieres usar un simulador por cualquier motivo, puedes ejecutar la celda siguiente para configurar un simulador que imite el dispositivo cuántico que seleccionamos anteriormente:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

Un único estado base computacional

Primero, intentemos transformar un único estado base computacional. Empezamos creando un estado computacional aleatorio:

# Step 1: Map

qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)

# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()

qc.measure_all()
qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Ahora, apliquemos la transformada de Fourier a este estado con QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Como puedes ver, medimos las poblaciones de cada estado de forma más o menos igual, salvo algo de ruido experimental y estadístico. Por tanto, si aplicas la QFT a un único estado base computacional, el resultado es una superposición igual de todos los estados. Si estás familiarizado con las transformadas de Fourier, esto probablemente no te sorprende. Un principio básico que puede ayudarnos a construir una conexión intuitiva entre una función y su transformada de Fourier es que el ancho de una función es inversamente proporcional al ancho de su transformada de Fourier. Así, algo que está muy localizado en el tiempo, como un pulso muy corto, requiere una amplia gama de frecuencias para generarse. Esa señal será muy amplia en el espacio de Fourier.

Este hecho está en realidad relacionado con la incertidumbre cuántica. El principio de incertidumbre de Heisenberg se enuncia típicamente como $\Delta x \Delta p \ge \hbar / 2$. Por tanto, si la incertidumbre en $x$ ($\Delta x$) es pequeña, la incertidumbre en el momento ($\Delta p$) debe ser grande, y viceversa. Resulta que la transformación desde la base de posición $x$ a la base de momento $p$ se realiza mediante una transformada de Fourier.

Nota: Ten en cuenta que estamos midiendo poblaciones en cada uno de los estados base, por lo que estamos perdiendo información sobre las fases relativas entre las distintas partes de la superposición. Por tanto, aunque la QFT de cualquier estado base computacional individual produce la misma distribución uniforme de población sobre todos los estados base, las fases no tienen por qué ser necesariamente iguales.

Dos estados base computacionales

Ahora veamos qué ocurre cuando preparamos una superposición de estados base computacionales. ¿Cómo crees que será la transformada de Fourier en este caso?

Elijamos la superposición:

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)

qc_qft = qc.copy()

qc.measure_all()

qc.draw("mpl")

# First, let's go through steps 2-4 for the first circuit, qc

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Ahora, apliquemos la transformada de Fourier a este estado con QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Este resultado puede ser un poco más sorprendente. Parece que la QFT del estado $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ es una superposición de todos los estados base pares. Pero si volvemos a nuestra visualización de cada estado base $|\phi_y\rangle$, y cómo la fase de cada componente gira $2\pi$ $y$ veces, la razón por la que obtenemos este resultado puede volverse más clara.

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para ver la solución.

Usando la pista anterior, explica por qué el resultado que obtuvimos para la QFT de $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ es el esperado.

Respuesta:

El estado original tiene una fase relativa de 0 (o un múltiplo entero de $2\pi$) entre las dos partes de la superposición. Por tanto, sabemos que este estado tiene componentes de Fourier cuyas fases también coinciden de esa forma: las que tienen un desfase de 0 entre el término |0000> y el término |1000>. Cada estado base de Fourier $|\phi_y\rangle$ está compuesto de términos cuya fase se acumula a una tasa de $2\pi y/N$, lo que significa que, ordenados de la forma habitual, cada término de la superposición tiene una fase $2\pi y/N$ mayor que el término anterior. Por tanto, en el punto medio $N/2$, queremos que la fase $2\pi y/N * N/2$ sea un múltiplo entero de $2\pi$. Esto ocurre cuando $y$ es par.

¿Qué superposición de estados computacionales correspondería a una QFT con picos en cada número binario impar?

Respuesta:

Si aplicaras la QFT al estado $\psi = |0\rangle - |N/2\rangle$, verías picos en cada estado de número binario impar.

Desglose del algoritmo QFT

Ahora que hemos desarrollado más intuición sobre la relación entre los estados de los qubits en la base computacional y la base de Fourier, profundicemos en el propio algoritmo QFT. En otras palabras, ¿qué gates implementamos realmente en la computadora cuántica para lograr esta transformada?

Empecemos con algo pequeño: un único qubit. Esto significa que tendremos dos estados base. La QFT$_2$ transforma los estados de la base computacional $|0\rangle$ y $|1\rangle$ en los estados de la base de Fourier $\phi_0$ y $\phi_1$:

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para revelar la solución.

Usa la ecuación de la QFT de la sección anterior para verificar estos dos estados de la base de Fourier.

Respuesta:

La fórmula general de la QFT es:

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

Para un único qubit ($n=1$), $N=2^n=2$, y $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Entonces, tenemos

$| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Observa esas dos ecuaciones. Puede que ya conozcas un gate cuántico que pueda usarse para implementar esta transformada. Es decir, existe un gate que transforma los estados de la base computacional $|0\rangle$ y $|1\rangle$ en los respectivos estados de la base de Fourier $|\phi_0\rangle$ y $|\phi_1\rangle$. ¡Es el gate de Hadamard! Esto queda aún más claro si introducimos una representación matricial de la operación QFT$_N$:

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

Si no estás familiarizado con esta notación para expresar un operador cuántico, ¡no te preocupes! Es una forma de representar una matriz $N \times N$, donde $x$ e $y$ indexan las columnas y filas de la matriz, de $0$ a $N-1$, y $\omega_N^{xy}$ es el valor de esa entrada en particular. Así, la entrada en la columna 0 y la fila 2, por ejemplo, sería simplemente $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

En esta representación, cada uno de los estados de la base computacional se asocia con uno de los vectores de base:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

Si quieres aprender más sobre esta representación en profundidad, consulta la lección de John Watrous sobre sistemas múltiples en el curso Basics of quantum information.

Intentemos construir la matriz para QFT$_4$. Usando la fórmula anterior, encontramos que

\text\{QFT\}_4 = \frac\{1\}\{2\} \begin\{pmatrix\} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end\{pmatrix\}

Para implementar esta matriz en una computadora cuántica, necesitaremos determinar qué combinación de gates aplicados a qué qubits nos dará una transformación unitaria que coincida con la matriz anterior. Ya conocemos uno de los gates que necesitaremos: el Hadamard. Otro gate que necesitaremos es el gate de fase controlada, que aplica una fase relativa $\alpha$ al estado del qubit objetivo, siempre que el qubit de control esté en el estado $|1\rangle$. En forma matricial, esto se ve así:

\text\{CP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^\{i\alpha\} \\ \end\{pmatrix\}

Dado que solo se cambia el estado $|11\rangle$, en realidad no importa cuál qubit se considera el "control" y cuál el "objetivo". El resultado será el mismo en ambos casos.

Finalmente, también necesitaremos algunos gates SWAP. Un gate SWAP intercambia los estados de dos qubits. Se ve así:

\text\{SWAP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end\{pmatrix\}

El procedimiento para construir un circuito QFT$_{2^m}$ sobre $m$ qubits es iterativo: primero aplicas QFT$_{2^{m-1}}$ a los qubits $1$ hasta $m-1$, luego añades algunos gates entre el qubit $0$ y los otros $m-1$ qubits. Pero para aplicar QFT$_{2^{m-1}}$, primero debes aplicar QFT$_{2^{m-2}}$ a los qubits 2 hasta $m-1$, y luego añadir algunos gates entre el qubit 1 y los qubits restantes $2$ hasta $m-1$. Es como una matrioska rusa: cada muñeca agrega un factor de dos a la dimensión del circuito QFT, con la muñeca más pequeña en el centro, que es QFT$_2$, o el gate de Hadamard.

Para meter una muñeca dentro de la siguiente de mayor tamaño, y así aumentar la dimensión de la QFT por un factor de dos, siempre se sigue el mismo procedimiento:

1. Primero, aplica QFT$_{2^{m-1}}$ a los $m-1$ qubits inferiores. Esta es tu "muñeca más pequeña" del conjunto de matrioskas que pronto meterás dentro de la siguiente.
2. Usa el siguiente qubit como control, y aplica gates de fase controlada a cada uno de los $m-1$ qubits inferiores, con fases a los estados de la base estándar de cada uno de los $m-1$ qubits restantes.
3. Realiza un Hadamard sobre ese mismo qubit superior que se usó como control en los gates de fase.
4. Usa gates SWAP para permutar el orden de los qubits, de modo que el bit menos significativo (superior) se convierta en el más significativo (inferior), y todos los demás suban una posición.

Ya hemos estado usando la función QFTGate de la biblioteca de circuits de Qiskit, pero ahora veamos el interior de algunos de estos gates QFT para verificar el procedimiento anterior. Podemos hacer esto con decompose().

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

Así que, con suerte, a partir de las primeras cuatro QFTs puedes empezar a ver cómo cada una está anidada dentro de la siguiente más grande. Puede que hayas notado, sin embargo, que algunos de los gates de fase no son exactamente como se prescribe en el procedimiento que describimos anteriormente, y los SWAPs no aparecen después de cada subrutina, sino solo al final de la QFT completa. Esto nos ahorra gates innecesarios, que harían que el circuito tardara más y fuera más propenso a errores. En lugar de implementar el SWAP después de cada muñeca anidada, el circuito lleva un registro de dónde debería estar cada estado de qubit y ajusta en consecuencia los qubits a los que aplica los gates de fase. Luego, un conjunto final de SWAPs al final coloca todo en su lugar correcto.

Aplicar la QFT: estimación de fase

Veamos cómo se puede usar la QFT para resolver un problema útil en computación cuántica. Calcular la transformada cuántica de Fourier inversa es un paso necesario en un algoritmo conocido como Estimación de Fase Cuántica (QPE, por sus siglas en inglés), que es a su vez una subrutina en muchos otros algoritmos, incluida la "joya de la corona" de los algoritmos cuánticos: el algoritmo de factorización de Shor.

El objetivo de QPE es estimar los valores propios de un operador unitario. Los operadores unitarios son omnipresentes en la computación cuántica, y a menudo, encontrar los valores propios de sus vectores propios asociados es un paso necesario en un algoritmo más grande. Dependiendo del problema, un valor propio puede representar la energía de un Hamiltoniano en un problema de simulación, puede ayudarnos a encontrar factores primos de un número en el algoritmo de Shor, o puede contener otra información esencial. QPE es una de las subrutinas más importantes y ampliamente utilizadas en computación cuántica.

Entonces, ¿qué tiene que ver esto con la transformada cuántica de Fourier? Pues bien, como recordarás, todo valor propio $\lambda$ de un operador unitario tiene magnitud $|\lambda| = 1$. Así que podemos escribir cada valor propio como un número complejo de magnitud uno:

$\lambda = e^{2\pi i \theta}$

donde $\theta$ es un número real entre 0 y 1. Si quieres más información sobre matrices unitarias, consulta la lección de John Watrous sobre el tema en Basics of quantum information.

Observa que $\lambda$ es periódico en $\theta$. Esto ya podría sugerirte que una QFT podría estar involucrada, ya que vimos lo útiles que son las QFTs para analizar funciones periódicas. A continuación, recorreremos el algoritmo y veremos con precisión cómo entra en juego la QFT.

Cómo funciona QPE

Primero, empezaremos con el algoritmo QPE más simple, que estima aproximadamente la fase con un único dígito binario de precisión. En otras palabras, este algoritmo puede distinguir entre $\theta = 0$ y $\theta = 1/2$, pero no puede hacerlo mejor que eso. Aquí está el diagrama del circuito:

Los qubits se preparan en el estado $|\pi_0\rangle = |\psi\rangle|0\rangle$, donde el qubit $0$ está en el estado $|0\rangle$ y los qubits restantes están en el estado $|\psi\rangle$, que es un autoestado de $U$. Después del primer Hadamard, el estado del qubit se convierte en:

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

El siguiente gate es un gate "controlled-$U$". Este aplica la operación unitaria $U$ a los qubits inferiores que están en el estado $|\psi\rangle$ si el qubit 0 está en el estado $|1\rangle$, pero no hace nada sobre $|\psi\rangle$ si el qubit 0 está en el estado $|0\rangle$. Esto transforma los qubits al estado:

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

Algo curioso acaba de ocurrir: el gate controlled-$U$ solo usa el qubit $0$ como qubit de control, por lo que uno podría pensar que este gate no cambiaría el estado del qubit 0 en absoluto. ¡Pero de alguna manera, sí lo hace! Aunque la operación se aplicó a los qubits inferiores, el efecto global del gate es cambiar la fase del qubit $0$. Esto se conoce como el "mecanismo de retroceso de fase" (phase kickback), y se usa en muchos algoritmos cuánticos, incluyendo los algoritmos de Deutsch-Jozsa y Grover. Si quieres aprender más sobre el mecanismo de retroceso de fase, consulta la lección de John Watrous sobre Algoritmos de consulta cuántica en Fundamentals of quantum algorithms.

Después del retroceso de fase, aplicamos un Hadamard más al qubit $0$, lo que resulta en el estado:

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

Así, cuando medimos el qubit $0$ al final, mediremos $|0\rangle$ con un 100% de certeza si $\theta = 0$ y mediremos $|1\rangle$ con un 100% de certeza si $\theta = \frac{1}{2}$ (y si nuestra computadora cuántica es perfecta, sin ruido). Si $\theta$ es distinto de estos valores, la medición final es solo probabilística y nos dice únicamente hasta cierto punto.

QPE con más precisión: más qubits

Podemos extender este concepto simple a un algoritmo más complejo con precisión arbitraria. Si en lugar de usar solo el qubit $0$ para medir la fase, usamos $m$ qubits del $0$ al $m-1$, podremos estimar la fase con $m$ bits de precisión. Veamos cómo funciona esto:

Este circuito QPE más preciso comienza igual que la versión de un solo bit: se aplican Hadamards a los primeros $m$ qubits, y los qubits restantes se preparan en el estado $|\psi\rangle$, creando el estado:

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

Ahora se aplican las unitarias controladas. El qubit $0$ es el control para la misma unitaria $U$ que antes. Pero ahora, el qubit $1$ es el control para la unitaria $U^2$, que es simplemente $U$ aplicada dos veces. Así, el valor propio de $U^2$ es $e^{2*2\pi i \theta}$. En general, cada qubit $k$ del 0 al $m-1$ será el control para la unitaria $U^{2^k}$. Eso significa que cada uno de estos qubits experimentará un retroceso de fase de $e^{2^k*2\pi i \theta}$. Esto da como resultado el estado:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

Esto puede reescribirse como una suma sobre los estados de la base computacional:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

¿Te resulta familiar la suma? ¡Es una QFT! Recuerda la ecuación para una transformada cuántica de Fourier:

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

Entonces, si la fase $\theta = y/2^m$ para algún entero $y$ entre $0$ y $2^m-1$, aplicar la QFT inversa a este estado dará como resultado el estado:

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

y a partir de $|y\rangle$, podemos deducir $\theta$.

Si $\theta/2^m$ no es un múltiplo entero, sin embargo, aplicar la QFT inversa solo aproximará $\theta$. Qué tan bien aproxima $\theta$ será probabilístico, lo que significa que no siempre obtendremos la mejor aproximación, pero será bastante cercana, y cuantos más qubits $m$ uses, mejor será la aproximación. Para aprender a cuantificar esta aproximación de $\theta$, consulta la lección de John Watrous sobre Estimación de fase y factorización en Fundamentals of quantum algorithms.

Conclusión

Este módulo ofreció una visión general de qué es una QFT, cómo se implementa en una computadora cuántica y cuán útil puede ser para resolver problemas. Te dimos una muestra de su utilidad cuando vimos cómo puede usarse en la estimación de fase cuántica para conocer los valores propios de una matriz unitaria.

Conceptos clave

• La Transformada Cuántica de Fourier es el análogo cuántico de la Transformada Discreta de Fourier.
• La QFT es un ejemplo de transformación de base.
• El procedimiento de Estimación de Fase Cuántica se basa en el mecanismo de retroceso de fase de las operaciones unitarias controladas, así como en una QFT inversa.
• La QFT y QPE son subrutinas ampliamente utilizadas en numerosos algoritmos cuánticos.

Preguntas

Verdadero/Falso

1. V/F La Transformada Cuántica de Fourier es el análogo cuántico de la transformada discreta de Fourier (DFT) clásica.
2. V/F La QFT puede implementarse usando solo gates de Hadamard y CNOT.
3. V/F La QFT es un componente clave del algoritmo de Shor.
4. V/F La salida de la Estimación de Fase Cuántica es un estado cuántico que representa el vector propio del operador.
5. V/F QPE requiere el uso de la Transformada Cuántica de Fourier inversa (QFT$^\dag$).
6. V/F En QPE, si la fase $\phi$ es exactamente representable con $n$ bits, el algoritmo da el resultado correcto con probabilidad 1.

Respuestas cortas

1. ¿Cuántos qubits se necesitan para realizar una QFT sobre un sistema con $2^n$ puntos de datos?
2. ¿Puede usarse la QFT en un estado que no sea un estado de la base computacional? Si es así, ¿qué ocurre?
3. ¿Cómo afecta el número de qubits de control utilizados en QPE a la resolución de la estimación de fase resultante?

Problemas

1. Usa multiplicación matricial para verificar que los pasos del algoritmo QFT efectivamente dan como resultado la matriz $\text{QFT}_4$:

$$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$$

(¡No tienes que hacerlo a mano!)

Problemas desafiantes

1. Crea un estado de cuatro qubits que sea una superposición equitativa de todas las bases computacionales impares: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Luego, realiza una QFT sobre el estado. ¿Cuál es el estado resultante? Explica por qué tu resultado tiene sentido usando tu conocimiento de las transformadas de Fourier.