Resolva o problema de Divisão de Mercado com o Otimizador Quântico Iskay da Kipu Quantum

Nota

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

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

Contexto

Este tutorial demonstra como resolver o problema de Divisão de Mercado usando o otimizador quântico Iskay da Kipu Quantum [1]. O problema de Divisão de Mercado representa um desafio real de alocação de recursos onde os mercados devem ser particionados em regiões de vendas balanceadas para atender metas exatas de demanda.

O desafio da Divisão de Mercado

O problema de Divisão de Mercado apresenta um desafio enganosamente simples, porém computacionalmente formidável, em alocação de recursos. Considere uma empresa com $m$ produtos sendo vendidos em $n$ mercados diferentes, onde cada mercado compra um pacote específico de produtos (representado pelas colunas da matriz $A$). O objetivo de negócio é particionar esses mercados em duas regiões de vendas balanceadas de modo que cada região receba exatamente metade da demanda total de cada produto.

Formulação matemática:

Procuramos um vetor de atribuição binária $x$, onde:

• $x_j = 1$ atribui o mercado $j$ à Região A
• $x_j = 0$ atribui o mercado $j$ à Região B
• A restrição $Ax = b$ deve ser satisfeita, onde $b$ representa as vendas-alvo (tipicamente metade da demanda total por produto)

Função de custo:

Para resolver este problema, minimizamos a violação de restrição ao quadrado:

$C(x) = ||Ax - b||^2 = \sum_{i=1}^{m} \left(\sum_{j=1}^{n} A_{ij}x_j - b_i\right)^2$

onde:

• $A_{ij}$ representa as vendas do produto $i$ no mercado $j$
• $x_j \in \{0,1\}$ é a atribuição binária do mercado $j$
• $b_i$ é a venda-alvo para o produto $i$ em cada região
• O custo é igual a zero precisamente quando todas as restrições são satisfeitas

Cada termo na soma representa o desvio ao quadrado das vendas-alvo para um produto específico. Quando expandimos esta função de custo, obtemos:

$C(x) = x^T A^T A x - 2b^T A x + b^T b$

Como $b^T b$ é uma constante, minimizar $C(x)$ é equivalente a minimizar a função quadrática $x^T A^T A x - 2b^T A x$, que é exatamente um problema QUBO (Otimização Binária Quadrática sem Restrições).

Complexidade computacional:

Apesar de sua interpretação de negócio direta, este problema exibe uma intratabilidade computacional notável:

• Falha em pequena escala: Resolvedores convencionais de Programação Inteira Mista falham em instâncias com apenas sete produtos sob um timeout de uma hora [4]
• Crescimento exponencial: O espaço de soluções cresce exponencialmente ($2^n$ atribuições possíveis), tornando abordagens de força bruta inviáveis

Esta severa barreira computacional, combinada com sua relevância prática para planejamento de território e alocação de recursos, torna o problema de Divisão de Mercado um benchmark ideal para algoritmos de otimização quântica [4].

O que torna a abordagem do Iskay única?

O otimizador Iskay usa o algoritmo bf-DCQO (otimização quântica contradiabática digitalizada com campo de viés) [1], que representa um avanço significativo em otimização quântica:

Eficiência de circuito: O algoritmo bf-DCQO alcança uma redução notável de portas [1]:

• Até 10 vezes menos portas entrelaçadas do que o Recozimento Quântico Digital (DQA)
• Circuitos significativamente mais rasos possibilitam:
  • Menos acúmulo de erros durante a execução quântica
  • Capacidade de lidar com problemas maiores no hardware quântico atual
  • Sem necessidade de técnicas de mitigação de erros

Design não-variacional: Ao contrário de algoritmos variacionais que requerem aproximadamente 100 iterações, o bf-DCQO tipicamente precisa de apenas aproximadamente 10 iterações [1]. Isto é alcançado através de:

• Cálculos inteligentes de campo de viés a partir de distribuições de estado medidas
• Início de cada iteração a partir de um estado de energia próximo à solução anterior
• Pós-processamento clássico integrado com busca local

Protocolos contradiabáticos: O algoritmo incorpora termos contradiabáticos que suprimem excitações quânticas indesejadas durante tempos curtos de evolução, permitindo que o sistema permaneça próximo ao estado fundamental mesmo com transições rápidas [1].

Requisitos

Antes de iniciar este tutorial, certifique-se de ter o seguinte instalado:

• Qiskit IBM Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions (pip install qiskit-ibm-catalog)
• NumPy (pip install numpy)
• Requests (pip install requests)
• Opt Mapper Qiskit addon (pip install qiskit-addon-opt-mapper)

Você também precisará obter acesso à função Iskay Quantum Optimizer do Catálogo de Funções Qiskit.

Configuração

Primeiro, importe todos os pacotes necessários para este tutorial.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit-addon-opt-mapper qiskit-ibm-catalog requests

import os
import tempfile
import time
from typing import Tuple, Optional

