UCL School of Management is delighted to welcome, Professor Sridhar R Tayur, Tepper School of Business, to host a research seminar discussing ‘GAMA: Quantum and Quantum-inspired Algorithms’

Abstract

I will discuss two original approaches to solve non-linear integer optimization problems that arise in applications in nance, cancer genomics and supply chain optimization. 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. A hybrid quantum-classical approach (GAMA-Q) that have the potential to solve a variety of hard linear and non-linear integer programs, as they form a test set (optimality certicate). We test two hybrid quantum-classical algorithms (on D-Wave) {one for computing Graver basis and a second for optimizing non-linear integer programs that utilize Graver bases {to understand the strengths and limitations of the practical quantum annealers available today. Our experiments suggest that with a modest increase in coupler precision {along with near-term improvements in the number of qubits and connectivity that are expected {the ability to outperform classical best-in-class algorithms is within reach. A (fully classical) approach (GAMA-C) to solving certain non-convex integer programs. This method is well suited for Cardinality Boolean Quadratic Problems (CBQP), Quadratic Semi- Assignment Problems (QSAP) and Quadratic Assignment Problems (QAP). 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 vastly out-performs in terms of time to find the optimal solution (by two or three orders of magnitude). Results of applying GAMA on data from The Cancer Genome Project (TCGA) to find mutated driver pathways are encouraging. I will discuss some results on Acute Myleoid Luekemia (AML) and Glioblastoma Multiforme (GBM).