Algoritmos cuánticos: búsqueda de Grover y aplicaciones

nota

Atsushi Matsuo (10 de mayo de 2024)

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.

El tiempo aproximado de QPU para este experimento es de 2 segundos.

1. Introducción al algoritmo de Grover

Este notebook es el cuarto de una serie de clases sobre el camino hacia la utilidad práctica en la computación cuántica. En este notebook aprendemos sobre el algoritmo de Grover.

El algoritmo de Grover es uno de los algoritmos cuánticos más conocidos debido a su aceleración cuadrática frente a los métodos de búsqueda clásicos. En la computación clásica, buscar en una base de datos no ordenada con $N$ entradas requiere una complejidad temporal de $O(N)$, lo que significa que en el peor de los casos hay que examinar cada entrada individualmente. Sin embargo, el algoritmo de Grover nos permite realizar esta búsqueda en un tiempo de $O(\sqrt{N})$, aprovechando los principios de la mecánica cuántica para encontrar el elemento objetivo de manera más eficiente.

El algoritmo utiliza la amplificación de amplitud, un proceso que aumenta la amplitud de probabilidad del estado de respuesta correcto en una superposición cuántica, de modo que pueda medirse con mayor probabilidad. Esta aceleración hace que el algoritmo de Grover sea valioso en diversas aplicaciones más allá de la simple búsqueda en bases de datos, especialmente cuando el conjunto de datos es grande. Se proporcionan explicaciones detalladas del algoritmo en el notebook del algoritmo de Grover.

La estructura básica del algoritmo de Grover

El algoritmo de Grover consta de cuatro componentes principales:

1. Inicialización: Creación de la superposición sobre todos los estados posibles.
2. Oráculo: Aplicación de una función oráculo que marca el estado objetivo invirtiendo su fase.
3. Operador de difusión: Aplicación de una serie de operaciones para amplificar la probabilidad del estado marcado.

Cada uno de estos pasos desempeña un papel crucial para que el algoritmo funcione de manera eficiente. Las explicaciones detalladas de cada paso se proporcionan más adelante.

2. Implementación del algoritmo de Grover

2.1 Preparación

Importa las bibliotecas necesarias y configura el entorno para la ejecución del circuito cuántico.

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

%config InlineBackend.figure_format = 'svg' # Makes the images look nice

# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

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

Considera una lista de 4 elementos, donde nuestro objetivo es identificar el índice de un elemento que cumple una condición determinada. Por ejemplo, queremos encontrar el índice del elemento que es igual a 2. En este ejemplo, el estado cuántico $|01\rangle$ representa el índice del elemento que cumple esta condición, ya que apunta a la posición donde se encuentra el valor 2.

Paso 2: Optimizar para el hardware objetivo

1: Inicialización

En el paso de inicialización, creamos una superposición de todos los estados posibles. Esto se logra aplicando una puerta Hadamard a cada qubit en un registro de n qubits, lo que resulta en una superposición uniforme de $2^n$ estados. Matemáticamente, esto se puede representar como:

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

donde $N = 2^n$ es el número total de estados posibles. También cambiamos el estado del qubit auxiliar a $|-\rangle$.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

2: Oráculo

El oráculo es un componente central del algoritmo de Grover. Marca el estado objetivo aplicando un desplazamiento de fase, típicamente invirtiendo el signo de la amplitud asignada al estado. El oráculo suele ser específico del problema y se construye en base a los criterios para identificar el estado objetivo. En términos matemáticos, el oráculo aplica la siguiente transformación:

$f(x) = \begin{cases} 1, & \text{if } x = x_{\text{target}} \\ 0, & \text{otherwise} \end{cases}$

Esta inversión de fase se logra aplicando un signo negativo a la amplitud del estado objetivo mediante phase kickback.

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

3: Operador de difusión

El proceso de amplificación de amplitud es lo que distingue al algoritmo de Grover de una búsqueda clásica. Después de que el oráculo marca el estado objetivo, aplicamos una serie de operaciones que aumentan la amplitud de ese estado marcado, haciendo más probable su observación al medir. Este proceso se logra mediante el operador de difusión, que efectivamente realiza una inversión respecto a la amplitud promedio. La operación matemática es:

$D = 2|\psi\rangle\langle\psi| - I$

donde $D$ es el operador de difusión, $I$ es la matriz identidad y $|\psi\rangle$ es el estado de superposición uniforme. La combinación del oráculo y el operador de difusión se aplica aproximadamente $\sqrt{N}$ veces para alcanzar la máxima probabilidad de medir el estado marcado.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

2.2 Un ejemplo de búsqueda de Grover con 2 qubits

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)

# the number of iterations
num_iterations = 1

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

2.3 Experimento con simuladores

Paso 3: Ejecución del circuito

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

Paso 4: Postprocesamiento de los resultados

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Hemos obtenido la respuesta correcta $|01\rangle$. Observa el orden de los qubits.

3. Experimento con dispositivos reales

Paso 2: Optimizar para el hardware objetivo

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")

# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)

# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

Al transpilar el circuito, se convirtió en un circuito con las puertas base nativas del dispositivo.

Paso 3: Ejecución del circuito

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)

job id: cw69csv19rzg0080yfkg

# Check the job status
job_real.status()

'QUEUED'

# If the Notebook session got disconnected you can also check your job status by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()

'DONE'

# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())

{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

Paso 4: Postprocesamiento de los resultados

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

4. Una búsqueda de Grover con 3 qubits

Probemos ahora un ejemplo de búsqueda de Grover con 3 qubits.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 2

def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

Esta vez $|111\rangle$ es el estado "bueno".

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

$|0111\rangle$ se observa con la mayor probabilidad, como se esperaba. Ten en cuenta que dos iteraciones son óptimas en este caso. Sin embargo, la probabilidad de obtener la respuesta correcta no es del 100 %, lo cual es habitual en la búsqueda de Grover.

¿Qué pasa si iteramos 3 veces?

Probemos ahora con 3 iteraciones.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 3

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

$|0111\rangle$ sigue observándose con la mayor probabilidad, aunque la probabilidad de obtener la respuesta correcta ha disminuido ligeramente.

¿Y con 4 iteraciones?

Probemos ahora con 4 iteraciones.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 4

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

$|0111\rangle$ se observa con la menor probabilidad, y la probabilidad de obtener la respuesta correcta ha disminuido aún más. Esto ilustra la importancia de elegir el número óptimo de iteraciones para el algoritmo de Grover con el fin de obtener los mejores resultados.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'