The goal of a quadratic unconstrained binary optimization (QUBO) problem is to find the values of the xi ∈ [0, 1] that minimize the quadratic pseudo-Boolean expression
where ai ∈ ℝ, and bi,j ∈ ℝ are given. There is always one minimum, but there can be more. For example, f(x) = 3x3 + x1x2 − 2x1x3 − 2x2x3 is minimized at {x1, x2, x3} = {0, 0, 0}, {0, 1, 0}, {1, 0, 0}, and {1, 1, 1}:
| x1 | x2 | x3 | f(x) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 3 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
A surprising number of problems can be expressed in this form, and it is the native input format for specialized computers based on classical or quantum annealing (such as the those developed by D-Wave Systems). One nice property of QUBOs is that they are additive in the sense that f(x) + g(x) is minimized at the intersection of the set of x where f(x) is minimized and the set of x where g(x) is minimized, assuming this intersection is non-empty.
The challenge that find-qubo addresses is the inverse problem: Given a set of x that should be minimized, return a corresponding f(x). What makes this difficult is that many problems are not directly solvable. In this case, additional ("ancillary") xi variables must be introduced to produce a valid f(x).
The importance of a tool like find-qubo is that it can be used to construct primitive QUBOs that can then be combined to formulate more complicated optimization problems.
Multiple implementations of find-qubo are provided in this repository:
| Tool | Language | Features | Non-standard dependencies |
|---|---|---|---|
find-qubo |
Go | Choice of fast heuristic or slow brute force, MPI parallelism | CLP |
find-qubo-pm |
Python | Faster than brute force | Ocean |
find-qubo-smt |
Python | Very fast on modest-sized problems | Z3 |
(In the above, pm stands for penalty model, and smt stands for satisfiability modulo theories.)
All three implementations iterate over the number of ancillary variables, first trying zero, then one, then two, and so forth. Each variable added makes the search for a solution exponentially slower. The first implementation, find-qubo, is the most experimental. It investigates a heuristic that often finds a solution extremely fast but may overlook a solution at a given number of ancillae and require more ancillae than necessary, becoming very slow. For comparison purposes, it also provides a brute-force mode, which can find either a single solution or a tally of all solutions (to gauge problem difficulty) and is extremely slow. find-qubo-smt is the most recent implementation and can be very fast on problems that do not contain too many variables.
find-qubo provides a Makefile for building find-qubo. Remove -tags mpi from the GOFLAGS line to disable support for MPI-based parallelism. find-qubo-pm and find-qubo-smt do not need to be compiled, but their dependencies must be met before they can run. Use the pip command to install dwave-ocean-sdk (for find-qubo-pm) or z3-solver (for find-qubo-smt).
All three implementations require the name of a file containing a truth table. (See the testcases directory for examples.) find-qubo accepts a large number of options, and find-qubo-smt accepts a few. Run with --help for information.
The following peer-reviewed publication introduces find-qubo:
Scott Pakin, "A Simple Heuristic for Expressing a Truth Table as a Quadratic Pseudo-Boolean Function". Proceedings of the 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), Broomfield, Colorado, USA, 17–22 October 2021, pp. 218–224. ISBN: 978-1-6654-1691-7, DOI: 10.1109/QCE52317.2021.00039.
Copyright © 2021 Triad National Security, LLC. All rights reserved.
This program was produced under U.S. Government contract 89233218CNA000001 for Los Alamos National Laboratory (LANL), which is operated by Triad National Security, LLC for the U.S. Department of Energy/National Nuclear Security Administration. All rights in the program are reserved by Triad National Security, LLC, and the U.S. Department of Energy/National Nuclear Security Administration. The Government is granted for itself and others acting on its behalf a nonexclusive, paid-up, irrevocable worldwide license in this material to reproduce, prepare derivative works, distribute copies to the public, perform publicly and display publicly, and to permit others to do so.
This program is open source under the BSD-3 License. Its LANL-internal identifier is C21038.
Scott Pakin, [email protected]
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent