Zum Hauptinhalt springe

Iskay Quantum Optimizer - A Qiskit Function by Kipu Quantum

Nonig übersetzt

Di Siite isch nonig übersetzt worde. Dir luege d englischi Originalversion aa.

Note
  • Qiskit Functions are an experimental feature available only to IBM Quantum® Premium Plan, Flex Plan, and On-Prem (via IBM Quantum Platform API) Plan users. They are in preview release status and subject to change.

Overview​

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

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.

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.

Description​

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.

How does the Quantum Optimizer work?​

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.

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, 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.

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.

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.

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.

Workflow​

A schematic of the workflow of the Quantum Optimizer follows.

Workflow

By using the Quantum Optimizer, solving an optimization problem on quantum hardware can be reduced to

  • Formulate the objective function of the problem
  • Access the Optimizer via Qiskit Functions
  • Run the Optimizer and collect the result

Benchmarks​

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.

The following table includes the approximation ratio (AR), a metric defined as follows:

AR=C∗−CmaxCmin−Cmax,AR = \frac{C^{*} - C_\textrm{max}}{C_{\textrm{min}} - C_{\textrm{max}}},

where CC is the objective function, CminC_{\textrm{min}}, CmaxC_{\textrm{max}} are its minimum and maximum values, and C∗C^{*} is the cost of the best solution found, respectively. Therefore, AR=100% means that the ground state of the problem has been obtained.

ExampleNumber of qubitsApproximation RatioTotal time (s)Runtime usage (s)Total Number of shotsNumber of iterations
Unweighted MaxCut28100%1803030k5
Unweighted MaxCut30100%1803030k5
Unweighted MaxCut32100%1803030k5
Unweighted MaxCut80100%4806090k9
Unweighted MaxCut100100%3306060k6
Unweighted MaxCut120100%3706060k6
HUBO 1156100%60070100k10
HUBO 2156100%60070100k10
  • The MaxCut instances with 28, 30, and 32 qubits were run on ibm_sherbrooke. Instances with 80, 100, and 120 were run on a Heron r2 processor.
  • The HUBO instances were also run on a Heron r2 processor.

All the benchmark instances are accessible on GitHub (see Kipu benchmark instances). An example to run these instances can be found in Example 3: Benchmark instances.

Inputs and outputs​

Input​

See the following table for all input parameters the Quantum Optimizer accepts. The subsequent Options section goes into more details about the available options.

