{ "cells": [ { "cell_type": "markdown", "id": "b6d1e3ec", "metadata": {}, "source": [ "---\n", "title: Solve the market split problem with the ParityQC Parity Twine Optimizer\n", "description: Learn how to solve the market split problem by using the Parity Twine Optimizer.\n", "---\n", "\n", "{/* cspell:ignore parityqc QOBLIB marketsplit independentset */}\n", "\n", "# Solve the market split problem with the ParityQC Parity Twine Optimizer\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "a6f69b77", "metadata": {}, "source": [ "*Usage estimate: 10 seconds on a Nighthawk r2 processor. (NOTE: This is an estimate only. Your runtime may vary.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "21156b6f", "metadata": {}, "source": [ "## Learning outcomes\n", "\n", "* Obtain and format the Market Split problem from the [QOBLIB - Quantum Optimization Benchmarking Library](https://github.com/ZIB-AOPT/QOBLIB).\n", "* Set up and use the Parity Twine Optimizer to solve a Market Split instance.\n", "* Learn how to choose options for the Parity Twine Optimizer and what results are output.\n", "\n" ] }, { "cell_type": "markdown", "id": "d185259f257c1618", "metadata": {}, "source": [ "## Background\n", "\n", "This tutorial demonstrates how to solve the Market Split problem using the ParityQC Parity Twine Optimizer.\n", "\n", "The problem instance is obtained from the [QOBLIB - Quantum Optimization Benchmarking Library](https://github.com/ZIB-AOPT/QOBLIB).\n", "\n", "### Market split problem\n", "\n", "The market split problem is a real-world, NP-hard resource allocation problem and has become a benchmark for quantum optimization algorithms.\n", "It represents a high-stakes logistical challenge: how to partition a complex landscape of customers and products into manageable, equalized territories.\n", "\n", "The goal is to divide $n$ markets into two balanced sales regions such that each region receives exactly half the total demand for $m$ products.\n", "The solution is the specific configuration that achieves the most even distribution of product demand possible, allowing a company to implement a logistics and staffing strategy where both regions are balanced,\n", "minimizing the risks such as localized product shortages or warehouse overflows.\n", "\n", "As the number of markets and products increases, the number of possible permutations grows exponentially, making it challenging to find the best split using traditional exhaustive searches.\n", "\n", "### Mathematical formulation\n", "\n", "Let $A$ be an $m \\times n$ matrix representing the demand of products across markets, where $A_{ij}$ is the demand for product $i$ in market $j$.\n", "\n", "A binary assignment vector, $x = [x_1, x_2, \\dots, x_n]^T \\in \\{0, 1\\}^n$, is defined where:\n", "\n", "* $x_j = 1$ assigns market $j$ to Region A.\n", "* $x_j = 0$ assigns market $j$ to Region B.\n", "\n", "Let $d = [d_1, d_2, \\dots, d_m]^T$ be the total demand vector for each product, calculated as $d = A \\cdot \\mathbf{1}$. The target sales volume per region for product $i$ is exactly $\\frac{d_i}{2}$.\n", "\n", "The optimization or feasibility constraint requires that the total sales allocated to Region A perfectly matches half the total demand for every product:\n", "\n", "$A x = \\frac{1}{2} A \\mathbf{1} = b.$\n", "\n", "In practice, because exact division is rarely possible, the problem is formulated to minimize the squared constraint violation (the cost function):\n", "\n", "$\\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.$\n", "\n", "Expanding this gives a form that is equivalent to a quadratic unconstrained binary optimization (QUBO) problem.\n", "\n", "Upon solving, the solution vector $x$ dictates to which region the market is assigned. This is the configuration that achieves the most balanced distribution of product demand possible.\n", "\n" ] }, { "cell_type": "markdown", "id": "55b94021", "metadata": {}, "source": [ "## Requirements\n", "\n", "Before starting this tutorial, ensure the following are installed:\n", "\n", "* Qiskit Functions Catalog IBM Client (`pip install qiskit-ibm-catalog`)\n", "* Qiskit addon Optimization Mapper (`pip install qiskit_addon_opt_mapper`)\n", "* NumPy (`pip install numpy`)\n", "\n", "You also need permission to access the ParityQC Twine Optimizer function. To request access, complete this [form](https://parityqc.com/products/parity-twine-optimizer/free-trial).\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "7db2e559", "metadata": {}, "source": [ "## Setup\n", "\n", "(This code assumes you've already [saved your account](/docs/guides/functions-get-started#install-qiskit-functions-catalog-client) to your local environment.)\n", "\n", "First, import all required packages for this tutorial.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bc380c46", "metadata": {}, "outputs": [], "source": [ "import tempfile\n", "\n", "from collections.abc import Callable\n", "from pathlib import Path\n", "\n", "import numpy as np\n", "import requests\n", "\n", "from qiskit_addon_opt_mapper import OptimizationProblem\n", "from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo\n", "from qiskit_ibm_catalog import QiskitFunctionsCatalog" ] }, { "cell_type": "markdown", "id": "d59c6bf33095b413", "metadata": {}, "source": [ "Load the Parity Twine Optimizer from the Qiskit Functions catalog:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "805c80a1180e79fe", "metadata": {}, "outputs": [], "source": [ "catalog = QiskitFunctionsCatalog(channel=\"ibm_quantum_platform\")\n", "function = catalog.load(\"parityqc/parity-twine-optimizer\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "988ee237", "metadata": {}, "source": [ "### Step 1: Define the problem as an objective function\n", "\n", "Obtain a market split problem instance from the [QOBLIB - Quantum Optimization Benchmarking Library](https://github.com/ZIB-AOPT/QOBLIB) as follows.\n", "\n", "The `load_market_split_problem` function retrieves a given problem from QOBLIB and converts it into a QUBO problem.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "2a90bce6-1925-436f-a167-4fab3255f4a0", "metadata": {}, "outputs": [], "source": [ "def load_market_split_problem(instance_name: str) -> OptimizationProblem:\n", " \"\"\"Load and formulate a market split optimization problem from an QOBLIB instance.\n", "\n", " The QOBLIB library can be found here:\n", " https://github.com/ZIB-AOPT/QOBLIB.\n", "\n", " Args:\n", " instance_name: Name of the market split instance to load as specified by the .dat file\n", " in the QOBLIB repo.\n", "\n", " Returns:\n", " The output OptimizationProblem containing the loaded market split problem.\n", " \"\"\"\n", "\n", " problem_matrix, problem_vector = fetch_and_parse(\n", " instance_name, \"01-marketsplit\", parse_marketsplit_dat\n", " )\n", "\n", " # Create optimization problem\n", " optimization_problem = OptimizationProblem(instance_name)\n", "\n", " # Add binary variables (one for each market)\n", " optimization_problem.binary_var_list(problem_matrix.shape[1])\n", "\n", " # Add equality constraints (one for each product)\n", " for idx, rhs in enumerate(problem_vector):\n", " optimization_problem.linear_constraint(\n", " problem_matrix[idx, :], sense=\"==\", rhs=rhs\n", " )\n", "\n", " # Convert to QUBO with penalty parameter\n", " return OptimizationProblemToQubo(penalty=1).convert(optimization_problem)" ] }, { "cell_type": "markdown", "id": "becd6460-8eb9-4796-8a21-60d6edc56cd1", "metadata": {}, "source": [ "The `load_market_split_problem` function requires the following parser functions to retrieve and process the market split problem data from QOBLIB.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "c07d1d1b-3dc1-4fd8-b7cd-b7898e974eee", "metadata": {}, "outputs": [], "source": [ "def fetch_and_parse(instance_name: str, problem: str, parse_func: Callable):\n", " \"\"\"Generic function to fetch and parse data from QOBLIB repository.\n", "\n", " Args:\n", " instance_name: Name of the instance to fetch.\n", " problem: Category of the problem (e.g., '01-marketsplit', '07-independentset').\n", " parse_func: Function used to parse the downloaded file\n", " (e.g., parse_marketsplit_dat, parse_gph_file).\n", "\n", " Returns:\n", " Result of `parse_func` - either (np.ndarray, np.ndarray) for marketsplit\n", " or nx.Graph for MIS.\n", " \"\"\"\n", " base_url = (\n", " \"https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/\"\n", " )\n", " url = (\n", " base_url\n", " + problem\n", " + \"/instances/\"\n", " + instance_name\n", " + (\".dat\" if problem == \"01-marketsplit\" else \".gph\")\n", " )\n", "\n", " try:\n", " response = requests.get(url, timeout=30)\n", " response.raise_for_status()\n", "\n", " with tempfile.NamedTemporaryFile(\n", " mode=\"w\",\n", " suffix=\".dat\" if problem == \"01-marketsplit\" else \".gph\",\n", " delete=False,\n", " encoding=\"utf-8\",\n", " ) as temp_file:\n", " temp_file.write(response.text)\n", " temp_file_path = temp_file.name\n", "\n", " try:\n", " return parse_func(temp_file_path)\n", " finally:\n", " Path(temp_file_path).unlink(missing_ok=True)\n", "\n", " except requests.RequestException as e:\n", " print(f\"Error fetching data from repository: {e}\")\n", " except (ValueError, OSError) as e:\n", " print(f\"Error processing data: {e}\")\n", " return None\n", "\n", "\n", "def parse_marketsplit_dat(filename: str) -> tuple[np.ndarray, np.ndarray]:\n", " \"\"\"Parse a market split problem from a .dat file format.\n", "\n", " Args:\n", " filename: Path to the .dat file.\n", "\n", " Returns:\n", " Tuple of (A, b) where:\n", " - A: (m, n) array of coefficients.\n", " - b: (m,) array of target values.\n", "\n", " Raises:\n", " ValueError: If file format is invalid or file is empty.\n", " \"\"\"\n", " with Path(filename).open(encoding=\"utf-8\") as f:\n", " lines = [\n", " line.strip()\n", " for line in f\n", " if line.strip() and not line.startswith(\"#\")\n", " ]\n", "\n", " if not lines:\n", " raise ValueError(\"Empty or invalid .dat file\")\n", "\n", " # First line: m n (number of products and markets)\n", " try:\n", " m, n = map(int, lines[0].split())\n", " except (ValueError, IndexError) as e:\n", " raise ValueError(\n", " \"Invalid file format: first line must contain 'm n' integers\"\n", " ) from e\n", "\n", " if len(lines) < m + 1:\n", " raise ValueError(\n", " f\"File contains {len(lines)} lines but expected {m + 1} lines\"\n", " )\n", "\n", " # Next m lines: each row of A followed by corresponding element of b\n", " mat_a = []\n", " vec_b = []\n", "\n", " for i in range(1, m + 1):\n", " try:\n", " values = list(map(int, lines[i].split()))\n", " except ValueError as e:\n", " raise ValueError(f\"Invalid integer values in line {i + 1}\") from e\n", "\n", " if len(values) != n + 1:\n", " raise ValueError(\n", " f\"Line {i + 1} contains {len(values)} values but expected {n + 1}\"\n", " )\n", "\n", " mat_a.append(values[:-1]) # First n values: product sales per market\n", " vec_b.append(values[-1]) # Last value: target sales for this product\n", "\n", " return np.array(mat_a), np.array(vec_b)" ] }, { "cell_type": "markdown", "id": "9811ef6c-717e-4033-963d-3fd85790be23", "metadata": {}, "source": [ "Once defined, `load_marketsplit_problem` can be used to load a specific problem instance from the library:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "287f6c52-9b2a-46b7-994d-7005bd4ab1c6", "metadata": {}, "outputs": [], "source": [ "ms_instance = \"ms_04_050_001\"\n", "\n", "ms_problem = load_market_split_problem(ms_instance)" ] }, { "cell_type": "markdown", "id": "ac6f36e3", "metadata": {}, "source": [ "### Step 2: Convert to JSON format\n", "\n", "In the first step, you obtained the QUBO form of the problem. Now, convert it to JSON format for the optimizer function:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "fe1169b1-50a0-4edb-9db5-7c0d99ce9a68", "metadata": {}, "outputs": [], "source": [ "def optimization_problem_to_json(\n", " problem: OptimizationProblem,\n", ") -> dict[str, float]:\n", " \"\"\"\n", " Converts an unconstrained quadratic OptimizationProblem in terms of binary or spin variables\n", " to the JSON input format of the Parity Twine Qiskit Function.\n", "\n", " Args:\n", " problem: The optimization problem to convert to JSON.\n", "\n", " Returns:\n", " The JSON input format of the given problem.\n", " \"\"\"\n", " ising, constant = problem.to_ising()\n", " output = {\"()\": float(constant)}\n", " for op, coefficient in zip(ising.paulis, ising.coeffs, strict=True):\n", " # Invert the label strings because Qiskit has opposite convention\n", " qubits = tuple(\n", " num\n", " for num, pauli in enumerate(op.to_label()[::-1])\n", " if pauli == \"Z\"\n", " )\n", " output[str(qubits)] = float(coefficient)\n", " return output" ] }, { "cell_type": "markdown", "id": "9e374de6-384a-497e-bcf1-c8617c1945ec", "metadata": {}, "source": [ "The QUBO instance of the Market Split problem is now converted to JSON format as:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "4885df90-4d15-4bc7-8130-ec1d9ece7670", "metadata": {}, "outputs": [], "source": [ "json_ms_problem = optimization_problem_to_json(ms_problem)" ] }, { "attachments": {}, "cell_type": "markdown", "id": "b4d480b3", "metadata": {}, "source": [ "### Step 3: Solve the problem using the Parity Twine Optimizer\n", "\n", "Now that you have obtained the market split problem and converted it into the correct form, you can find a solution by using the Twine Optimizer and a chosen IBM® backend.\n", "\n", "To run the function, choose a suitable backend device; for example, `ibm_phoenix`.\n", "\n", "You can use `options` for (optional) additional control over the submission:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "a3eaff0a-9c54-4ffc-b6b2-5d43c49e6a07", "metadata": {}, "outputs": [], "source": [ "options = {\n", " \"shots\": 100000,\n", " \"postprocessing_level\": 1,\n", " \"transpile_only\": False,\n", " \"job_tags\": [\"market_split\"],\n", "}" ] }, { "cell_type": "markdown", "id": "864629a2-34fe-473b-b9f1-277e0a99752d", "metadata": {}, "source": [ "where `shots` is an integer that specifies the number of circuit executions, `postprocessing_level` determines if post-processing is applied to the result, `transpile_only`\n", "specifies whether the problem is only transpiled to a circuit (and not solved), and `job_tags` is the label used to identify job on IBM Quantum® Platform.\n", "\n", "Run the optimizer:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "2c4a5ce3de728746", "metadata": {}, "outputs": [], "source": [ "function_job = function.run(\n", " problem=json_ms_problem,\n", " variable_type=\"spin\",\n", " backend_name=\"ibm_phoenix\",\n", " options=options,\n", ")\n", "print(f\"Job ID: {function_job.job_id}\")" ] }, { "cell_type": "markdown", "id": "e8e66a1efeef3757", "metadata": {}, "source": [ "Check the job status:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "be7bbe053da38198", "metadata": {}, "outputs": [], "source": [ "# Monitor the job status\n", "function_job.status()" ] }, { "cell_type": "markdown", "id": "fe4ea9784df0bcbb", "metadata": {}, "source": [ "Retrieve results:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "9af5dddb30694451", "metadata": {}, "outputs": [], "source": [ "# Retrieve the job result if the status is DONE\n", "result = function_job.result()\n", "\n", "result" ] }, { "cell_type": "markdown", "id": "8b888ac0-c0eb-4849-be0d-4bf331707df5", "metadata": {}, "source": [ "The result is of form:\n", "\n", "```\n", "{\n", " 'solution': {'0': 1, '1': -1, '10': 1, ... },\n", " 'objective_value': 1.0,\n", " 'solution_bitstring': '010000011101111011001001110010',\n", " 'metadata': {\n", " 'circuit_metrics': {\n", " 'depth': 309,\n", " 'gate_count': 3880,\n", " 'two_qubit_gate_depth': 116,\n", " 'two_qubit_gate_count': 899,\n", " 'num_qubits': 30,\n", " 'operations': {'sx': 1244, 'rz': 1227, 'cz': 899, 'delay': 473, 'measure': 30, 'x': 7},\n", " },\n", " 'solver_info': {\n", " 'variable_mapping': {'0': 0, '1': 1, '10': 2, ... },\n", " 'bitstring_distributions': {\n", " 'before_postprocessing': {'011101110010110111001110011000': 1, ...},\n", " 'after_postprocessing': {'011011110000110101001111011000': 1, ...}\n", " },\n", " 'best_parameters': {\n", " 'beta': [-0.18054534155552715],\n", " 'gamma': [1.4141236348317905]\n", " }\n", " },\n", " 'resource_usage': {\n", " 'RUNNING: MAPPING': {'CPU_TIME': 172.936},\n", " 'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU_TIME': 0.272},\n", " 'RUNNING: WAITING_FOR_QPU': {'CPU_TIME': 7.798},\n", " 'RUNNING: EXECUTING_QPU': {'QPU_TIME': 30.0},\n", " 'RUNNING: POST_PROCESSING': {'CPU_TIME': 31.613},\n", " },\n", " }\n", "}\n", "```\n", "\n", "where the `solution` dictionary corresponds to the qubits defined in the problem and gives their optimized spin values.\n", "`metadata` gives information on the transpilation (two-qubit gates counts/depth, gates used, active qubits), and various runtimes.\n", "\n", "In the context of the market split problem, the solution bitstring represents a binary assignment vector used to partition markets into two separate regions. A value of 1 assigns that\n", "specific market to Region A while a value of 0 assigns it to Region B. For the optimal solution, the combination balances the split, meaning both regions receive exactly half of the total company\n", "demand for every product.\n", "\n" ] }, { "cell_type": "markdown", "id": "2cb5785c", "metadata": {}, "source": [ "## Next steps\n", "\n", "\n", " * Request access to the function by completing this [form](https://parityqc.com/products/parity-twine-optimizer/free-trial).\n", " * Visit the [API reference](/docs/api/functions/parity-twine-optimizer) for this Qiskit Function.\n", " * Read the [guide](/docs/guides/parity-twine-optimizer).\n", " * Try the [tutorial](/docs/tutorials/parity-twine-optimizer-sk) for applying the Parity Twine Optimizer to the Sherrington-Kirkpatrick model.\n", " * Review the [Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025)](https://arxiv.org/abs/2501.14020) ArXiv preprint.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }