VQEC: Constrained Optimization on a Variational Quantum Computer: Problem Modeling, Algorithmic Design, and Performance Analysis
Abstract
Background. Optimization solvers running on fault-tolerant quantum computers feature speed-ups over their classical computing counterparts. However, such quantum computers are not expected to be available soon. On the other hand, VQCs rely on the noisy and small-scale quantum hardware currently available to accomplish meaningful computational tasks and showcase practical quantum advantage in the near term. VQCs have so far been successful in providing near-optimal solutions to binary and large-scale continuous unconstrained optimization. In dealing with constraints, existing approaches either convert constraints to heavily penalized cost functions with unfavorable numerical properties or handle constraints of a few limiting types by crafting the VQC architecture. The lack of a principled manner to handle constraints has hampered the adoption of VQCs for constrained optimization. Project overview. We propose a hybrid quantum/classical computing framework using VQCs to solve large-scale quadratically constrained quadratic programs (QCQPs) and semidefinite programs (SDPs) encountered in engineering optimization. The framework is termed Variational Quantum Eigensolver with Constraints (VQEC). The 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 optimization problems and application domains that could be handled by VQEC and modify algorithms accordingly; and iii) Analyze the loss in optimality when solving a problem in its variational quantum rather than its original form.Novelty. The project explores three creative, original, and potentially transformative ideas: i) Constraints can be handled by VQCs by judiciously adjusting primal-dual optimization algorithms to the hybrid quantum/classical setting; ii) VQEC can naturally model decision variables as continuous or binary-valued vectors, and semidefinite matrices; and iii) The approximation properties of VQCs can be genuinely combined with duality theory togauge the loss in optimality involved in variational quantum optimization.Impact. This project can markedly expand the scope of VQCs to cope with optimization tasks of Department of Defense (DoD) interest. More specifically, QCQPs and SDPs appear in various domains, such as optimal resource allocation in wireless networks or electric power systems, optimal beamforming in radars, filter and circuit designs, controller design, and community detection in social networks. The framework is also applicable to binary programs, large-scale linear programs, and mixed-integer programs, which are used in large-scale logistic, learning, and mission planning problems that are of relevance to the Office of Naval Research as well. The developed models may form indispensable ingredients of optimization packages a few years from now when some quantum processing unit has been integrated into our computing machinery. Variational quantum optimization could surrogate classical solutions, warm-start classical solvers, or screen active constraints to reduce the constraint set. The expected benefits to related industries (quantum software/hardware, optimization vendors) are cutting-edge algorithms of value added to the nascent yet possibly disrupting technology of VQCs.Approved for Public Release
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412614
Entities
People
- Vassilis Kekatos
Organizations
- Office of Naval Research
- Purdue University
- United States Navy