NameTypeDescriptionRequiredDefaultExample
problemDict[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 formatsYesN/A{"()": -21.0, "(0, 4)": 0.5,"(0, 2)": 0.5,"(0, 1)": 0.5,"(1, 3)": 0.5}
problem_typestrSpecify whether the problem coefficients are in binary (QUBO/HUBO) or spin format. The two possibilities are "spin" or "binary"YesN/A"spin"
backend_namestrName of the backend to make the queryYesN/A"ibm_fez"
optionsDict[str, Any]Options to handle the hardware submission, such as number of shots. For further details on the options configuration, see the Options sectionNoTo see the default values of the options configuration see the Options section{"shots": 5000, "num_iterations": 3, "use_session": True, "seed_transpiler": 42}

Accepted problem formats​

The problem and problem_type arguments encode an optimization problem of the form

min⁡(x1,x2,…,xn)∈DC(x1,x2,…,xn)\begin{align} \min_{(x_1, x_2, \ldots, x_n) \in D} C(x_1, x_2, \ldots, x_n) \nonumber \end{align}

where

C(x1,...,xn)=a+∑ibixi+∑i,jci,jxixj+...+∑k1,...,kmgk1,...,kmxk1...xkmC(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}
  • By choosing problem_type = "binary", you specify that the cost function is in binary format, which means that D={0,1}nD = \{0, 1\}^{n}, as in, the cost function is written in QUBO/HUBO formulation.
  • On the other hand, by choosing problem_type = "spin", the cost function is written in Ising formulation, where D={−1,1}nD = \{-1, 1\}^{n}.

The coefficients of the problem should be encoded in a dictionary as follows:

{"()":a,"(i,)":bi,"(i, j)":ci,j,⋮"(k1,...,km)":gk1,...,km,}\begin{align} \nonumber &\texttt{\{} \\ \nonumber &\texttt{"()"}&: \quad &a, \\ \nonumber &\texttt{"(i,)"}&: \quad &b_i, \\ \nonumber &\texttt{"(i, j)"}&: \quad &c_{i, j}, \\ \nonumber &\quad \vdots \\ \nonumber &\texttt{"(} k_1, ..., k_m \texttt{)"} &: \quad &g_{k_1, ..., k_m}, \\ \nonumber &\texttt{\}} \end{align}
  • Please note that the keys of the dictionary must be strings containing a valid tuple of non-repeating integers.

Options​

Iskay provides fine-tuning capabilities through optional parameters. While the defaults work well for most problems, you can customize the behavior for specific requirements:

ParameterTypeDefaultDescription
shotsint10000Quantum measurements per iteration (higher = more accurate)
num_iterationsint10Algorithm iterations (more iterations can improve solution quality)
use_sessionboolTrueUse IBM sessions for reduced queue times
seed_transpilerintNoneSet for reproducible quantum circuit compilation
direct_qubit_mappingboolFalseMap virtual qubits directly to physical qubits
job_tagsList[str]NoneCustom tags for job tracking
preprocessing_levelint0Problem preprocessing intensity (0-3) - see details below
postprocessing_levelint2Solution refinement level (0-2) - see details below
transpilation_levelint0Transpiler optimization trials (0-5) - see details below
transpile_onlyboolFalseAnalyze circuit optimization without running full execution

Preprocessing Levels (0-3): Specially important for larger problems that cannot currently fit on the coherence times of the hardware. Higher preprocessing levels achieve shallower circuit depths by approximations in the problem transpilation:

  • Level 0: Exact, longer circuits
  • Level 1: Good balance between accuracy and approximation, cutting out only the gates with angles in the lowest 10th percentile
  • Level 2: Slightly higher approximation, cutting out the gates with angles in the lowest 20th percentile and using approximation_degree=0.95 in the transpilation
  • Level 3: Maximum approximation level, cutting out the gates in the lowest 30th percentile and using approximation_degree=0.90 in the transpilation

Transpilation Levels (0-5): Control the advanced transpiler optimization trials for quantum circuit compilation. This can lead to an increase in classical overhead, and for some cases it might not change the circuit depth. The default value 2 in general leads to the smallest circuit and is relatively fast.

  • Level 0: Optimization of the decomposed DCQO circuit (layout, routing, scheduling)
  • Level 1: Optimization of PauliEvolutionGate and then the decomposed DCQO circuit (max_trials=10)
  • Level 2: Optimization of PauliEvolutionGate and then the decomposed DCQO circuit (max_trials=15)
  • Level 3: Optimization of PauliEvolutionGate and then the decomposed DCQO circuit (max_trials=20)
  • Level 4: Optimization of PauliEvolutionGate and then the decomposed DCQO circuit (max_trials=25)
  • Level 5: Optimization of PauliEvolutionGate and then the decomposed DCQO circuit (max_trials=50)

Postprocessing Levels (0-2): Control how much classical optimization, compensating for bit-flip errors with different number of greedy passes of a local search:

  • Level 0: 1 pass
  • Level 1: 2 passes
  • Level 2: 3 passes

Transpile-only mode: Now available for users who want to analyze circuit optimization without running the full quantum algorithm execution.

Custom configuration example: Here's how you might configure Iskay with different settings:

# Added by doQumentation — required packages for this notebook
!pip install -q PyGithub networkx qiskit-ibm-catalog
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": ["custom_config"],  # Custom tracking tags
}

Seed optimization: Note that seed_transpiler is set to None by default. This enables the transpiler's automatic optimization process. When None, the system will start a trial with multiple seeds and select the one that produces the best circuit depth, leveraging the full power of the max_trials parameter for each transpilation level.

Transpilation level performance: Increasing the number of max_trials with higher values for transpilation_level will unavoidably increase the transpilation time, but it might not always change the final circuit - this depends heavily on the specific circuit structure and complexity. For some circuits/problems, however, the difference between 10 trials (level 1) and 50 trials (level 5) can be dramatic, so exploring these parameters might be the key to successfully finding a solution.

Output​

NameTypeDescriptionExample
resultDict[str, Any]Solution and metadata. Structure varies based on transpile_only option.See "Result dictionary contents" below

Result dictionary contents​

The result dictionary structure depends on the execution mode:

