Resolva um problema de conjunto independente máximo com mais variáveis do que qubits usando o SQOA Solver da JIJ

nota

O Qiskit Functions é um recurso experimental disponível apenas para usuários do IBM Quantum® Premium Plan, Flex Plan e On-Prem (via IBM Quantum Platform API) Plan. Ele está em status de versão preliminar e sujeito a alterações.

Estimativa de uso: 10 segundos em um processador Heron r2. (OBSERVAÇÃO: Esta é apenas uma estimativa. Seu tempo de execução pode variar.)

Contexto

Este tutorial mostra como usar o SQOA Solver, uma Qiskit Function da JIJ, para resolver um problema de conjunto independente máximo (MIS) com mais variáveis binárias do que a QPU selecionada tem qubits. Os passos básicos são carregar uma instância de MIS da Quantum Optimization Benchmarking Library (QOBLIB) [1], formulá-la na forma de otimização binária quadrática sem restrições (QUBO) com o qiskit-addon-opt-mapper, enviá-la ao SQOA Solver para execução em uma QPU da IBM® e validar a solução retornada.

O problema do conjunto independente máximo

Um conjunto independente é um subconjunto de nós de um grafo tal que nenhum par de nós selecionados compartilha uma aresta. Um conjunto independente máximo (MIS) é um conjunto independente com o maior número possível de nós. As aplicações do MIS incluem agendamento, alocação de recursos e projeto de redes.

O MIS é NP-difícil. Em uma busca exaustiva, cada nó adicional dobra o número de subconjuntos a considerar, então essa abordagem é impraticável mesmo para grafos de tamanho moderado. O QOBLIB inclui o MIS como uma de suas dez classes de problemas, por isso é um benchmark útil para avaliar fluxos de trabalho de otimização quântica em hardware real.

Formulação matemática

Dado um grafo não direcionado $G = (V, E)$, atribua uma variável binária $x_v$ a cada nó $v$:

• $x_v = 1$ se o nó $v$ for selecionado.

• $x_v = 0$ otherwise.

A formulação linear binária maximiza o número de nós selecionados e impede que ambas as extremidades de qualquer aresta sejam selecionadas:

$$\begin{aligned} \max_{x} \quad & \sum_{v \in V} x_v \\ \text{subject to} \quad & x_v + x_w \leq 1 && \forall (v,w) \in E, \\ & x_v \in \{0,1\} && \forall v \in V. \end{aligned}$$

O objetivo conta os nós selecionados. Em conjunto, as restrições de aresta garantem que os nós selecionados formem um conjunto independente.

Este tutorial usa a formulação binária sem restrições do QOBLIB, que substitui as restrições de aresta por penalidades quadráticas:

$$\max_{x \in \{0,1\}^{|V|}} \quad \sum_{v \in V} x_v - 2 \sum_{(v,w) \in E} x_v x_w.$$

Sempre que ambas as extremidades de uma aresta são selecionadas, o segundo termo subtrai dois do objetivo. Essa penalidade torna uma seleção conflitante menos favorável do que manter apenas uma das extremidades. O objetivo resultante é um QUBO, que é o formato de entrada aceito pelo SQOA Solver.

Por que usar o SQOA Solver?

Muitas abordagens de otimização quântica atribuem um qubit a cada variável binária, então a capacidade do hardware quântico pode limitar diretamente o tamanho do problema. O SQOA Solver combina várias técnicas de redução e de computação híbrida para amenizar essa restrição:

• Ele pode lidar com problemas com mais variáveis binárias do que a QPU tem qubits. O presolve aplica regras de redução que podem fixar variáveis e simplificar o QUBO restante, preservando ao menos uma solução ótima. Empiricamente, o presolve também pode tornar o QUBO restante mais esparso, o que ajuda a codificação baseada em QRAC que vem a seguir.

  Em seguida, o solver usa uma codificação baseada em QRAC derivada da Quantum Random Access Optimization (QRAO) [3] para representar várias variáveis (até três) sem interação direta no QUBO no mesmo qubit.

  As reduções do presolve e da codificação dependem da estrutura do problema. Por exemplo, neste tutorial, um problema de 200 variáveis usa apenas 67 qubits.

