Beginner Tutorial 1 - How to generate the QUBO matrix#

Introduction#

In this tutorial, we will take the maximum cut problem as an example to illustrate how to use the Kaiwu SDK to build the corresponding QUBO (Quadratic Unconstrained Binary Optimization) model and generate the QUBO matrix.

QUBO Modeling#

Take an undirected map for example. In graph G(V, E), V stands for graph vertices. E stands for figure edge set. w is the adjacency matrix of the graph. For i,j \in V, w_{ij} indicates whether there is an edge from vertex i to vertex j, if there is a connecting edge: 1, if not: 0. Vertex i is represented by the decision variable x_i , its possible values indicating its classifications are \{0, 1\}, indicateing the vertices i is divided into class A or class B respectively.

Then, in the given undirected graph, the number of edges corresponding to the cuts that splits all vertices into two groups is Z, and the model is expressed as:

\max Z= \sum_{(i,j)\in E}{(x_{i}+x_{j}-2x_{i}x_{j})}

Modeling Code#

Input the Matrix#

import numpy as np
import kaiwu as kw
import pandas as pd

# Define the input adjacency matrix for the graph
adj_matrix = np.array([
                [0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
                [1, 0, 1, 0, 0, 1, 1, 1, 0, 0],
                [0, 1, 0, 1, 1, 0, 0, 0, 1, 0],
                [1, 0, 1, 0, 0, 1, 1, 0 ,1, 0],
                [1, 0, 1, 0, 0, 1, 0, 1, 0, 1],
                [0, 1, 0, 1, 1, 0, 0, 0, 1, 1],
                [0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
                [1, 1, 0, 0, 1, 0, 0, 0, 1, 0],
                [1, 0, 1, 1, 0, 1, 0, 1, 0, 1],
                [0, 0, 0, 0, 1, 1, 1, 0, 1, 0]])

# Get the number of nodes in the graph
num_nodes = len(adj_matrix)

# Create a QUBO variable array 'x' with 'num_nodes' variables
# each representing a node in the graph
x = kw.qubo.ndarray(num_nodes,'x',kw.qubo.Binary)

# Define the objective function for the QUBO model of Max cut problem
obj = -x.T @ adj_matrix @ (1-x)

# parse QUBO
obj = kw.qubo.make(obj)

# Extract the QUBO matrix and store it in a pandas DataFrame
qubo_matrix = kw.qubo.qubo_model_to_qubo_matrix(obj)['qubo_matrix']

# Check whether the QUBO matrix satisfy the precision requirement
kw.qubo.check_qubo_matrix_bit_width(qubo_matrix)

# Save the QUBO matrix to a CSV file without including index or header
df = pd.DataFrame(qubo_matrix)
csv_file_path = 'qubo_matrix.csv'
df.to_csv(csv_file_path,index=False,header=False)