FieldTypeModeDescriptionExample
solutionDict[str, int]StandardThe sorted mapped solution where keys are variable indices (as strings) sorted numerically and values are the corresponding variable values (1/-1 for spin problems, 1/0 for binary problems).{'0': -1, '1': -1, '2': -1, '3': 1, '4': 1}
solution_infoDict[str, Any]StandardDetailed information about the solution (see details below){'bitstring': '11100', 'cost': -13.8, 'seed_transpiler': 42, 'mapping': {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}}
prob_typestrStandardThe type of optimization problem ('spin' or 'binary')'spin'
transpilation_infoDict[str, Any]Transpile-onlyCircuit analysis and transpilation details (see details below){'best_seed': 42, 'transpilation_time_seconds': 50.06, 'transpiled_circuit': {'depth': 576, 'gate_count': 4177, 'num_qubits': 156, 'width': 176, 'operations': {'sx': 1325, 'rx': 891, 'cz': 783, 'rz': 650, 'rzz': 466, 'x': 42, 'measure': 20}}}

Standard execution​

When the optional parameter transpile_only=False:

solution_info dictionary:

  • "bitstring" (str): The raw bitstring representation of the solution.
  • "cost" (float): The cost/energy value associated with the solution.
  • "seed_transpiler" (int): The random seed used for the transpiler that produced this result.
  • "mapping" (Dict[int, int]): The original qubit-to-variable mapping used in the computation.
  • "qpu_time" (float, optional): The QPU execution time in seconds.

Variable mapping notes:

  • 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→−1,0→11 \rightarrow -1, \quad 0 \rightarrow 1.
  • Keys in the solution dictionary are variable indices sorted numerically as strings.

Transpilation analysis​

When the optional parameter transpile_only=True:

transpilation_info dictionary:

  • "best_seed" (int): The optimal seed found for transpilation
  • "transpilation_time_seconds" (float): Time taken for transpilation process
  • "transpiled_circuit" (Dict): Circuit analysis containing:
    • "depth" (int): Circuit depth (number of layers)
    • "gate_count" (int): Total number of gates in the circuit
    • "num_qubits" (int): Number of qubits used
    • "width" (int): Circuit width
    • "operations" (Dict[str, int]): Count of each gate type used

Transpile-only mode usage:

  • Available for users who want to analyze circuit optimization without running the full quantum algorithm execution.
  • Useful for circuit analysis, depth optimization studies, and understanding transpilation effects before committing to full execution.

Get started​

In this documentation, we will go through the steps of using the Iskay Quantum Optimizer. In the process we will quickly show how to load the function from the catalog and how to convert your problem to a valid input, all while showing how you can experiment with different optional parameters.

For a more detailed example, please check out the tutorial Solve the Market Split problem with Kipu Quantum's Iskay Quantum Optimizer, where we work through the whole process of using Iskay Solver to address the Market Split problem, which represents a real-world resource allocation challenge where markets must be partitioned into balanced sales regions to meet exact demand targets.

Authenticate using your API key, found on the IBM Quantum Platform dashboard, and select the Qiskit Function as follows:

# ruff: noqa: F821
hinwiis

The following code assumes that you have saved your credentials. If you have not, follow the instructions in save your IBM Cloud account to authenticate with your API key.

from qiskit_ibm_catalog import QiskitFunctionsCatalog

catalog = QiskitFunctionsCatalog(
    channel="ibm_quantum_platform",
    instance="INSTANCE_CRN",
    token="YOUR_API_KEY",  # Use the 44-character API_KEY you created and saved from the IBM Quantum Platform Home dashboard
)

# Access Function
optimizer = catalog.load("kipu-quantum/iskay-quantum-optimizer")

Example 1: Simple cost function​

Consider the cost function in spin formulation:

