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.)

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 v1.4 o posterior, con soporte de visualización
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 o posterior

Configuración

# Added by doQumentation — required packages for this notebook
!pip install -q 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

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; equivalente a tener un control abierto en ese qubit. En el siguiente código, definimos un oráculo que hace justamente eso, marcando 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.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
backend.name

'ibm_brisbane'

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")

marked_states = ["011", "100"]

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

marked_states = ["011", "100"]

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

Operador de Grover

El grover_operator() integrado de Qiskit toma un circuito oráculo y devuelve un circuito que está compuesto por el circuito oráculo mismo y un circuito que amplifica los estados marcados por el oráculo. Aquí, usamos el método decompose() del circuito para ver los gates dentro del operador:

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

Las aplicaciones repetidas de este circuito grover_op amplifican los estados marcados, haciéndolos las cadenas de bits más probables en la distribución de salida del circuito. Hay un número óptimo de tales aplicaciones que está determinado por la relación de estados marcados al 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 completo de Grover

Un experimento completo de Grover comienza con un gate Hadamard en cada qubit; creando una superposición uniforme de todos los estados de base computacional, seguido del operador de Grover (grover_op) repetido el número óptimo de veces. Aquí hacemos uso del método QuantumCircuit.power(INT) para aplicar repetidamente el operador de 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")

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

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

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

Paso 3: Ejecutar usando primitivas de Qiskit

La amplificación de amplitud es un problema de muestreo que es adecuado para la ejecución con la primitiva de runtime Sampler.

Ten en cuenta que el método run() de Qiskit Runtime SamplerV2 toma un iterable de bloques unificados primitivos (PUBs). Para el sampler, cada PUB es un iterable en el formato (circuit, parameter_values). Sin embargo, como mínimo, toma una lista de circuito(s) cuántico(s).

# To run on local simulator:
#   1. Use the StatevectorSampler from qiskit.primitives instead
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Paso 4: Post-procesar y devolver el resultado en el formato clásico deseado

plot_distribution(dist)

Encuesta del tutorial

Por favor, responda esta breve encuesta para proporcionar comentarios sobre este tutorial. Sus opiniones nos ayudarán a mejorar nuestras ofertas de contenido y experiencia de usuario.

Enlaza a la encuesta