jrnl · home about list my companies

## # List of QUBO formulations

Below a list of 48 optimization problems and a reference to the QUBO formulation of each problem is shown. While a lot of these problems are classical optimization problems from mathematics (also mostly NP-hard problems), there are interestingly already formulations for Machine Learning, such as the L1 norm or linear regression. Graph based optimization problems often encode the graph structure (adjacency matrix) in the QUBO, while others, such as Number Partitioning or Quadratic Assignment encode the problem matrices s.t. a non-linear system of equations can be found in the QUBO. The quadratic unconstrained binary optimization (QUBO) problem itself is a NP-hard optimization problem that is solved by finding the ground state of the corresponding Hamiltonian on a Quantum Annealer. The ground state if found by adiabatically evolving from an initial Hamiltonian with a well-known ground state to the problem Hamiltonian.

This is by no means the definite list of all QUBO formulations out there. This list will grow over time.

For 14 of these problems the QUBO formulation is implemented using Python (including unittests) in the QUBO-NN project. The Github can be found here.

Problem QUBO formulation
Number Partitioning (NP) Glover et al.2
Maximum Cut (MC) Glover et al.2
Minimum Vertex Cover (MVC) Glover et al.2
Set Packing (SP) Glover et al.2
Set Partitioning (SPP) Glover et al.2
Maximum 2-SAT (M2SAT) Glover et al.2
Maximum 3-SAT (M3SAT) Dinneen et al.9
Graph Coloring (GC) Glover et al.2
General 0/1 Programming (G01P) Glover et al.2
Quadratic Assignment (QA) Glover et al.2
Quadratic Knapsack (QK) Glover et al.2
Graph Partitioning Lucas7
Decisional Clique Problem Lucas7
Maximum Clique Problem Chapuis19
Binary Integer Linear Programming Lucas7
Exact Cover Lucas7
3SAT Lucas7
Maximal Independent Set Djidjev et al.8
Minimal Maximal Matching Lucas7
Set Cover Lucas7
Knapsack with Integer Weights Lucas7
Clique Cover Lucas7
Job Sequencing Problem Lucas7
Hamiltonian Cycles Problem Lucas7
Minimal Spanning Tree Lucas7
Steiner Trees Lucas7
Directed Feedback Vertex Set Lucas7
Undirected Feedback Vertex Set Lucas7
Feedback Edge Set Lucas7
Traveling Salesman (TSP) Lucas7
Traveling Salesman with Time Windows (TSPTW) Papalitsas et al.1
Graph Isomorphism Calude et al.4
Subgraph Isomorphism Calude et al.4
Induced Subgraph Calude et al.4
Capacitated Vehicle Routing (CVRP) Irie et al.5
Multi-Depot Capacitated Vehicle Routing (MDCVRP) Harikrishnakumar et al.6
L1 norm Yokota et al.3
k-Medoids Bauckhage1 et al.10
Contact Map Overlap Problem Oliveira et al.11
Minimum Multicut Problem Cruz-Santos et al.12
Broadcast Time Problem Calude et al.13
Maximum Common Subgraph Isomorphism Huang et al.14
Densest k-subgraph Calude et al.15
Longest Path Problem McCollum et al.16
Airport Gateway Assignment Stollenwerk et al.18
Linear regression Date et al.17
Support Vector Machine Date et al.17
k-means clustering Date et al.17

Note that a few of these references define Ising formulations and not QUBO formulations. However, these two formulations are very close to each other. As a matter of fact, converting from Ising to QUBO is as easy as setting $S_{i} \rightarrow 2x_i - 1$, where $S_i$ is an Ising spin variable and $x_i$ is a QUBO variable.

Published on