import numpy as np
import requests

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo

print("All required libraries imported successfully")

Configure as credenciais do IBM Quantum

Defina suas credenciais da Plataforma IBM Quantum®. Você precisará de:

• Token da API: Sua chave de API de 44 caracteres da Plataforma IBM Quantum
• CRN da Instância: Seu identificador de instância do IBM Cloud®

token = "<YOUR_API_KEY>"
instance = "<YOUR_INSTANCE_CRN>"

Passo 1: Mapeie entradas clássicas para um problema quântico

Começamos mapeando nosso problema clássico para uma representação compatível com quântica. Este passo envolve:

1. Conectar ao Otimizador Quântico Iskay
2. Carregar e formular o problema de Divisão de Mercado
3. Compreender o algoritmo bf-DCQO que irá resolvê-lo

Conecte ao Otimizador Quântico Iskay

Começamos estabelecendo uma conexão com o Catálogo de Funções Qiskit e carregando o Otimizador Quântico Iskay. O Otimizador Iskay é uma função quântica fornecida pela Kipu Quantum que implementa o algoritmo bf-DCQO para resolver problemas de otimização em hardware quântico.

catalog = QiskitFunctionsCatalog(token=token, instance=instance)
iskay_solver = catalog.load("kipu-quantum/iskay-quantum-optimizer")

print("Iskay optimizer loaded successfully")
print("Ready to solve optimization problems using bf-DCQO algorithm")

Carregue e formule o problema

Compreenda o formato dos dados do problema

Instâncias de problema do QOBLIB (Biblioteca de Benchmarking de Otimização Quântica) [2] são armazenadas em um formato de texto simples. Vamos examinar o conteúdo real de nossa instância-alvo ms_03_200_177.dat:

3 20
60   92  161   53   97    2   75   81    6  139  132   45  108  112  181   93  152  200  164   51 1002
176  196   41  143    2   88    0   79   10   71   75  148   82  135   34  187   33  155   58   46  879
68   68  179  173  127  163   48   49   99   78   44   52  173  131   73  198   84  109  180   95 1040

Estrutura do formato:

• Primeira linha: 3 20

  • 3 = número de produtos (restrições/linhas na matriz $A$)
  • 20 = número de mercados (variáveis/colunas na matriz $A$)

• Próximas 3 linhas: Matriz de coeficientes $A$ e vetor-alvo $b$

  • Cada linha tem 21 números: os primeiros 20 são coeficientes da linha, o último é o alvo
  • Linha 2: 60 92 161 ... 51 | 1002
    • Primeiros 20 números: Quanto do Produto 1 cada um dos 20 mercados vende
    • Último número (1002): Vendas-alvo para o Produto 1 em uma região
  • Linha 3: 176 196 41 ... 46 | 879
    • Vendas do Produto 2 por mercado e alvo (879)
  • Linha 4: 68 68 179 ... 95 | 1040
    • Vendas do Produto 3 por mercado e alvo (1040)

Interpretação de negócio:

• Mercado 0 vende: 60 unidades do Produto 1, 176 unidades do Produto 2, 68 unidades do Produto 3
• Mercado 1 vende: 92 unidades do Produto 1, 196 unidades do Produto 2, 68 unidades do Produto 3
• E assim por diante para todos os 20 mercados...
• Objetivo: Dividir esses 20 mercados em duas regiões onde cada região receba exatamente 1002 unidades do Produto 1, 879 unidades do Produto 2 e 1040 unidades do Produto 3

Transformação QUBO

Das restrições ao QUBO: a transformação matemática

O poder da otimização quântica reside em transformar problemas restritos em formas quadráticas sem restrições [4]. Para o problema de Divisão de Mercado, convertemos as restrições de igualdade

$Ax = b$

onde $x ∈ \{0,1\}^n$, em um QUBO penalizando violações de restrições.

O método de penalidade: Como precisamos que $Ax = b$ se mantenha exatamente, minimizamos a violação ao quadrado: $f(x) = ||Ax - b||^2$

Isto é igual a zero precisamente quando todas as restrições são satisfeitas. Expandindo algebricamente: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Objetivo QUBO: Como $b^T b$ é constante, nossa otimização se torna: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Insight-chave: Esta transformação é exata, não aproximada. Restrições de igualdade naturalmente se elevam ao quadrado em forma quadrática sem exigir variáveis auxiliares ou parâmetros de penalidade - tornando esta formulação matematicamente elegante e computacionalmente eficiente para resolvedores quânticos [4]. Usaremos a classe OptimizationProblem para definir nosso problema restrito, depois o converteremos para o formato QUBO usando OptimizationProblemToQubo, ambos do pacote qiskit_addon_opt_mapper. Isso lida automaticamente com a transformação baseada em penalidade.

Implemente funções de carregamento de dados e conversão QUBO

Agora definimos três funções utilitárias:

1. parse_marketsplit_dat() - Analisa o formato de arquivo .dat e extrai as matrizes $A$ e $b$
2. fetch_marketsplit_data() - Baixa instâncias de problema diretamente do repositório QOBLIB

