(177f) Use of Quantum Computing to Solve Optimization Problems in Process Systems Engineering

David E. Bernal, Ignacio E. Grossmann

Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA

Optimization problems arise in different areas of Process Systems Engineering (PSE). Being able to solve these problems efficiently is essential for addressing important industrial applications. Using tools of computer science and mathematics, the field of mathematical programming derives different algorithms to solve these optimization problems. Very often, these problems involve variables that must be discrete, which makes the problem exponentially hard to solve using the computers that we currently have, classical computers. Several powerful tools have been proposed to solve these discrete/combinatorial problems when the relations involved in them are linear. However, many applications involve nonlinearities in the model, which complicate the problem further. We propose to use a different type of computers, quantum computers, that are able to harness the effects of quantum mechanics in order to tackle these challenging problems. There is potential for this type of computers to efficiently solve these challenging combinatorial problems. However, quantum computers that are currently available cannot solve problems of the size that practical applications require, or deal with nonlinear constraints efficiently. We apply tools from optimization problem decomposition to break-down the problems into smaller sub-problems that can be solved more efficiently by using specialized tools such as quantum computers, in hybrid classical-quantum algorithms.

Our ultimate goal is to address optimization problems in Process Systems Engineering (PSE) that can be expressed with algebraic equations and constraints in terms of decision variables involving discrete and continuous variables. These mathematical programing models, known as Mixed-integer Nonlinear Program (MINLP), have many applications in PSE including process operations, like planning and scheduling, process control and synthesis design, and molecular design¹. The applications of MINLP are not exclusive of PSE since it has been successfully used in areas like medicine, e.g. cancer treatment, civil engineering, e.g. building design, and economics, e.g. portfolio investment². Methods to solve MINLP problems rely on the exploration of the feasible region, defined as the possible values of variables given the problem. Enumerating all the combinations of discrete values is exponentially hard. Furthermore, having nonlinearity in the constraints makes the search more demanding. The solution of these problems is commonly found through Branch-and-bound algorithms, where a divide-and-conquer approach evaluates the different alternatives arising from the discrete options of the integer variables². The many applications of MINLPs have motivated the study of efficient solution methods, particularly decomposition schemes^2,3. Nevertheless, MINLP methods at some point rely on Branch-and-bound, and hence are exponentially hard to solve with respect to the number of variables.

As a first step towards solving MINLP problems, we address in this presentation the application of quantum computing to special classes of 0-1 nonlinear programming problems. The new computational paradigm of quantum computing harvests the physical phenomena of quantum mechanics, e.g. tunneling, entanglement, and superposition, and has shown the potential to outperform in some problems the best classical algorithms⁴. Although we are likely to be years away from large-scale universal quantum computers, small-scale universal computers and special-purpose quantum computational hardware have emerged in the past few years⁵. Quantum Annealing (QA) is one of the algorithms for which special-purpose hardware, Quantum Annealers, has been created and is likely to keep growing over time. In QA, a physical system is allowed to evolve from an initial state to a final one, where each state is defined by having a minimal energy⁴. This hardware is built in a way that the Hamiltonians, i.e. energy functions, are quadratic functions of physical binary states and that the final one resembles a user defined function. In optimization theory, QA can be regarded as a method to heuristically solve Quadratic Unconstrained Binary Optimization (QUBO), and has shown to outperform by orders of magnitude the best classical algorithms⁶. The relationship between QA and mathematical programming is not one-directional, with traditional Integer programming methods being useful for QA^7,8. Notice that QUBOs are a subclass of MINLP, which considers an unconstrained quadratic objective and binary variables.

Although some problems in PSE can be modeled using QUBOs, and there are certain ways of reformulating certain applications directly into this form, e.g. discretizing continuous variables and posing them as integers and dualizing constraints to leave an unconstrained problem^9,10, there are limitations to this approach. The first one is that the limited size of the current Quantum Annealers, added to the increase in the number of variables in the discretization scheme, poses a natural limit to the size and complexity of the problems to be solved. The second one is that without knowledge of the values of the Lagrange multipliers, the reformulation to an unconstrained problem becomes incomplete. Motivated by these facts, we propose quantum-enhanced and quantum-inspired algorithms to solve MINLPs. We use decomposition schemes to fragment our MINLP problems in QUBOs, and allow specialized algorithms, including QA, to tackle the exponentially hard combinatorial part. Our decomposition schemes include Lagrangean relaxation/decomposition¹¹ to remove the constraints and Graver basis computations for finding improving search directions¹² to our problems. The resulting algorithms can use the existing Quantum Annealers, like the D-Wave 2000Q, to solve the QUBOs arising from the decomposition scheme. On the other hand, we can use classical methods to solve the Hamiltonian energy minimization such as traditional mathematical programming modeling in Integer quadratic programs, Simulated Annealing, Monte Carlo based algorithms such as Metropolis-Hastings⁸, or analytically solving these problems¹³, among others. This last group of methods, which are only executed in classical computers, can be classified as quantum- or physics-inspired algorithms. In this presentation, we show that the resulting algorithms prove to be efficient in solving several specific MINLP problems relevant to chemical engineering, namely process job-shop scheduling, facility location-allocation⁹, lightly doped semiconductors ground state computation¹⁴, and cancer genomic identification¹⁵. The order of magnitude reductions in computational time that have been obtained highlight the potential of quantum-enhanced and quantum-inspired algorithms for process systems engineering.

1. Grossmann, I. E. & Trespalacios, F. Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming. AIChE J. 59, 3276–3295 (2013).
2. Kronqvist, J., Bernal, D. E., Lundell, A. & Grossmann, I. E. A review and comparison of solvers for convex MINLP. Optim. Eng. 1–59 (2019). doi:10.1007/s11081-018-9411-8
3. Bernal, D. E. On Solving Convex Mixed-integer Nonlinear Programs, PhD Thesis Proposal. (Carnegie Mellon University, 2019).
4. Nielsen, M. A. & Chuang, I. L. Quantum computation and quantum information. (Cambridge University Press, 2010).
5. Rieffel, E. G. et al. From Ansätze to Z-gates: a NASA View of Quantum Computing. (2019).
6. McGeoch, C. C. & Wang, C. Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. in Proceedings of the ACM International Conference on Computing Frontiers, CF 2013 (2013). doi:10.1145/2482767.2482797
7. Bernal, D. E. et al. Integer programming techniques for minor-embedding in quantum annealers. (2019).
8. Coffrin, C., Nagarajan, H. & Bent, R. Evaluating Ising Processing Units with Integer Programming. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (2019). doi:10.1007/978-3-030-19212-9_11
9. Ajagekar, A. & You, F. Quantum computing for energy systems optimization: Challenges and opportunities. Energy (2019). doi:10.1016/j.energy.2019.04.186
10. Ajagekar, A., Humble, T. & You, F. Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems. Comput. Chem. Eng. (2020). doi:10.1016/j.compchemeng.2019.106630
11. Kocis, G. R. & Grossmann, I. E. A modelling and decomposition strategy for the minlp optimization of process flowsheets. Comput. Chem. Eng. (1989). doi:10.1016/0098-1354(89)85053-7
12. Alghassi, H., Dridi, R. & Tayur, S. Graver Bases via Quantum Annealing with application to non-linear integer programs. (2019).
13. Alghassi, H., Dridi, R. & Tayur, S. GAMA: A Novel Algorithm for Non-Convex Integer Programs. (2019).
14. Pörn, R., Nissfolk, O., Jansson, F. & Westerlund, T. The Coulomb Glass - Modeling and Computational Experience with a Large Scale 0-1 QP Problem. Computer Aided Chemical Engineering 29, (Elsevier B.V., 2011).
15. Alghassi, H., Dridi, R., Robertson, A. G. & Tayur, S. Quantum and Quantum-inspired Methods for de novo Discovery of Altered Cancer Pathways. bioRxiv 845719 (2019). doi:10.1101/845719