QUBO formulation

Device: Dirac-1

Introduction

Quadratic Unconstrained Binary Optimization (QUBO) problems are a class of optimization problems where the goal is to maximize or minimize a quadratic objective function without any constraints on the decision variables. Furthermore, QUBO problems serve as fundamental building blocks for more complex optimization models that can address many real-world problems. This tutorial will go through why QUBOs are valuable, what they can do, and how to run such problems on QCi's Dirac entropy computing systems.

Importance

QUBO encodings tend to naturally arise in quantum settings, or any setting where variable interactions are directly encoded into physical interactions between bits. The reason for this is that physical interactions tend to naturally be two-body, while most constraints in computer science problems do not. For this reason, QUBOs are a natural underlying model to think about when using a wide variety of quantum optimization systems. Since QUBOs are formally NP-hard, it is technically possible to map any optimization problem to a QUBO. Efforts have been made to do so efficiently. For example, this work expresses many common problems as QUBOs with the aim of bridging to quantum technology. QUBOs can be used to construct the kinds of linear constraints often found in optimization problems. Since automatic handling of such constraints is often very useful, we have also developed a related model called Quadratic Linearly Constrained Binary Optimization (QLCBO), which is documented in this tutorial. This lesson however will focus on using the underlying unconstrained model.

Applications

QUBOs are fundamental in various fields, serving as a basis for formulating discrete combinatorial optimization problems. As an NP-hard problem, QUBO finds numerous applications across diverse domains, including machine learning, operations research, finance, chemistry, medicine, machine learning and beyond. A number of our tutorials and use cases use the QUBO representation directly:

• QBoost: A QUBO Based Binary Classification Method
• Max-Cut Demonstration using Dirac-1
• Dimensionality reduction
• Set Partitioning (A QUBO is sent to the device but linear constraints are constructed directly)

Mathematical Definition

A Quadratic Unconstrained Binary Optimization (QUBO) defined by second order interactions between binary variables with no constraints, 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 encode 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^{*} = \mathop{\arg \min}_{x} x^T Q x$.

Package Installation and Remote Connection

Begin by importing the necessary packages:

• numpy
• qci_client
• os

Establish connection with qci_client and QCi's server using your unique token ID and our default API URL.

Uploading 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.

Enter your file credentials, including the QUBO file.

Uploading

To upload the matrix encoded above in qubo_data, we use the qci_client imported previously. The following line

The response contains a file_id for the uploaded file. This id is provided when a job is run, along with 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. Triggering a job requires two items: first a job body that contains essential and optional metadata for the job, and second, the type of job a user wants to run.

Running a QUBO job

Job body

This section defines the job body for a QUBO job. Be sure to state the Dirac device of your choice under sampler_type and the number of samples nsamples required for your job.

Once the job_body is complete, use job_response to start running your job on the Dirac device.

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

Dissecting results

Under file_config, the job title and your results should be present in solutions.

process_job status

Here, we have the process_job presenting the timestamp of each step of the run process.

Dirac allocation balance = 0
Job submitted job_id='xxxxx'-: yyyy/mm/dd hh:mm:ss
queued: yyyy/mm/dd hh:mm:ss
running: yyyy/mm/dd hh:mm:ss
completed: yyyy/mm/dd hh:mm:ss
Dirac allocation balance = 0

job_response status

Details pertaining to the configuration of your job are presented here, including information about the job submitted, job_info, the device chosen, device_config, the status of the job repeated from process_job, job_status, and details of whether the job was completed or uncompleted, details.

{
  "job_info": {
    "job_id": "6601958b832ac38bab8fe27f",
    "job_submission": {
      "problem_config": {
        "quadratic_unconstrained_binary_optimization": {
          "qubo_file_id": "6601953438d25ec78cae8a65"
        }
      },
      "device_config": {
        "dirac-1": {
          "num_samples": 1
        }
      }
    },
    
    "job_status": {
      "submitted_at_rfc3339nano": "yyyy-mm-ddThh:mm:ss",
      "queued_at_rfc3339nano": "yyyy-mm-ddThh:mm:ss",
      "running_at_rfc3339nano": "yyyy-mm-ddThh:mm:ss",
      "completed_at_rfc3339nano": "yyyy-mm-ddThh:mm:ss"
    },
    "job_result": {
      "file_id": "660198fc38d25ec78cae8a67",
      "device_usage_s": 1
    },
    
    "details": {
      "status": "completed"
    }
  },
}

job_response results

Within the job_response we can identify the solutions, energies, and counts resulting from the job.

Solutions are the binary solutions of the polynomial function. Energies are values obtained by evaluating a polynomial function at each solution obtained from the optimization process. Counts are the number of times a solution was found among all the samples taken.

{
  "results": {
    "file_id": "660198fc38d25ec78cae8a67",
    "num_parts": 1,
    "num_bytes": 235,
    "file_config": {
      "quadratic_unconstrained_binary_optimization_results": {
        "counts": [1],
        "energies": [-3],
        "solutions": [[1, 1, 0]]
      }
    }
  }
}

Conclusion

Quadratic Unconstrained Binary Optimization (QUBO) problems are the underlying model used by many quadratic solvers, based on physical interactions being naturally quadratic. Understanding QUBOs is therefore key to understanding how to solve problems on quantum hardware. Sometimes a slightly higher level of abstraction including constraints may also be useful, such as QLCBO as explained in this tutorial. If you feel like you understand QUBOs and want to see how they are applied without engineering constraints, then we encourage you to look at one of the lessons linked above. If however, your application includes constraints, you may wish to proceed to the QLCBO tutorial. Of course, once you are ready, you should try our device with one of your own problems.