Quadratic Optimization and Quantum Computing

Recent advances in quantum computing along with increased interest in solving difficult optimization problems is shining a light on a research area that has been quietly growing for the past twenty plus years.

This area involves modeling difficult decision problems as Quadratic Unconstrained Binary Optimization (QUBO) problems and then solving them on a new type of quantum computer using qubits. D-Wave Systems is currently the only company building commercially available quantum computers. D-Wave employs quantum superposition and entanglement between qubits (analogous to binary digits, or bits) that can be both 0 and 1 at the same time. This allows them to effectively explore an unimaginably large solution space. In addition, the D-Wave’s unique architecture allows it to solve QUBO very efficiently.

For the past half-century operations research (which focuses on mathematical modeling and optimization) has relied on concepts associated with linear programming (LP) using the simplex method developed by George Dantzig in the late 1940s. However, many real-world problems are neither linear nor continuous, as required for LPs. Non-linear, discrete problems modeled as quadratic problems (QP) can be effective when two variables interact with one another, or are highly correlated. A QUBO is a subclass of QP where the variables are binary (0/1, yes/no, on/off, -1/+1, and so on) and there are no constraints (or the constraints can be absorbed into the unconstrained formulation by clever representation techniques, often utilizing penalties for constraint violations).

The exponential growth in computer processing power along with cheap memory have allowed LP solvers to run some quadratic optimization models, but the conversion process from QP to LP can result in LPs that are too large to be solved within practical time limits. A dramatic example of this is the generalized vertex cover problem (GVCP), which is an extension of the classic vertex cover problem. The goal is to find a minimum cost subset of the nodes in a graph such that every edge in the graph is incident to at least one of the chosen nodes. For example, if all nodes have the same cost, then nodes 1 and 2 optimally cover the graph below because every edge is incident to either node 1 or 2.

GVCP adds edge costs to the problem, where the cost of not including an edge is higher than including only one endpoint of the edge, and the lowest cost solution includes edges with both endpoints covered. A linear programming model of a 5000 node GVCP can have over 21 million variables and 31 million constraints! A problem of that size requires a lot of time even for the most powerful supercomputers. By contrast, an equivalent QUBO model has only 5000 variables and no constraints and QUBO problems of this size have been readily solved on standard PCs. Although this size problem is too large for the currently available quantum computers, larger and denser quantum chips are being designed.

What sort of problems are amenable to quantum annealing computers such as the D-Wave? There are many general business and science areas that could see benefits. In addition, there are multiple broad classes of mathematical problem types that are classified as hard (technically they are non-deterministic in polynomial time) with broad application. For a summary of QUBO methods and applications see the survey paper listed in the reference section.

Areas with QUBO components:Some established QUBO problem categories:
Finance & Portfolio optimizationIsing spin glass
Project SelectionSatisfiability
Cluster AnalysisMax-cut
Economic AnalysisTwo machine scheduling
Traffic ManagementMax clique
Circuit Board DesignSet Partitioning
Robust Business Decision makingMax 2-sat
Protein FoldingMaximal Independent Set
Network DesignLinear Ordering
Website traffic analysisTask Allocation
Social network & link analysisVertex Coloring & Covering
Fault generation for SW testingSum Coloring
Image analysis2-TAP (task allocation problem)
Prediction of epileptic seizuresQuadratic knapsack

As good as this sounds, there are serious obstacles to overcome when solving QUBO on quantum computers such as the D-Wave. Problems that can be directly solved on a current D-Wave system are limited by the number connectivity of the qubits, meaning that QUBO problems with 2000 decisions (qubits) and a large number of quadratic correlations are not directly solvable via quantum entanglement. However, software tools exist that partition large QUBO so they can be solved on a D- Wave system and improvements in software tools and coming generations of D-Wave computers are in the works.