def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:
    """
    Parse a market split problem from a .dat file format.

    Parameters
    ----------
    filename : str
        Path to the .dat file containing the market split problem data.

    Returns
    -------
    A : np.ndarray
        Coefficient matrix of shape (m, n) where m is the number of products
        and n is the number of markets.
    b : np.ndarray
        Target vector of shape (m,) containing the target sales per product.
    """
    with open(filename, "r", encoding="utf-8") as f:
        lines = [
            line.strip()
            for line in f
            if line.strip() and not line.startswith("#")
        ]

    if not lines:
        raise ValueError("Empty or invalid .dat file")

    # First line: m n (number of products and markets)
    m, n = map(int, lines[0].split())

    # Next m lines: each row of A followed by corresponding element of b
    A, b = [], []
    for i in range(1, m + 1):
        values = list(map(int, lines[i].split()))
        A.append(values[:-1])  # First n values: product sales per market
        b.append(values[-1])  # Last value: target sales for this product

    return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)

def fetch_marketsplit_data(
    instance_name: str = "ms_03_200_177.dat",
) -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:
    """
    Fetch market split data directly from the QOBLIB repository.

    Parameters
    ----------
    instance_name : str
        Name of the .dat file to fetch (default: "ms_03_200_177.dat").

    Returns
    -------
    A : np.ndarray or None
        Coefficient matrix if successful, None if failed.
    b : np.ndarray or None
        Target vector if successful, None if failed.
    """
    url = f"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}"

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w", suffix=".dat", delete=False, encoding="utf-8"
        ) as f:
            f.write(response.text)
            temp_path = f.name

        try:
            return parse_marketsplit_dat(temp_path)
        finally:
            os.unlink(temp_path)
    except Exception as e:
        print(f"Error: {e}")
        return None, None

Carregue a instância do problema

Agora carregamos a instância específica do problema ms_03_200_177.dat do QOBLIB [2]. Esta instância tem:

• 3 produtos (restrições)
• 20 mercados (variáveis de decisão binárias)
• Mais de 1 milhão de atribuições de mercado possíveis para explorar ($2^{20} = 1.048.576$)

# Load the problem instance
instance_name = "ms_03_200_177.dat"
A, b = fetch_marketsplit_data(instance_name=instance_name)

