About the author:
Daniel is CTO at rhome GmbH, and Co-Founder at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning and quantum computing. He writes about technical topics in quantum computing and startups.
jrnl · home about list ventures publications LinkedIn Join my Slack

# 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 Si→2xi−1S_{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