Encontre o Conjunto Independente Máximo com o Aqarios Constrained Quantum Optimizer

Nota

Qiskit Functions são um recurso experimental disponível apenas para usuários dos planos IBM Quantum® Premium Plan, Flex Plan e On-Prem (via IBM Quantum Platform API). Eles estão em status de lançamento prévio e sujeitos a alterações.

Estimativa de uso: 30 segundos em um processador Heron r2. (NOTA: Isso é apenas uma estimativa. Seu tempo de execução pode variar.)

Contexto

Este tutorial demonstra como encontrar o conjunto independente máximo de um grafo usando o Aqarios Constrained Quantum Optimizer [1], um problema de otimização combinatória com restrições. Uma instância da biblioteca de benchmark QOBLIB [2] é formulada como um programa linear binário e passada para a Optimizer Application Function. O otimizador trata internamente toda a reformulação, síntese de circuitos, transpilação e warm-starting iterativo (veja [3] para detalhes).

O tutorial cobre as seguintes etapas:

1. Defina o problema como um programa linear usando o OptimizationProblem do qiskit-addon-opt-mapper

2. Execute a otimização quântica usando o Aqarios Constrained Quantum Optimizer

3. Recupere e visualize os resultados

O problema do Conjunto Independente Máximo

O problema do Conjunto Independente Máximo (MIS) é um desafio fundamental em otimização combinatória. Formalmente, dado um grafo $G(V, E)$, o objetivo é encontrar o maior subconjunto de vértices $V_I \subset V$ tal que nenhum par de vértices em $V_I$ esteja conectado por uma aresta, como em $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Cada vértice recebe uma variável de decisão binária $x_i \in \{0, 1\}$, e uma restrição $x_u + x_v \leq 1$ é introduzida para cada aresta, garantindo que no máximo uma extremidade de cada aresta seja selecionada. O problema pode, portanto, ser formulado como o seguinte problema de maximização:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(encontre o maior conjunto)}\\ \text{sujeito a} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

O MIS tem uma ampla gama de aplicações práticas. No planejamento de redes sem fio, um conjunto independente corresponde a um grupo de transmissores que podem transmitir simultaneamente sem interferência mútua. No escalonamento, ele modela o maior conjunto de tarefas que podem ser executadas simultaneamente dados conflitos de recursos entre pares. Na biologia computacional, ele captura conjuntos de proteínas que não interagem mutuamente em uma rede.

Apesar de sua formulação intuitiva, o MIS é NP-difícil, e mesmo para grafos com algumas centenas de nós, instâncias específicas se tornam difíceis de resolver de forma exata ou heurística [2]. O problema também dá origem a estruturas de restrição esparsas que são bem adequadas para implementações de hardware de otimização quântica, tornando-o um benchmark atraente para dispositivos quânticos de curto prazo.

Aqarios Constrained Quantum Optimizer

A abordagem padrão para incorporar um problema binário com restrições em uma otimização quântica transforma o modelo em um formato sem restrições ao adicionar termos de penalidade: cada restrição violada $x_u + x_v \leq 1$ contribui com $2 x_u x_v$ para o objetivo de minimização $-\sum_i x_i$. Isso é tratado automaticamente pela Constrained Quantum Optimizer Qiskit Function.

Além dessa transformação padrão, o otimizador identifica cliques no grafo de restrições. Um clique é um conjunto de nós $V_C$ no qual todo par de nós compartilha uma aresta. Como consequência, as $\binom{|V_C|}{2}$ restrições em pares $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ podem ser substituídas por uma única restrição mais forte $\sum_{i \in V_C} x_i \leq 1$. Introduzir uma variável de folga $y$ transforma isso em uma igualdade $\sum_i x_i + y = 1$, que assume a forma de uma restrição one-hot que pode ser aplicada diretamente no QAOA usando XY-mixers [3]. Isso reduz o espaço de busca e evita a necessidade de termos de penalidade para essas restrições, melhorando a qualidade da solução.

