Pular para o conteúdo principal

Optimization Solver: Uma Qiskit Function do Q-CTRL Fire Opal

nota

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

Visão geral​

Com o Fire Opal Optimization Solver, você pode resolver problemas de otimização em escala utilitária em hardware quântico sem precisar de conhecimento especializado em computação quântica. Basta inserir a definição do problema em alto nível e o Solver cuida do resto. Todo o fluxo de trabalho é ciente de ruído e utiliza o Gerenciamento de Desempenho do Fire Opal por baixo dos panos. O Solver entrega consistentemente soluções precisas para problemas classicamente desafiadores, mesmo em escala de dispositivo completo nos maiores QPUs da IBM®.

O Solver é flexível e pode ser usado para resolver problemas de otimização combinatória definidos como funções objetivo ou grafos arbitrários. Os problemas não precisam ser mapeados para a topologia do dispositivo. Tanto problemas sem restrições quanto com restrições são resolúveis, desde que as restrições possam ser formuladas como termos de penalidade. Os exemplos incluídos neste guia demonstram como resolver um problema de otimização em escala utilitária sem restrições e um com restrições, usando diferentes tipos de entrada do Solver. O primeiro exemplo envolve um problema Max-Cut definido em um grafo 3-regular com 156 nós, enquanto o segundo aborda um problema de Cobertura Mínima de Vértices com 50 nós definido por uma função de custo.

Para obter acesso ao Optimization Solver, entre em contato com o Q-CTRL.

Descrição da função​

O Solver otimiza e automatiza completamente todo o algoritmo, desde a supressão de erros no nível de hardware até o mapeamento eficiente de problemas e a otimização clássica em malha fechada. Por baixo dos panos, o pipeline do Solver reduz erros em cada etapa, possibilitando o desempenho aprimorado necessário para escalar de forma significativa. O fluxo de trabalho subjacente é inspirado no Quantum Approximate Optimization Algorithm (QAOA), que é um algoritmo híbrido quântico-clássico. Para um resumo detalhado do fluxo de trabalho completo do Optimization Solver, consulte o manuscrito publicado.

Visualização do fluxo de trabalho do Optimization Solver

Para resolver um problema genérico com o Optimization Solver:

  1. Defina seu problema como uma função objetivo, um grafo ou uma cadeia de spin SparsePauliOp.
  2. Conecte-se à função por meio do Catálogo de Qiskit Functions.
  3. Execute o problema com o Solver e recupere os resultados.

Entradas e saídas​

Entradas​

NomeTipoDescriçãoObrigatórioPadrãoExemplo
problemstr ou SparsePauliOpUma das representações listadas em "Formatos de problema aceitos"SimN/APoly(2.0*n[0]*n[1] + 2.0*n[0]*n[2] - 3.13520241298341*n[0] + 2.0*n[1]*n[2] - 3.14469748506794*n[1] - 3.18897660121566*n[2] + 6.0, n[0], n[1], n[2], domain='RR')
problem_typestrNome da classe do problema; usado apenas para definições de problema em grafo e cadeia de spin, que se limitam a "maxcut" ou "spin_chain"; não é necessário para definições de problema com função objetivo arbitráriaNãoNone"maxcut"
backend_namestrNome do backend a ser usadoNãoBackend menos ocupado ao qual sua instância tem acesso"ibm_fez"
optionsdictOpções de entrada, incluindo: (Opcional) session_id: str; o comportamento padrão cria uma nova SessãoNãoNone{"session_id": "cw2q70c79ws0008z6g4g"}

