# 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 NPhard 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 nonlinear system of equations can be found in the QUBO. The quadratic unconstrained binary optimization (QUBO) problem itself is a NPhard 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 wellknown 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 QUBONN 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 2SAT (M2SAT)  Glover et al.^{2} 
Maximum 3SAT (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  Lucas^{7} 
Decisional Clique Problem  Lucas^{7} 
Maximum Clique Problem  Chapuis^{19} 
Binary Integer Linear Programming  Lucas^{7} 
Exact Cover  Lucas^{7} 
3SAT  Lucas^{7} 
Maximal Independent Set  Djidjev et al.^{8} 
Minimal Maximal Matching  Lucas^{7} 
Set Cover  Lucas^{7} 
Knapsack with Integer Weights  Lucas^{7} 
Clique Cover  Lucas^{7} 
Job Sequencing Problem  Lucas^{7} 
Hamiltonian Cycles Problem  Lucas^{7} 
Minimal Spanning Tree  Lucas^{7} 
Steiner Trees  Lucas^{7} 
Directed Feedback Vertex Set  Lucas^{7} 
Undirected Feedback Vertex Set  Lucas^{7} 
Feedback Edge Set  Lucas^{7} 
Traveling Salesman (TSP)  Lucas^{7} 
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} 
MultiDepot Capacitated Vehicle Routing (MDCVRP)  Harikrishnakumar et al.^{6} 
L1 norm  Yokota et al.^{3} 
kMedoids  Bauckhage1 et al.^{10} 
Contact Map Overlap Problem  Oliveira et al.^{11} 
Minimum Multicut Problem  CruzSantos et al.^{12} 
Broadcast Time Problem  Calude et al.^{13} 
Maximum Common Subgraph Isomorphism  Huang et al.^{14} 
Densest ksubgraph  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} 
kmeans 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.

A QUBO Model for the Traveling Salesman Problem with Time Windows for Execution on the DWave ↩

QUBO Formulations for the Graph Isomorphism Problem and Related Problems ↩↩↩

Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity ↩

A Quantum Annealing Approach for Dynamic MultiDepot Capacitated Vehicle Routing Problem ↩

Efficient Combinatorial Optimization Using Quantum Annealing ↩

A QUBO Formulation of the Stereo Matching Problem for DWave Quantum Annealers ↩

Solving the Broadcast Time Problem Using a Dwave Quantum Computer ↩

A New QUBO Objective Function for Solving the Maximum Common Subgraph Isomorphism Problem Via Quantum Annealing ↩