แก้ปัญหา market split ด้วย ParityQC Parity Twine Optimizer

ประมาณเวลาที่ใช้: 10 วินาที บนโปรเซสเซอร์ Nighthawk r2 (หมายเหตุ: นี่เป็นเพียงการประมาณการเท่านั้น เวลาการทำงานจริงของคุณอาจแตกต่างกันไป)

ผลลัพธ์การเรียนรู้

• ดึงและจัดรูปแบบปัญหา Market Split จาก QOBLIB - Quantum Optimization Benchmarking Library

• ตั้งค่าและใช้งาน Parity Twine Optimizer เพื่อแก้อินสแตนซ์ Market Split

• เรียนรู้วิธีเลือกตัวเลือกสำหรับ Parity Twine Optimizer และผลลัพธ์ที่ได้จากการทำงาน

ความเป็นมา

บทช่วยสอนนี้สาธิตวิธีการแก้ปัญหา Market Split โดยใช้ ParityQC Parity Twine Optimizer

อินสแตนซ์ของปัญหาได้มาจาก QOBLIB - Quantum Optimization Benchmarking Library

ปัญหา Market Split

ปัญหา market split เป็นปัญหาการจัดสรรทรัพยากรในโลกจริงที่เป็น NP-hard และได้กลายเป็นเกณฑ์มาตรฐานสำหรับอัลกอริทึมการหาค่าเหมาะที่สุดเชิงควอนตัม ปัญหานี้สะท้อนความท้าทายด้านโลจิสติกส์ที่มีเดิมพันสูง: จะแบ่งภูมิทัศน์ที่ซับซ้อนของลูกค้าและผลิตภัณฑ์ออกเป็นพื้นที่ที่จัดการได้และเท่าเทียมกันได้อย่างไร

เป้าหมายคือการแบ่งตลาด $n$ แห่งออกเป็นสองภูมิภาคการขายที่สมดุลกัน โดยที่แต่ละภูมิภาคได้รับความต้องการทั้งหมดสำหรับผลิตภัณฑ์ $m$ ชนิดเป็นครึ่งหนึ่งพอดี คำตอบคือการจัดเรียงเฉพาะที่ทำให้การกระจายความต้องการผลิตภัณฑ์เท่าเทียมกันมากที่สุดเท่าที่จะเป็นไปได้ ทำให้บริษัทสามารถดำเนินกลยุทธ์ด้านโลจิสติกส์และบุคลากรที่ทั้งสองภูมิภาคมีความสมดุลกัน ลดความเสี่ยง เช่น การขาดแคลนผลิตภัณฑ์เฉพาะพื้นที่หรือคลังสินค้าล้น

เมื่อจำนวนตลาดและผลิตภัณฑ์เพิ่มขึ้น จำนวนการเรียงสับเปลี่ยนที่เป็นไปได้จะเพิ่มขึ้นแบบเอ็กซ์โพเนนเชียล ทำให้การหาการแบ่งที่ดีที่สุดด้วยวิธีค้นหาแบบละเอียดถี่ถ้วนแบบดั้งเดิมเป็นเรื่องท้าทาย

การกำหนดปัญหาทางคณิตศาสตร์

ให้ $A$ เป็นเมทริกซ์ขนาด $m \times n$ ที่แสดงความต้องการของผลิตภัณฑ์ในแต่ละตลาด โดยที่ $A_{ij}$ คือความต้องการสำหรับผลิตภัณฑ์ $i$ ในตลาด $j$

เวกเตอร์การกำหนดแบบไบนารี $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$ ถูกกำหนดขึ้นดังนี้:

• $x_j = 1$ กำหนดให้ตลาด $j$ อยู่ในภูมิภาค A
• $x_j = 0$ กำหนดให้ตลาด $j$ อยู่ในภูมิภาค B

ให้ $d = [d_1, d_2, \dots, d_m]^T$ เป็นเวกเตอร์ความต้องการรวมของผลิตภัณฑ์แต่ละชนิด ซึ่งคำนวณได้จาก $d = A \cdot \mathbf{1}$ ปริมาณการขายเป้าหมายต่อภูมิภาคสำหรับผลิตภัณฑ์ $i$ คือ $\frac{d_i}{2}$ พอดี

เงื่อนไขการหาค่าเหมาะที่สุดหรือความเป็นไปได้กำหนดว่ายอดขายรวมที่จัดสรรให้ภูมิภาค A ต้องตรงกับครึ่งหนึ่งของความต้องการรวมสำหรับผลิตภัณฑ์ทุกชนิดพอดี:

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

ในทางปฏิบัติ เนื่องจากการแบ่งที่แม่นยำพอดีเกิดขึ้นได้ยาก ปัญหานี้จึงถูกกำหนดให้หาค่าต่ำสุดของการละเมิดเงื่อนไขแบบยกกำลังสอง (ฟังก์ชันต้นทุน):

$\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.$

การขยายสมการนี้จะได้รูปแบบที่เทียบเท่ากับปัญหา quadratic unconstrained binary optimization (QUBO)

เมื่อแก้ปัญหาแล้ว เวกเตอร์คำตอบ $x$ จะกำหนดว่าตลาดถูกจัดสรรให้ภูมิภาคใด นี่คือการจัดเรียงที่ทำให้การกระจายความต้องการผลิตภัณฑ์สมดุลที่สุดเท่าที่จะเป็นไปได้

