710 lines
33 KiB
Plaintext
710 lines
33 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "f7d9993f",
|
|
"metadata": {},
|
|
"source": [
|
|
"{/* cspell:ignore Kipu, DCQO, QUBO, HUBO, counterdiabatic, Iskay */}"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "dde95705",
|
|
"metadata": {},
|
|
"source": [
|
|
"# Iskay Quantum Optimizer - A Qiskit Function by Kipu Quantum\n",
|
|
"\n",
|
|
"<Admonition type=\"note\">\n",
|
|
" Qiskit Functions are an experimental feature available only to IBM Quantum™ Premium Plan users. They are in preview release status and subject to change.\n",
|
|
"</Admonition>\n",
|
|
"\n",
|
|
"## Overview\n",
|
|
"\n",
|
|
"With the Iskay Quantum Optimizer by Kipu Quantum, you can tackle complex optimization problems using IBM® quantum computers. This solver leverages Kipu's cutting-edge [bf-DCQO algorithm](https://doi.org/10.48550/arXiv.2409.04477) requiring only the objective function as input to automatically deliver problem solutions. It can handle optimization problems involving up to 156 qubits, enabling the use of all qubits of the IBM quantum devices. The Optimizer uses a 1-to-1 mapping between classical variables and qubits, which allows you to tackle optimization problems with up to 156 binary variables.\n",
|
|
"\n",
|
|
"The Optimizer enables the solving of unconstrained binary optimization problems. In addition to the commonly used QUBO (Quadratic Unconstrained Binary Optimization) formulation, it also supports higher-order (HUBO) optimization problems. The solver utilizes a non-variational quantum algorithm, performing most of the computation on quantum devices.\n",
|
|
"\n",
|
|
"The following provides more details about the used algorithm and a brief guide on how to use the function, as well as benchmarking results on various problem instances of different sizes and complexities."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "5f761442",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Description\n",
|
|
"\n",
|
|
"The Optimizer is a ready-to-use implementation of cutting-edge quantum optimization algorithms. It solves optimization problems by running highly-compressed quantum circuits on quantum hardware. This compression is achieved by introducing counterdiabatic terms into the underlying time evolution of the quantum system. The algorithm executes several iterations of hardware runs to obtain the final solutions and combines it with post-processing. These steps are seamlessly integrated into the Optimizer's workflow and are executed automatically.\n",
|
|
"\n",
|
|
"### How does the Quantum Optimizer work?\n",
|
|
"This section outlines the basics of the implemented bf-DCQO algorithm. An introduction to the algorithm can also be found on the [Qiskit YouTube channel.](https://www.youtube.com/watch?v=33QmsXhIlpU&t=1223s)\n",
|
|
"\n",
|
|
"The algorithm is based on the time evolution of a quantum system which is transformed over time, where the problem solution is encoded in the ground state of the quantum system at the end of the evolution. According to the [adiabatic theorem](https://en.wikipedia.org/wiki/Adiabatic_theorem), this evolution has to be slow to ensure the system remains in its ground state. Digitizing this evolution is the basis of digitized quantum adiabatic computation (DQA) and the infamous QAOA algorithm. However, the required slow evolution is not feasible for increasing problem sizes since it results in an increasing circuit depth. By using counterdiabatic protocols, you can suppress unwanted excitations occurring during short evolution times while remaining in the ground state. Here, digitizing this shorter evolution time results in quantum circuits with shorter depth and fewer entangling gates.\n",
|
|
"\n",
|
|
"The circuits of the bf-DCQO algorithms typically use up to ten times fewer entangling gates than DQA, and three to four times fewer entangling gates than standard QAOA implementations. Because of the smaller number of gates, fewer errors occur during the circuit execution on hardware. Hence, the optimizer does not require using techniques like error suppression or error mitigation. Implementing them in future versions can enhance the solution quality even further.\n",
|
|
"\n",
|
|
"Although the bf-DCQO algorithm uses iterations, it is non-variational. After each iteration of the algorithm, the distribution of states is measured. The obtained distribution is used to calculate a so-called bias-field. The bias-field allows starting the next iteration from an energy state near the previously found solution. In this way, the algorithm moves with each iteration to solutions of lower energy. Typically, approximately ten iterations are sufficient to converge to a solution, in total requiring a much lower number of iterations than variational algorithms, which is on the order of approximately 100 iterations.\n",
|
|
"\n",
|
|
"The optimizer combines the bf-DCQO algorithm with classical post-processing. After measuring the distribution of states, a local search is performed. During the local search, the bits of the measured solution are randomly flipped. After the flip, the energy of the new bitstring is evaluated. If the energy is lower, the bitstring is kept as the new solution. The local search only scales linearly with the number of qubits; hence, it is computationally cheap. Since the post-processing corrects local bitflips, it compensates for bit-flip errors that often are the result of hardware imperfections and readout errors.\n",
|
|
"\n",
|
|
"### Workflow\n",
|
|
"\n",
|
|
"A schematic of the workflow of the Quantum Optimizer follows.\n",
|
|
"\n",
|
|
"![Workflow](/images/guides/kipu-optimization/workflow.svg \"Workflow of the Quantum Optimizer\")\n",
|
|
"\n",
|
|
"By using the Quantum Optimizer, solving an optimization problem on quantum hardware can be reduced to\n",
|
|
"* Formulate the objective function of the problem\n",
|
|
"* Access the Optimizer via Qiskit Functions\n",
|
|
"* Run the Optimizer and collect the result"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "b34fe075",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Benchmarks\n",
|
|
"\n",
|
|
"The benchmark metrics below show that the Optimizer effectively addresses problems involving up to 156 qubits and offer a general overview of the optimizer's accuracy and scalability across different problem types. Note that actual performance metrics may vary depending on specific problem characteristics, such as the number of variables, the density and locality of terms in the objective function, and the polynomial order.\n",
|
|
"\n",
|
|
"The following table includes the approximation ratio (AR), a metric defined as follows:\n",
|
|
"$$\n",
|
|
"AR = \\frac{C^{*} - C_\\textrm{max}}{C_{\\textrm{min}} - C_{\\textrm{max}}},\n",
|
|
"$$\n",
|
|
"where $C$ is the objective function, $C_{\\textrm{min}}$, $C_{\\textrm{max}}$ are its minimum and maximum values, and $C^{*}$ is the cost of the best solution found, respectively. Therefore, AR=100\\% means that the ground state of the problem has been obtained.\n",
|
|
"\n",
|
|
"\n",
|
|
"| Example | Number of qubits | Approximation Ratio | Total time (s) | Runtime usage (s) | Total Number of shots | Number of iterations |\n",
|
|
"| ----------------- | :--------------: | :------: | :------------: | :---------------: | :-------------------: | :------------------: |\n",
|
|
"| Unweighted MaxCut | 28 | 100% | 180 | 30 | 30k | 5 |\n",
|
|
"| Unweighted MaxCut | 30 | 100% | 180 | 30 | 30k | 5 |\n",
|
|
"| Unweighted MaxCut | 32 | 100% | 180 | 30 | 30k | 5 |\n",
|
|
"| Unweighted MaxCut | 80 | 100% | 480 | 60 | 90k | 9 |\n",
|
|
"| Unweighted MaxCut | 100 | 100% | 330 | 60 | 60k | 6 |\n",
|
|
"| Unweighted MaxCut | 120 | 100% | 370 | 60 | 60k | 6 |\n",
|
|
"| HUBO 1 | 156 | 100% | 600 | 70 | 100k | 10 |\n",
|
|
"| HUBO 2 | 156 | 100% | 600 | 70 | 100k | 10 |\n",
|
|
"\n",
|
|
"- The MaxCut instances with 28, 30, and 32 qubits were run on ibm_sherbrooke. Instances with 80, 100, and 120 were run on ibm_marrakesh.\n",
|
|
"- The HUBO instances were also run on ibm_marrakesh.\n",
|
|
"\n",
|
|
"All the benchmark instances are accessible on GitHub (see [Kipu benchmark instances](https://github.com/Kipu-Quantum-GmbH/benchmark-instances)). An example to run these instances can be found in [Example 3: Benchmark instances](#example-3-benchmark-instances)."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e2817b13",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Inputs and outputs\n",
|
|
"\n",
|
|
"### Input\n",
|
|
"See the following table for all input parameters the Quantum Optimizer accepts. The subsequent **Options** section goes into more details about the available `options`."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "80e055cd",
|
|
"metadata": {},
|
|
"source": [
|
|
"| Name | Type | Description | Required | Default | Example |\n",
|
|
"| ------------ | ------------------ | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------- | --------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------- |\n",
|
|
"| problem | `Dict[str, float]` | The coefficients of the optimization problem formulated as QUBO/HUBO or spin format. For more information on the problem specification, see [Accepted problem formats](#accepted-problem-formats) | Yes | N/A | `{\"()\": -21.0, \"(0, 4)\": 0.5,\"(0, 2)\": 0.5,\"(0, 1)\": 0.5,\"(1, 3)\": 0.5}` |\n",
|
|
"| problem_type | `str` | Specify whether the problem coefficients are in binary (QUBO/HUBO) or spin format. The two possibilities are `\"spin\"` or `\"binary\"` | Yes | N/A | `\"spin\"` |\n",
|
|
"| backend_name | `str` | Name of the backend to make the query | Yes | N/A | `\"ibm_fez\"` |\n",
|
|
"| instance | `str` | The hub/group/project to use | No | A Premium access instance is randomly chosen if your account has access to multiple instances. | \"hub1/group1/project1\" |\n",
|
|
"| options | `Dict[str, Any]` | Options to handle the hardware submission, such as number of shots. For further details on the options configuration, see the [Options](#options) section | No | To see the default values of the options configuration see the [Options](#options) section | `{\"shots\": 5000, \"num_iterations\": 3, \"use_session\": True, \"seed_transpiler\": 42}` |"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "21b5761c",
|
|
"metadata": {},
|
|
"source": [
|
|
" #### Accepted problem formats\n",
|
|
"The `problem` and `problem_type` arguments encode an optimization problem of the form\n",
|
|
"\n",
|
|
"$$\n",
|
|
"\\begin{align}\n",
|
|
"\\min_{(x_1, x_2, \\ldots, x_n) \\in D} C(x_1, x_2, \\ldots, x_n) \\nonumber\n",
|
|
"\\end{align}\n",
|
|
"$$\n",
|
|
"where\n",
|
|
"\n",
|
|
"$$\n",
|
|
"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}\n",
|
|
"$$\n",
|
|
"\n",
|
|
"- By choosing `problem_type = \"binary\"`, you specify that the cost function is in `binary` format, which means that $D = \\{0, 1\\}^{n}$, as in, the cost function is written in QUBO/HUBO formulation.\n",
|
|
"- On the other hand, by choosing `problem_type = \"spin\"`, the cost function is written in Ising formulation, where $D = \\{-1, 1\\}^{n}$.\n",
|
|
"\n",
|
|
"The coefficients of the problem should be encoded in a dictionary as follows:\n",
|
|
"$$\n",
|
|
"\\begin{align} \\nonumber\n",
|
|
"&\\texttt{\\{} \\\\ \\nonumber\n",
|
|
"&\\texttt{\"()\"}&: \\quad &a, \\\\ \\nonumber\n",
|
|
"&\\texttt{\"(i,)\"}&: \\quad &b_i, \\\\ \\nonumber\n",
|
|
"&\\texttt{\"(i, j)\"}&: \\quad &c_{i, j}, \\\\ \\nonumber\n",
|
|
"&\\quad \\vdots \\\\ \\nonumber\n",
|
|
"&\\texttt{\"(} k_1, ..., k_m \\texttt{)\"} &: \\quad &g_{k_1, ..., k_m}, \\\\ \\nonumber\n",
|
|
"&\\texttt{\\}}\n",
|
|
"\\end{align}\n",
|
|
"$$\n",
|
|
"\n",
|
|
"- Please note that the keys of the dictionary must be strings containing a valid tuple of non-repeating integers."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "43dc063b",
|
|
"metadata": {},
|
|
"source": [
|
|
"#### Options\n",
|
|
"\n",
|
|
"The hyper-parameters of the algorithm are set automatically. However, you can fine-tune the algorithm by exposing parameters to the user. For example, you can select the number of iterations of the algorithm."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "b600b8fb",
|
|
"metadata": {},
|
|
"source": [
|
|
"| Name | Type | Description | Required | Default |\n",
|
|
"| -------------------- | ----------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------- | ------- |\n",
|
|
"| shots | `int` | The number of shots per iteration to execute on hardware. | No | 10000 |\n",
|
|
"| num_iterations | `int` | The total number of Bias Field iterations performed by the solver. | No | 10 |\n",
|
|
"| use_session | `bool` | Whether to run the solver within an IBM session. | No | True |\n",
|
|
"| seed_transpiler | `int` | Optional parameter to set a specific seed to the transpiler, ensures that the same circuit is submitted to hardware. | No | None |\n",
|
|
"| direct_qubit_mapping | `bool` | Optional parameter to indicate that virtual and physical qubits should be addressed by the same index. This option should only be turned on when the connectivity of the problem matches that of the hardware. | No | False |\n",
|
|
"| job_tags | `List[str]` | Optional parameter to include additional tags to the quantum jobs executed by the optimizer. Note, that any job submitted with the Iskay quantum optimizer will contain the tags 'Kipu_Quantum' and 'BF-DCQO'. | No | None |"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "c9eaf19a",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Output\n",
|
|
"\n",
|
|
"| Name | Type | Description | Example |\n",
|
|
"| ------ | ------------------ | ----------------------------------------------------------------------| ---------------------------------------------------------------------- |\n",
|
|
"| result | `Dict[str, float]` | Solution and metadata listed under \"Result dictionary contents\". | `{'solution': {'bitstring': '011', 'cost': -23.5, 'mapped_solution': {'0': 0, '1': 1, '2': 1} , 'mapping': {0: 0, 2: 1, 1: 2}, 'problem type': 'spin', 'seed': 42}` |"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "6a5db0aa",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Result dictionary contents"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "2b741feb",
|
|
"metadata": {},
|
|
"source": [
|
|
"| Name | Type | Description |\n",
|
|
"| ------------ | :------------------: | ----------------------------------------------------------------------------------------------------------------------- |\n",
|
|
"| solution | `Dict` | The solution to the optimization problem in the format it was formulated. This corresponds to a dictionary with items `var_label: var_value` where each `var_label` is a variable in the optimization problem, and `var_value` is its corresponding value (spin or binary) in the optimal solution.|\n",
|
|
"| solution_info | `Dict` | The mapping from the bitstring bit to the equivalent variable in the problem |\n",
|
|
"| prob_type | `str` | Whether the problem is formulated in binary or spin variables |"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "5565f130",
|
|
"metadata": {},
|
|
"source": [
|
|
"#### solution_info dictionary\n",
|
|
"This is a dictionary containing the details of the solution found by the optimizer. It contains the following items:\n",
|
|
" - **\"bitstring\"**: The optimal bitstring measured.\n",
|
|
" - **\"cost\"**: The cost value of the solution.\n",
|
|
" - **\"mapping\"**: The mapping from the bitstring bit to the equivalent variable in the problem.\n",
|
|
" - **\"seed_transpiler\"**: Seed to the transpiler, can be used to ensure the same exact quantum circuit is submitted to hardware. If a seed is not provided, a seed search is run to optimize circuit depth.\n",
|
|
"\n",
|
|
"\n",
|
|
"Note that the `solution` dictionary is obtained from the solution bitstring, using the `mapping` object for indexing the variables. When `problem_type=spin` we use the assignment $1 \\rightarrow -1, \\quad 0 \\rightarrow 1$."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "73390a19",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Get started\n",
|
|
"\n",
|
|
"Authenticate using your [IBM Quantum™ Platform API token](http://quantum.ibm.com/), and select the Qiskit Function as follows:"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "0e4fd124",
|
|
"metadata": {
|
|
"tags": [
|
|
"remove-cell"
|
|
]
|
|
},
|
|
"outputs": [],
|
|
"source": [
|
|
"# ruff: noqa: F821"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "95a715d2",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from qiskit_ibm_catalog import QiskitFunctionsCatalog\n",
|
|
"\n",
|
|
"# If you have not previously saved your credentials, follow instructions at\n",
|
|
"# https://docs.quantum.ibm.com/guides/setup-channel#iqp\n",
|
|
"# to authenticate with your API token.\n",
|
|
"catalog = QiskitFunctionsCatalog()\n",
|
|
"\n",
|
|
"# Access Function\n",
|
|
"optimizer = catalog.load(\"kipu-quantum/iskay-quantum-optimizer\")"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "d4ca2590",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Example 1: Simple cost function\n",
|
|
"\n",
|
|
"Consider the cost function in spin formulation:\n",
|
|
"$$\n",
|
|
"C(x_0, x_1, x_2, x_3, x_4) = 1 + 1.5x_0 + 2x_1 + 1.3x_2 + 2.5x_0x_3 + 3.5x_1x_4 + 4x_0x_1x_2\n",
|
|
"$$\n",
|
|
"\n",
|
|
"where $(x_0, ..., x_4) \\in \\{-1, 1\\}^5$.\n",
|
|
"\n",
|
|
"The solution to this simple cost function is\n",
|
|
"$$\n",
|
|
"(x_0, x_1, x_2, x_3, x_4) = (-1, -1, -1, 1, 1)\n",
|
|
"$$\n",
|
|
"with minimum value $C^{*} = -6$"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "a98e8232",
|
|
"metadata": {},
|
|
"source": [
|
|
"### 1. Create the objective function\n",
|
|
"\n",
|
|
"We start by creating a dictionary with the coefficients of the objective function as follows"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "3b4a58b1",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"objective_func = {\n",
|
|
" \"()\": 1,\n",
|
|
" \"(0,)\": 1.5,\n",
|
|
" \"(1,)\": 2,\n",
|
|
" \"(2,)\": 1.3,\n",
|
|
" \"(0, 3)\": 2.5,\n",
|
|
" \"(1, 4)\": 3.5,\n",
|
|
" \"(0, 1, 2)\": 4,\n",
|
|
"}"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "ab63b08f",
|
|
"metadata": {},
|
|
"source": [
|
|
"### 2. Run the Optimizer\n",
|
|
"\n",
|
|
"We solve the problem by running the optimizer. Since $(x_0, ..., x_4) \\in \\{-1, 1\\}^5$ we must set `problem_type=spin`."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "469ae361",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"# Setup options to run the optimizer\n",
|
|
"options = {\"shots\": 5000, \"num_iterations\": 5, \"use_session\": True}\n",
|
|
"\n",
|
|
"arguments = {\n",
|
|
" \"problem\": objective_func,\n",
|
|
" \"problem_type\": \"spin\",\n",
|
|
" \"instance\": instance, # E.g. \"ibm-q/open/main\"\n",
|
|
" \"backend_name\": backend_name, # E.g. \"ibm_fez\"\n",
|
|
" \"options\": options,\n",
|
|
"}\n",
|
|
"\n",
|
|
"job = optimizer.run(**arguments)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "1e3a8542",
|
|
"metadata": {},
|
|
"source": [
|
|
"### 3. Retrieve the result\n",
|
|
"\n",
|
|
"The solution of the optimization problem is provided directly from the optimizer."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "2f74d7e2",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"print(job.result())"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "c4d0a0f8",
|
|
"metadata": {},
|
|
"source": [
|
|
"This will show a dictionary of the form:\n",
|
|
"\n",
|
|
"```\n",
|
|
"{'solution': {'0': -1, '1': -1, '2': -1, '3': 1, '4': 1},\n",
|
|
" 'solution_info': {'bitstring': '11100',\n",
|
|
" 'cost': -13.8,\n",
|
|
" 'seed_transpiler': 42,\n",
|
|
" 'mapping': {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}},\n",
|
|
" 'prob_type': 'spin'}\n",
|
|
"```\n",
|
|
"\n",
|
|
"Notice that the dictionary `solution` displays the result vector $(x_0, x_1, x_2, x_3, x_4) = (-1, -1, -1, 1, 1)$."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "7eaa5cac",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Example 2: MaxCut\n",
|
|
"\n",
|
|
"Many graph problems like MaxCut or Maximum independent set are NP-hard problems and ideal candidates for testing quantum algorithms and hardware. This example demonstrates solving the MaxCut problem of a 3-regular graph with the Quantum Optimizer.\n",
|
|
"\n",
|
|
"To run this example you must install the `networkx` package in addition to the `qiskit-ibm-catalog`. To install it, run the following command:"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "9ea6d138",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"# %pip install networkx numpy"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "0c63487f",
|
|
"metadata": {},
|
|
"source": [
|
|
"### 1. Create the objective function\n",
|
|
"\n",
|
|
"Start by generating a random 3-regular graph. For this graph, we define the objective function of the MaxCut problem."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "d1d4017f",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"import networkx as nx\n",
|
|
"\n",
|
|
"# Create a random 3-regular graph\n",
|
|
"G = nx.random_regular_graph(3, 10, seed=42)\n",
|
|
"\n",
|
|
"\n",
|
|
"# Create the objective function for MaxCut in Ising formulation\n",
|
|
"def graph_to_ising_maxcut(G):\n",
|
|
" \"\"\"\n",
|
|
" Convert a NetworkX graph to an Ising Hamiltonian for the Max-Cut problem.\n",
|
|
" Args:\n",
|
|
" G (networkx.Graph): The input graph.\n",
|
|
" Returns:\n",
|
|
" dict: The objective function of the Ising model\n",
|
|
" \"\"\"\n",
|
|
" # Initialize the linear and quadratic coefficients\n",
|
|
" objective_func = {}\n",
|
|
" # Populate the coefficients\n",
|
|
" for i, j in G.edges:\n",
|
|
" objective_func[f\"({i}, {j})\"] = 0.5\n",
|
|
" return objective_func\n",
|
|
"\n",
|
|
"\n",
|
|
"objective_func = graph_to_ising_maxcut(G)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "3be09664",
|
|
"metadata": {},
|
|
"source": [
|
|
"### 2. Run the Optimizer\n",
|
|
"\n",
|
|
"Solve the problem by running the optimizer."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "2499ab67",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"options = {\"shots\": 5000, \"num_iterations\": 5, \"use_session\": True}\n",
|
|
"\n",
|
|
"arguments = {\n",
|
|
" \"problem\": objective_func,\n",
|
|
" \"problem_type\": \"spin\",\n",
|
|
" \"instance\": instance, # E.g. \"ibm-q/open/main\"\n",
|
|
" \"backend_name\": backend_name, # E.g. \"ibm_fez\"\n",
|
|
" \"options\": options,\n",
|
|
"}\n",
|
|
"\n",
|
|
"job = optimizer.run(**arguments)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "3548f6dc",
|
|
"metadata": {},
|
|
"source": [
|
|
"### 3. Retrieve the result\n",
|
|
"\n",
|
|
"Retrieve the result and map the solution bitstring back to the original graph nodes."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "169cbd6e",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"print(job.result())"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "7f22d66a",
|
|
"metadata": {},
|
|
"source": [
|
|
"The solution to the Maxcut problem is directly contained in the `solution` sub-dictionary of the result object"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "38309554",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"maxcut_solution = job.result()[\"solution\"]"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "19a664c4",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Example 3: Benchmark instances"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "98545ce3",
|
|
"metadata": {},
|
|
"source": [
|
|
"The benchmark instances are available on GitHub: [Kipu benchmark instances.](https://github.com/Kipu-Quantum-GmbH/benchmark-instances)\n",
|
|
"\n",
|
|
"The instances can be loaded using the `pygithub` library. To install it, run the following command:"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "1d8777e4",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"# %pip install pygithub"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e3a03447",
|
|
"metadata": {},
|
|
"source": [
|
|
"The paths for the benchmark instances are:\n",
|
|
"\n",
|
|
"**Maxcut:**\n",
|
|
"- `'maxcut/maxcut_28_nodes.json'`\n",
|
|
"- `'maxcut/maxcut_30_nodes.json'`\n",
|
|
"- `'maxcut/maxcut_32_nodes.json'`\n",
|
|
"- `'maxcut/maxcut_80_nodes.json'`\n",
|
|
"- `'maxcut/maxcut_100_nodes.json'`\n",
|
|
"- `'maxcut/maxcut_120_nodes.json'`\n",
|
|
"\n",
|
|
"**HUBO:**\n",
|
|
"- `'HUBO/hubo1_marrakesh.json'`\n",
|
|
"- `'HUBO/hubo2_marrakesh.json'`\n",
|
|
"\n",
|
|
"To reproduce the performance of the benchmark for the HUBO instances, select the backend `ibm_marrakesh` and set `direct_qubit_mapping` to `True` in the `options` sub-dictionary."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "adbed9be",
|
|
"metadata": {},
|
|
"source": [
|
|
"The following example runs the Maxcut instance with 32 nodes."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "da681a18",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from github import Github\n",
|
|
"import urllib\n",
|
|
"import json\n",
|
|
"import ast\n",
|
|
"\n",
|
|
"repo = \"Kipu-Quantum-GmbH/benchmark-instances\"\n",
|
|
"path = \"maxcut/maxcut_32_nodes.json\"\n",
|
|
"gh = Github()\n",
|
|
"repo = gh.get_repo(repo)\n",
|
|
"branch = \"main\"\n",
|
|
"file = repo.get_contents(urllib.parse.quote(path), ref=branch)\n",
|
|
"\n",
|
|
"# load json file with benchmark problem\n",
|
|
"problem_json = json.loads(file.decoded_content)\n",
|
|
"\n",
|
|
"# convert objective function to compatible format\n",
|
|
"objective_func = {\n",
|
|
" key: ast.literal_eval(value) for key, value in problem_json.items()\n",
|
|
"}\n",
|
|
"\n",
|
|
"\n",
|
|
"# Setup configuration to run the optimizer\n",
|
|
"options = {\n",
|
|
" \"shots\": 5_000,\n",
|
|
" \"num_iterations\": 5,\n",
|
|
" \"use_session\": True,\n",
|
|
" \"direct_qubit_mapping\": False,\n",
|
|
"}\n",
|
|
"\n",
|
|
"arguments = {\n",
|
|
" \"problem\": objective_func,\n",
|
|
" \"problem_type\": \"spin\",\n",
|
|
" \"backend_name\": \"ibm_brisbane\",\n",
|
|
" \"instance\": instance, # E.g. \"ibm-q/open/main\"\n",
|
|
" \"options\": options,\n",
|
|
"}\n",
|
|
"\n",
|
|
"job = optimizer.run(**arguments)\n",
|
|
"\n",
|
|
"result = job.result()"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "664476ff",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Use cases\n",
|
|
"\n",
|
|
"Typical use cases for the Optimization solver are combinatorial optimization problems. You can solve problems from many industries like finance, pharmaceutics, or logistics. Some examples follow.\n",
|
|
"* Portfolio optimization (QUBO): [scientific publication](https://doi.org/10.1103/PhysRevApplied.22.054037) and [white paper](https://kipu-quantum.com/zope64/kipu_2024/content/e3915/e3916/e4187/White-Paper-2-Financial-modeling-on-quantum-computers-using-digitally-compressed-algorithms-1.pdf)\n",
|
|
"* Protein folding (HUBO): [scientific publication](https://doi.org/10.1103/PhysRevApplied.20.014024)\n",
|
|
"* Logistics scheduling (QUBO): [scientific publication](https://doi.org/10.1103/PhysRevApplied.22.064068)\n",
|
|
"* Network optimization: [webinar](https://www.youtube.com/watch?v=w5SrCIK88No)\n",
|
|
"\n",
|
|
"If you are interested in tackling a specific use case and develop a dedicated mapping, we can assist you. [Contact us.](https://share-eu1.hsforms.com/2Ff8cgWvTR9ukT_fPoaNhDw2dqpz5)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e9ec2e67",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Get support\n",
|
|
"\n",
|
|
"To get support, please contact support@kipu-quantum.com."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "5a6a25c8",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Next steps\n",
|
|
"\n",
|
|
"[Request access to the Quantum Optimizer by Kipu Quantum](https://share-eu1.hsforms.com/2Ff8cgWvTR9ukT_fPoaNhDw2dqpz5)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "f73ef6c4",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Additional information"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "52b5221c",
|
|
"metadata": {},
|
|
"source": [
|
|
"Iskay, like our company name Kipu Quantum, is a Peruvian word. Although we are a startup from Germany, these words come from the native country of one of our co-founders, where the Quipu was one of the very first calculation machines developed by mankind 2000 years BCE."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"description": "Efficiently solve optimization problems with Kipu Quantum's Iskay Quantum Optimizer, available on the IBM Qiskit Functions Catalog",
|
|
"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"
|
|
},
|
|
"title": "Iskay Quantum Optimizer - A Qiskit Function by Kipu Quantum"
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|