Quantum computing (QC) harnesses the properties of subatomic particles to perform computations in a fundamentally different way than classical computing. QC has the potential to make a revolutionary impact on the way we model, and subsequently solve real-world optimization problems for which no numerically—or even theoretically—efficient classical algorithms exist.
In this talk, we begin by discussing the synergistic relationship between optimization and QC by showing how state-of-the-art optimization can be used to improve QC and vice versa. In particular, we provide an overview of work in the latter direction by our QC & optimization research group at Lehigh University. Then we have a more detailed discussion on how to obtain the "best" quadratic unconstrained binary optimization (QUBO) formulations for combinatorial optimization (COPT) problems. Both gate-based and annealing-based quantum computers are designed to solve QUBO problems. Also, it is not difficult to reformulate COPT problems as QUBO problems. However, the way this reformulation is performed can dramatically affect the efficiency of the quantum computer to solve the desired COPT problem. If time permits, we will finish by discussing related directions of future research.
Luis F. Zuluaga earned his Ph.D. in Operations Research from the Tepper School of Business, Carnegie Mellon University. Luis also has a Master's degree in Industrial Engineering, and Bachelor's degrees in Physics and Electrical Engineering from the University of Los Andes (Colombia). Currently, Luis is serving as Professor at the Industrial and Systems Engineering (ISE) Department, Lehigh University. Luis has authored multiple articles in journals such as Operations Research, SIAM Journal on Optimization, Mathematical Programming, and Mathematics of Operations Research. Luis' research is mainly focused on developing solution schemes and effective algorithms for problems involving optimization over polynomials; especially those arising from integer programming, probability, finance applications, and quantum computing. In the area of quantum computing, Luis recently established, with collaborators, the Quantum Computing and Optimization Laboratory (QCOL) at the ISE Department, Lehigh University. QCOL was initially funded by a DARPA ONISQ grant and its purpose is to research how the potential of quantum computers can be exploited to solve complex decision-making problems. Other research by Luis has been funded by NSF, AFOSR, PITA, and the US Army OSBP. Besides his academic work, Luis has served as consultant to organizations such as the State Department of Colombia, General Re-New England Asset Management Inc., IBM Global Business Services, and PricewaterhouseCoopers.