## # 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
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
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.50

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