if A is not None:
    print("Successfully loaded problem instance from QOBLIB")
    print("\nProblem Instance Analysis:")
    print("=" * 50)
    print(f"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}")
    print(f"   → {A.shape[0]} products (constraints)")
    print(f"   → {A.shape[1]} markets (decision variables)")
    print(f"Target Vector b: {b}")
    print("   → Target sales per product for each region")
    print(
        f"Solution Space: 2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

Converta para o formato QUBO

Agora transformamos o problema de otimização restrito em formato QUBO:

# Create optimization problem
ms = OptimizationProblem(instance_name.replace(".dat", ""))

# Add binary variables (one for each market)
ms.binary_var_list(A.shape[1])

# Add equality constraints (one for each product)
for idx, rhs in enumerate(b):
    ms.linear_constraint(A[idx, :], sense="==", rhs=rhs)

# Convert to QUBO with penalty parameter
qubo = OptimizationProblemToQubo(penalty=1).convert(ms)

print("QUBO Conversion Complete:")
print("=" * 50)
print(f"Number of variables: {qubo.get_num_vars()}")
print(f"Constant term: {qubo.objective.constant}")
print(f"Linear terms: {len(qubo.objective.linear.to_dict())}")
print(f"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}")

Converta QUBO para o formato Iskay

Agora precisamos converter o objeto QUBO para o formato de dicionário requerido pelo Otimizador Iskay da Kipu Quantum.

Os argumentos problem e problem_type codificam um problema de otimização da forma

$$\begin{align} \min_{(x_1, x_2, \ldots, x_n) \in D} C(x_1, x_2, \ldots, x_n) \nonumber \end{align}$$

onde

$$C(x_1, ... , x_n) = a + \sum_{i} b_i x_i + \sum_{i, j} c_{i, j} x_i x_j + ... + \sum_{k_1, ..., k_m} g_{k_1, ..., k_m} x_{k_1} ... x_{k_m}$$

• Ao escolher problem_type = "binary", você especifica que a função de custo está no formato binary, o que significa que $D = \{0, 1\}^{n}$, ou seja, a função de custo é escrita na formulação QUBO/HUBO.
• Por outro lado, ao escolher problem_type = "spin", a função de custo é escrita na formulação Ising, onde $D = \{-1, 1\}^{n}$.

Os coeficientes do problema devem ser codificados em um dicionário da seguinte forma:

$$\begin{align} \nonumber &\texttt{\{} \\ \nonumber &\texttt{"()"}&: \quad &a, \\ \nonumber &\texttt{"(i,)"}&: \quad &b_i, \\ \nonumber &\texttt{"(i, j)"}&: \quad &c_{i, j}, \quad (i \neq j) \\ \nonumber &\quad \vdots \\ \nonumber &\texttt{"(} k_1, ..., k_m \texttt{)"}&: \quad &g_{k_1, ..., k_m}, \quad (k_1 \neq k_2 \neq \dots \neq k_m) \\ \nonumber &\texttt{\}} \end{align}$$

Note que as chaves do dicionário devem ser strings contendo uma tupla válida de inteiros não repetidos. Para problemas binários, sabemos que:

$$x_i^2 = x_i$$

para $i=j$ (já que $x_i \in \{0,1\}$ significa $x_i \cdot x_i = x_i$). Então, em sua formulação QUBO, se você tem tanto contribuições lineares $b_i x_i$ quanto contribuições quadráticas diagonais $c_{i,i} x_i^2$, esses termos devem ser combinados em um único coeficiente linear:

Coeficiente linear total para a variável $x_i$: $b_i + c_{i,i}$

Isso significa:

• Termos lineares como "(i, )" contêm: coeficiente linear original + coeficiente quadrático diagonal
• Termos quadráticos diagonais como "(i, i)" NÃO devem aparecer no dicionário final
• Apenas termos quadráticos fora da diagonal como "(i, j)" onde $i \neq j$ devem ser incluídos como entradas separadas

Exemplo: Se seu QUBO tem $3x_1 + 2x_1^2 + 4x_1 x_2$, o dicionário Iskay deve conter:

• "(0, )": 5.0 (combinando $3 + 2 = 5$)
• "(0, 1)": 4.0 (termo fora da diagonal)

NÃO entradas separadas para "(0, )": 3.0 e "(0, 0)": 2.0.

# Convert QUBO to Iskay dictionary format:

# Create empty Iskay input dictionary
iskay_input_problem = {}

# Convert QUBO to Iskay dictionary format
iskay_input_problem = {"()": qubo.objective.constant}

for i in range(qubo.get_num_vars()):
    for j in range(i, qubo.get_num_vars()):
        if i == j:
            # Add linear term (including diagonal quadratic contribution)
            iskay_input_problem[f"({i}, )"] = float(
                qubo.objective.linear.to_dict().get(i)
            ) + float(qubo.objective.quadratic.to_dict().get((i, i)))
        else:
            # Add off-diagonal quadratic term
            iskay_input_problem[f"({i}, {j})"] = float(
                qubo.objective.quadratic.to_dict().get((i, j))
            )

# Display Iskay dictionary summary
print("Iskay Dictionary Format:")
print("=" * 50)
print(f"Total coefficients: {len(iskay_input_problem)}")
print(f"  • Constant term: {iskay_input_problem['()']}")
print(
    f"  • Linear terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}"
)
print("\nSample coefficients:")

# Get first 10 and last 5 items properly
items = list(iskay_input_problem.items())
first_10 = list(enumerate(items[:10]))
last_5 = list(enumerate(items[-5:], start=len(items) - 5))

for i, (key, value) in first_10 + last_5:
    coeff_type = (
        "constant"
        if key == "()"
        else "linear"
        if ", )" in key
        else "quadratic"
    )
    print(f"  {key}: {value} ({coeff_type})")
print("  ...")
print("\n✓ Problem ready for Iskay optimizer!")

Entenda o algoritmo bf-DCQO

Antes de executarmos a otimização, vamos entender o sofisticado algoritmo quântico que alimenta o Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

O que é bf-DCQO?

O bf-DCQO é baseado na evolução temporal de um sistema quântico onde a solução do problema é codificada no estado fundamental (estado de menor energia) do Hamiltoniano quântico final [1]. O algoritmo aborda um desafio fundamental na otimização quântica:

O desafio: A computação quântica adiabática tradicional requer evolução muito lenta para manter as condições do estado fundamental de acordo com o teorema adiabático. Isso exige circuitos quânticos cada vez mais profundos conforme a complexidade do problema cresce, levando a mais operações de portas e acúmulo de erros.

A solução: O bf-DCQO usa protocolos contradiabáticos para permitir evolução rápida enquanto mantém a fidelidade do estado fundamental, reduzindo drasticamente a profundidade do circuito.

Estrutura matemática

O algoritmo minimiza uma função de custo da forma:

$\min_{(x_1,x_2,...,x_n) \in D} C(x_1,x_2,...,x_n)$

onde $D = \{0,1\}^n$ para variáveis binárias e:

$C(x) = a + \sum_i b_i x_i + \sum_{i,j} c_{ij} x_i x_j + ... + \sum g_{k_1,...,k_m} x_{k_1}...x_{k_m}$

Para nosso problema de Market Split, a função de custo é:

$C(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b$

O papel dos termos contradiabáticos

Termos contradiabáticos são termos adicionais introduzidos no Hamiltoniano dependente do tempo que suprimem excitações indesejadas durante a evolução quântica. Aqui está o motivo pelo qual eles são cruciais:

Na otimização quântica adiabática, evoluímos o sistema de acordo com um Hamiltoniano dependente do tempo:

$H(t) = \left(1 - \frac{t}{T}\right) H_{\text{initial}} + \frac{t}{T} H_{\text{problem}}$

onde $H_{\text{problem}}$ codifica nosso problema de otimização. Para manter o estado fundamental durante a evolução rápida, adicionamos termos contradiabáticos:

$H_{\text{CD}}(t) = H(t) + H_{\text{counter}}(t)$

Esses termos contradiabáticos fazem o seguinte:

1. Suprimem transições indesejadas: Impedem que o estado quântico salte para estados excitados durante a evolução rápida
2. Permitem tempos de evolução mais curtos: Nos permitem alcançar o estado final muito mais rápido sem violar a adiabaticidade
3. Reduzem a profundidade do circuito: Evolução mais curta leva a menos portas e menos erro

O impacto prático é dramático: o bf-DCQO usa até 10 vezes menos portas de emaranhamento do que o Digital Quantum Annealing [1], tornando-o prático para o hardware quântico ruidoso de hoje.

Otimização iterativa por campo de viés

Ao contrário de algoritmos variacionais que otimizam parâmetros de circuito através de muitas iterações, o bf-DCQO usa uma abordagem guiada por campo de viés que converge em aproximadamente 10 iterações [1]:

Processo iterativo:

1. Evolução quântica inicial: Começar com um circuito quântico implementando o protocolo de evolução contradiabático

2. Medição: Medir o estado quântico para obter uma distribuição de probabilidade sobre bitstrings

3. Cálculo do campo de viés: Analisar as estatísticas de medição e calcular um campo de viés ideal $h_i$ para cada qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Próxima iteração: O campo de viés modifica o Hamiltoniano para a próxima iteração: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Isso permite começar perto da solução boa encontrada anteriormente, efetivamente realizando uma forma de "busca local quântica"

5. Convergência: Repetir até que a qualidade da solução se estabilize ou um número máximo de iterações seja alcançado

Vantagem chave: Cada iteração fornece progresso significativo em direção à solução ideal ao incorporar informações de medições anteriores, ao contrário de métodos variacionais que devem explorar o espaço de parâmetros cegamente.

Pós-processamento clássico integrado

Após a convergência da otimização quântica, o Iskay realiza pós-processamento clássico de busca local:

• Exploração de inversão de bits: Inverter sistematicamente ou aleatoriamente bits na melhor solução medida
• Avaliação de energia: Calcular $C(x)$ para cada solução modificada
• Seleção gulosa: Aceitar melhorias que reduzam a função de custo
• Múltiplas passagens: Realizar várias passagens (controladas por postprocessing_level)

Essa abordagem híbrida compensa erros de inversão de bits de imperfeições de hardware e erros de leitura, garantindo soluções de alta qualidade mesmo em dispositivos quânticos ruidosos.

Por que o bf-DCQO se destaca no hardware atual

O algoritmo bf-DCQO é especificamente projetado para se destacar nos dispositivos quânticos de escala intermediária ruidosa (NISQ) de hoje [1]:

1. Resiliência a erros: Menos portas (redução de 10 vezes) significa acúmulo de erro dramaticamente menor
2. Não requer mitigação de erro: A eficiência inerente do algoritmo elimina a necessidade de técnicas caras de mitigação de erro [1]
3. Escalabilidade: Pode lidar com problemas de até 156 qubits (156 variáveis binárias) com mapeamento direto de qubits [1]
4. Desempenho comprovado: Atinge razões de aproximação de 100% em instâncias de benchmark MaxCut e HUBO [1]

Agora vamos ver esse poderoso algoritmo em ação no nosso problema de Market Split!

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

O algoritmo bf-DCQO lida automaticamente com a otimização de circuito, criando circuitos quânticos rasos com termos contradiabáticos especificamente projetados para o backend alvo.

Configure a otimização

O Iskay Optimizer requer vários parâmetros-chave para resolver efetivamente seu problema de otimização. Vamos examinar cada parâmetro e seu papel no processo de otimização quântica:

Parâmetros obrigatórios

Parâmetro	Tipo	Descrição	Exemplo
problem	Dict[str, float]	Coeficientes QUBO no formato de chave de string	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Especificação de formato: "binary" para QUBO ou "spin" para Ising	"binary"
backend_name	str	Dispositivo quântico alvo	"ibm_fez"

Conceitos essenciais

• Formato do problema: Usamos "binary" já que nossas variáveis são binárias (0/1), representando atribuições de mercado.
• Seleção de backend: Escolher entre as QPUs disponíveis (por exemplo, "ibm_fez") com base em suas necessidades e instância de recurso de computação.
• Estrutura QUBO: Nosso dicionário de problema contém os coeficientes exatos da transformação matemática.

Opções avançadas (opcional)

O Iskay fornece capacidades de ajuste fino através de parâmetros opcionais. Embora os padrões funcionem bem para a maioria dos problemas, você pode personalizar o comportamento para requisitos específicos:

Parâmetro	Tipo	Padrão	Descrição
shots	int	10000	Medições quânticas por iteração (maior = mais preciso)
num_iterations	int	10	Iterações do algoritmo (mais iterações podem melhorar a qualidade da solução)
use_session	bool	True	Usar sessões IBM para tempos de fila reduzidos
seed_transpiler	int	None	Definir para compilação de circuito quântico reproduzível
direct_qubit_mapping	bool	False	Mapear qubits virtuais diretamente para qubits físicos
job_tags	List[str]	None	Tags personalizadas para rastreamento de trabalho
preprocessing_level	int	0	Intensidade de pré-processamento do problema (0-3) - veja detalhes abaixo
postprocessing_level	int	2	Nível de refinamento da solução (0-2) - veja detalhes abaixo
transpilation_level	int	0	Tentativas de otimização do transpilador (0-5) - veja detalhes abaixo
transpile_only	bool	False	Analisar otimização de circuito sem executar a execução completa

Níveis de pré-processamento (0-3): Especialmente importante para problemas maiores que atualmente não cabem nos tempos de coerência do hardware. Níveis mais altos de pré-processamento alcançam profundidades de circuito mais rasas por aproximações na transpilação do problema:

• Nível 0: Exato, circuitos mais longos
• Nível 1: Bom equilíbrio entre precisão e aproximação, cortando apenas as portas com ângulos no percentil mais baixo de 10
• Nível 2: Aproximação ligeiramente maior, cortando as portas com ângulos no percentil mais baixo de 20 e usando approximation_degree=0.95 na transpilação
• Nível 3: Nível máximo de aproximação, cortando as portas no percentil mais baixo de 30 e usando approximation_degree=0.90 na transpilação

Níveis de transpilação (0-5): Controlam as tentativas avançadas de otimização do transpilador para compilação de circuito quântico. Isso pode levar a um aumento na sobrecarga clássica, e para alguns casos pode não alterar a profundidade do circuito. O valor padrão 2 em geral leva ao menor circuito e é relativamente rápido.

• Nível 0: Otimização do circuito DCQO decomposto (layout, roteamento, agendamento)
• Nível 1: Otimização de PauliEvolutionGate e depois o circuito DCQO decomposto (max_trials=10)
• Nível 2: Otimização de PauliEvolutionGate e depois o circuito DCQO decomposto (max_trials=15)
• Nível 3: Otimização de PauliEvolutionGate e depois o circuito DCQO decomposto (max_trials=20)
• Nível 4: Otimização de PauliEvolutionGate e depois o circuito DCQO decomposto (max_trials=25)
• Nível 5: Otimização de PauliEvolutionGate e depois o circuito DCQO decomposto (max_trials=50)

Níveis de pós-processamento (0-2): Controlam quanto de otimização clássica, compensando erros de inversão de bits com número diferente de passagens gulosas de uma busca local:

• Nível 0: 1 passagem
• Nível 1: 2 passagens
• Nível 2: 3 passagens

Modo transpile-only: Agora disponível para usuários que desejam analisar a otimização de circuito sem executar a execução completa do algoritmo quântico.

Exemplo de configuração personalizada

Veja como você pode configurar o Iskay com diferentes configurações:

custom_options = {
    "shots": 15_000,                                        # Higher shot count for better statistics
    "num_iterations": 12,                                   # More iterations for solution refinement
    "preprocessing_level": 1,                               # Light preprocessing for problem simplification
    "postprocessing_level": 2,                              # Maximum postprocessing for solution quality
    "transpilation_level": 3,                               # Using higher transpilation level for circuit optimization
    "seed_transpiler": 42,                                  # Fixed seed for reproducible results
    "job_tags": ["market_split"]                            # Custom tracking tags
}

Para este tutorial, manteremos a maioria dos parâmetros padrão e apenas alteraremos o número de iterações de campo de viés:

# Specify the target backend
backend_name = "ibm_fez"

# Set the number of bias-field iterations and set a tag to identify the jobs
options = {
    "num_iterations": 3,  # Change number of bias-field iterations
    "job_tags": ["market_split_example"],  # Tag to identify jobs
}

# Configure Iskay optimizer
iskay_input = {
    "problem": iskay_input_problem,
    "problem_type": "binary",
    "backend_name": backend_name,
    "options": options,
}

print("Iskay Optimizer Configuration:")
print("=" * 40)
print(f"  Backend: {backend_name}")
print(f"  Problem: {len(iskay_input['problem'])} terms")
print("  Algorithm: bf-DCQO")

Passo 3: Executar usando primitivas Qiskit

Agora enviamos nosso problema para executar no hardware IBM Quantum. O algoritmo bf-DCQO irá:

1. Construir circuitos quânticos rasos com termos contradiabáticos
2. Executar aproximadamente 10 iterações com otimização de campo de viés
3. Realizar pós-processamento clássico com busca local
4. Retornar a atribuição ideal de mercado

# Submit the optimization job
print("Submitting optimization job to Kipu Quantum...")
print(
    f"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms"
)
print(
    "Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)"
)

job = iskay_solver.run(**iskay_input)

print("\nJob successfully submitted!")
print(f"Job ID: {job.job_id}")
print("Optimization in progress...")
print(
    f"The bf-DCQO algorithm will efficiently explore {2**A.shape[1]:,} possible assignments"
)

Monitorar status do trabalho

Você pode verificar o status atual do seu trabalho de otimização. Os possíveis status são:

• QUEUED: Trabalho está aguardando na fila
• RUNNING: Trabalho está sendo executado no hardware quântico
• DONE: Trabalho concluído com sucesso
• CANCELED: Trabalho foi cancelado
• ERROR: Trabalho encontrou um erro

# Check job status
print(f"Job status: {job.status()}")

Aguardar conclusão

Esta célula bloqueará até que o trabalho seja concluído. O processo de otimização inclui:

• Tempo de fila (aguardando acesso ao hardware quântico)
• Tempo de execução (executando o algoritmo bf-DCQO com aproximadamente 10 iterações)
• Tempo de pós-processamento (busca local clássica)

Tempos de conclusão típicos variam de alguns minutos a dezenas de minutos dependendo das condições da fila.

# Wait for job completion
while True:
    status = job.status()
    print(
        f"Waiting for job {job.job_id} to complete... (status: {status})",
        end="\r",
        flush=True,
    )
    if status in ["DONE", "CANCELED", "ERROR"]:
        print(
            f"\nJob {job.job_id} completed with status: {status}" + " " * 20
        )
        break
    time.sleep(30)

# Retrieve the optimization results
result = job.result()
print("\nOptimization complete!")

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

Agora pós-processamos os resultados da execução quântica. Isso inclui:

• Analisar a estrutura da solução
• Validar a satisfação de restrições
• Fazer benchmark contra abordagens clássicas

Analisar resultados

Entenda a estrutura do resultado

O Iskay retorna um dicionário de resultado abrangente contendo:

• solution: Um dicionário mapeando índices de variáveis para seus valores ideais (0 ou 1)
• solution_info: Informações detalhadas incluindo:
  • bitstring: A atribuição ideal como uma string binária
  • cost: O valor da função objetivo (deve ser 0 para satisfação perfeita de restrição)
  • mapping: Como as posições da bitstring mapeiam para variáveis do problema
  • seed_transpiler: Semente usada para reprodutibilidade
• prob_type: Se a solução está em formato binário ou spin

Vamos examinar a solução retornada pelo otimizador quântico.

# Display the optimization results
print("Optimization Results")
print("=" * 50)
print(f"Problem Type: {result['prob_type']}")
print("\nSolution Info:")
print(f"  Bitstring: {result['solution_info']['bitstring']}")
print(f"  Cost: {result['solution_info']['cost']}")
print("\nSolution (first 10 variables):")
for i, (var, val) in enumerate(list(result["solution"].items())[:10]):
    print(f"  {var}: {val}")
print("  ...")

Validação da solução

Agora validamos se a solução quântica satisfaz as restrições de Market Split. O processo de validação verifica:

O que é uma violação de restrição?

• Para cada produto $i$, calculamos as vendas reais na Região A: $(Ax)_i$
• Comparamos isso com as vendas alvo $b_i$
• A violação é a diferença absoluta: $|(Ax)_i - b_i|$
• Uma solução viável tem violações zero para todos os produtos

O que esperamos:

• Caso ideal: Violação total = 0 (todas as restrições perfeitamente satisfeitas)
  • Região A recebe exatamente 1002 unidades do Produto 1, 879 unidades do Produto 2 e 1040 unidades do Produto 3
  • Região B recebe as unidades restantes (também 1002, 879 e 1040 respectivamente)
• Caso bom: Violação total é pequena (solução quase ideal)
• Caso ruim: Grandes violações indicam que a solução não satisfaz os requisitos de negócio

A função de validação calculará:

1. Vendas reais por produto em cada região
2. Violações de restrição para cada produto
3. Distribuição de mercado entre regiões

def validate_solution(A, b, solution):
    """Validate market split solution."""
    x = np.array(solution)
    region_a = A @ x
    region_b = A @ (1 - x)
    violations = np.abs(region_a - b)

    return {
        "target": b,
        "region_a": region_a,
        "region_b": region_b,
        "violations": violations,
        "total_violation": np.sum(violations),
        "is_feasible": np.sum(violations) == 0,
        "region_a_markets": int(np.sum(x)),
        "region_b_markets": len(x) - int(np.sum(x)),
    }

# Convert bitstring to list of integers and validate
optimal_assignment = [
    int(bit) for bit in result["solution_info"]["bitstring"]
]
validation = validate_solution(A, b, optimal_assignment)

Interpretar os resultados da validação

Os resultados da validação mostram se o Quantum Optimizer encontrou uma solução viável. Vamos examinar o seguinte:

Verificação de viabilidade:

• is_feasible = True significa que a solução satisfaz perfeitamente todas as restrições (violação total = 0)
• is_feasible = False significa que algumas restrições são violadas

Análise de vendas:

• Comparar vendas Alvo versus Reais para cada produto
• Para uma solução perfeita: Real = Alvo para todos os produtos em ambas as regiões
• A diferença indica quão perto estamos da divisão de mercado desejada

Distribuição de mercado:

• Mostra quantos mercados são atribuídos a cada região
• Não há exigência de números iguais de mercados, apenas que as metas de vendas sejam atendidas

print("Solution Validation")
print("=" * 50)
print(f"Feasible solution: {validation['is_feasible']}")
print(f"Total constraint violation: {validation['total_violation']}")

print("\nSales Analysis (Target vs Actual):")
for i, (target, actual_a, actual_b) in enumerate(
    zip(validation["target"], validation["region_a"], validation["region_b"])
):
    violation_a = abs(actual_a - target)
    violation_b = abs(actual_b - target)
    print(f"  Product {i+1}:")
    print(f"    Target: {target}")
    print(f"    Region A: {actual_a} (violation: {violation_a})")
    print(f"    Region B: {actual_b} (violation: {violation_b})")

print("\nMarket Distribution:")
print(f"  Region A: {validation['region_a_markets']} markets")
print(f"  Region B: {validation['region_b_markets']} markets")

Avaliação da qualidade da solução

Com base nos resultados de validação acima, podemos avaliar a qualidade da solução quântica:

Se is_feasible = True (Violação total = 0):

• O Quantum Optimizer encontrou com sucesso uma solução ideal
• Todas as restrições de negócio são perfeitamente satisfeitas
• Isso demonstra vantagem quântica em um problema onde solucionadores clássicos têm dificuldade [4]

Se is_feasible = False (Violação total > 0):

• A solução é quase ideal, mas não perfeita
• Pequenas violações podem ser aceitáveis na prática
• Considere ajustar os parâmetros do otimizador:
  • Aumentar num_iterations para mais passagens de otimização
  • Aumentar postprocessing_level para mais refinamento clássico
  • Aumentar shots para melhores estatísticas de medição

Interpretação da função de custo:

• O valor de cost de solution_info é igual a $||Ax - b||^2$
• Custo = 0 indica satisfação perfeita de restrição
• Valores de custo mais altos indicam maiores violações de restrição

Conclusão

O que realizamos

Neste tutorial, obtivemos sucesso em:

1. Carregar um problema de otimização real: Obtivemos uma instância desafiadora de Market Split da biblioteca de benchmark QOBLIB [2]
2. Transformar para formato QUBO: Convertemos o problema restrito em uma formulação quadrática irrestrita [3]
3. Aproveitar algoritmos quânticos avançados: Usamos o algoritmo bf-DCQO da Kipu Quantum com termos contradiabáticos [1]
4. Obter soluções ideais: Encontramos soluções viáveis satisfazendo todas as restrições

Principais conclusões

Inovação algorítmica: O algoritmo bf-DCQO representa um avanço significativo [1]:

• 10 vezes menos portas do que o annealing quântico digital
• Aproximadamente 10 iterações em vez de aproximadamente 100 para métodos variacionais
• Resiliência a erros incorporada através da eficiência do circuito

Termos contradiabáticos: Permitem evolução quântica rápida enquanto mantêm a fidelidade do estado fundamental, tornando a otimização quântica prática no hardware ruidoso de hoje [1].

Orientação por campo de viés: A abordagem iterativa de campo de viés permite que cada iteração comece perto de soluções boas encontradas anteriormente, fornecendo uma forma de busca local aprimorada quanticamente [1].

Próximos passos

Para aprofundar seu entendimento e explorar mais:

1. Experimentar diferentes instâncias: Experimentar com outras instâncias QOBLIB de tamanhos variados
2. Ajustar parâmetros: Ajustar num_iterations, preprocessing_level, postprocessing_level
3. Comparar com clássico: Fazer benchmark contra solucionadores de otimização clássicos
4. Experimentar diferentes estratégias: Tentar encontrar uma melhor codificação para o problema ou formulá-lo como HUBO (se possível)
5. Aplicar ao seu domínio: Adaptar as técnicas de formulação QUBO/HUBO aos seus próprios problemas de otimização

References

[1] IBM Quantum. "Kipu Quantum Optimization." IBM Quantum Documentation.

[2] QOBLIB - Quantum Optimization Benchmarking Library. Zuse Institute Berlin (ZIB). https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library

[3] Glover, F., Kochenberger, G., & Du, Y. (2019). "Quantum bridge analytics I: a tutorial on formulating and using QUBO models." 4OR: A Quarterly Journal of Operations Research, 17(4), 335-371.