# List of QUBO formulations
Below a list of 95 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 is 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 20 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}, Feld et al.^{31} 
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} 
Eigencentrality  Prosper et al.^{20} 
Container Assignment Problem  Phillipson et al.^{21} 
kcolorable 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} 
MaxFlow Problem  Krauss et al.^{28} 
Network Shortest Path Problem  Krauss et al.^{29} 
Structural Isomer Search Problem  Terry et al.^{30} 
kdensest Common SubGraph 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 GraphBased Systems  PerdomoOrtiz et al.^{41} 
BoundedDepth 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} 
TwoDimensional Cutting Stock Problem  Arai et al.^{48} 
Labelled Maximum Weighted Common Subgraph  Hernandez et al.^{49} 
Maximum Weighted Cokplex  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  OssorioCastillo et al. ^{55} 
Job Shop Scheduling  Venturelli et al.^{56} 
Parallel Flexible Job Shop Scheduling  Denkena et al.^{57} 
Bin Packing with Integer Weights  Lodewijks^{58} (alternative: ref) 
Number Partitioning with m sets  Lodewijks^{58} 
Graph Partitioning with m sets  Lodewijks^{58} 
Subset Sum Problem  Lodewijks^{58} 
Numerical ThreeDimensional Matching  Lodewijks^{58} 
Social Workers Problem  Adelomou et al.^{59} 
EVBus Charging Scheduling Problem  Yu et al.^{61} 
Vehicle Routing Problem  Borowski et al.^{60} 
(*) applied to Covid19 by JimenezGuardeñ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.

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 ↩

Multimodal Container Planning: a QUBO Formulation and Implementation on a Quantum Annealer ↩

Characterization of QUBO reformulations for the maximum kcolorable subgraph problem ↩

Routing and Wavelength Assignment with Protection: A Quadratic Unconstrained Binary Optimization Approach ↩

Aircraft Loading Optimization  QUBO models under multiple constraints ↩

Analyzing the Quantum Annealing Approach for Solving Linear Least Squares Problems ↩

Solving the MaxFlow Problem on a Quantum Annealing Computer ↩

Solving the Network Shortest Path Problem on a Quantum Annealer ↩

A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer ↩

A QUBO Formulation For the Kdensest Common Subgraph Isomorphism Problem Via Quantum Annealing ↩

Detecting multiple communities using quantum annealing on the DWave system ↩

Application of Quantum Annealing to Nurse Scheduling Problem ↩

Aircraft Loading Optimization  QUBO models under multiple constraints ↩

Generalized Ramsey numbers through adiabatic quantum optimization ↩

Quantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement ↩

Solving Sensor Placement Problems In Real Water Distribution Networks Using Adiabatic Quantum Computation ↩

A Quantum Annealing Approach for Fault Detection and Diagnosis of GraphBased Systems ↩

Solving the BoundedDepth Steiner Tree Problem using an Adiabatic Quantum Computer ↩

Adiabatic quantum graph matching with permutation matrix constraints ↩

Quantum computing for energy systems optimization: Challenges and opportunities ↩↩

Garden optimization problems for benchmarking quantum annealers ↩

A Study of Ising Formulations for Minimizing Setup Cost in the TwoDimensional Cutting Stock Problem ↩

A Novel Graphbased Approach for Determining Molecular Similarity ↩↩↩

Drug repurposing based on a QuantumInspired method versus classical fingerprinting uncovers potential antivirals against SARSCoV2 including vitamin B12 ↩

Quantum Portfolio Optimization with Investment Bands and Target Volatility ↩

Experiences with Scheduling Problems on Adiabatic Quantum Computers ↩

Optimization of a refinery scheduling process with column generation and a quantum annealer ↩

Quantum algorithms for process parallel flexible job shop scheduling ↩

Mapping NPhard and NPcomplete optimisation problems to quadratic unconstrained binary optimisation problems. ↩↩↩↩↩

Formulation of the Social Workers’ Problem in Quadratic Unconstrained Binary Optimization Form and Solve It on a Quantum Computer ↩

New Hybrid Quantum Annealing Algorithms for Solving Vehicle Routing Problem ↩

Applying the HubbardStratonovich Transformation to Solve Scheduling Problems Under Inequality Constraints With Quantum Annealing ↩