Além disso, variáveis conectadas a apenas um único vizinho são chamadas de nós pendentes e são fixadas deterministicamente pelo algoritmo antes da execução quântica, reduzindo ainda mais o tamanho efetivo do problema.

O Constrained Quantum Optimizer emprega uma abordagem de warm-starting iterativo compatível com XY-mixers [1], que estreita progressivamente o espaço de busca ao enviesar a distribuição do estado quântico em direção a regiões de solução promissoras ao longo das iterações. Isso permite o uso de parâmetros de QAOA de ângulo fixo, eliminando a necessidade de treinamento de parâmetros variacionais. Os requisitos totais de recursos quânticos são regidos apenas pelo número de iterações de warm-start, o que torna o custo quântico simples de controlar.

Requisitos

Antes de iniciar este tutorial, certifique-se de ter instalado os seguintes requisitos:

• Qiskit Runtime (pip install qiskit-ibm-runtime)

• Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)

• Qiskit Addon Optimization Mapper (pip install qiskit-addon-opt-mapper)

• Numpy (pip install numpy)

• Matplotlib (pip install matplotlib)

• NetworkX (pip install networkx)

Opcionalmente, para o Apêndice, você precisa instalar

• Luna Model (pip install luna-model)

Configuração

Importe todas as dependências necessárias.

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

_needed = {"luna_model": "luna-model", "networkx": "networkx", "numpy": "numpy", "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")

import networkx as nx
import urllib.request

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.applications import IndependentSet
from qiskit_addon_opt_mapper.translators import to_docplex_mp

Primeiro, autentique-se usando sua chave de API do IBM Quantum. Em seguida, selecione a Qiskit Function conforme a seguir. (Este código pressupõe que você já tenha salvado sua conta em seu ambiente local.)

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

# Verify that you have access to the function
catalog.list()

[QiskitFunction(aqarios/constrained-quantum-optimizer)]

# Load the function
optimizer = catalog.load("aqarios/constrained-quantum-optimizer")

# Check the list of backends you have access to
catalog.backends()

[<IBMBackend('ibm_pittsburgh')>,
 <IBMBackend('ibm_boston')>,
 <IBMBackend('ibm_phoenix')>,
 <IBMBackend('ibm_fez')>,
 <IBMBackend('ibm_miami')>,
 <IBMBackend('ibm_marrakesh')>,
 <IBMBackend('ibm_kingston')>]

# Select the backend you want to use
backend = catalog.backend("ibm_pittsburgh")

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

O problema é formulado como um arquivo LP, um formato comum para problemas de otimização que serve como entrada para o Aqarios Constrained Quantum Optimizer. Além de arquivos LP, a função também suporta arquivos MPS e representações nativas do Luna Model. O arquivo LP é gerado por meio das seguintes etapas:

1. Obtenha uma instância de grafo da QOBLIB [2]

2. Modele o problema de otimização

3. Gere o arquivo LP

Carregue o grafo da instância do problema

Os grafos são especificados no formato DIMACS .gph, um formato baseado em linhas em que linhas iniciadas com e definem arestas, linhas iniciadas com p definem o cabeçalho do problema, e linhas iniciadas com c são comentários:

c some-comment
p edge 3 2
e 1 2
e 2 3
...

