About the author:
Daniel is co-founder and CTO at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning. He writes about technical topics in quantum computing.
jrnl · home about list my companies

# 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.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 Si2xi1S_{i} \rightarrow 2x_i - 1, where SiS_i is an Ising spin variable and xix_i is a QUBO variable.

  1. A QUBO Model for the Traveling Salesman Problem with Time Windows for Execution on the D-Wave 

  2. A tutorial on Formulating and Using QUBO Models 

  3. Derivation of QUBO formulations for sparse estimation 

  4. QUBO Formulations for the Graph Isomorphism Problem and Related Problems 

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

  6. A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem 

  7. Ising formulations of many NP problems 

  8. Efficient Combinatorial Optimization Using Quantum Annealing 

  9. Maximum 3-SAT as QUBO 

  10. A QUBO Formulation of the k-Medoids Problem 

  11. QUBO formulation for the contact map overlap problem 

  12. A QUBO Formulation of the Stereo Matching Problem for D-Wave Quantum Annealers 

  13. Solving the Broadcast Time Problem Using a D-wave Quantum Computer 

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

  15. Quantum Solutions for Densest K-Subgraph Problems 

  16. QUBO formulations of the longest path problem 

  17. QUBO formulations for training machine learning models 

  18. Flight Gate Assignment with a Quantum Annealer 

  19. Finding Maximum Cliques on the D-Wave Quantum Annealer 

  20. A QUBO Formulation for Eigencentrality 

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

  22. Characterization of QUBO reformulations for the maximum k-colorable subgraph problem 

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

  24. Aircraft Loading Optimization - QUBO models under multiple constraints 

  25. Analyzing the Quantum Annealing Approach for Solving Linear Least Squares Problems 

  26. Traffic Flow Optimization Using a Quantum Annealer 

  27. Quantum Permutation Synchronization 

  28. Solving the Max-Flow Problem on a Quantum Annealing Computer 

  29. Solving the Network Shortest Path Problem on a Quantum Annealer 

  30. Quantum isomer search 

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

  32. A QUBO Formulation For the K-densest Common Subgraph Isomorphism Problem Via Quantum Annealing 

  33. Detecting multiple communities using quantum annealing on the D-Wave system 

  34. Application of Quantum Annealing to Nurse Scheduling Problem 

  35. Aircraft Loading Optimization - QUBO models under multiple constraints 

  36. Adiabatic quantum algorithm for search engine ranking 

  37. Ramsey numbers and adiabatic quantum computing 

  38. Generalized Ramsey numbers through adiabatic quantum optimization 

  39. Quantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement 

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

  41. A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems 

  42. Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer 

  43. Adiabatic quantum graph matching with permutation matrix constraints 

  44. A QUBO Model for Gaussian Process Variance Reduction 

  45. Quantum Permutation Synchronization 

  46. Quantum computing for energy systems optimization: Challenges and opportunities 

  47. Garden optimization problems for benchmarking quantum annealers 

  48. A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem 

  49. A Novel Graph-based Approach for Determining Molecular Similarity 

  50. Drug repurposing based on a Quantum-Inspired method versus classical fingerprinting uncovers potential antivirals against SARS-CoV-2 including vitamin B12 

  51. Quantum Portfolio Optimization with Investment Bands and Target Volatility 

  52. Portfolio Optimisation Using the D-Wave Quantum Annealer 

  53. Advanced anneal paths for improved quantum annealing 

  54. Experiences with Scheduling Problems on Adiabatic Quantum Computers 

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

  56. Job Shop Scheduling Solver based on Quantum Annealing 

  57. Quantum algorithms for process parallel flexible job shop scheduling 

  58. Mapping NP-hard and NP-complete optimisation problems to quadratic unconstrained binary optimisation problems. 

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

  60. New Hybrid Quantum Annealing Algorithms for Solving Vehicle Routing Problem 

  61. Applying the Hubbard-Stratonovich Transformation to Solve Scheduling Problems Under Inequality Constraints With Quantum Annealing 

  62. QUARK: A Framework for Quantum Computing Application Benchmarking 

  63. A case study in programming a quantum annealer for hard operational planning problems 

  64. Market Graph Clustering via QUBO and Digital Annealing 

  65. Balanced k-Means Clustering on an Adiabatic Quantum Computer 

  66. Distance-based clustering using QUBO formulations 

  67. Unconstrained binary models of the travelling salesman problem variants for quantum optimization 

  68. Optimal feature selection in credit scoring and classification using a quantum annealer 

  69. Dynamic portfolio optimization with real datasets using quantum processors and quantum-inspired tensor networks 

  70. Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines 

  71. Foundations for Workflow Application Scheduling on D-Wave System 

  72. Solving large break minimization problems ni a mirrored double round-robin tournament using quantum annealing 

  73. Solving the Extended Job Shop Scheduling Problem with AGVs – Classical and Quantum Approaches 

  74. Avoiding blocking by scheduling transactions using quantum annealing 

  75. A Quantum Computational Approach to Correspondence Problems on Point Sets 

  76. Benchmarking Quantum Annealing Against “Hard” Instances of the Bipartite Matching Problem 

  77. Multi-car paint shop optimization with quantum annealing 

  78. Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm 

Published on