QUBOTools.jl

Tools for Quadratic Unconstrained Binary Optimization models in Julia

Introduction

The QUBOTools.jl package implements codecs for QUBO (Quadratic Unconstrained Binary Optimization) instances. Its purpose is to provide fast and reliable conversion between common formats used to represent such problems. This allows for rapid leverage of many emergent computing architectures whose job is to solve this kind of optimization problem.

The term QUBO is widely used when referring to boolean problems of the form

$$\begin{array}{rl} \min & \mathbf{x}'\ Q\ \mathbf{x} \\ \text{s.t.} & \mathbf{x} \in \mathbb{B}^{n} \end{array}$$

with symmetric $Q \in \mathbb{R}^{n \times n}$. Nevertheless, this package also fully supports Ising Models, given by

$$\begin{array}{rl} \min & \mathbf{s}'\ J\ \mathbf{s} + \mathbf{h}'\ \mathbf{s} \\ \text{s.t.} & \mathbf{s} \in \left\lbrace-1, 1\right\rbrace^{n} \end{array}$$

where $J \in \mathbb{R}^{n \times n}$ is triangular and $\mathbf{h} \in \mathbb{R}^{n}$.

Getting Started

Installation

import Pkg

Pkg.add("QUBOTools")

Basic Usage

using QUBOTools

model = QUBOTools.read_model("problem.json")

QUBOTools.write_model("problem.qubo", model)

Supported Formats

The r and w marks indicate that reading and writing modes are available for the corresponding file format, respectively.

BQPJSON rw

The BQPJSON format was designed at LANL-ANSI to represent Binary Quadratic Programs in a platform-independet fashion. This is accomplished by using .json files validated using a well-defined JSON Schema.

QUBO rw

The QUBO specification appears as the input format in many of D-Wave's applications. A brief explanation about it can be found in qbsolv's repository README.

Qubist rw

This is the simplest of all current supported formats.

MiniZinc rw

MiniZinc is a constraint modelling language that can be used as input for many solvers.

HFS w

HFS is a very low-level mapping of weights to D-Wave's chimera graph.

PSR Quantum Optimization Toolchain