QLCBO formulation

Device: Dirac-1

Introduction

Quadratic Linearly Constrained Binary Optimization, or QLCBO, is a fundamental building block for optimizing where the primary goal is maximizing or minimizing a function that has both quadratic terms (involving pairwise products of decision variables) and linear constraints (applied to sums of terms). Furthermore, QLCBO problems serve as fundamental building blocks for more complex optimization models that can address many real world problems. This tutorial will go through why QLCBOs are valuable, what they can do, and how to run such problems on QCi's Dirac entropy computing systems.

Importance

In general, the QLCBO formulation allows a combination of the types of constraints that more typically appear in traditional computer science, as well as quadratic terms that naturally arise in physics-based hardware such as ours. Note that if the $O$ $O$ matrix is diagonal then QLCBO reduces to standard binary linear programming, but the off-diagonal terms allow the quadratic interactions that are native to our device to be added. This could be useful for example if formulating a quadratic knapsack problem with a global constraint on weights but a quadratic objective function. Terms of this form tend to arise because physical interactions are naturally two-body. By providing a way to effectively use a binary linear programming problem as a starting point, the QLCBO formulation allows a natural way to start with an existing model and then add complexity. This may correspond to the kind of quadratic terms on which systems like ours excel, and provide a bridge from a linear programming setting that may be more familiar to some of our users to a quadratic setting that is more natural for quantum hardware.

Applications

Because of its versatility and the sample constraint function, our software implementation of QLCBO is the workhorse of many tutorial examples using Dirac-1, and is likely to be the same for many of your use cases. The following tutorials and use cases rely on constructing a QLCBO problem:

Portfolio Optimization
Quadratic Assignment Problem
Feature Selection
Travelling Salesperson
Set Partitioning (A QUBO is sent to the device, but linear constraints are used)

Mathematical Definition

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, $O$ $O$ , of dimension $n \times n$ $n \times n$ , and a set of $m$ $m$ constraints, represented by the matrix $A$ $A$ , with dimension $m \times n$ $m \times n$ and right-hand side vector $b$ $b$ of length $m$ $m$ . We want to combine them into a QUBO, which can be defined as $Q = O + \alpha (A^T A-2\mathrm{diag}(b^TA))$ $Q = O + α (A^{T} A - 2 diag (b^{T} A))$ , where $\alpha \in \mathbb{R}$ $α \in R$ . At this point, we can find an optimal solution, $x^{*} = \min_{x} x^T Q x$ $x^{*} = 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, but 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,$ $- 3 x y + x z,$ subject to the constraints $x + z = 1$ $x + z = 1$ and $2x + 2y= 2$ $2 x + 2 y = 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 $\mathbf{A}\vec{x}$ $A x$ = $\vec{b}$ $b$ → $\mathbf{A}\vec{x}$ $A x$ - $\vec{b}$ $b$ = 0.

Uploading and file_id's

First, import the necessary packages:

In [1]:

import os
import numpy as np
from qci_client import QciClient

In [2]:

# The following gets your access token from the os envirinment, if configured.
# It is preferable to configure that way, but you may also specify in code otherwise
# see the Quick Start on Cloud tutorial at 
#   https://quantumcomputinginc.com/learn/tutorials-and-use-cases/quick-start-on-cloud
# to learn how to set the environment variables
token = os.environ.get("QCI_TOKEN", None)
if token is None:
    # environment variables not configured
    api_url = "https://api.qci-prod.com"
    token = "REPLACE WITH YOUR TOKEN"
    qclient = QciClient(url=api_url, api_token=token)
else:
    qclient = QciClient()

Formation

For the equation above, $\mathbf{A}\vec{x}$ $A x$ - $\vec{b}$ $b$ = 0, we will break it down into an objective function and constraints.

→ $\mathbf{A}$ $A$ as the objective function, obj
→ $\vec{b}$ $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(file=qlcbo_constraints)
file_id_constraints = response_json["file_id"]
response_json = qclient.upload_file(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:

Building a job body to submit.
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={"num_samples": 1, "alpha": 2, "device_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': '664e6d9798263204a3659050',
 '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_response

Out [ ]:

2024-05-22 16:11:36 - Dirac allocation balance = 0 s (unmetered)
2024-05-22 16:11:36 - Job submitted: job_id='664e6d98a3e6a645a5c4d479'
2024-05-22 16:11:36 - QUEUED
2024-05-22 16:11:38 - RUNNING
2024-05-22 16:11:49 - COMPLETED
2024-05-22 16:11:51 - Dirac allocation balance = 0 s (unmetered)

Out [11]:

{'job_info': {'job_id': '664e6d98a3e6a645a5c4d479',
  'job_submission': {'problem_config': {'quadratic_linearly_constrained_binary_optimization': {'constraints_file_id': '664e6d9798263204a3659050',
     'objective_file_id': '664e6d9798263204a3659052',
     'alpha': 2,
     'atol': 1e-10}},
   'device_config': {'dirac-1': {'num_samples': 1}}},
  'job_status': {'submitted_at_rfc3339nano': '2024-05-22T22:11:36.179Z',
   'queued_at_rfc3339nano': '2024-05-22T22:11:36.179Z',
   'running_at_rfc3339nano': '2024-05-22T22:11:36.677Z',
   'completed_at_rfc3339nano': '2024-05-22T22:11:46.529Z'},
  'job_result': {'file_id': '664e6da298263204a3659054', 'device_usage_s': 10}},
 'status': 'COMPLETED',
 'results': {'counts': [1],
  'energies': [-10],
  'feasibilities': [True],
  'objective_values': [0],
  'solutions': [[1, 0, 0]]}}

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

In [12]:

def error_status(job_response):
    try:
        if job_response['status'] == "ERROR":
            return job_response['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 [12]:

'No errors detected'

Conclusion

In this tutorial, we have shown how to make use of the quadratic linearly constrained optimization formulation of problems. By combining quadratic objective functions with linear constraints, QLCBOs provide a powerful and versatile setting for formulating problems. These problems act as a workhorse for many of our other examples and prove to be particularly valuable as the problem size increases. If you feel comfortable with the QLCBO formulation and want to go further, a good next step is to see how it works in practice through the tutorials listed in this module. Another alternative would be to work through examples using the unconstrained version QUBO. Of course, you could also try out some of your own problems.