Resolva o problema de divisão de mercado com o ParityQC Parity Twine Optimizer

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

Resultados de aprendizagem

Obtenha e formate o problema de divisão de mercado a partir da QOBLIB - Quantum Optimization Benchmarking Library.
Configure e use o Parity Twine Optimizer para resolver uma instância de divisão de mercado.
Aprenda a escolher opções para o Parity Twine Optimizer e quais resultados são gerados.

Contexto

Este tutorial demonstra como resolver o problema de divisão de mercado usando o ParityQC Parity Twine Optimizer.

A instância do problema é obtida da QOBLIB - Quantum Optimization Benchmarking Library.

Problema de divisão de mercado

O problema de divisão de mercado é um problema real de alocação de recursos NP-difícil que se tornou um benchmark para algoritmos de otimização quântica. Ele representa um desafio logístico de alto risco: como particionar um cenário complexo de clientes e produtos em territórios gerenciáveis e equilibrados.

O objetivo é dividir $n$ mercados em duas regiões de vendas equilibradas, de modo que cada região receba exatamente metade da demanda total para $m$ produtos. A solução é a configuração específica que alcança a distribuição mais equilibrada possível da demanda de produtos, permitindo que uma empresa implemente uma estratégia de logística e de pessoal em que ambas as regiões fiquem equilibradas, minimizando riscos como escassez localizada de produtos ou excesso de estoque em armazéns.

À medida que o número de mercados e produtos aumenta, o número de permutações possíveis cresce exponencialmente, tornando desafiador encontrar a melhor divisão usando buscas exaustivas tradicionais.

Formulação matemática

Seja $A$ uma matriz $m \times n$ representando a demanda de produtos entre mercados, onde $A_{ij}$ é a demanda pelo produto $i$ no mercado $j$ .

Um vetor de atribuição binária, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$ , é definido em que:

$x_j = 1$ atribui o mercado $j$ à Região A.
$x_j = 0$ atribui o mercado $j$ à Região B.

Seja $d = [d_1, d_2, \dots, d_m]^T$ o vetor de demanda total para cada produto, calculado como $d = A \cdot \mathbf{1}$ . O volume de vendas-alvo por região para o produto $i$ é exatamente $\frac{d_i}{2}$ .

A restrição de otimização ou viabilidade exige que o total de vendas alocado à Região A corresponda perfeitamente à metade da demanda total de cada produto:

$A x = \frac{1}{2} A \mathbf{1} = b.$

Na prática, como a divisão exata raramente é possível, o problema é formulado para minimizar a violação quadrática da restrição (a função de custo):

$\min_{x} \left\Vert{} A x - b \right\Vert{}^2 = \sum_{i=1}^{m} \left( \sum_{j=1}^{n} A_{ij} x_j - b\right)^2.$

Expandindo isso, obtém-se uma forma equivalente a um problema de otimização binária quadrática irrestrita (QUBO).

Após a resolução, o vetor de solução $x$ determina a qual região cada mercado é atribuído. Essa é a configuração que alcança a distribuição mais equilibrada possível da demanda de produtos.

Requisitos

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

Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)
Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)
NumPy (pip install numpy)

Você também precisa de permissão para acessar a função ParityQC Twine Optimizer. Para solicitar acesso, preencha este formulário.

Configuração

(Este código pressupõe que você já salvou sua conta no seu ambiente local.)

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

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

