algoritmo de Grover

Estimativa de tempo de execução: menos de um minuto em um processador Eagle r3 (NOTA: Trata-se apenas de uma estimativa. (O tempo de execução pode variar.)

Resultados do aprendizado

Ao concluir este tutorial, você deverá compreender as seguintes informações:

• Como construir oráculos de Grover que marquem um ou mais estados da base computacional
• Como usar a grover_operator() função da biblioteca de circuitos do Qiskit
• Como determinar o número ideal de iterações de Grover para um determinado 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 dos algoritmos quânticos: o algoritmo de Grover
• Noções básicas de informação quântica

Segundo plano

A amplificação de amplitude é um algoritmo quântico de uso geral, ou sub-rotina, que pode ser utilizado para obter um aumento de velocidade quadrático em relação a alguns algoritmos clássicos. O algoritmo de Grover foi o primeiro a demonstrar essa aceleração em problemas de busca não estruturados. A formulação de um problema de busca de Grover requer uma função oráculo que identifique um ou mais estados da base computacional como aqueles que nos interessam encontrar, e um circuito de amplificação que aumente a amplitude dos estados identificados, suprimindo, consequentemente, os demais estados.

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 pesquisa de Grover. A primitiva de tempo de execução Sampler permite a execução contínua dos circuitos Grover.

Requisitos

Antes de iniciar este tutorial, certifique-se de que os seguintes itens estejam instalados:

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

Instalação

# 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, vamos acompanhar cada etapa do algoritmo de Grover em pequena escala, utilizando 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 especifique um ou mais estados da base computacional marcados, sendo que “marcado” significa um estado com uma fase de -1. Uma porta de Z controlado, ou sua generalização multicontrolada sobre qubits d $N$, marca o estado de $2^{N}-1$ ('1'*sequência de bits $N$ ). Para marcar estados de base com um ou mais '0' na representação binária, é necessário aplicar portas X nos qubits correspondentes antes e depois da porta Z controlada, o que equivale a aplicar um comando de controle aberto nesse qubit. No código a seguir, definimos um oráculo que identifica um ou mais estados de base de entrada definidos por meio de sua representação em cadeia de bits. A MCMT porta é utilizada para implementar a porta Z multicontrolada.

Instanciação específica de Grover

Agora que temos a função de oráculo, podemos definir uma instância específica da pesquisa de Grover. Neste exemplo, marcaremos dois estados computacionais dentre os 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")

Output:

Operador Grover

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

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

Output:

As aplicações repetidas desse circuito grover_op amplificam os estados marcados, tornando-os as cadeias de bits mais prováveis na distribuição de saída do circuito. Há um número ideal desses aplicativos que é determinado pela proporção de estados marcados em relação ao 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 Grover completo

Um experimento completo de Grover começa com uma porta Hadamard em cada qubit, criando uma superposição uniforme de todos os estados da base computacional, seguida do operador de Grover (grover_op) repetido o número ideal 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")

Output:

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

Para a simulação em pequena escala, compilamos o circuito sem direcioná-lo a um 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")

Output:

Passo 3: Execute usando Qiskit primitives

A amplificação de amplitude é um problema de amostragem adequado para ser executado com a SamplerV2 primitiva. Aqui, utilizamos 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()

Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado

plot_distribution(dist)

Output:

Exemplo de hardware

Etapas 1 a 4

O algoritmo de Grover é, em essência, um algoritmo tolerante a falhas — as portas Z multicontroladas, que constituem o núcleo do oráculo e do operador de difusão, resultam em profundidades de porta de dois qubits que aumentam muito rapidamente com o número de qubits (como mostraremos na próxima seção). Isso significa que o algoritmo não se adapta bem ao hardware atual, que apresenta ruídos. Por esse motivo, demonstramos a execução em hardware na mesma escala reduzida do exemplo do simulador acima, em vez de tentarmos resolver um problema de maior dimensão.

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

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

Uma das principais razões pelas quais o algoritmo de Grover é considerado um algoritmo tolerante a falhas é o rápido aumento da profundidade da porta de dois qubits do circuito à medida que o número de qubits aumenta. A porta Z multicontrolada, que está no centro tanto do oráculo quanto do operador de difusão, decompõe-se em um número de portas de dois qubits que cresce exponencialmente com o número de qubits de controle. Somado ao fato de que o número ideal de iterações de Grover cresce na proporção de $O(\sqrt{2^n})$, a profundidade total de dois qubits rapidamente se torna impraticável para hardware sujeito a ruídos.

A seguir, construímos circuitos de Grover para um número crescente de qubits, os transpilamos e representamos graficamente a profundidade da porta de dois qubits resultante para ilustrar essa escalabilidade.

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 mostra o gráfico, a profundidade da porta 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 atual, sujeito a ruídos, exceto para problemas de dimensões muito pequenas. O algoritmo continua sendo um alvo importante para futuros computadores quânticos tolerantes a falhas, nos quais a correção de erros permitirá que circuitos complexos sejam executados de forma confiável.

Próximas etapas