(373k) Direct Quantum Optimization of a Class of MINLP Involving Quadratic and Signomial Terms

Quantum optimization presents a paradigm shift in scientific computing. By leveraging quantum mechanical phenomena [1], such as superposition, entanglement, and quantum tunneling, quantum optimization techniques seek to expedite the exploration of solution spaces [2] and navigate beyond local optima during quantum annealing processes [3]. This makes quantum optimization a potentially attractive avenue for optimal decision-making, especially for addressing combinatorially complex optimization problems involving discrete decisions. Recent technological advancements and concerted industrial endeavors aimed at establishing commercial cloud-based quantum computing systems [4-5] have significantly enhanced the efficiency of quantum computers in solving discrete optimization problems. A few examples include graph coloring [6], traffic flow optimization [7], job-shop scheduling [8], and the vehicle routing problem [9]. However, current quantum computers cannot directly solve all types of optimization problems. Hence quantum hardware requires the reformulation of the original problem into equivalent formulations amenable to quantum annealing, such as the Ising model or the quadratic unconstrained binary optimization (QUBO) model [10]. Additionally, the physical characteristics of quantum computing, alongside existing hardware constraints, preclude the straightforward incorporation of constraints and optimization over continuous domains. This is a significant issue for constrainted optimization involving mixed-integer decisions [11]. Several hybrid classical-quantum optimization strategies and applications have emerged in the recent past [12] that aim to complement the power of quantum computing with sophisticated off-the-shelf deterministic solvers. However, the convergence is not always guaranteed for hybrid and/or decomposion approaches. In this work, we propose a new approach that allows for the direct solution of a class of mixed-integer nonlinear programs (MINLP) using quantum computing. Following our previous preliminary work [13], we represent continuous variables (e.g., x \in R) by a set of binary variables (z \in R^q). This transformation makes it possible to directly reformulate a mixed-integer quadratically constrained quadratic program (MIQCQP) as a QUBO problem, which is then solved using quantum annealing. Furthermore, we have developed a new formulation that directly encodes signomial terms. These encoding schemes together allow to reformulate a MINLP with quadratic and signomial terms to a single QUBO, thereby avoiding the need for hybrid techniques for the continuous parts of the problem. We have tested our technique on various types of problems, ranging from process synthesis to pooling to computer-aided molecular and process design problems.

Keywords: Quantum optimization, Quantum computing, Quantum annealing, QUBO, MINLP, Process synthesis.

References:

[1] Albash, T., and Lidar, D. A. Adiabatic quantum computation. Reviews of Modern Physics, 90, 015002 (2018).

[2] Baldassi, C, and Zecchina, R. Efficiency of quantum vs. classical annealing in nonconvex learning problems. Proceedings of the National Academy of Sciences, 115, 1457–1462 (2018).

[3] Lanting, T., Przybysz, A. J., Smirnov, A. Y., Spedalieri, F. M., Amin, M. H., Berkley, A. J., Harris, R., Altomare, F., Boixo, S., Bunyk, P., et al. Entanglement in a quantum annealing processor. Physical Review X, 4, 021041 (2014).

[4] Friis, N., Marty, O., Maier, C., Hempel, C., Holz¨apfel, M., Jurcevic, P., Plenio, M. B., Huber, M., Roos, C., Blatt, R., et al. Observation of entangled states of a fully controlled 20-qubit system. Physical Review X, 8, 021012 (2018).

[5] Mooney, G. J. White, G. A. Hill, C. D. and Hollenberg, L. C. Whole-Device Entanglement in a 65-Qubit Superconducting Quantum Computer. Advanced Quantum Technologies, 4, 2100061 (2021).

[6] Titiloye, O., and Crispin, A. Quantum annealing of the graph coloring problem. Discrete Optimization, 8, 376–384 (2011).

[7] Neukart, F., Compostella, G., Seidel, C., Von Dollen, D., Yarkoni, S., and Parney, B. Traffic flow optimization using a quantum annealer. Frontiers in ICT, 4, 29 (2017).

[8] Rieffel, E. G., Venturelli, D., O’Gorman, B., Do, M. B., Prystay, E. M., and Smelyanskiy, V. N. A case study in programming a quantum annealer for hard operational planning problems. Quantum Information Processing, 14, 1–36 (2015).

[9] Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I., Mauerer, W., Linnhoff-Popien, C. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Frontiers in ICT, 6, 13 (2019).

[10] Lucas, A. Ising formulations of many NP problems. Frontiers in physics, 5 (2014).

[11] Demirel, S. E., Li, J., Hasan, M. M. F. (2017). Systematic process intensification using building blocks. Computers & Chemical Engineering, 105, 2–38.

[12] Zhao, Z., Fan, L., Han, Z. (2022). Hybrid Quantum Benders’ Decomposition for Mixed-integer Linear Programming. IEEE Wireless Communications and Networking Conference (WCNC), 2536-2540.

[13] Iftakher, A., Kazi, M. K., Hasan M. M. F. (2023). Mixed-integer Quadratic Optimization using Quantum Computing for Process Applications. In Proceeding of the Foundations of Computer Aided Process Operations/Chemical Process Control,1-6.