Qatalyst
Get Started

Quadratic Unconstrained Binary Optimization (QUBO)

Introduction

The Quadratic Unconstrained Binary Optimization (QUBO) is a foundational problem type used in many fields to formulate discrete combinatorial optimization problems. Generically, a Qubo is defined by linear and quadratic terms, but since x2=xx^2 = x when x∈{0,1}x \in \{0,1\}, we can simplify the optimization expression as such f(x)=∑i∑jJijxixjf(x) = \sum_{i} \sum_{j} J_{ij} x_i x_j, where f:Bn→Rf: \mathbb{B}^n \rightarrow \mathbb{R}. Note that the coefficients naturally encodes as a square symmetric matrix, so that f(x)=xtQxf(x) = x^t Q x, where QQ has entries QijQ_{ij}. The goal of the optimization problem is to find the binary vector, x∗x^{*}, that minimizes f(x)f(x),
x∗=min⁡xxtQxx^{*} = \min_{x} x^t Q x.

Running a QUBO job

Data format

To upload a square symmetric matrix or Qubo, we encode it in a sparse matrix format as shown below. We use Numpy array notation.
1
Q = np.array([[0, -1.5, 0.5], [-1.5, 0, 0], [0.5, 0, 0]]) ,
then the JSON will take the following list of dictionary sparse matrix format: {(i,j): value}
123456789101112131415161718192021222324252627
qubo_data = {
  "data": [
    {
      "i": 0,
      "j": 1,
      "val": -1.5
    },
    {
      "i": 0,
      "j": 2,
      "val": 0.5
    },
    {
      "i": 1,
      "j": 0,
      "val": -1.5
    },
    {
      "i": 2,
      "j": 0,
      "val": 0.5
    }
  ],
  "file_name": "smallest_objective.json", # can be any short string
  "num_variables": 3, # number of rows
  "file_type": "qubo" # defines the data type, 'qubo' in this case
}

Uploading

To upload the matrix encoded above in `qubo_data`, we use the the `qci_client` imported previously. The following line
1
response_json = qci.upload_file(qubo_data)
The response contains a file_id for the uploaded file. This id is provided when a job is run, along a few other parameters (see #Running). Note: the same `file_id` can be used multiple times to run a problem repeatedly. This enables an "upload once, run many times" scheme, which is especially useful for job types in which parameter searches may be involved.

Contents