_needed = {"numpy": "numpy", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_ibm_catalog": "qiskit-ibm-catalog", "requests": "requests"}
_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 tempfile

from collections.abc import Callable
from pathlib import Path

import numpy as np
import requests

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

Carregue o Parity Twine Optimizer do catálogo do Qiskit Functions:

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
function = catalog.load("parityqc/parity-twine-optimizer")

Etapa 1: Defina o problema como uma função objetivo

Obtenha uma instância do problema de divisão de mercado da QOBLIB - Quantum Optimization Benchmarking Library da seguinte forma.

A função load_market_split_problem recupera um determinado problema da QOBLIB e o converte em um problema QUBO.

def load_market_split_problem(instance_name: str) -> OptimizationProblem:
    """Load and formulate a market split optimization problem from an QOBLIB instance.

    The QOBLIB library can be found here:
    https://github.com/ZIB-AOPT/QOBLIB.

    Args:
        instance_name: Name of the market split instance to load as specified by the .dat file
            in the QOBLIB repo.

    Returns:
        The output OptimizationProblem containing the loaded market split problem.
    """

    problem_matrix, problem_vector = fetch_and_parse(
        instance_name, "01-marketsplit", parse_marketsplit_dat
    )

    # Create optimization problem
    optimization_problem = OptimizationProblem(instance_name)

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

    # Add equality constraints (one for each product)
    for idx, rhs in enumerate(problem_vector):
        optimization_problem.linear_constraint(
            problem_matrix[idx, :], sense="==", rhs=rhs
        )

    # Convert to QUBO with penalty parameter
    return OptimizationProblemToQubo(penalty=1).convert(optimization_problem)

A função load_market_split_problem requer as seguintes funções de análise (parser) para recuperar e processar os dados do problema market split da QOBLIB.

def fetch_and_parse(instance_name: str, problem: str, parse_func: Callable):
    """Generic function to fetch and parse data from QOBLIB repository.

    Args:
        instance_name: Name of the instance to fetch.
        problem: Category of the problem (e.g., '01-marketsplit', '07-independentset').
        parse_func: Function used to parse the downloaded file
            (e.g., parse_marketsplit_dat, parse_gph_file).

    Returns:
        Result of `parse_func` - either (np.ndarray, np.ndarray) for marketsplit
        or nx.Graph for MIS.
    """
    base_url = (
        "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/"
    )
    url = (
        base_url
        + problem
        + "/instances/"
        + instance_name
        + (".dat" if problem == "01-marketsplit" else ".gph")
    )

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

        with tempfile.NamedTemporaryFile(
            mode="w",
            suffix=".dat" if problem == "01-marketsplit" else ".gph",
            delete=False,
            encoding="utf-8",
        ) as temp_file:
            temp_file.write(response.text)
            temp_file_path = temp_file.name

        try:
            return parse_func(temp_file_path)
        finally:
            Path(temp_file_path).unlink(missing_ok=True)

    except requests.RequestException as e:
        print(f"Error fetching data from repository: {e}")
    except (ValueError, OSError) as e:
        print(f"Error processing data: {e}")
        return None

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

    Args:
        filename: Path to the .dat file.

    Returns:
        Tuple of (A, b) where:
            - A: (m, n) array of coefficients.
            - b: (m,) array of target values.

    Raises:
        ValueError: If file format is invalid or file is empty.
    """
    with Path(filename).open(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)
    try:
        m, n = map(int, lines[0].split())
    except (ValueError, IndexError) as e:
        raise ValueError(
            "Invalid file format: first line must contain 'm n' integers"
        ) from e

    if len(lines) < m + 1:
        raise ValueError(
            f"File contains {len(lines)} lines but expected {m + 1} lines"
        )

    # Next m lines: each row of A followed by corresponding element of b
    mat_a = []
    vec_b = []

    for i in range(1, m + 1):
        try:
            values = list(map(int, lines[i].split()))
        except ValueError as e:
            raise ValueError(f"Invalid integer values in line {i + 1}") from e

        if len(values) != n + 1:
            raise ValueError(
                f"Line {i + 1} contains {len(values)} values but expected {n + 1}"
            )

        mat_a.append(values[:-1])  # First n values: product sales per market
        vec_b.append(values[-1])  # Last value: target sales for this product

    return np.array(mat_a), np.array(vec_b)

Uma vez definida, load_marketsplit_problem pode ser usada para carregar uma instância específica do problema a partir da biblioteca:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Etapa 2: Converta para o formato JSON

Na primeira etapa, você obteve a forma QUBO do problema. Agora, converta-a para o formato JSON para a função otimizadora:

def optimization_problem_to_json(
    problem: OptimizationProblem,
) -> dict[str, float]:
    """
    Converts an unconstrained quadratic OptimizationProblem in terms of binary or spin variables
    to the JSON input format of the Parity Twine Qiskit Function.

    Args:
        problem: The optimization problem to convert to JSON.

    Returns:
        The JSON input format of the given problem.
    """
    ising, constant = problem.to_ising()
    output = {"()": float(constant)}
    for op, coefficient in zip(ising.paulis, ising.coeffs, strict=True):
        # Invert the label strings because Qiskit has opposite convention
        qubits = tuple(
            num
            for num, pauli in enumerate(op.to_label()[::-1])
            if pauli == "Z"
        )
        output[str(qubits)] = float(coefficient)
    return output

A instância QUBO do problema de divisão de mercado agora está convertida para o formato JSON, da seguinte forma:

json_ms_problem = optimization_problem_to_json(ms_problem)

Etapa 3: Resolva o problema usando o Parity Twine Optimizer

Agora que você obteve o problema market split e o converteu para o formato correto, você pode encontrar uma solução usando o Twine Optimizer e um backend IBM® escolhido.

Para executar a função, escolha um dispositivo backend adequado; por exemplo, ibm_phoenix.

Você pode usar options para (opcionalmente) obter controle adicional sobre a submissão:

options = {
    "shots": 100000,
    "postprocessing_level": 1,
    "transpile_only": False,
    "job_tags": ["market_split"],
}

onde shots é um número inteiro que especifica o número de execuções do circuito, postprocessing_level determina se o pós-processamento é aplicado ao resultado, transpile_only especifica se o problema é apenas transpilado para um circuito (e não resolvido), e job_tags é a etiqueta usada para identificar o job na IBM Quantum® Platform.

Execute o otimizador:

function_job = function.run(
    problem=json_ms_problem,
    variable_type="spin",
    backend_name="ibm_phoenix",
    options=options,
)
print(f"Job ID: {function_job.job_id}")

Verifique o status do job:

# Monitor the job status
function_job.status()

Recupere os resultados:

# Retrieve the job result if the status is DONE
result = function_job.result()

result

O resultado tem o seguinte formato:

{
    'solution': {'0': 1, '1': -1, '10': 1, ... },
    'objective_value':  1.0,
    'solution_bitstring': '010000011101111011001001110010',
    'metadata': {
        'circuit_metrics': {
            'depth': 309,
            'gate_count': 3880,
            'two_qubit_gate_depth': 116,
            'two_qubit_gate_count': 899,
            'num_qubits': 30,
            'operations': {'sx': 1244, 'rz': 1227, 'cz': 899, 'delay': 473, 'measure': 30, 'x': 7},
        },
        'solver_info': {
            'variable_mapping': {'0': 0, '1': 1, '10': 2, ... },
            'bitstring_distributions': {
                'before_postprocessing': {'011101110010110111001110011000': 1, ...},
                'after_postprocessing': {'011011110000110101001111011000': 1, ...}
            },
            'best_parameters': {
                'beta': [-0.18054534155552715],
                'gamma': [1.4141236348317905]
            }
        },
        'resource_usage': {
            'RUNNING: MAPPING': {'CPU_TIME': 172.936},
            'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU_TIME': 0.272},
            'RUNNING: WAITING_FOR_QPU': {'CPU_TIME': 7.798},
            'RUNNING: EXECUTING_QPU': {'QPU_TIME': 30.0},
            'RUNNING: POST_PROCESSING': {'CPU_TIME': 31.613},
        },
    }
}

onde o dicionário solution corresponde aos qubits definidos no problema e fornece seus valores de spin otimizados. metadata fornece informações sobre a transpilação (contagem/profundidade de portas de dois qubits, portas usadas, qubits ativos) e vários tempos de execução.

No contexto do problema market split, a bitstring da solução representa um vetor de atribuição binária usado para dividir os mercados em duas regiões separadas. Um valor de 1 atribui esse mercado específico à Região A, enquanto um valor de 0 o atribui à Região B. Para a solução ótima, a combinação equilibra a divisão, o que significa que ambas as regiões recebem exatamente metade da demanda total da empresa para cada produto.

Próximos passos

Recomendações

Solicite acesso à função preenchendo este formulário.
Visite a referência da API para esta Qiskit Function.
Leia o guia.
Experimente o tutorial para aplicar o Parity Twine Optimizer ao modelo de Sherrington-Kirkpatrick.
Revise o preprint do ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).

Resultados de aprendizagem​

Contexto​

Problema de divisão de mercado​

Formulação matemática​

Requisitos​

Configuração​

Etapa 1: Defina o problema como uma função objetivo​

Etapa 2: Converta para o formato JSON​

Etapa 3: Resolva o problema usando o Parity Twine Optimizer​

Próximos passos​