GAMA: A Quantum Inspired Classical Algorithm

583 1

I am getting ready to travel to Innsbruck for the Adiabatic Quantum Computing (AQC) 2019 Conference.

Two things happened today.

First, I received the hard copy of Science and Culture issue that carried our expository article that connected Algebraic Geometry to AQC and my interview on quantum computing. Love it!

Second, we finished our new paper

GAMA: A Novel Algorithm for Non-Convex Integer Programs.

The abstract reads:

Inspired by the decomposition in the hybrid quantum-classical optimization algorithm we introduced in [ADT19], we propose here a new (fully classical) approach to solving non-convex integer programs using Graver bases. This method is well suited when (a) the matrix A has a special structure so that its Graver basis can be computed systematically and (b) several feasible solutions can also be constructed easily. Classes of problems that satisfy these conditions include Cardinality Boolean Quadratic Problems (CBQP), Quadratic Semi-Assignment Problems (QSAP) and Quadratic Assignment Problems (QAP). Our Graver Augmented Multi-seed Algorithm (GAMA) utilizes augmentation along Graver basis elements (the improvement direction is obtained by comparing objective function values) from these multiple initial feasible solutions. We compare our approach with a best-in-class commercially available solver (Gurobi). Sensitivity analysis indicates that the rate at which GAMA slows down as the problem size increases is much lower than that of Gurobi. We find that for several instances of practical relevance, GAMA not only vastly outperforms in terms of time to find the optimal solution (by two or three orders of magnitude), but also finds optimal solutions within minutes when the commercial solver is not able to do so in 4 or 10 hours (depending on the problem class) in several cases.

Apart from the fact that our method is so much faster on important industry instances, of great satisfaction to me also comes from the how we conceived of this approach, in line with Hilbert’s observation (from his 1900 speech in Paris, at the Second International Conference of Mathematicians, titled Mathematical Problems):

If we do not succeed in solving a mathematical problem, the reason frequently consists in our failure to recognize the more general standpoint from which the problem before us appears only as a single link in a chain of related problems. After finding this standpoint, not only is this problem frequently more accessible to our investigation, but at the same time we come into possession of a method which is applicable also to related problems.

What are we presenting at AQC 2019 on Monday? Our [ADT19] paper

Graver Bases via Quantum Annealing with Application to Non-Linear Integer Programs.

Indeed, the GAMA procedure was introduced there, but we did not name it until now. 

What is different is that in our new paper, we do not need a quantum computer, as the constraint matrices are structured such that we can compute the Graver basis and many well spread out (initial) feasible solutions (seeds) entirely classically! Furthermore, we do not require the objective function to be convex.

As we write in our Introduction:

Suppose the non-convex objective function can be viewed as many convex functions stitched together. Thus, the entire feasible solution space can be seen as a collection of parallel subspaces, each with a convex objective function. If we have the Graver basis for the constraint matrix, and a feasible solution in every one of these sub-regions, putting this all together, we envision an algorithm that can find the optimal solution as follows:

  Find the Graver basis.

  Find a number of feasible solutions, spread out so that there is at least one feasible solution in each of the sub-regions that has a convex objective function.

 Augment along the Graver basis from each of the feasible solutions (“seeds”) until you end up with a number of local optimal solutions (one for each seed).

Choose the best from among these local optimal solutions.

It works so well!🤷🏽‍♂️😊

So, now we have to make our quantum GAMA even faster to beat our classical GAMA!

In the meantime, we are applying GAMA (both classical and quantum) to:

Discover new mutated driver pathways in cancer.

We are seeing some exciting results on Acute Myeloid Leukemia (AML) and Glioblastoma multiforme (GBM).

More on this later this summer.


1 comment

  1. Love this! Especially the cancer research application!

Leave a Reply