List of QUBO formulations

Below a list of 112 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 is 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 20 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, Salehi et al.67
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, Feld et al.31
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
Eigencentrality	Prosper et al.20
Container Assignment Problem	Phillipson et al.21
k-colorable subgraph problem	Rodolfo et al.22
Routing and Wavelength Assignment with Protection	Oylum et al.23
Aircraft Loading Optimization	Giovanni et al.24
Linear least squares / system of linear equations	Ajinkya et al.25
Traffic Flow Optimization	Neukart et al.26
Permutation Synchronization	Tolga et al.27
Max-Flow Problem	Krauss et al.28
Network Shortest Path Problem	Krauss et al.29
Structural Isomer Search Problem	Terry et al.30
k-densest Common Sub-Graph Isomorphism	Huang et al.32
Community Detection	Negre et al.33
Nurse Scheduling problem	Ikeda et al.34
Aircraft Loading Optimization	Pilon et al.35
PageRank	Garnerone et al.36
Ramsey numbers	Gaitan et al.37
Generalized Ramsey numbers	Ranjbar et al.38
Transaction Settlement	Braine et al.39
Sensor placement problem in water distribution networks	Speziali et al.40
Fault Detection and Diagnosis of Graph-Based Systems	Perdomo-Ortiz et al.41
Bounded-Depth Steiner Trees	Liu et al.42
Graph Matching with Permutation Matrix Constraints	Benkner et al.43
Gaussian Process Variance Reduction	Bottarelli et al.44
Quantum Permutation Synchronization	Birdal et al.45
Unit Commitment Problem	Ajagekar et al.46
Heat Exchanger Network Synthesis	Ajagekar et al.46
Garden Optimization Problem	Calaza et al.47
Two-Dimensional Cutting Stock Problem	Arai et al.48
Labelled Maximum Weighted Common Subgraph	Hernandez et al.49
Maximum Weighted Co-k-plex	Hernandez et al.49
Molecular Similarity based on Graphs	Hernandez et al.49 (*)
Portfolio Optimization (Modern Portfolio Theory)	Palmer et al.51, Phillipson et al.52
Weighted Maximum Cut	Pelofske et al.53
Weighted Maximum Clique	Pelofske et al.53
Satellite Scheduling	Stollenwerk et al.54
Refinery Scheduling	Ossorio-Castillo et al. 55
Job Shop Scheduling	Venturelli et al.56
Extended Job Shop Scheduling with Autonomous Ground Vehicles	Geitz et al.73
Parallel Flexible Job Shop Scheduling	Denkena et al.57
Bin Packing with Integer Weights	Lodewijks58 (alternative: ref)
Number Partitioning with m sets	Lodewijks58
Graph Partitioning with m sets	Lodewijks58
Subset Sum Problem	Lodewijks58
Numerical Three-Dimensional Matching	Lodewijks58
Social Workers Problem	Adelomou et al.59
EV-Bus Charging Scheduling Problem	Yu et al.61
Vehicle Routing Problem	Borowski et al.60
Robot Path Planning	Finžgar et al.62
Scheduling on Undirected Hamiltonian Paths	Rieffel et al.63
Market Graph Clustering	Hong et al.64
Balanced k-Means Clustering	Arthur et al.65
Distance-based Clustering in general	Matsumoto et al.66
Credit Scoring and Classification	Milne et al.68
Dynamic Portfolio Optimization	Mugel et al.69
Railway Dispatching and Conflict Management Optimization	Domino et al.70
Workflow Application Scheduling	Tomasiewicz et al.71
Mirrored Double Round-robin Tournament	Kuramata et al.72
Transaction Scheduling	Bittner et al.74
Transformation Estimation	Golyanik et al.75
Point Set Registration	Golyanik et al.75
Maximum Cardinality Matching	Vert et al.76
Multi-car Paint Shop Optimization	Yarkoni et al.77
Binary Paint Shop Problem	Streif et al.78

(*) applied to Covid-19 by Jimenez-Guardeño et al.⁵⁰

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 2021-06-10