The Quantum Computing Revolution and Optimization: Challenges and Opportunities
Abstract
The most important developments in the field of quantum computing (QC) have been mostly driven by research from investigators in the general fields of physics and computer science. However, one of the main motivations behind research in QC is its potential to substantially increase our capability to solve complex combinatorial optimization (COPT) problems for which no classical empirical or theoretical efficient solution algorithms exist. Thus, it is surprising to find out the lack of research in the area of QC from investigators in COPT, and in more generality, from investigators in the area of operations research (OR), who focus on devising theoretical, algorithmic, and computational techniques to address the solution of this class of fundamental and widely relevant class of problems. The central objective of this proposal is to set up a team of accomplished researchers in the areas of COPT (and in general OR) and QC to collaborate in devising hybrid QC+COPT theoretical methodologies and testing environments that would evidence the potential solution speed-ups that could be obtained, when comparing with classical solution approaches, by near future noisy intermediate-scale quantum devices (NISQ). We will accomplish this main objective by focusing on two COPT problems: The stable set problem: is the problem of finding the maximum cardinality set of nodes in a graph without edges between them. This is a COPT problem of great national security relevance, as a number of keystone problems in telecommunications, cyber security and cryptography can be formulated as a stable set problem over an appropriate graph. Optimal Submatrix Pursuit problem: By optimal submatrix pursuit problem we refer to a wide class of COPT problems in which the aim is to find an optimal or appropriate combination or permutation of the rows of a given matrix that forms a new matrix or submatrix with certain desired properties like non-singularity, surjectivity, or structural sparsity. This class of problems have great national security relevance, as they arise as subproblems that need to be solved in a wide-range of logistics applications, as means to compute the accuracy of certain heuristics for COPT problems, and as subproblems whose solution can greatly speed-up general classes of optimization algorithms. More specifically, we will principally consider these COPT problems in three directions of work 1. Devise specific, scalable instances of these COPT problems that evidence their NP-hardness in a classical computing framework, when the instances scale is small enough for it to be solved by NISQ devices. With this work we are addressing the lack of this type of instances that would greatly impact the way in which QC devices and algorithms are benchmarked. 2. Use decomposition, reformulation and symmetry reduction optimization techniques to increase size of COPT problems that can be approximately solved with NISQ devices. With this work we are addressing the unexplored use of a wide range of techniques that can be used to obtain substantial gains in the ability to solve COPT problems with NISQ devices. 3. Devise a new, theoretical quantum algorithm, based on convex optimization techniques that can provide more efficient solution schemes for COPT problems using future QC devises. Considering the use of novel convex optimization techniques, together with an improved use of QC capabilities will have a substantial impact in the class of problems that could be solved or approximately solved with future available QC devises.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 03, 2020
- Source ID
- W911NF2010022
Entities
People
- Tamás Terlaky
Organizations
- Army Contracting Command
- Defense Advanced Research Projects Agency
- Lehigh University