Algoritmo de Grover

Estimación de uso: menos de un minuto en un procesador Eagle r3 (NOTA: Esta es solo una estimación. Su tiempo de ejecución puede variar.)

Resultados de aprendizaje

Tras completar este tutorial, podrás comprender lo siguiente:

Cómo construir oráculos de Grover que marquen uno o más estados de base computacional
Cómo usar la función grover_operator() de la biblioteca de circuitos de Qiskit
Cómo determinar el número óptimo de iteraciones de Grover para un problema dado
Cómo ejecutar el algoritmo de Grover usando la primitiva Sampler de Qiskit Runtime

Requisitos previos

Se recomienda que te familiarices con estos temas:

Antecedentes

La amplificación de amplitud es un algoritmo cuántico de propósito general, o subrutina, que puede usarse para obtener una aceleración cuadrática sobre un puñado de algoritmos clásicos. El algoritmo de Grover fue el primero en demostrar esta aceleración en problemas de búsqueda no estructurada. Formular un problema de búsqueda de Grover requiere una función oráculo que marque uno o más estados de base computacional como los estados que nos interesa encontrar, y un circuito de amplificación que aumenta la amplitud de los estados marcados, suprimiendo consecuentemente los estados restantes.

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

Requisitos

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

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

Configuración

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

# 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 simulación a pequeña escala

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

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

El algoritmo de Grover requiere un oráculo que especifica uno o más estados de base computacional marcados, donde "marcado" significa un estado con una fase de -1. Un gate Z controlado, o su generalización multi-controlada sobre $N$ qubits, marca el estado $2^{N}-1$ (cadena de bits '1'* $N$ ). Marcar estados de base con uno o más '0' en la representación binaria requiere aplicar gates X en los qubits correspondientes antes y después del gate Z controlado, lo que equivale a tener un control abierto en ese qubit. En el siguiente código, definimos un oráculo que marca uno o más estados de base de entrada definidos a través de su representación de cadena de bits. El gate MCMT se usa para implementar el gate Z multi-controlado.

Instancia específica de Grover

Ahora que tenemos la función oráculo, podemos definir una instancia específica de búsqueda de 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")