Encontre o Conjunto Independente Máximo com o Otimizador Quântico Restrito Aqarios

Estimativa de tempo de execução: 30 segundos em um processador Heron r2. (OBSERVAÇÃO: Trata-se apenas de uma estimativa. (O tempo de execução pode variar.)

Segundo plano

Este tutorial demonstra como encontrar o conjunto independente máximo de um grafo utilizando o Otimizador Quântico com Restrições Aqarios [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 Função de Aplicação do Otimizador. O otimizador realiza internamente toda a reformulação, síntese de circuitos, transpilagem e inicialização iterativa (consulte [3] para obter mais detalhes).

O tutorial aborda as seguintes etapas:

1. Defina o problema como um programa linear utilizando o OptimizationProblem do qiskit-addon-opt-mapper
2. Execute a otimização quântica utilizando o Aqarios Constrained Quantum Optimizer
3. Recuperar e visualizar os resultados

O problema do Conjunto Independente Máximo

O problema do Conjunto Independente Máximo (MIS) é um desafio fundamental na 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, conforme ilustrado em $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. A cada vértice é atribuída 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 das extremidades de cada aresta seja selecionada. O problema pode, portanto, ser formulado como o seguinte problema de maximização:

O MIS possui 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 causar interferência mútua. No planejamento de horários, ele modela o maior conjunto de tarefas que podem ser executadas simultaneamente, levando em conta os conflitos de recursos entre pares. Na biologia computacional, ele identifica conjuntos de proteínas que não interagem entre si 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 tornam-se difíceis de resolver exatamente ou de forma heurística [2]. O problema também dá origem a estruturas de restrições esparsas que são adequadas para implementações em hardware de otimização quântica, tornando-o um benchmark atraente para dispositivos quânticos no curto prazo.

Otimizador Quântico com Restrições Aqarios

A abordagem padrão para incorporar um problema binário com restrições à otimização quântica transforma o modelo em um formato sem restrições por meio da adição de 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 função Constrained Quantum Optimizer do Qiskit.

Além dessa transformação padrão, o otimizador identifica cliques no grafo de restrições. Um clique é um conjunto de vértices $V_C$ em que cada par de vértices é conectado por uma aresta. Consequentemente, as restrições em pares $\binom{|V_C|}{2}$ $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ podem ser substituídas por uma única restrição mais restritiva $\sum_{i \in V_C} x_i \leq 1$. A introdução de 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 misturadores XY [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, as variáveis conectadas a apenas um único vizinho são chamadas de nós pendentes e são definidas de forma determinística pelo algoritmo antes da execução quântica, reduzindo ainda mais o tamanho efetivo do problema.

O Otimizador Quântico Restrito emprega uma abordagem iterativa de “warm-starting” compatível com misturadores XY [1], que reduz progressivamente o espaço de busca ao direcionar a distribuição do estado quântico para regiões de solução promissoras ao longo das iterações. Isso permite o uso de parâmetros QAOA de ângulo fixo, eliminando a necessidade de treinamento de parâmetros variacionais. Os requisitos totais de recursos quânticos são determinados exclusivamente pelo número de iterações de inicialização a quente, o que significa que o custo quântico é fácil de controlar.

Requisitos

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

• Qiskit Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions Catalog IBM Cliente (pip install qiskit-ibm-catalog)
• Mapeador de otimização do complemento do Qiskit (pip install qiskit-addon-opt-mapper)
• Numpy (pip install numpy)
• Matplotlib (pip install matplotlib)
• NetworkX (pip install networkx)

Opcionalmente, para o Apêndice, é necessário instalar

• Modelo Luna (pip install luna-model)

Instalação

Importe todas as dependências necessárias.

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, faça a autenticação usando sua chave de API do IBM Quantum. Em seguida, selecione a função do Qiskit da seguinte maneira. (Este código pressupõe que você já tenha salvo sua conta no seu ambiente local.)

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

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

Output:

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

Output:

[<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: Mapeamento de 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 dos 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. Buscar uma instância de grafo da biblioteca QOBLIB [2]
2. Modelar o problema de otimização
3. Gerar o arquivo LP

Carregar o gráfico da instância do problema

Os gráficos são especificados no formato .gph DIMACS, um formato baseado em linhas em que as linhas que começam com e definem arestas, as linhas que começam com p definem o cabeçalho do problema e as linhas que começam 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 por meio da seguinte função, que também o analisa para gerar um gráfico do tipo “ NetworkX ”. Observe que o formato DIMACS utiliza numeração de nós a partir de 1, que é convertida aqui para indexação a partir de 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)

Output:

Loading graph with 186 nodes and 280 edges.

Este exemplo utiliza a es60fst02 instância da QOBLIB, um grafo com 186 nós e 280 arestas. Graças às etapas de pré-processamento empregadas pelo Otimizador Quântico Restrito, esta instância pode ser resolvida em dispositivos Heron de 156 qubits. O gráfico pode ser visualizado usando o matplotlib:

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

Output:

Formule 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 que garante 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 qiskit-addon-opt-mapper pacote oferece uma classe de aplicação pré-implementada para o problema do Conjunto Independente Máximo, o que simplifica a formulação acima em uma única chamada:

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

Converta o problema em um arquivo LP

O próprio OptimizationProblem programa não oferece suporte à exportação de arquivos LP, mas é compatível com o DOcplex, que oferece esse recurso. Para gerar o conteúdo do arquivo LP, bastam 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("...")

Output:

\ 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 transpilagem de circuitos são realizadas de forma nativa pela função. Consulte a seção de entradas na referência da API para conhecer os argumentos com os quais se deve chamar a função.

Para ajustar o comportamento do algoritmo, consulte a lista de opções na referência da API.

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

Etapa 3: Executar usando o comando Qiskit primitives

Agora, o arquivo LP pode ser enviado ao otimizador:

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

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

Output:

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

Internamente, o algoritmo passa pelas seguintes etapas:

1. Pré-processamento :
   • Reduzir variáveis que podem ser fixadas
   • Encontre grupos
   • Identificar tipos de restrições
   • Avaliar os fatores de penalidade para os termos de penalidade
   • Aplicar transformações de restrição
   • Sintetizar circuitos com métodos de imposição de restrições
   • Aproximação do problema e transpilagem
2. Cadeias paralelas de loops iterativos :
   • Amostra de circuito com parâmetros fixos
   • Aplicar pós-processamento
   • Avaliar e definir novas probabilidades de partida a quente
3. Pós-processamento :
   • Encontre as melhores amostras e verifique a viabilidade em relação ao problema de entrada

Acompanhar o andamento

Consulte as seções a seguir na página “Introdução ao Qiskit Functions ” para acompanhar o andamento do seu trabalho:

• Verificar o status do trabalho
• Recuperar resultados

# Monitor the job status
job.status()

Output:

'QUEUED'

Etapa 4: Realizar o pós-processamento e apresentar os resultados no formato clássico desejado

O resultado retornado é um dicionário, cujos campos estão descritos na seção “Saídas” da referência da API.

Quando a lista solutions contém mais de um item, foram encontrados vários ótimos degenerados. Aqui, considera-se apenas a primeira solução:

# 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['obj_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}."
)
print("{" + " ".join(k[2:] for k, v in solution.items() if v == 1) + "}")

Output:

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-se os nós selecionados no gráfico:

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

Output:

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

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

Configuração:

from luna_model import Model, Sense
import numpy as np

O modelo é então construído a partir do gráfico da mesma forma que em 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(model=input_str, backend_name="ibm_fez")

Próximos passos

Referências

1. IBM Quantum, Guia do Otimizador Quântico Restrito do Aqarios
2. Koch et al. (2026), The Quantum Optimization Benchmarking Library 10.1038/s43588-026-00991-1
3. Bucher et al. (2026), *Otimização quântica com restrições por meio de misturadores XY iterativos com inicialização a quente *10.1088/1367-2630/ae8ea2
4. Documentação do modelo Luna da Aqarios GmbH,