• Ele pode ser menos sensível ao ruído do hardware. A diagonalização quântica baseada em amostras [4], [5] usa a QPU para amostrar bitstrings, mas realiza a diagonalização de forma clássica. Isso evita avaliações repetidas na QPU para atualizações de parâmetros variacionais e pode reduzir o impacto do ruído no fluxo de trabalho de otimização.

• Ele automatiza o fluxo de trabalho do presolve até o pós-processamento. Você fornece uma instância de QUBO formatada corretamente e seleciona um Backend. O SQOA Solver então executa todo o fluxo de trabalho automaticamente. Ele aplica o presolve, mapeia as variáveis clássicas para um problema quântico relaxado, constrói e transpila os circuitos de amostragem, realiza a amostragem quântica e a diagonalização clássica, arredonda e refina a atribuição, e reconstrói e avalia a solução clássica.

Requisitos

Antes de começar este tutorial, verifique se você tem os seguintes pacotes instalados:

• Cliente do Qiskit Functions Catalog (pip install qiskit-ibm-catalog).

• Qiskit addon optimization mapper, usado para formular o problema (pip install qiskit-addon-opt-mapper).

• NetworkX e Matplotlib, usados para manipular e plotar o grafo (pip install networkx matplotlib).

Você também precisa de acesso ao SQOA Solver pelo Qiskit Functions Catalog. Preencha o formulário para solicitar acesso à função.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"matplotlib": "matplotlib", "networkx": "networkx", "ommx": "ommx", "ommx_quantum_benchmarks": "ommx-quantum-benchmarks", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_ibm_catalog": "qiskit-ibm-catalog"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

# %pip install qiskit-ibm-catalog qiskit-addon-opt-mapper networkx matplotlib

Configuração

Primeiro, importe os pacotes e as ferramentas necessários.

import urllib.request

import matplotlib.pyplot as plt
import networkx as nx
from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

O SQOA Solver aceita um problema QUBO como um dicionário de coeficientes no formato de tupla-string usado pelas funções de otimização da IBM®. Defina uma função auxiliar que converta o QUBO retornado por OptimizationProblemToQubo nesse formato.

O conversor sempre retorna um problema de minimização, o que corresponde à forma como o SQOA Solver trata um problema em dicionário. As chaves usam os índices de variável do QUBO, e toda variável recebe uma entrada linear, mesmo com coeficiente zero, para que a solução retornada cubra todas as variáveis.

def to_problem_dict(qubo: OptimizationProblem) -> dict[str, float]:
    """Convert a QUBO from OptimizationProblemToQubo to the SQOA Solver dictionary format."""
    objective = qubo.objective
    payload = {"()": objective.constant}
    # Keep every variable in the problem, even with a zero linear coefficient.
    payload.update({f"({i},)": 0.0 for i in range(qubo.get_num_vars())})
    for i, coefficient in objective.linear.to_dict().items():
        payload[f"({i},)"] += coefficient
    for (i, j), coefficient in objective.quadratic.to_dict().items():
        # Fold a binary diagonal term x_i * x_i = x_i into the linear term.
        key = f"({i},)" if i == j else f"({i}, {j})"
        payload[key] = payload.get(key, 0.0) + coefficient
    return {key: float(value) for key, value in payload.items()}

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

O SQOA Solver aceita um problema QUBO e realiza o mapeamento quântico dentro da função. Neste tutorial, você baixa uma instância de MIS do QOBLIB e a formula como um QUBO com qiskit-addon-opt-mapper. Esta etapa abrange o seguinte:

• Conectar-se ao SQOA Solver.

• Entender o framework SQOA.

• Carregar a instância do problema.

• Formular o QUBO e convertê-lo para envio.

Conectar-se ao SQOA Solver

