Algoritmo de Grover

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

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 v1.4 ou posterior, com suporte para visualização
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 ou posterior

Configuração

# 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

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; equivalente a ter um controle aberto naquele qubit. No código a seguir, definimos um oráculo que faz exatamente isso, marcando um ou mais estados de base de entrada definidos através de sua representação em bit-string. A porta MCMT é usada para implementar a porta Z multi-controlada.

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

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

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

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

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

Passo 3: Executar usando primitivas Qiskit

Amplificação de amplitude é um problema de amostragem adequado para execução com a primitiva Sampler do runtime.

Observe que o método run() do Qiskit Runtime SamplerV2 recebe um iterável de blocos unificados primitivos (PUBs). Para o sampler, cada PUB é um iterável no formato (circuit, parameter_values). No entanto, no mínimo, ele recebe uma lista de circuito(s) quâ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()

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

plot_distribution(dist)

Pesquisa do tutorial

Por favor, responda esta breve pesquisa para fornecer feedback sobre este tutorial. Suas opiniões nos ajudarão a melhorar nossas ofertas de conteúdo e experiência do usuário.

Link para a pesquisa