O arquivo .gph pode ser baixado do repositório QOBLIB usando a função a seguir, que também o analisa em um grafo NetworkX. Observe que o formato DIMACS usa rotulação de nós baseada em 1, que é convertida aqui para indexação baseada em 0.

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

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Fetch and parse the QOBLIB graph file."""
    # Download the .gph file
    file, _ = urllib.request.urlretrieve(URL_BASE + f"{name}.gph")
    with open(file) as f:
        # Read the file contents
        lines = f.readlines()

    # Skip comments
    lines = [line for line in lines if not line.startswith("c")]

    # Read graph definition
    _, _, num_nodes, num_edges = lines[0].split()
    print(f"Loading graph with {num_nodes} nodes and {num_edges} edges.")

    # Parse edge information
    # The .gph format starts node labeling with 1; we need 0 here, so we subtract one.
    split_edges = (line.split() for line in lines[1:])
    edges = [(int(u) - 1, int(v) - 1) for _, u, v in split_edges]

    return nx.Graph(edges)

graph_name = "es60fst02"
graph = fetch_qoblib_graph(graph_name)

Loading graph with 186 nodes and 280 edges.

Este exemplo usa a instância es60fst02 da QOBLIB, um grafo com 186 nós e 280 arestas. Graças às etapas de pré-processamento empregadas pelo Constrained Quantum Optimizer, essa instância pode ser resolvida em dispositivos Heron de 156 qubits. O grafo pode ser visualizado usando matplotlib:

# Keep layout for later reuse
layout = nx.spring_layout(graph, seed=1)
nx.draw(graph, layout, node_size=40)

Construa o problema de otimização

O problema do Conjunto Independente Máximo pode ser formulado diretamente usando OptimizationProblem. Cada nó do grafo se torna uma variável de decisão binária, e cada aresta introduz uma restrição garantindo que no máximo uma de suas extremidades seja selecionada:

# Create an OptimizationProblem instance
mis_problem = OptimizationProblem("MIS")

# Add a binary variable for each node
x = mis_problem.binary_var_list(graph.number_of_nodes())

# Maximize the sum of all node variables
mis_problem.maximize(linear={xi.name: 1 for xi in x})

# Add '<= 1' constraints for each edge
for u, v in graph.edges:
    mis_problem.linear_constraint({x[u].name: 1, x[v].name: 1}, "<=", 1)

Um atalho

O pacote qiskit-addon-opt-mapper fornece uma classe de aplicação pré-implementada para o problema do Conjunto Independente Máximo, que simplifica a formulação acima em uma única chamada:

mis = IndependentSet(graph)
mis_problem = mis.to_optimization_problem()

Traduza o problema para um arquivo LP

O próprio OptimizationProblem não suporta exportação para arquivo LP, mas é interoperável com o DOcplex, que suporta. Gerar o conteúdo do arquivo LP requer apenas duas linhas:

mp_model = to_docplex_mp(mis_problem)
lp_str = mp_model.export_as_lp_string()

print("\n".join(lp_str.split("\n")[:60]))
print("...")

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Independent set

Maximize
 obj: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_10 + x_11
      + x_12 + x_13 + x_14 + x_15 + x_16 + x_17 + x_18 + x_19 + x_20 + x_21
      + x_22 + x_23 + x_24 + x_25 + x_26 + x_27 + x_28 + x_29 + x_30 + x_31
      + x_32 + x_33 + x_34 + x_35 + x_36 + x_37 + x_38 + x_39 + x_40 + x_41
      + x_42 + x_43 + x_44 + x_45 + x_46 + x_47 + x_48 + x_49 + x_50 + x_51
      + x_52 + x_53 + x_54 + x_55 + x_56 + x_57 + x_58 + x_59 + x_60 + x_61
      + x_62 + x_63 + x_64 + x_65 + x_66 + x_67 + x_68 + x_69 + x_70 + x_71
      + x_72 + x_73 + x_74 + x_75 + x_76 + x_77 + x_78 + x_79 + x_80 + x_81
      + x_82 + x_83 + x_84 + x_85 + x_86 + x_87 + x_88 + x_89 + x_90 + x_91
      + x_92 + x_93 + x_94 + x_95 + x_96 + x_97 + x_98 + x_99 + x_100 + x_101
      + x_102 + x_103 + x_104 + x_105 + x_106 + x_107 + x_108 + x_109 + x_110
      + x_111 + x_112 + x_113 + x_114 + x_115 + x_116 + x_117 + x_118 + x_119
      + x_120 + x_121 + x_122 + x_123 + x_124 + x_125 + x_126 + x_127 + x_128
      + x_129 + x_130 + x_131 + x_132 + x_133 + x_134 + x_135 + x_136 + x_137
      + x_138 + x_139 + x_140 + x_141 + x_142 + x_143 + x_144 + x_145 + x_146
      + x_147 + x_148 + x_149 + x_150 + x_151 + x_152 + x_153 + x_154 + x_155
      + x_156 + x_157 + x_158 + x_159 + x_160 + x_161 + x_162 + x_163 + x_164
      + x_165 + x_166 + x_167 + x_168 + x_169 + x_170 + x_171 + x_172 + x_173
      + x_174 + x_175 + x_176 + x_177 + x_178 + x_179 + x_180 + x_181 + x_182
      + x_183 + x_184 + x_185
Subject To
 c0: x_60 + x_61 <= 1
 c1: x_14 + x_60 <= 1
 c2: x_7 + x_60 <= 1
 c3: x_7 + x_61 <= 1
 c4: x_61 + x_62 <= 1
 c5: x_61 + x_64 <= 1
 c6: x_14 + x_62 <= 1
 c7: x_62 + x_65 <= 1
 c8: x_23 + x_63 <= 1
 c9: x_53 + x_63 <= 1
 c10: x_39 + x_63 <= 1
 c11: x_7 + x_68 <= 1
 c12: x_18 + x_68 <= 1
 c13: x_68 + x_69 <= 1
 c14: x_68 + x_72 <= 1
 c15: x_64 + x_65 <= 1
 c16: x_64 + x_69 <= 1
 c17: x_65 + x_66 <= 1
 c18: x_51 + x_53 <= 1
 c19: x_69 + x_73 <= 1
 c20: x_66 + x_67 <= 1
 c21: x_42 + x_66 <= 1
 c22: x_67 + x_75 <= 1
 c23: x_43 + x_67 <= 1
 c24: x_42 + x_75 <= 1
 c25: x_75 + x_83 <= 1
 c26: x_12 + x_51 <= 1
 c27: x_18 + x_70 <= 1
 c28: x_18 + x_26 <= 1
 c29: x_70 + x_71 <= 1
 c30: x_70 + x_76 <= 1
 c31: x_71 + x_72 <= 1
 c32: x_72 + x_73 <= 1
 c33: x_72 + x_78 <= 1
...

Esse formato é nativo do Constrained Quantum Optimizer.

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

Toda a síntese, otimização e transpilação de circuitos é tratada nativamente pela função. Consulte a seção de entradas na referência da API para os argumentos com os quais chamar a função.

Para ajustar o comportamento do algoritmo, consulte a lista de opções na referência da API. Se você quiser que o mapeamento do circuito seja reproduzível entre execuções, fixe a opção seed_transpiler.

Para mais informações, consulte o guia do Aqarios Constrained Quantum Optimizer e a referência da API.

Etapa 3: Executar usando as primitivas do Qiskit

O arquivo LP agora pode ser enviado ao otimizador:

job = optimizer.run(problem=lp_str, backend_name=backend.name)

print(f"Job ID: {job.job_id}")

Job ID: 87ec08b9-6275-40fa-be94-340a0a916bf1

Internamente, o algoritmo passa pelas seguintes etapas:

1. Preprocessing:

   • Reduza variáveis fixáveis

   • Encontre cliques

   • Identifique tipos de restrição

   • Avalie fatores de penalidade para os termos de penalidade

   • Aplique transformações de restrição

   • Sintetize o circuito com métodos de imposição de restrições

   • Aproximação do problema e transpilação

2. Cadeias paralelas de laços iterativos:

   • Amostre do circuito com parâmetros fixos

   • Aplique pós-processamento

   • Avalie e defina novas probabilidades de warm-starting

3. Postprocessing:

   • Encontre as melhores amostras e verifique a viabilidade em relação ao problema de entrada

Monitore o progresso

Consulte as seguintes seções na página Get started with Qiskit Functions para monitorar o progresso do seu job:

• Verificar o status do job

• Recuperar resultados

# Monitor the job status
job.status()

'QUEUED'

Etapa 4: Pós-processar e retornar os resultados no formato clássico desejado

A saída do resultado é um dicionário, cujos campos são descritos na seção de saídas da referência da API.

Quando a lista solutions contém mais de uma entrada, múltiplos ótimos degenerados foram encontrados. Aqui, apenas a primeira solução é considerada, indicada pelo nome da variável. As mesmas soluções também estão disponíveis como bitstrings em solution_bitstrings, onde metadata.solver_info.variable_mapping fornece a posição de caractere de cada variável.

# Retrieve the job result
result = job.result()

# Retrieve the first solution from the result
solution = result["solutions"][0]

print(f"The found maximum independent set of {graph_name} contains:", end=" ")
print(
    f"{int(result['objective_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}."
)
print("{" + " ".join(k[2:] for k, v in solution.items() if v == 1) + "}")

The found maximum independent set of es60fst02 contains: 88 nodes and is feasible.
{100 103 107 109 111 113 115 118 121 123 124 127 129 130 132 133 138 142 144 148 149 155 156 16 161 162 165 167 169 170 175 28 31 33 35 36 47 50 58 59 60 62 64 66 68 71 73 75 78 79 84 85 87 90 91 93 94 95 39 5 27 23 43 15 22 9 4 56 32 30 53 26 17 54 1 37 41 49 34 11 139 153 12 3 6 57 20 44}

Visualização

O conjunto independente identificado pode ser visualizado destacando os nós selecionados no grafo:

# Color all selected nodes in orange
node_map = {
    int(k.split("_")[1]): "tab:orange" if v else "tab:blue"
    for k, v in solution.items()
}
node_colors = [node_map[k] for k in graph.nodes]

# Draw with the same layout used before
nx.draw(graph, layout, node_size=40, node_color=node_colors)

Apêndice: Formulação do problema com o Luna Model

Além da abordagem qiskit-addon-opt-mapper mostrada acima, a Qiskit Function também aceita modelos criados com o Luna Model [4], o SDK de modelagem da Aqarios. Após a instalação do pacote PyPI luna-model, importe-o da seguinte forma:

Setup:

from luna_model import Model, Sense
import numpy as np

O modelo é então construído a partir do grafo da mesma forma que com o qiskit-addon-opt-mapper: Construa o modelo:

edges = np.array(graph.edges)

# Create the optimization model with a name
model = Model(name=f"MIS-{graph_name}", sense=Sense.MAX)
# Add binary variables
x = model.add_variables("x", graph.number_of_nodes())
# Set the objective
model.objective = x.sum()

# Use numpy like batch generation of constraints
model.add_constraints(x[edges].sum(axis=1) <= 1)

input_str = model.encode_b64()

# optimizer.run(problem=input_str, backend_name="ibm_fez")

Próximos passos

Recomendações

• Consulte o guia do Aqarios Constrained Quantum Optimizer para um passo a passo detalhado de todos os recursos da função.
• Explore a referência da API para a lista completa de parâmetros de entrada e campos de saída.
• Experimente as opções do algoritmo (reps, num_parallel, shots, postprocessing_level) em seu próprio problema de otimização binária com restrições para avaliar seu impacto na qualidade da solução e no tempo de execução.

Referências

1. IBM Quantum, Aqarios Constrained Quantum Optimizer Guide

2. Koch et al. (2026), The Quantum Optimization Benchmarking Library 10.1038/s43588-026-00991-1

3. Bucher et al. (2026), Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers 10.1088/1367-2630/ae8ea2

4. Aqarios GmbH, Luna Model Docs