ข้อกำหนดเบื้องต้น

ก่อนเริ่มบทช่วยสอนนี้ ตรวจสอบให้แน่ใจว่าได้ติดตั้งสิ่งต่อไปนี้แล้ว:

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

• Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)

• NumPy (pip install numpy)

คุณยังต้องได้รับสิทธิ์ในการเข้าถึงฟังก์ชัน ParityQC Twine Optimizer หากต้องการขอสิทธิ์เข้าถึง ให้กรอกแบบฟอร์มนี้

การตั้งค่า

(โค้ดนี้สมมติว่าคุณได้ บันทึกบัญชีของคุณ ไว้ในสภาพแวดล้อมท้องถิ่นของคุณแล้ว)

ก่อนอื่น ให้นำเข้าแพ็กเกจที่จำเป็นทั้งหมดสำหรับบทช่วยสอนนี้

# 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

โหลด Parity Twine Optimizer จาก Qiskit Functions catalog:

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

ขั้นตอนที่ 1: กำหนดปัญหาเป็นฟังก์ชันวัตถุประสงค์

รับอินสแตนซ์ของปัญหา market split จาก QOBLIB - Quantum Optimization Benchmarking Library ดังนี้

ฟังก์ชัน load_market_split_problem ดึงปัญหาที่กำหนดจาก QOBLIB และแปลงเป็นปัญหา 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)

ฟังก์ชัน load_market_split_problem ต้องใช้ฟังก์ชัน parser ต่อไปนี้เพื่อดึงและประมวลผลข้อมูลปัญหา market split จาก 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)

เมื่อกำหนดแล้ว load_marketsplit_problem สามารถใช้เพื่อโหลดอินสแตนซ์ของปัญหาที่ระบุจากไลบรารีได้:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

ขั้นตอนที่ 2: แปลงเป็นรูปแบบ JSON

ในขั้นตอนแรก คุณได้รับรูปแบบ QUBO ของปัญหาแล้ว ตอนนี้ให้แปลงเป็นรูปแบบ JSON สำหรับฟังก์ชัน optimizer:

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

อินสแตนซ์ QUBO ของปัญหา Market Split ถูกแปลงเป็นรูปแบบ JSON แล้วดังนี้:

json_ms_problem = optimization_problem_to_json(ms_problem)

ขั้นตอนที่ 3: แก้ปัญหาโดยใช้ Parity Twine Optimizer

ตอนนี้คุณได้รับปัญหา market split และแปลงเป็นรูปแบบที่ถูกต้องแล้ว คุณสามารถหาคำตอบได้โดยใช้ Twine Optimizer และ backend ของ IBM® ที่เลือก

หากต้องการรันฟังก์ชัน ให้เลือกอุปกรณ์ backend ที่เหมาะสม เช่น ibm_phoenix

คุณสามารถใช้ options เพื่อควบคุมการส่งงานเพิ่มเติม (ไม่บังคับ):

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

โดยที่ shots เป็นจำนวนเต็มที่ระบุจำนวนครั้งของการรันวงจร postprocessing_level กำหนดว่าจะมีการทำ post-processing กับผลลัพธ์หรือไม่ transpile_only ระบุว่าปัญหาจะถูก transpile เป็นวงจรเท่านั้น (โดยไม่แก้ปัญหา) หรือไม่ และ job_tags เป็นป้ายกำกับที่ใช้ระบุ job บน IBM Quantum® Platform

รัน optimizer:

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}")

ตรวจสอบสถานะของ job:

# Monitor the job status
function_job.status()

ดึงผลลัพธ์:

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

result

ผลลัพธ์มีรูปแบบดังนี้:

{
    '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},
        },
    }
}

โดยที่ dictionary solution สอดคล้องกับ qubit ที่กำหนดไว้ในปัญหา และให้ค่า spin ที่ผ่านการปรับให้เหมาะสมแล้ว metadata ให้ข้อมูลเกี่ยวกับการ transpile (จำนวน/ความลึกของ two-qubit gate ที่ใช้, gate ที่ใช้, qubit ที่ใช้งาน) และเวลาการทำงานต่างๆ

ในบริบทของปัญหา market split บิตสตริงคำตอบแสดงถึงเวกเตอร์การกำหนดแบบไบนารีที่ใช้แบ่งตลาดออกเป็นสองภูมิภาค ค่า 1 หมายถึงการกำหนดตลาดนั้นให้กับภูมิภาค A ในขณะที่ค่า 0 หมายถึงการกำหนดให้กับภูมิภาค B สำหรับคำตอบที่เหมาะสมที่สุด การจัดสรรชุดนี้จะทำให้การแบ่งสมดุล กล่าวคือทั้งสองภูมิภาคจะได้รับความต้องการของบริษัททั้งหมดสำหรับแต่ละผลิตภัณฑ์ในสัดส่วนครึ่งหนึ่งพอดี

ขั้นตอนถัดไป

คำแนะนำ

• ขอสิทธิ์เข้าถึงฟังก์ชันโดยกรอกแบบฟอร์มนี้
• เยี่ยมชม เอกสารอ้างอิง API สำหรับ Qiskit Function นี้
• อ่านคู่มือ
• ลองบทเรียน สำหรับการนำ Parity Twine Optimizer ไปใช้กับโมเดล Sherrington-Kirkpatrick
• ทบทวนพรีปรินท์ ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025)