Conecte-se ao Qiskit Functions Catalog com suas credenciais do IBM Quantum Platform e, em seguida, carregue o SQOA Solver. O código a seguir pressupõe que você já salvou sua conta no seu ambiente local.

Se a conexão falhar, confirme que o administrador da sua conta do IBM Quantum Platform concedeu à instância de serviço selecionada acesso ao SQOA Solver.

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
solver = catalog.load("jij/sqoa-solver")

Entender o framework SQOA

O Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] combina a Quantum Random Access Optimization (QRAO) com a diagonalização quântica baseada em amostras:

1. Relaxamento quântico e codificação: O SQOA Solver converte o QUBO em um objetivo de Ising de minimização da forma $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, em que $z_i \in \{-1, +1\}$. A QRAO [3] então mapeia cada variável de spin para um observável de Pauli. Para a codificação $(3,1)$-QRAC usada aqui, o Hamiltoniano relaxado é

   $$\widetilde{H} = cI + \sum_i \sqrt{k_i} h_i P_{f(i)} + \sum_{i<j} \sqrt{k_i k_j} J_{ij} P_{f(i)} P_{f(j)},$$

   em que $I$ é o operador identidade, $f(i)$ atribui a variável $i$ a um qubit e a um dentre $X$, $Y$ ou $Z$, e $k_i \in \{1,2,3\}$ é o número de variáveis mapeadas para o mesmo qubit que $i$. Quando ambos os qubits relevantes contêm três variáveis, os fatores de escala linear e quadrático passam a ser $\sqrt{3}$ e $3$, respectivamente.

   Variáveis que compartilham um qubit recebem observáveis de Pauli diferentes que não comutam. Variáveis que interagem no QUBO são mantidas em qubits diferentes, enquanto variáveis sem interação direta no QUBO podem compartilhar um qubit. A redução na contagem de qubits depende, portanto, da estrutura do problema.

2. Amostragem quântica: Um processador quântico amostra bitstrings de circuitos projetados para explorar estados de baixa energia do Hamiltoniano relaxado.

3. Diagonalização baseada em amostras: O solver projeta o Hamiltoniano relaxado no subespaço gerado pelos estados da base obtidos dos bitstrings amostrados e diagonaliza classicamente o Hamiltoniano projetado [4], [5]. Para um conjunto fixo de bitstrings amostrados, seja $\mathcal{S}_r$ o subespaço gerado por $r$ estados da base distintos, de modo que $\dim(\mathcal{S}_r) \leq r$. Sua energia estimada do estado fundamental é:

   $$E_r = \min_{\substack{|\psi\rangle \in \mathcal{S}_r \\ \langle\psi|\psi\rangle=1}} \langle\psi|\widetilde{H}|\psi\rangle, \qquad \mathcal{S}_r \subseteq \mathcal{S}_{r'} \Longrightarrow E_{\mathrm{exact}} \leq E_{r'} \leq E_r \quad (r' \geq r),$$

   em que $E_{\mathrm{exact}}$ é a energia do estado fundamental do Hamiltoniano relaxado completo. Portanto, um subespaço retido maior não pode aumentar a energia estimada do estado fundamental.

   Essa ordenação pressupõe o mesmo resultado de amostragem e diz respeito à energia do Hamiltoniano relaxado antes do arredondamento. Ela não garante teoricamente uma solução clássica retornada melhor. No entanto, na QRAO, espera-se heuristicamente que um estado de menor energia forneça uma solução clássica melhor.

4. Arredondamento: O estado relaxado obtido da diagonalização é convertido em uma atribuição binária clássica.

O SQOA Solver envolve esse framework com processamento clássico. Antes do mapeamento quântico, o presolve aplica regras de redução que podem fixar variáveis e simplificar o QUBO restante, preservando ao menos uma solução ótima. Após a diagonalização e o arredondamento, uma busca local clássica refina a atribuição, e o OMMX reconstrói e avalia a solução completa.

Carregar a instância

O QOBLIB distribui cada instância de MIS como um grafo no formato DIMACS .gph, um formato baseado em linhas em que a linha que começa com p informa o número de nós e arestas e cada linha que começa com e define uma aresta.

O QOBLIB também publica uma solução de referência ótima ou a melhor conhecida para cada instância. As funções a seguir baixam ambos do repositório do QOBLIB. O DIMACS rotula os nós a partir de 1, então o grafo é reindexado para começar em 0.

Se você quiser começar com seu próprio grafo, pule o download e formule o problema a partir do seu grafo do NetworkX da mesma maneira.

QOBLIB_URL = "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/07-independentset"

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Download a QOBLIB independent-set instance as a NetworkX graph."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/instances/{name}.gph"
    ) as response:
        lines = response.read().decode().splitlines()
    graph = nx.Graph()
    for fields in map(str.split, lines):
        if fields and fields[0] == "p":
            # Header: p edge <number of nodes> <number of edges>
            graph.add_nodes_from(range(int(fields[2])))
        elif fields and fields[0] == "e":
            # DIMACS labels nodes from 1; relabel them to start from 0.
            graph.add_edge(int(fields[1]) - 1, int(fields[2]) - 1)
    return graph

