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 as Q=O+α(ATA2diag(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=minxxTQxx^{*} = \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. 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.

Uploading

There are three matrix components that can be associated with a constraint problem of this type. The objective function in matrix form, the linear constraints matrix, and the right-hand side (RHS) represent the linear constraints themselves. The format should follow the transformation from Ax\mathbf{A}\vec{x} = b\vec{b}Ax\mathbf{A}\vec{x} - b\vec{b} = 0.

Uploading and file_id's

First, import the necessary packages:

In [1]:

import numpy as np
from qci_client import QciClient

In [2]:

token = "token_here"
api_url = "https://api.qci-prod.com"
qclient = QciClient(api_token=token, url=api_url)

Formation

For the equation above, Ax\mathbf{A}\vec{x} - b\vec{b} = 0, we will break it down into an objective function and constraints. A\mathbf{A} as the objective function, obj b\vec{b} as the constraints (b & rhs)

In [3]:

obj = np.array([[ 0. , -1.5, 0.5],
[-1.5, 0. , 0. ],
[ 0.5, 0. , 0. ]])

The constraints take the form and an explicit RHS vector can be represented as

In [4]:

b = np.array([[1, 0, 1],
[2, 2, 0]])
rhs = -(np.array([[1],
[2]]))
b, rhs

Out [4]:

(array([[1, 0, 1],
        [2, 2, 0]]),
 array([[-1],
        [-2]]))

In [5]:

constraints = np.hstack((b, rhs))
constraints

Out [5]:

array([[ 1,  0,  1, -1],
       [ 2,  2,  0, -2]])

Concatenate your objective function and constraints into two dictionaries:

In [6]:

qlcbo_obj = {
'file_name': "smallest_objective.json",
'file_config': {'objective':{"data": obj, "num_variables": 3}}
}

In [7]:

qlcbo_constraints = {
"file_name": "smallest_constraints.json",
"file_config": {'constraints':{"data": constraints,
"num_constraints": 2,
"num_variables": 3}}
}

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.

In [8]:

response_json = qclient.upload_file(qlcbo_constraints)
file_id_constraints = response_json["file_id"]
response_json = qclient.upload_file(qlcbo_obj)
file_id_obj = 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 Section.

Running

Running a job involves two key steps to build parameters for the job:

  1. Building a job body to submit.
  2. Providing a job_type.

Building the job_body

The job_body is a dictionary that contains the file_id's and parameter data for running the job. All job bodies must contain the following data fields, which can be leveraged by the user to track jobs.

It is easiest to use qci.build_job_body() to construct a job_body.

In [9]:

job_body = qclient.build_job_body(
job_type="sample-constraint",
job_params={"nsamples": 40, "alpha": 2, "sampler_type": "dirac-1"},
constraints_file_id=file_id_constraints,
objective_file_id=file_id_obj)

In [10]:

qclient.download_file(file_id=file_id_constraints)

Out [10]:

{'file_id': '660d9ad238d25ec78cae9eac',
 'num_parts': 1,
 'num_bytes': 373,
 'file_name': 'smallest_constraints.json',
 'file_config': {'constraints': {'num_constraints': 2,
   'num_variables': 3,
   'data': [{'i': 0, 'j': 0, 'val': 1},
    {'i': 0, 'j': 2, 'val': 1},
    {'i': 0, 'j': 3, 'val': -1},
    {'i': 1, 'j': 0, 'val': 2},
    {'i': 1, 'j': 1, 'val': 2},
    {'i': 1, 'j': 3, 'val': -2}]}}}

This returns a job_body with the file_id fields appended to the above dictionary. Each of these file_id's was obtained after uploading the corresponding file in the Uploading section. Now we can trigger a job using the following command:

In [11]:

job_response = qclient.process_job(job_body=job_body, job_type="sample-constraint")
job_response

Out [ ]:

Dirac allocation balance = 0 s (unmetered)
Job submitted job_id='660d9ad5f984e6c4496610ad'-: 2024/04/03 14:07:17
RUNNING: 2024/04/03 14:07:18
COMPLETED: 2024/04/03 14:16:21
Dirac allocation balance = 0 s (unmetered)

Out [11]:

{'job_info': {'job_id': '660d9ad5f984e6c4496610ad',
  'job_submission': {'problem_config': {'quadratic_linearly_constrained_binary_optimization': {'constraints_file_id': '660d9ad238d25ec78cae9eac',
     'objective_file_id': '660d9ad338d25ec78cae9eae',
     'alpha': 2,
     'atol': 1e-10}},
   'device_config': {'dirac-1': {'num_samples': 40}}},
  'job_status': {'submitted_at_rfc3339nano': '2024-04-03T18:07:17.035Z',
   'queued_at_rfc3339nano': '2024-04-03T18:07:17.035Z',
   'running_at_rfc3339nano': '2024-04-03T18:07:17.304Z',
   'completed_at_rfc3339nano': '2024-04-03T18:16:21.174Z'},
  'job_result': {'file_id': '660d9cf538d25ec78cae9eb8', 'device_usage_s': 79},
  'details': {'status': 'COMPLETED'}},
 'results': {'file_id': '660d9cf538d25ec78cae9eb8',
  'num_parts': 1,
  'num_bytes': 362,
  'file_config': {'quadratic_linearly_constrained_binary_optimization_results': {'counts': [23,
     17],
    'energies': [-10, -10],
    'feasibilities': [True, True],
    'objective_values': [0, 0],
    'solutions': [[1, 0, 0], [0, 1, 1]]}}}}

Below we show how to query the result object if an error occurs:

In [13]:

def error_status(job_response):
try:
if job_response['job_info']['details']['status'] == "ERROR":
return job_response['job_info']['details']['status'], job_response['job_info']['results']['error']
else:
return "No errors detected"
except KeyError:
return "Error: Unable to retrieve error status information from the job response"
error_status(job_response)

Out [13]:

'No errors detected'