Formatos de problema aceitos:

  • Representação por expressão polinomial de uma função objetivo. Idealmente criada em Python com um objeto SymPy Poly existente e formatada como string usando sympy.srepr.
  • Representação em grafo de um tipo específico de problema. O grafo deve ser criado usando a biblioteca networkx em Python e, em seguida, convertido para string usando a função networkx [nx.readwrite.json_graph.adjacency_data](http://nx.readwrite.json_graph.adjacency_data.).
  • Representação em cadeia de spin de um problema específico. A cadeia de spin deve ser representada como um objeto SparsePauliOp; consulte a documentação para mais detalhes.

Backends suportados: Execute o código a seguir para ver a lista de backends atualmente suportados. Se o seu dispositivo não estiver listado, entre em contato com o Q-CTRL para adicionar suporte.

# Added by doQumentation — required packages for this notebook
!pip install -q networkx numpy qiskit-ibm-catalog qiskit-ibm-runtime sympy
from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()

service.backends()
[<IBMBackend('ibm_fez')>,
 <IBMBackend('ibm_brisbane')>,
 <IBMBackend('ibm_pittsburgh')>,
 <IBMBackend('ibm_kingston')>,
 <IBMBackend('ibm_torino')>,
 <IBMBackend('ibm_marrakesh')>]

Opções:

NomeTipoDescriçãoPadrão
session_idstrID de uma sessão do Qiskit Runtime existente"cw4r3je6f0t010870y3g"
job_tagslist[str]Uma lista de tags de job[]

Saídas​

NomeTipoDescriçãoExemplo
resultdict[str, Any]Solução e metadados listados em "Conteúdo do dicionário de resultados"{'solution_bitstring_cost': 3.0, 'final_bitstring_distribution': {'000001': 100, '000011': 2}, 'iteration_count': 3, 'solution_bitstring': '000001', 'variables_to_bitstring_index_map': {n[1]': 5, 'n[2]': 4, 'n[3]': 3, 'n[4]': 2, 'n[5]': 1}, 'best_parameters': [0.19628831763697097, -1.047052334523102], 'warnings': []}

Conteúdo do dicionário de resultados:

NomeTipoDescrição
solution_bitstring_costfloatO melhor custo mínimo entre todas as iterações
final_bitstring_distributionCountsDictO dicionário de contagens de bitstring associado ao custo mínimo
solution_bitstringstrBitstring com o melhor custo na distribuição final
iteration_countintO número total de iterações do QAOA realizadas pelo Solver
variables_to_bitstring_index_mapfloatO mapeamento das variáveis para o bit equivalente na bitstring
best_parameterslist[float]Os parâmetros beta e gamma otimizados em todas as iterações
warningslist[str]Os avisos produzidos durante a compilação ou execução do QAOA (padrão: None)

Benchmarks​

Resultados de benchmarking publicados mostram que o Solver resolve com sucesso problemas com mais de 120 qubits, superando até mesmo resultados previamente publicados em dispositivos de recozimento quântico e de íons aprisionados. As métricas de benchmark a seguir fornecem uma indicação aproximada da precisão e da escala dos tipos de problema com base em alguns exemplos. As métricas reais podem variar com base em diversas características do problema, como o número de termos na função objetivo (densidade) e sua localidade, o número de variáveis e a ordem polinomial.

O "Número de qubits" indicado não é uma limitação rígida, mas representa limites aproximados em que você pode esperar uma precisão de solução extremamente consistente. Problemas de maior escala já foram resolvidos com sucesso, e testes além desses limites são encorajados.

Conectividade arbitrária de qubits é suportada em todos os tipos de problema.

Tipo de problemaNúmero de qubitsExemploPrecisãoTempo total (s)Uso de runtime (s)Número de iterações
Problemas quadráticos com conexões esparsas156Max-Cut 3-regular100%176429316
Otimização binária de ordem superior156Modelo Ising spin-glass100%146127216
Problemas quadráticos com conexões densas50Max-Cut totalmente conectado100%175826812
Problema com restrições e termos de penalidade50Cobertura Mínima de Vértices Ponderada com 8% de densidade de arestas100%107421510

Primeiros passos​

Primeiro, autentique-se usando sua chave de API do IBM Quantum. Em seguida, selecione a Qiskit Function da seguinte forma. (Este trecho assume que você já salvou sua conta no seu ambiente local.)

from qiskit_ibm_catalog import QiskitFunctionsCatalog

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

# Access Function
solver = catalog.load("q-ctrl/optimization-solver")

Exemplo: Otimização sem restrições​

Execute o problema de corte máximo (Max-Cut). O exemplo a seguir demonstra as capacidades do Solver em um problema Max-Cut em um grafo 3-regular não ponderado com 156 nós, mas você também pode resolver problemas com grafos ponderados. Além do qiskit-ibm-catalog, você também usará os seguintes pacotes para executar este exemplo: networkx e numpy. Você pode instalar esses pacotes descomentando a célula a seguir se estiver executando este exemplo em um notebook com o kernel IPython.

# %pip install networkx numpy

1. Definir o problema​

Você pode executar um problema Max-Cut definindo um problema em grafo e especificando problem_type='maxcut'.

import networkx as nx
import numpy as np

# Generate a random graph with 156 nodes
maxcut_graph = nx.random_regular_graph(d=3, n=156, seed=8)
# Optionally, visualize the graph
nx.draw_networkx(
    maxcut_graph, nx.kamada_kawai_layout(maxcut_graph), node_size=100
)

Saída da célula de código anterior

O Solver aceita uma string como entrada da definição do problema.

# Convert graph to string
problem_as_str = nx.readwrite.json_graph.adjacency_data(maxcut_graph)

2. Executar o problema​

Ao usar o método de entrada baseado em grafo, especifique o tipo de problema.

# This cell is hidden from users
from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
backend_name = service.least_busy(n_qubits=156).name
# Solve the problem
maxcut_job = solver.run(
    problem=problem_as_str,
    problem_type="maxcut",
    backend_name=backend_name,  # E.g. "ibm_fez"
)

Verifique o status da carga de trabalho da sua Qiskit Function ou recupere os resultados da seguinte forma:

# Get job status
print(maxcut_job.status())
QUEUED

3. Recuperar o resultado​

Recupere o valor de corte ótimo do dicionário de resultados.

nota
O mapeamento das variáveis para a bitstring pode ter mudado. O dicionário de saída contém um subdicionário variables_to_bitstring_index_map, que ajuda a verificar a ordenação.
# Poll for results
maxcut_result = maxcut_job.result()

# Take the absolute value of the solution since the cost function is minimized
qctrl_maxcut = abs(maxcut_result["solution_bitstring_cost"])

# Print the optimal cut value found by the Optimization Solver
print(f"Optimal cut value: {qctrl_maxcut}")
Optimal cut value: 209.0

Você pode verificar a precisão do resultado resolvendo o problema classicamente com solvers de código aberto como o PuLP, caso o grafo não seja densamente conectado. Problemas de alta densidade podem exigir solvers clássicos avançados para validar a solução.

Exemplo: Otimização com restrições​

O exemplo anterior de Max-Cut é um problema comum de otimização binária quadrática sem restrições. O Optimization Solver do Q-CTRL pode ser usado para diversos tipos de problemas, incluindo otimização com restrições. Você pode resolver tipos de problema arbitrários fornecendo a definição do problema representada como um polinômio em que as restrições são modeladas como termos de penalidade.

O exemplo a seguir demonstra como construir uma função de custo para um problema de otimização com restrições, a cobertura mínima de vértices (MVC). Além dos pacotes qiskit-ibm-catalog e qiskit, você também usará os seguintes pacotes para executar este exemplo: numpy, networkx e sympy. Você pode instalar esses pacotes descomentando a célula a seguir se estiver executando este exemplo em um notebook com o kernel IPython.

# %pip install numpy networkx sympy

1. Definir o problema​

Defina um problema MVC aleatório gerando um grafo com nós ponderados aleatoriamente.

import networkx as nx
from sympy import symbols, Poly, srepr

# To change the weights, change the seed to any integer.
rng_seed = 18
_rng = np.random.default_rng(rng_seed)
node_count = 50
edge_probability = 0.08
mvc_graph = nx.erdos_renyi_graph(
    node_count, edge_probability, seed=rng_seed, directed=False
)

# add node weights
for i in mvc_graph.nodes:
    mvc_graph.add_node(i, weight=_rng.random())

# Optionally, visualize the graph
nx.draw_networkx(mvc_graph, nx.kamada_kawai_layout(mvc_graph), node_size=200)

Saída da célula de código anterior

Um modelo de otimização padrão para MVC ponderado pode ser formulado da seguinte forma. Primeiro, uma penalidade deve ser adicionada para qualquer caso em que uma aresta não esteja conectada a um vértice no subconjunto. Portanto, seja ni=1n_i = 1 se o vértice ii está na cobertura (ou seja, no subconjunto) e ni=0n_i = 0 caso contrário. Em segundo lugar, o objetivo é minimizar o número total de vértices no subconjunto, o que pode ser representado pela seguinte função:

Minimizey=∑i∈Vωini\textbf{Minimize}\qquad y = \sum_{i\in V} \omega_i n_i

# Construct the cost function.
variables = symbols([f"n[{i}]" for i in range(node_count)])
cost_function = Poly(0, variables)

for i in mvc_graph.nodes():
    weight = mvc_graph.nodes[i].get("weight", 0)
    cost_function += variables[i] * weight

Agora, cada aresta no grafo deve incluir pelo menos um ponto de extremidade da cobertura, o que pode ser expresso como a inequação:

ni+nj≥1 for all (i,j)∈En_i + n_j \ge 1 \texttt{ for all } (i,j)\in E

Todo caso em que uma aresta não está conectada ao vértice de cobertura deve ser penalizado. Isso pode ser representado na função de custo adicionando uma penalidade da forma P(1−ni−nj+ninj)P(1-n_i-n_j+n_i n_j), em que PP é uma constante de penalidade positiva. Assim, uma alternativa sem restrições para a inequação restrita para MVC ponderado é:

Minimizey=∑i∈Vωini+P(∑(i,j)∈E(1−ni−nj+ninj))\textbf{Minimize}\qquad y = \sum_{i\in V}\omega_i n_i + P(\sum_{(i,j)\in E}(1 - n_i - n_j + n_i n_j))

# Add penalty term.
penalty_constant = 2
for i, j in mvc_graph.edges():
    cost_function += penalty_constant * (
        1 - variables[i] - variables[j] + variables[i] * variables[j]
    )

2. Executar o problema​

# Solve the problem
mvc_job = solver.run(
    problem=srepr(cost_function),
    backend_name=backend_name,  # E.g. "ibm_fez"
)

Verifique o status da carga de trabalho da sua Qiskit Function ou recupere os resultados da seguinte forma:

print(mvc_job.status())

3. Obter o resultado​

Recupere a solução e analise os resultados. Como este problema tem nós ponderados, a solução não é simplesmente o número mínimo de nós cobertos. Em vez disso, o custo da solução representa a soma dos pesos dos vértices incluídos na cobertura de vértices. Ele representa o "custo" ou "peso" total de cobrir todas as arestas do grafo usando os vértices selecionados.

mvc_result = mvc_job.result()
qctrl_cost = mvc_result["solution_bitstring_cost"]

# Print results
print(f"Solution cost: {qctrl_cost}")
Solution cost: 10.248198273708624

Obter suporte​

Para qualquer dúvida ou problema, entre em contato com o Q-CTRL.

Próximos passos​

Recomendações