One group of researchers, led by Gary Kochenberger and Fred Glover at the University of Colorado, have a long history of finding transformations from LP to QUBO and are now investigating QUBO-to-QUBO transformations. Their latest research published in the journals Networks and the European Journal of Operational Research derive multiple rules for transforming a given QUBO to an equivalent QUBO with fewer variables. For example, QUBO problems with 10,000 variables and certain natural network properties have been reduced to equivalent QUBO with less than 100 variables. Unlike the graph morphology transformations used in image processing which are very difficult, inexact and time consuming, these new rules are very fast and exact. A goal of the research is to be able to transform a given QUBO into one that exactly matches the capabilities of a D-Wave. Due to the difficulty of this problem, carefully designed heuristic approaches offer the greatest promise for future advances.


  1. Mark Lewis & Fred Glover, 2016. Binary Quadratic Network Preprocessing: Theory and Empirical Analysis. Networks, doi:10.1002/net.21751.
  2. Fred Glover, Mark Lewis, Gary Kochenberger, 2017. Logical and Inequality Implications for Reducing the Size and Difficulty of Quadratic Unconstrained Binary Optimization Problems, European Journal of Operational Research, doi.org/10.1016/j.ejor.2017.08.025.
  3. Kochenberger, G. et al., 2014. The Unconstrained Binary Quadratic Programming Problem: a Survey. Journal of Combinatorial Optimization, 28(1), pp. 55-81.

This article is based on the recent study, Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis, by Mark Lewis and Fred Glover.

About The Author

Mark Lewis

Mark Lewis is a research scientist at Missouri Western State University with expertise in algorithms and mathematical modeling.

Speak Your Mind!


Why Are Pandas Still Endangered?

About a year ago there was some massive hype that giant pandas were taken off the endangered species list, but unfortunately, pandas are still very much endangered due to one main cause; their habitats are being lost due to human interference. That’s right folks, these adorable animals are losing their¬†habitats because of us.¬†Unlike many other […]

Machine Learning Algorithms Identify Genes Responsible For Drug Resistance In Tuberculosis Bacteria

One of the larger challenges facing modern medicine is the rise of drug-resistant strains of bacteria. Overuse and overexposure to antibiotics during the past century have resulted in adapted strains of bacteria that are resistant to common antibiotics. Developing new drugs to combat drug-resistant strains is a difficult process, as scientists are often unsure exactly […]

Cultural Adaptation Of Cognitive Stimulation Therapy For India

In the context of a Low and Middle Income Country (LMIC) like India, where an estimated 4.4 million people have dementia, the service gap for diagnosis and treatment exceeds 90% in most parts of the country (Dias & Patel, 2009). Effective interventions that are culturally relevant and feasible to deliver are a high priority for […]

Periodic Table Ionic Charges, Name, And Mass

The periodic table ionic charge can be broken down by metals which are positive and on the left of the table and nonmetals which are negative and found on the right. The periodic table can also be broken down by name and mass depending on your interests. There can be no doubt that any science […]

Unakite: Characteristics And Properties

Unakite is a granite that is generally altered with green epidote, pink orthoclase feldspar, and sometimes colorless quartz. If you would like to know the characteristics and properties of unakite, you have come to the right place. In this article, we will talk about the properties of this granite composite. What Is Unakite? You may […]

Listening To Music While Exercising May Help Avoid Fatigue

A new neuroimaging study has found evidence suggesting that listening to music could help people ward off fatigue while exercising. The study, recently published in the International Journal of Psychophysiology, found that increased activity within a particular region of the brain was witnessed when listening to music while exercising and that this activity was correlated […]

Levosimendan: A FDA-Approved Drug Treating Heart Failure Also Blocks HIV-1 Reactivation

Human immunodeficiency virus type 1 (HIV-1) infection causes acquired immune deficiency syndrome (AIDS), which remains a¬†major public health concern. Combination antiretroviral therapy (cART), typically consisting three or more antiretroviral drugs, has been shown to efficiently block active HIV-1 replication, which leads to an improved life expectancy of HIV-infected patients. Nevertheless, HIV-1/AIDS is still an incurable […]