C(x0,x1,x2,x3,x4)=1+1.5x0+2x1+1.3x2+2.5x0x3+3.5x1x4+4x0x1x2C(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

where (x0,...,x4)∈{−1,1}5(x_0, ..., x_4) \in \{-1, 1\}^5.

The solution to this simple cost function is

(x0,x1,x2,x3,x4)=(−1,−1,−1,1,1)(x_0, x_1, x_2, x_3, x_4) = (-1, -1, -1, 1, 1)

with minimum value C∗=−6C^{*} = -6

1. Create the objective function​

We start by creating a dictionary with the coefficients of the objective function as follows:

objective_func = {
    "()": 1,
    "(0,)": 1.5,
    "(1,)": 2,
    "(2,)": 1.3,
    "(0, 3)": 2.5,
    "(1, 4)": 3.5,
    "(0, 1, 2)": 4,
}

2. Run the Optimizer​

We solve the problem by running the optimizer. Since (x0,...,x4)∈{−1,1}5(x_0, ..., x_4) \in \{-1, 1\}^5 we must set problem_type=spin.

# Setup options to run the optimizer
options = {"shots": 5000, "num_iterations": 5, "use_session": True}

arguments = {
    "problem": objective_func,
    "problem_type": "spin",
    "backend_name": backend_name,  # such as "ibm_fez"
    "options": options,
}

job = optimizer.run(**arguments)

3. Retrieve the result​

The solution of the optimization problem is provided directly from the optimizer.

print(job.result())

This will show a dictionary of the form:

{'solution': {'0': -1, '1': -1, '2': -1, '3': 1, '4': 1},
 'solution_info': {'bitstring': '11100',
  'cost': -13.8,
  'seed_transpiler': 42,
  'mapping': {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}},
 'prob_type': 'spin'}

Notice that the dictionary solution displays the result vector (x0,x1,x2,x3,x4)=(−1,−1,−1,1,1)(x_0, x_1, x_2, x_3, x_4) = (-1, -1, -1, 1, 1).

Example 2: MaxCut​

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.

To run this example you must install the networkx package in addition to the qiskit-ibm-catalog. To install it, run the following command:

# %pip install networkx numpy

1. Create the objective function​

Start by generating a random 3-regular graph. For this graph, we define the objective function of the MaxCut problem.

import networkx as nx

# Create a random 3-regular graph
G = nx.random_regular_graph(3, 10, seed=42)

# Create the objective function for MaxCut in Ising formulation
def graph_to_ising_maxcut(G):
    """
    Convert a NetworkX graph to an Ising Hamiltonian for the Max-Cut problem.
    Args:
        G (networkx.Graph): The input graph.
    Returns:
        dict: The objective function of the Ising model
    """
    # Initialize the linear and quadratic coefficients
    objective_func = {}
    # Populate the coefficients
    for i, j in G.edges:
        objective_func[f"({i}, {j})"] = 0.5
    return objective_func

objective_func = graph_to_ising_maxcut(G)

2. Run the Optimizer​

Solve the problem by running the optimizer.

options = {"shots": 5000, "num_iterations": 5, "use_session": True}

arguments = {
    "problem": objective_func,
    "problem_type": "spin",
    "backend_name": backend_name,  # such as "ibm_fez"
    "options": options,
}

job = optimizer.run(**arguments)

3. Retrieve the result​

Retrieve the result and map the solution bitstring back to the original graph nodes.

print(job.result())

The solution to the Maxcut problem is directly contained in the solution sub-dictionary of the result object

maxcut_solution = job.result()["solution"]

Example 3: Benchmark instances​

The benchmark instances are available on GitHub: Kipu benchmark instances.

The instances can be loaded using the pygithub library. To install it, run the following command:

# %pip install pygithub

The paths for the benchmark instances are:

Maxcut:

  • 'maxcut/maxcut_28_nodes.json'
  • 'maxcut/maxcut_30_nodes.json'
  • 'maxcut/maxcut_32_nodes.json'
  • 'maxcut/maxcut_80_nodes.json'
  • 'maxcut/maxcut_100_nodes.json'
  • 'maxcut/maxcut_120_nodes.json'

HUBO:

  • 'HUBO/hubo1_marrakesh.json'
  • 'HUBO/hubo2_marrakesh.json'

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. The following example runs the Maxcut instance with 32 nodes.

from github import Github
import urllib
import json
import ast

repo = "Kipu-Quantum-GmbH/benchmark-instances"
path = "maxcut/maxcut_32_nodes.json"
gh = Github()
repo = gh.get_repo(repo)
branch = "main"
file = repo.get_contents(urllib.parse.quote(path), ref=branch)

# load json file with benchmark problem
problem_json = json.loads(file.decoded_content)

# convert objective function to compatible format
objective_func = {
    key: ast.literal_eval(value) for key, value in problem_json.items()
}

# Setup configuration to run the optimizer
options = {
    "shots": 5_000,
    "num_iterations": 5,
    "use_session": True,
    "direct_qubit_mapping": False,
}

arguments = {
    "problem": objective_func,
    "problem_type": "spin",
    "backend_name": "ibm_brisbane",
    "options": options,
}

job = optimizer.run(**arguments)

result = job.result()

Use cases​

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.

If you are interested in tackling a specific use case and develop a dedicated mapping, we can assist you. Contact us.

Get support​

For support, contact support@kipu-quantum.com.

Next steps​

Additional information​

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.