Algoritmo de Grover

Estimativa de uso: menos de um minuto em um processador Eagle r3 (NOTA: Esta é apenas uma estimativa. Seu tempo de execução pode variar.)

Resultados de aprendizagem

Após concluir este tutorial, você poderá compreender as seguintes informações:

• Como construir oráculos de Grover que marcam um ou mais estados de base computacional
• Como usar a função grover_operator() da biblioteca de circuitos Qiskit
• Como determinar o número ótimo de iterações de Grover para um dado problema
• Como executar o algoritmo de Grover usando a primitiva Sampler do Qiskit Runtime

Pré-requisitos

Recomenda-se que você se familiarize com estes tópicos:

• Fundamentos de algoritmos quânticos: Algoritmo de Grover
• Básicos de informação quântica

Contexto

Amplificação de amplitude é um algoritmo quântico de propósito geral, ou sub-rotina, que pode ser usado para obter uma aceleração quadrática sobre um punhado de algoritmos clássicos. O algoritmo de Grover foi o primeiro a demonstrar essa aceleração em problemas de busca não estruturada. Formular um problema de busca de Grover requer uma função oráculo que marca um ou mais estados de base computacional como os estados que estamos interessados em encontrar, e um circuito de amplificação que aumenta a amplitude dos estados marcados, consequentemente suprimindo os estados restantes.

Aqui, demonstramos como construir oráculos de Grover e usar o grover_operator() da biblioteca de circuitos Qiskit para configurar facilmente uma instância de busca de Grover. A primitiva Sampler do runtime permite a execução contínua de circuitos de Grover.

Requisitos

Antes de iniciar este tutorial, certifique-se de ter o seguinte instalado:

• Qiskit SDK v2.0 ou posterior, com suporte para visualização
• Qiskit Runtime v0.22 ou posterior (pip install qiskit-ibm-runtime)

Configuração

# 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

Exemplo de simulador em pequena escala

Nesta seção, percorremos cada passo do algoritmo de Grover em pequena escala usando um simulador local, antes de executar o mesmo problema em hardware quântico real.

Passo 1: Mapear entradas clássicas para um problema quântico

O algoritmo de Grover requer um oráculo que especifica um ou mais estados de base computacional marcados, onde "marcado" significa um estado com uma fase de -1. Uma porta controlled-Z, ou sua generalização multi-controlada sobre $N$ qubits, marca o estado $2^{N}-1$ (bit-string '1'*$N$). Marcar estados de base com um ou mais '0' na representação binária requer a aplicação de portas X nos qubits correspondentes antes e depois da porta controlled-Z, o que é equivalente a ter um controle aberto naquele qubit. No código a seguir, definimos um oráculo que marca um ou mais estados de base de entrada definidos através de sua representação em bitstring. A porta MCMT é usada para implementar a porta Z multi-controlada.

Instância específica de Grover

Agora que temos a função oráculo, podemos definir uma instância específica de busca de Grover. Neste exemplo, marcaremos dois estados computacionais dos oito disponíveis em um espaço computacional de três qubits:

marked_states = ["011", "100"]

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

Operador de Grover

O grover_operator() integrado do Qiskit recebe um circuito oráculo e retorna um circuito que é composto pelo próprio circuito oráculo e um circuito que amplifica os estados marcados pelo oráculo. Aqui, usamos o método decompose() do circuito para ver as portas dentro do operador:

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

Aplicações repetidas deste circuito grover_op amplificam os estados marcados, tornando-os as bit-strings mais prováveis na distribuição de saída do circuito. Existe um número ótimo de tais aplicações que é determinado pela razão de estados marcados para o número total de estados computacionais possíveis:

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

Circuito completo de Grover

Um experimento completo de Grover começa com uma porta Hadamard em cada qubit; criando uma superposição uniforme de todos os estados de base computacional, seguida pelo operador de Grover (grover_op) repetido o número ótimo de vezes. Aqui usamos o método QuantumCircuit.power(INT) para aplicar repetidamente o 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")

Passo 2: Otimizar o problema para execução em hardware quântico

Para a simulação em pequena escala, transcompilamos o circuito sem apontar para hardware específico.

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

Passo 3: Executar usando primitivas Qiskit

Amplificação de amplitude é um problema de amostragem adequado para execução com a primitiva SamplerV2. Aqui usamos o StatevectorSampler de qiskit.primitives para simulação local.

from qiskit.primitives import StatevectorSampler

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

Passo 4: Pós-processar e retornar o resultado no formato clássico desejado

plot_distribution(dist)

Exemplo em hardware

Passos 1-4

O algoritmo de Grover é fundamentalmente um algoritmo tolerante a falhas — as portas Z multi-controladas no núcleo do oráculo e do operador de difusão levam a profundidades de portas de dois qubits que crescem muito rapidamente com o número de qubits (como mostraremos na próxima seção). Isso significa que o algoritmo não escala bem no hardware barulhento atual. Por essa razão, demonstramos a execução em hardware na mesma pequena escala do exemplo do simulador acima, em vez de tentar um tamanho de problema maior.

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

Discussão: Escalonamento da profundidade de portas de dois qubits

Um motivo chave pelo qual o algoritmo de Grover é considerado um algoritmo tolerante a falhas é o rápido crescimento da profundidade de portas de dois qubits do circuito à medida que o número de qubits aumenta. A porta Z multi-controlada no núcleo tanto do oráculo quanto do operador de difusão se decompõe em um número de portas de dois qubits que cresce exponencialmente com o número de qubits de controle. Combinado com o fato de que o número ótimo de iterações de Grover cresce como $O(\sqrt{2^n})$, a profundidade total de dois qubits rapidamente se torna impraticável para hardware barulhento.

Abaixo, construímos circuitos de Grover para contagens crescentes de qubits, transcompilamos e plotamos a profundidade resultante de portas de dois qubits para ilustrar esse escalonamento.

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

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 o gráfico mostra, a profundidade de portas de dois qubits cresce extremamente rápido com o número de qubits — aproximadamente de forma exponencial. Isso torna o algoritmo de Grover impraticável no hardware quântico barulhento atual além de tamanhos de problemas muito pequenos. O algoritmo continua sendo um alvo importante para futuros computadores quânticos tolerantes a falhas, onde a correção de erros permitirá a execução confiável de circuitos profundos.

Próximos passos

Recomendações

Se você achou este trabalho interessante, pode se interessar pelo seguinte material:

• Biblioteca de circuitos Qiskit: referência da API grover_operator()
• O tutorial de QAOA e a lição de QAOA em escala de utilidade oferecem exemplos de curto prazo de otimização com computadores quânticos
• Para um aprofundamento em algoritmos de curto prazo, veja o curso Computação quântica na prática