# 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 $x^2 = x$ when $x \in \{0,1\}$, we can simplify the optimization expression as such $f(x) = \sum_{i} \sum_{j} J_{ij} x_i x_j$, where $f: \mathbb{B}^n \rightarrow \mathbb{R}$. Note that the coefficients naturally encodes as a square symmetric matrix, so that $f(x) = x^t Q x$, where $Q$ has entries $Q_{ij}$. The goal of the optimization problem is to find the binary vector, $x^{*}$, that minimizes $f(x)$,

$x^{*} = \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.