Algoritmos cuánticos: estimación de fase

nota

Kento Ueda (15 de mayo de 2024)

Este notebook presenta los conceptos fundamentales y la implementación de la transformada cuántica de Fourier (QFT) y la estimación de fase cuántica (QPE).

Descargar el PDF de la clase original. Ten en cuenta que algunos fragmentos de código pueden estar desactualizados, ya que son imágenes estáticas.

Tiempo aproximado de QPU para este experimento: 7 segundos.

1. Introducción

Transformada cuántica de Fourier (QFT)

La transformada cuántica de Fourier es el equivalente cuántico de la transformada discreta de Fourier clásica. Es una transformación lineal que se aplica a estados cuánticos y convierte representaciones en la base computacional a sus representaciones en la base de Fourier. La QFT desempeña un papel central en muchos algoritmos cuánticos y ofrece un método eficiente para extraer información de periodicidad de los estados cuánticos. La QFT puede implementarse con $O(N^2)$ operaciones mediante puertas cuánticas como puertas Hadamard y puertas de fase controladas para $N$ qubits, lo que permite una aceleración exponencial frente a la transformada de Fourier clásica.

• Aplicaciones: Es un componente fundamental en algoritmos cuánticos como el algoritmo de Shor para la factorización de números enteros grandes y el logaritmo discreto.

Estimación de fase cuántica (QPE)

La estimación de fase cuántica es un algoritmo cuántico que estima la fase de un eigenvector de un operador unitario. Este algoritmo establece un puente entre las propiedades matemáticas abstractas de los estados cuánticos y sus aplicaciones computacionales.

• Aplicaciones: Puede resolver problemas como encontrar eigenvalores de matrices unitarias y la simulación de sistemas cuánticos.

Juntas, la QFT y la QPE forman la columna vertebral esencial de muchos algoritmos cuánticos que resuelven problemas que son intratables para los computadores clásicos. Al final de este notebook, comprenderás cómo se implementan estas técnicas.

2. Fundamentos de la transformada cuántica de Fourier (QFT)

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

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

En analogía con la transformada discreta de Fourier, la QFT actúa sobre un estado cuántico $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ para $N$ qubits y lo transforma en el estado cuántico $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

donde $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

O representado como una matriz unitaria:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. Intuición

La transformada cuántica de Fourier (QFT) transforma entre dos bases: la base computacional (base Z) y la base de Fourier. ¿Qué significa la base de Fourier en este contexto? Seguramente recuerdas que la transformada de Fourier $F(\omega)$ de una función $f(x)$ describe la convolución de $f(x)$ con una función sinusoidal de frecuencia $\omega$. En términos simples: la transformada de Fourier es una función que describe cuánto de cada frecuencia $\omega$ se necesitaría para construir $f(x)$ a partir de funciones seno (o coseno). Para obtener una mejor comprensión de lo que significa la QFT en este contexto, considera las imágenes paso a paso a continuación, que muestran un número codificado en binario con cuatro qubits:

En la base computacional almacenamos números en forma binaria utilizando los estados $|0\rangle$ y $|1\rangle$.

Observa la frecuencia con la que cambian los diferentes qubits: el qubit más a la izquierda cambia con cada incremento del número, el siguiente cada dos incrementos, el tercero cada cuatro incrementos, etc.

Si aplicamos una transformada cuántica de Fourier a estos estados, mapeamos:

$$|\text{Estado en base computacional}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{Estado en base de Fourier}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Los estados en la base de Fourier a menudo se denotan con una tilde (~).)

En la base de Fourier almacenamos números mediante diferentes rotaciones alrededor del eje Z:

IFRAME

El número a almacenar determina el ángulo en el que cada qubit se rota alrededor del eje Z. En el estado $|\widetilde{0}\rangle$, todos los qubits se encuentran en el estado $|{+}\rangle$. Como se ve en el ejemplo anterior, para codificar el estado $|\widetilde{5}\rangle$ en 4 qubits, el qubit más a la izquierda fue rotado $\tfrac{5}{2^n} = \tfrac{5}{16}$ vueltas completas ($\tfrac{5}{16}\times 2\pi$ radianes). El siguiente qubit se rota el doble ($\tfrac{10}{16}\times 2\pi$ radianes o $10/16$ vueltas completas), este ángulo se duplica nuevamente para el siguiente qubit, etc.

Observa nuevamente la frecuencia con la que cambia cada qubit. El qubit más a la izquierda (qubit 0) tiene en este caso la frecuencia más baja, el más a la derecha la más alta.

2.2 Ejemplo: QFT de 1 qubit

Consideremos el caso $N = 2^1 = 2$.

La matriz unitaria se puede escribir como:

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

Esta operación corresponde al resultado de aplicar la puerta Hadamard ($H$).

