CQIS: Constrained Optimization on a Variational Quantum Computer: Problem Modeling, Algorithmic Design, and Performance Analysis

Quantum computing could be a disruptive technology in dealing with challenging computational tasks, such as integer factorization, searching in databases, solving systems of linear equations, and various machine learning tasks with polynomial or exponential speed-ups over their classical computing alternatives. However, these algorithms are assumed to operate on fault-tolerant quantum computers, which are projected not to be available soon. Recent research and development efforts focus on devising algorithms relevant to practical applications on the qubit-limited, low-circuit depth, and noisy quantum hardware currently available, referred to as Noisy Intermediate-Scale Quantum (NISQ). Variational quantum approaches (VQAs) exploit variational quantum circuits (VQCs) of limited depth and reduced number of qubits, and become the leading candidates to showcase quantum advantage in the NISQ era. VQAs are hybrid approaches as a VQC operates in tandem with a classical computer to solve an optimization problem. Most existing VQAs either consider optimization problems without constraints or handle limited types of constraints in an ad-hoc manner. This project pursues a systematic framework for dealing with constrained optimization using VQCs, and it thus advances discovery at the intersection of quantum computing and optimization on three fronts. First, the proposed algorithms could markedly expand the applicability of VQCs to cope with large-scale optimization with applications in optimal resource allocation, signal processing, machine learning, and quantum physical sciences. Second, the proposed optimization models may constitute indispensable ingredients of the optimization software packages ten years from now, when some sort of quantum processing unit may have been integrated into our computing machinery. Third, the proposed analyses may identify the engineering applications VQCs could have a more profound impact and usher the design of more refined architectures as quantum hardware matures. The expected benefits to the industry are cutting-edge algorithmic solutions that offer value added to the nascent yet possibly disrupting technology of VQCs. This project proposes a comprehensive hybrid quantum/classical computing framework for solving optimization problems with constraints over binary and/or large-scale continuous decision variables using VQCs. The framework is termed Variational Quantum Eigensolver with Constraints (VQEC). The specific project objectives are to: i) Devise novel iterative algorithms for optimizing the parameters of a VQC to deal with constrained problems, featuring enhanced convergence while complying with the oddities of VQCs; ii) Chart the types of optimization problems (binary programs, linear programs, quadratically constrained quadratic programs, semidefinite programs) that could be handled by VQEC and modify VQEC algorithms accordingly; and iii) Analyze the performance degradation when solving an optimization problem in its variational quantum form over the VQC parameters rather than its original form. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.