def fetch_reference_objective(name: str) -> float:
    """Read the objective value of the QOBLIB reference solution."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/solutions/{name}.opt.sol"
    ) as response:
        for line in response.read().decode().splitlines():
            if line.startswith("# Objective value"):
                return float(line.split("=")[1])
    raise ValueError(f"No objective value found for {name}.")

INSTANCE_NAME = "gen200_p0-9_44"
G = fetch_qoblib_graph(INSTANCE_NAME)
reference_objective = fetch_reference_objective(INSTANCE_NAME)

Você usa depois o valor objetivo da solução de referência para avaliar o resultado do SQOA Solver. Este tutorial resolve esse problema em um dispositivo com 156 qubits.

print(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
print(f"Reference objective: {reference_objective:g}")

gen200_p0-9_44: 200 nodes, 1990 edges
Reference objective: 44

Visualize o grafo. Depois, você também o usa para verificar que os nós retornados pelo SQOA Solver formam um conjunto independente.

layout = nx.forceatlas2_layout(
    G, max_iter=500, scaling_ratio=3.0, gravity=1.0, seed=7
)
node_size = max(8, min(60, 4000 / max(G.number_of_nodes(), 1)))

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G, layout, node_size=node_size, node_color="lightgray", ax=ax
)
ax.set_title(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
ax.set_axis_off()
plt.show()

Formular o QUBO

Construa a formulação linear binária da seção Contexto como um OptimizationProblem com uma variável binária por nó, um objetivo que conta os nós selecionados e uma restrição por aresta. Em seguida, converta-o com OptimizationProblemToQubo.

Com um peso de penalidade de 2, o conversor substitui cada restrição de aresta pelo termo de penalidade $2 x_v x_w$ e transforma a maximização em uma minimização, de modo que o problema convertido é a formulação binária sem restrições do QOBLIB com o sinal invertido. Os índices de variável do QUBO são os rótulos dos nós do grafo. A classe de aplicação IndependentSet em qiskit_addon_opt_mapper.applications constrói o mesmo modelo com restrições com IndependentSet(G).to_optimization_problem().

Por fim, converta o QUBO para o formato de dicionário com to_problem_dict(). Como o problema é um QUBO binário, a requisição na Etapa 2 declara seu domínio de variável como "binary". A função realiza o presolve, o mapeamento quântico e a construção dos circuitos após o envio.

mis = OptimizationProblem(INSTANCE_NAME)
mis.binary_var_list(G.number_of_nodes(), name="x")
mis.maximize(linear={v: 1 for v in G.nodes})
for u, v in G.edges:
    mis.linear_constraint({u: 1, v: 1}, "<=", 1)

converter = OptimizationProblemToQubo(penalty=2)
qubo = converter.convert(mis)
problem_dict = to_problem_dict(qubo)

print(f"QUBO variables: {qubo.get_num_vars()}")
print(f"Dictionary entries: {len(problem_dict)}")

QUBO variables: 200
Dictionary entries: 2191

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

O SQOA Solver realiza o mapeamento quântico e a preparação para o hardware dentro da função. Primeiro ele aplica o presolve ao QUBO e, em seguida, mapeia as variáveis restantes para um Hamiltoniano relaxado usando uma codificação baseada em QRAC.

Para a amostragem quântica, ele constrói circuitos com base no Hamiltoniano relaxado e os transpila para o Backend selecionado. As reduções do tamanho do problema e da contagem de qubits obtidas com o presolve e a codificação dependem do problema, então configure o solver sem presumir um fator de redução fixo.

Configurar as entradas do solver

O SQOA Solver exige duas entradas:

• problem, o dicionário da Etapa 1.

• variable_type, que é "binary" para este QUBO.

Ele também aceita duas entradas opcionais:

• backend_name seleciona a QPU. Quando é omitido ou None, a função seleciona a QPU operacional menos ocupada que esteja acessível à sua instância.

• options é um dicionário que controla o orçamento de amostragem (shots), a semente clássica (seed), o uso de sessão (session), a busca local clássica (postprocessing_level) e as tags do job (job_tags). Se você aumentar shots, as estatísticas de amostragem podem melhorar.

Para todas as entradas, seus valores padrão e regras de validação, consulte a referência da API.

Este tutorial nomeia o Backend explicitamente, usa os valores padrão para shots, session e postprocessing_level e define a semente clássica. Reúna as entradas em um dicionário para poder passá-las a solver.run() na Etapa 3.

# ibm_fez has 156 qubits
backend_name = (
    "ibm_fez"  # Omit this key or pass None for automatic selection.
)

sqoa_input = {
    "problem": problem_dict,
    "variable_type": "binary",
    "backend_name": backend_name,
}

sqoa_input["options"] = {
    "shots": 4096,
    "seed": 42,
    "session": False,
    "postprocessing_level": 1,
}

Etapa 3: Executar usando primitivas

Envie o job com a conexão do SQOA Solver criada na Etapa 1. A função executa a primitiva IBM Quantum Sampler no Backend selecionado, coleta os bitstrings medidos e continua com a diagonalização clássica e o pós-processamento. Você interage com um único job de função.

job = solver.run(**sqoa_input)
print(f"Job ID: {job.job_id}")

Job ID: dcee8e26-b8ac-4dd7-a76e-5adb5bc388e5

Para verificar o status da carga de trabalho, consulte Verificar o status do job. Internamente, a função passa pelas fases de mapeamento, otimização para o hardware, espera na fila, execução na QPU e pós-processamento.

job.status()

'INITIALIZING'

job.result() bloqueia até que o job termine e retorna um dicionário com a solução, seu valor objetivo e viabilidade, e metadados que contêm informações do solver e o uso de recursos. Para a definição completa das entradas e saídas, consulte a referência da API.

result = job.result()

Etapa 4: Pós-processar o resultado e convertê-lo para um formato clássico

Inspecione a saída completa da função, mapeie a atribuição retornada de volta para o grafo, verifique os nós selecionados e visualize o resultado.

Inspecionar o resultado

O dicionário de resultado contém quatro campos de nível superior:

• solution é a atribuição completa de variáveis, indexada por x_i, em que i é o índice da variável (por exemplo, x_17). Neste tutorial, o índice da variável é o rótulo do nó.

• objective_value é o objetivo dessa atribuição avaliado no dicionário enviado, isto é, no QUBO de minimização.

• feasible se refere apenas ao domínio das variáveis, porque o dicionário não tem restrições.

• metadata contém solver_info e resource_usage. solver_info registra a seed efetiva da execução. Se a busca local clássica foi executada, solver_info também registra a atribuição arredondada de antes desse refinamento em solution_before_postprocessing.

solver_info = result["metadata"]["solver_info"]

print(f"Result fields: {list(result)}")
print(f"Solution entries: {len(result['solution'])}")
print(f"First entries: {dict(list(result['solution'].items())[:3])}")
print(f"Objective value: {result['objective_value']}")
print(f"Feasible: {result['feasible']}")
print(f"Solver-info fields: {list(solver_info)}")
print(f"Effective seed: {solver_info['seed']}")
print(f"Resource-usage phases: {list(result['metadata']['resource_usage'])}")

Result fields: ['solution', 'objective_value', 'feasible', 'metadata']
Solution entries: 200
First entries: {'x_0': 0.0, 'x_1': 0.0, 'x_2': 1.0}
Objective value: -35.0
Feasible: True
Solver-info fields: ['seed', 'solution_before_postprocessing']
Effective seed: 42
Resource-usage phases: ['RUNNING: MAPPING', 'RUNNING: OPTIMIZING_FOR_HARDWARE', 'RUNNING: WAITING_FOR_QPU', 'RUNNING: EXECUTING_QPU', 'RUNNING: POST_PROCESSING']

Mapear a solução para o grafo

Reúna os valores retornados na ordem dos índices das variáveis e mapeie-os de volta para as variáveis do problema original com interpret(). Os nós selecionados são as variáveis com valor 1, e is_feasible() verifica a atribuição em relação às restrições de aresta do problema original.

x_qubo = [result["solution"][f"x_{i}"] for i in range(qubo.get_num_vars())]
x = converter.interpret(x_qubo)
selected_nodes = [node for node, value in enumerate(x) if value > 0.5]

print(f"Selected nodes: {len(selected_nodes)}")
print(f"Satisfies every edge constraint: {mis.is_feasible(x)}")

Selected nodes: 35
Satisfies every edge constraint: True

Comparar com a solução antes do pós-processamento

Como postprocessing_level é 1, solver_info também registra a atribuição arredondada de antes da busca local clássica em solution_before_postprocessing. Ela usa as mesmas chaves de solution.

Avalie-a no QUBO para ver quanto o refinamento melhorou o resultado. Ambos os valores são objetivos do QUBO de minimização enviado, então um valor menor é melhor. O campo é omitido quando a busca local não é executada, por exemplo, quando o presolve fixa todas as variáveis.

before = solver_info.get("solution_before_postprocessing")
if before is None:
    print("The classical local search did not run for this problem.")
else:
    x_before = [before[f"x_{i}"] for i in range(qubo.get_num_vars())]
    changed = sum(
        before[key] != value for key, value in result["solution"].items()
    )
    print(
        f"Objective before local search: {qubo.objective.evaluate(x_before)}"
    )
    print(f"Objective after local search: {result['objective_value']}")
    print(f"Variables changed by local search: {changed}")

Objective before local search: -12.0
Objective after local search: -35.0
Variables changed by local search: 19

Verificar a restrição de independência

Como o QUBO representa a adjacência por meio de termos de penalidade em vez de restrições explícitas, um resultado heurístico ainda pode selecionar nós adjacentes. Verifique os nós retornados diretamente em relação ao grafo. Para a comparação e a visualização nas seções a seguir, copie o conjunto retornado e remova de forma gulosa uma extremidade de cada conflito detectado.

returned_set = set(selected_nodes)
conflicts = [
    (u, v) for u, v in G.edges if u in returned_set and v in returned_set
]
print(f"Conflicting edges in the returned set: {len(conflicts)}")

independent_set = returned_set.copy()
for u, v in conflicts:
    if u in independent_set and v in independent_set:
        # Drop the endpoint that has more selected neighbors.
        drop = max(
            (u, v),
            key=lambda node: sum(nb in independent_set for nb in G[node]),
        )
        independent_set.remove(drop)

assert all(
    not (u in independent_set and v in independent_set) for u, v in G.edges
)
print(f"Independent set size after repair: {len(independent_set)}")

Conflicting edges in the returned set: 0
Independent set size after repair: 35

Comparar com a solução de referência

Na Etapa 1, você baixou o valor objetivo da solução de referência do QOBLIB. As soluções de referência do QOBLIB podem ser ótimas ou as melhores conhecidas, então compare com o objetivo de referência sem presumir que ele seja sempre um ótimo certificado.

Para este problema de maximização, uma razão de 1.0 significa que o resultado reparado coincide com o objetivo de referência.

ratio_to_reference = len(independent_set) / reference_objective

print(f"Reference objective: {reference_objective:g}")
print(f"Ratio to reference: {ratio_to_reference:.3f}")

Reference objective: 44
Ratio to reference: 0.795

Visualizar o resultado

Plote o grafo novamente com o conjunto independente reparado destacado. Nenhum par de nós destacados compartilha uma aresta.

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=[v for v in G if v not in independent_set],
    node_size=node_size,
    node_color="lightgray",
    ax=ax,
)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=sorted(independent_set),
    node_size=node_size * 1.4,
    node_color="tab:blue",
    ax=ax,
)
ax.set_title(
    f"Independent set size: {len(independent_set)} "
    f"(reference: {reference_objective:g})"
)
ax.set_axis_off()
plt.show()

Ler o uso de recursos

Os metadados do resultado informam CPU_TIME para as fases diferentes de RUNNING: EXECUTING_QPU, quando disponível. A fase RUNNING: EXECUTING_QPU pode informar QPU_TIME, o uso da QPU retornado pelo Quantum Compute, se o uso final estiver disponível para todos os jobs do Quantum Compute.

usage = result["metadata"]["resource_usage"]

for phase, metrics in usage.items():
    line = f"{phase:36s}"
    if "CPU_TIME" in metrics:
        line += f" CPU {metrics['CPU_TIME']:8.1f} s"
    if "QPU_TIME" in metrics:
        line += f" QPU {metrics['QPU_TIME']:8.1f} s"
    print(line)

RUNNING: MAPPING                     CPU     11.8 s
RUNNING: OPTIMIZING_FOR_HARDWARE     CPU     15.4 s
RUNNING: WAITING_FOR_QPU             CPU     16.5 s
RUNNING: EXECUTING_QPU               QPU      3.0 s
RUNNING: POST_PROCESSING             CPU     55.8 s

Conclusão

Neste tutorial, você baixou uma instância de MIS do QOBLIB, a formulou como um QUBO com qiskit-addon-opt-mapper, se conectou ao SQOA Solver, configurou e enviou a carga de trabalho, mapeou a atribuição retornada de volta para o grafo e verificou os nós selecionados em relação ao grafo original.

Você também comparou o resultado com a solução de referência do QOBLIB, examinou a contribuição do pós-processamento clássico e inspecionou o uso de recursos de cada fase de execução.

O SQOA Solver combina presolve, QRAO com uma codificação baseada em QRAC, construção de circuitos de amostragem, transpilação consciente do hardware, diagonalização baseada em amostras, arredondamento e refinamento clássico. Esse fluxo de trabalho pode mapear mais variáveis binárias do que uma codificação de uma variável por qubit permitiria. A quantidade de redução obtida com o presolve e a codificação depende da estrutura do problema, e a qualidade da solução depende das amostras obtidas.

As configurações shots e postprocessing_level controlam, respectivamente, o orçamento de amostragem quântica e o refinamento clássico, sem alterar o fluxo de envio.

Apêndice: envie o problema como uma instância OMMX

O SQOA Solver também aceita uma ommx.v1.Instance do SDK OMMX. O pacote OMMX Quantum Benchmarks distribui os problemas do QOBLIB como instâncias OMMX junto com suas soluções de referência, para que você possa carregar o mesmo QUBO sem precisar formulá-lo você mesmo.

Com uma entrada OMMX, objective_value é avaliado no sentido da instância, e o resultado também contém a ommx.v1.Solution canônica. Instale o pacote, que também instala o SDK OMMX:

# %pip install ommx-quantum-benchmarks

Carregue o modelo binary_unconstrained da mesma instância. O carregador do conjunto de dados imprime mensagens de progresso, por isso o código as captura para manter a saída compacta.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

ommx_instance, _ = IndependentSet()("binary_unconstrained", INSTANCE_NAME)

O SQOA Solver recebe uma instância OMMX como uma string Base64 padrão com preenchimento e retorna a solução canônica no mesmo formato. Defina duas funções auxiliares para essa conversão:

• to_problem_payload() serializa uma ommx.v1.Instance na string que você passa como problem.

• to_ommx_solution() decodifica a ommx.v1.Solution canônica a partir do resultado.

import base64

from ommx.v1 import Instance, Solution

def to_problem_payload(instance: Instance) -> str:
    """Serialize an OMMX instance into the `problem` string for SQOA Solver."""
    return base64.b64encode(instance.to_bytes()).decode()

def to_ommx_solution(result: dict) -> Solution:
    """Decode the canonical OMMX solution from a SQOA Solver result."""
    payload = result["metadata"]["solver_info"]["ommx_solution"]
    return Solution.from_bytes(base64.b64decode(payload, validate=True))

Envie a instância com as mesmas entradas de antes, substituindo apenas problem. Depois, decodifique a solução canônica e leia os nós selecionados pelo nome da variável.

ommx_job = solver.run(
    **{**sqoa_input, "problem": to_problem_payload(ommx_instance)}
)
ommx_result = ommx_job.result()

ommx_solution = to_ommx_solution(ommx_result)
x_values = ommx_solution.extract_decision_variables("x")
ommx_nodes = sorted(
    node for (node,), value in x_values.items() if value > 0.5
)

print(f"Objective value: {ommx_result['objective_value']}")
print(f"Selected nodes: {len(ommx_nodes)}")

Objective value: 35.0
Selected nodes: 35

Próximos passos

Recomendações

• Aplique o fluxo de trabalho aos seus próprios problemas QUBO. Construa um OptimizationProblem como mostrado no guia do SQOA Solver. As etapas de conversão e envio continuam as mesmas, mas adapte a validação à estrutura do seu problema.
• Envie o problema como uma instância OMMX, como mostrado no apêndice. Consulte a referência da API para ver os formatos de problema aceitos e os campos retornados.
• Explore outras instâncias de conjunto independente no repositório do QOBLIB ou por meio do OMMX Quantum Benchmarks.
• Saiba mais sobre modelagem com qiskit-addon-opt-mapper ou JijModeling e sobre troca de problemas com OMMX.

Referências

[1] Koch, T., Bernal Neira, D. E., Chen, Y., Cortiana, G., Egger, D. J., Heese, R., Hegade, N. N., Gomez Cadavid, A., Huang, R., Itoko, T., et al. (2026). Quantum optimization benchmarking library: The intractable decathlon. Nature Computational Science, 6, 653–671. DOI, arXiv:2504.03832

[2] Matsuyama, H., & Yamashiro, Y. (2025). Sampling-based quantum optimization algorithm with quantum relaxation. 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 1, 2323–2333. DOI, arXiv:2504.12629

[3] Fuller, B., Hadfield, C., Glick, J. R., Imamichi, T., Itoko, T., Thompson, R. J., Jiao, Y., Kagele, M. M., Blom-Schieber, A. W., Raymond, R., et al. (2024). Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5, 1–15. DOI, arXiv:2111.03167

[4] Kanno, K., Kohda, M., Imai, R., Koh, S., Mitarai, K., Mizukami, W., & Nakagawa, Y. O. (2026). Quantum-selected configuration interaction: Classical diagonalization of Hamiltonians in subspaces selected by quantum computers. Physical Review Research, 8(2), 023268. DOI, arXiv:2302.11320

[5] Robledo-Moreno, J., Motta, M., Haas, H., Javadi-Abhari, A., Jurcevic, P., Kirby, W., et al. (2025). Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances, 11(25), eadu9991. DOI, arXiv:2405.05068