2.3 Representación como producto de la QFT

Generalicemos la transformación para $N = 2^n$, $QFT_{N}$ aplicada al estado $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{ya que}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{y}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{reescrito en notación binaria fraccionaria}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{tras desarrollar la exponencial de una suma como producto de exponenciales,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{tras reordenar las sumas y productos y desarrollar} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 Ejemplo: construcción del circuito QFT de 3 qubits

A partir de la descripción anterior, puede no ser inmediatamente claro cómo construir un circuito QFT. Primero, observa que con tres qubits esperamos fases que evolucionan a diferentes "ritmos". La traducción exacta a un circuito se deja como ejercicio para el lector. Hay varios diagramas y ejemplos en el PDF de la clase. Recursos adicionales se encuentran en esta lección del curso "Fundamentos de algoritmos cuánticos".

Demostramos la QFT solo con simuladores y utilizamos el framework Qiskit Patterns cuando pasemos a la estimación de fase cuántica.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

Como ejemplo, aplicamos la QFT a $|5\rangle$.

Primero confirmamos la representación binaria del entero 5 y creamos el circuito que codifica el estado 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

Verificamos los estados cuánticos con el simulador Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Finalmente, añadimos la QFT y observamos el estado final de nuestros qubits:

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Vemos que la función QFT ha funcionado correctamente. El qubit 0 fue rotado $\tfrac{5}{8}$ de una vuelta completa, el qubit 1 fue rotado $\tfrac{10}{8}$ vueltas completas (equivalente a $\tfrac{1}{4}$ de una vuelta completa) y el qubit 2 fue rotado $\tfrac{20}{8}$ vueltas completas (equivalente a $\tfrac{1}{2}$ de una vuelta completa).

2.5 Ejercicio: QFT

(1) Implementa la QFT para 4 qubits.

##your code goes here##

(2) Aplica la QFT a $|14\rangle$, simula y dibuja el vector de estado en la esfera de Bloch.

##your code goes here##

Solución del ejercicio: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. Fundamentos de la estimación de fase cuántica (QPE)

Dado un operador unitario $U$, la QPE estima $\theta$ en $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$; como $U$ es unitario, todos los eigenvalores tienen módulo 1.

3.1 Procedimiento

1. Configuración

$\vert\psi\rangle$ se encuentra en un registro de qubits. Otro registro de $n$ qubits forma el registro contador, donde almacenaremos el valor $2^n\theta$:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. Superposición

Aplicamos una operación de puerta Hadamard de $n$ bits $H^{\otimes n}$ al registro contador:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. Operaciones unitarias controladas

Introducimos el unitario controlado $CU$, que aplica el operador unitario $U$ al registro objetivo cuando el bit de control correspondiente es $|1\rangle$. Como $U$ es un operador unitario con eigenvector $|\psi\rangle$ tal que $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, se cumple:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 Ejemplo: QPE con puerta T

Utilicemos la puerta $T$ como ejemplo para la QPE y estimemos su fase $\theta$.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

Esperamos:

$$\theta = \frac{1}{8}$$

donde

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

Inicializamos $\vert\psi\rangle = \vert1\rangle$ como eigenvector de la puerta $T$ aplicando una puerta $X$:

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

A continuación, aplicamos puertas Hadamard a los qubits contadores:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

Realizamos las operaciones unitarias controladas:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

Aplicamos la transformada cuántica de Fourier inversa para convertir el estado del registro contador, y luego medimos el registro contador:

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

Podemos simular con el simulador Aer:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

Obtenemos un resultado (001) con certeza, que como número decimal es 1. Ahora debemos dividir nuestro resultado (1) por $2^n$ para obtener $\theta$:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

El algoritmo de Shor nos permite factorizar un número construyendo un circuito con $\theta$ desconocido y determinando $\theta$.

3.3 Ejercicio

Estima $\theta = 1/3$ con 3 qubits para contar y un qubit para un eigenvector.

$P|1\rangle = e^{i\lambda}|1\rangle$. Como queremos implementar $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, debemos establecer $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Solución del ejercicio: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. Ejecución con el Sampler Primitive de Qiskit Runtime

Ejecutaremos QPE en un dispositivo cuántico real siguiendo los 4 pasos de Qiskit Patterns.

1. Convertir el problema a un formato cuántico nativo
2. Optimizar los circuitos
3. Ejecutar el circuito objetivo
4. Postprocesar los resultados

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Paso 1: Mapear el problema a circuitos cuánticos y operadores

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

4.2 Paso 2: Optimizar para el hardware objetivo

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 Paso 3: Ejecutar en el hardware objetivo

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

4.4 Paso 4: Postprocesar los resultados

from qiskit.visualization import plot_histogram

plot_histogram(result_real[0].data.c.get_counts())

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'