Algoritmo de Grover

Tiempo estimado de ejecución: menos de un minuto en un procesador Eagle r3 (NOTA: Se trata únicamente de una estimación). (El tiempo de ejecución puede variar.)

Resultados del aprendizaje

Una vez completado este tutorial, habrás adquirido los siguientes conocimientos:

• Cómo construir oráculos de Grover que marquen uno o más estados de la base computacional
• Cómo utilizar la grover_operator() función de la biblioteca de circuitos de Qiskit
• Cómo determinar el número óptimo de iteraciones de Grover para un problema determinado
• Cómo ejecutar el algoritmo de Grover utilizando la primitiva « Qiskit Runtime » del sampler

Requisitos previos

Se recomienda que te familiarices con estos temas:

• Fundamentos de los algoritmos cuánticos: el algoritmo de Grover
• Fundamentos de la información cuántica

En segundo plano

La amplificación de amplitud es un algoritmo cuántico de uso general, o subrutina, que puede utilizarse para obtener una aceleración cuadrática con respecto a varios algoritmos clásicos. El algoritmo de Grover fue el primero en demostrar esta mejora en la velocidad en problemas de búsqueda no estructurados. Para formular un problema de búsqueda de Grover se necesita una función oráculo que marque uno o varios estados de la base computacional como los estados que nos interesa encontrar, y un circuito de amplificación que aumente la amplitud de los estados marcados, suprimiendo así los estados restantes.

Aquí, demostramos cómo construir oráculos de Grover y utilizar el grover_operator() de la biblioteca de circuitos Qiskit para configurar fácilmente una instancia de búsqueda de Grover. La primitiva de ejecución Sampler permite ejecutar circuitos Grover sin problemas.

Requisitos

Antes de comenzar este tutorial, asegúrate de tener instalado lo siguiente:

• Qiskit SDK v2.0 o posterior, con soporte para visualización
• Qiskit Runtime v0.22 o posterior (pip install qiskit-ibm-runtime)

Configuración

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Imports from Qiskit Runtime
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler


def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bit-string to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bit-string
        zero_inds = [
            ind
            for ind in range(num_qubits)
            if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bit-string has a '0' entry
        if zero_inds:
            qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        if zero_inds:
            qc.x(zero_inds)
    return qc

Ejemplo de simulador a pequeña escala

En esta sección, repasamos cada paso del algoritmo de Grover a pequeña escala utilizando un simulador local, antes de ejecutar el mismo problema en hardware cuántico real.

Paso 1: Asignar entradas clásicas a un problema cuántico

El algoritmo de Grover requiere un oráculo que especifique uno o más estados de base computacional «marcados», donde «marcado» significa un estado con una fase de -1. Una puerta de Z controlada, o su generalización multiconrolada sobre qubits de tipo « $N$ », define el estado « $2^{N}-1$ » ('1'*cadena de bits $N$ ). Para marcar los estados de base con uno o más '0' en la representación binaria, es necesario aplicar puertas X a los qubits correspondientes antes y después de la puerta Z controlada, lo que equivale a aplicar una puerta de control abierto a ese qubit. En el siguiente código, definimos un oráculo que identifica uno o varios estados de base de entrada definidos mediante su representación en cadena de bits. La MCMT puerta se utiliza para implementar la puerta Z multicontrolada.

Instancia específica de Grover

Ahora que tenemos la función oráculo, podemos definir una instancia específica de búsqueda Grover. En este ejemplo marcaremos dos estados computacionales de los ocho disponibles en un espacio computacional de tres qubits:

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Output:

Operador Grover

El built-in Qiskit grover_operator() toma un circuito de oráculo y devuelve un circuito que se compone del propio circuito de oráculo y un circuito que amplifica los estados marcados por el oráculo. Aquí, utilizamos el método decompose() el circuito para ver las puertas dentro del operador:

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")

Output:

Las aplicaciones repetidas de este circuito grover_op amplifican los estados marcados, convirtiéndolos en las cadenas de bits más probables en la distribución de salida del circuito. Existe un número óptimo de estas aplicaciones que viene determinado por la relación entre los estados marcados y el número total de estados computacionales posibles:

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

Circuito Grover completo

Un experimento Grover completo comienza con una puerta Hadamard en cada qubit; creando una superposición par de todos los estados base computacionales, seguido del operador Grover (grover_op) repetido el número óptimo de veces. Aquí utilizamos el método QuantumCircuit.power(INT) para aplicar repetidamente el operador Grover.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Output:

Paso 2: Optimizar el problema para la ejecución en hardware cuántico

Para la simulación a pequeña escala, compilamos el circuito sin orientarlo a un hardware concreto.

pm = generate_preset_pass_manager(optimization_level=3)
circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Output:

Paso 3: Ejecutar utilizando Qiskit primitives

La amplificación de amplitud es un problema de muestreo que se presta a ser resuelto mediante la SamplerV2 primitiva. Aquí utilizamos el StatevectorSampler de qiskit.primitives para la simulación local.

from qiskit.primitives import StatevectorSampler

sampler = StatevectorSampler()
result = sampler.run([circuit_isa], shots=10_000).result()
dist = result[0].data.meas.get_counts()

Paso 4: Procesamiento posterior y devolución del resultado en el formato clásico deseado

plot_distribution(dist)

Output:

Ejemplo de hardware

Pasos 1 a 4

El algoritmo de Grover es, en esencia, un algoritmo tolerante a fallos: las puertas Z multicontroladas que constituyen el núcleo del oráculo y del operador de difusión dan lugar a profundidades de puerta de dos qubits que aumentan muy rápidamente con el número de qubits (como demostraremos en la siguiente sección). Esto significa que el algoritmo no se adapta bien al hardware actual, que suele presentar interferencias. Por este motivo, mostramos la ejecución en hardware a la misma escala reducida que el ejemplo del simulador anterior, en lugar de intentar abordar un problema de mayor envergadura.

# -------------------------Step 1-------------------------
marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
grover_op = grover_operator(oracle)

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

# -------------------------Step 2-------------------------
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# -------------------------Step 3-------------------------
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
sampler.options.environment.job_tags = ["TUT-GA"]
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# -------------------------Step 4-------------------------
plot_distribution(dist)

Output:

Debate: Escalabilidad de la profundidad de las puertas de dos qubits

Una de las razones principales por las que el algoritmo de Grover se considera un algoritmo tolerante a fallos es el rápido aumento de la profundidad de las puertas de dos qubits del circuito a medida que aumenta el número de qubits. La puerta Z multicontrolada, que constituye el núcleo tanto del oráculo como del operador de difusión, se descompone en una serie de puertas de dos qubits cuyo número crece exponencialmente con el número de qubits de control. Si a esto le sumamos que el número óptimo de iteraciones de Grover crece a un ritmo de $O(\sqrt{2^n})$, la profundidad total de dos qubits pronto resulta inviable para un hardware con ruido.

A continuación, construimos circuitos de Grover para un número creciente de qubits, los transpilamos y representamos gráficamente la profundidad de las puertas de dos qubits resultante para ilustrar esta escalabilidad.

import matplotlib.pyplot as plt

num_qubits_list = list(range(3, 10))
two_q_depths = []
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
for n in num_qubits_list:
    # Mark a single state for simplicity
    marked = ["1" * n]
    oracle_n = grover_oracle(marked)
    grover_op_n = grover_operator(oracle_n)

    # Optimal number of iterations
    num_iters = math.floor(
        math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))
    )

    # Build the full Grover circuit
    qc_n = QuantumCircuit(n)
    qc_n.h(range(n))
    qc_n.compose(grover_op_n.power(num_iters), inplace=True)
    qc_n.measure_all()

    # Transpile to a basis gate set and count 2Q depth
    pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)
    qc_transpiled = pm_n.run(qc_n)

    # Compute depth restricted to 2-qubit operations
    depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)

    two_q_depths.append(depth_2q)
    print(f"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}")

# Plot
fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(
    num_qubits_list,
    two_q_depths,
    "o-",
    linewidth=2,
    markersize=8,
    color="#6929C4",
)
ax.set_xlabel("Number of qubits", fontsize=13)
ax.set_ylabel("Two-qubit gate depth", fontsize=13)
ax.set_title("Grover's algorithm: 2Q depth scaling", fontsize=14)
ax.set_yscale("log")
ax.grid(True, alpha=0.3)
ax.set_xticks(num_qubits_list)
plt.tight_layout()
plt.show()

Output:

n=3: optimal_iters=2, 2Q depth=39
n=4: optimal_iters=3, 2Q depth=111
n=5: optimal_iters=4, 2Q depth=466
n=6: optimal_iters=6, 2Q depth=1646
n=7: optimal_iters=8, 2Q depth=3550
n=8: optimal_iters=12, 2Q depth=7989
n=9: optimal_iters=17, 2Q depth=14824

Como muestra el gráfico, la profundidad de las puertas de dos qubits aumenta muy rápidamente con el número de qubits, más o menos de forma exponencial. Esto hace que el algoritmo de Grover resulte poco práctico en el hardware cuántico actual, que adolece de ruido, salvo en el caso de problemas de tamaño muy reducido. El algoritmo sigue siendo un objetivo importante para los futuros ordenadores cuánticos tolerantes a fallos, en los que la corrección de errores permitirá ejecutar circuitos profundos de forma fiable.

Próximos pasos