Qatalyst
Get Started

Quadratic Linearly Constrained Binary Optimization

Introduction

Quadratic Unconstrained Binary Optimization (Qubo) problems can be formulated from a square, symmetric objective function and a matrix of binary constraints. Suppose we are given an objective function, OO, of dimension n×nn \times n, and a set of mm constraints, represented by the matrix AA, with dimension m×nm \times n and right hand side vector bb of length mm. We want to combine them into a Qubo, which can be defined Q=O+α(ATA−2diag(bTA))Q = O + \alpha (A^T A-2\mathrm{diag}(b^TA)), where α∈R\alpha \in \mathbb{R}. At this point, we can find an optimal solution,
x∗=min⁡xxTQxx^{*} = \min_{x} x^T Q x.
The parameter α\alpha plays an important role in guaranteeing that the constraints are satisfied. We will not go into more detail on this page.
We will define a simple problem on the Upload tab and show how to upload the components. The examples on the Running tab will describe how to run the a constraint problem.
Suppose the original problem we want to minimize is
−3xy+xz,-3xy + xz,
subject to the constraints x+z=1x + z = 1 and 2x+2y=22x + 2y= 2.
There are three matrix components that can be associated with to a constraint problem of this type. The objective function in matrix form, the linear constraints matrix, and an optional right hand side (RHS) representing the linear constraints themselves. This can optionally be appended to the last column of the aforementioned constraints matrix. We will describe them and their upload formats in what follows.
The objective matrix is written
1234
import numpy as np
obj = np.array([[ 0. , -1.5,  0.5],
                [-1.5,  0. ,  0. ],
                [ 0.5,  0. ,  0. ]]).
The constraints take the form
12
A = np.array([[1, 0, 1],
              [2, 2, 0]])
and an explicit RHS vector can be represented as
12
rhs = np.array([[1],
                [2]]).

API format

We encode the above in a sparse dictionary format for the upload step to the API:

Objective

It is essential to label the file_type value as "objective":
1234567891011121314151617181920212223242526
{
    "data": [
        {
            "i": 1,
            "j": 0,
            "val": -1.5
        },
        {
            "i": 2,
            "j": 0,
            "val": 0.5
        },
        {
            "i": 0,
            "j": 1,
            "val": -1.5
        },
        {
            "i": 0,
            "j": 2,
            "val": 0.5
        }
    ],
    "file_name": "smallest_objective.json",
    "num_variables": 3,
    "file_type": "objective"}

Constraints

Similarly, the file_type must be labels as "constraints" for the constraints matrix.
123456789101112131415161718192021222324252627
{
    "data": [
        {
            "i": 0,
            "j": 0,
            "val": 1.0
        },
        {
            "i": 1,
            "j": 0,
            "val": 2.0
        },
        {
            "i": 1,
            "j": 1,
            "val": 2.0
        },
        {
            "i": 0,
            "j": 2,
            "val": 1.0
        }
    ],
    "file_name": "smallest_constraints.json",
    "num_constraints": 2,
    "num_variables": 3,
    "file_type": "constraints"}

RHS

Similarly, file_type should be "rhs" for the optional RHS vector.
12345678
{
    "data": [
        1.0,
        2.0
    ],
    "file_name": "smallest_rhs.json",
    "file_type": "rhs",
    "num_constraints": 2}

Uploading and file_id's

First, import the necessary packages:
123
import json
from qci_client import QciClient
qci = QciClient()
Now we can upload the various files using the client. Suppose we store the data in a variable data. Then we call upload_file to push the data to the server.
12
response_json = qci.upload_file(constraints_data)
file_id = response_json["file_id"]
We can extract the file_id for later use. Triggering a job to run requires the file_id to tell the backend which data to use. We cover this step in the Running tab.

Contents