Abstract Quadratically Constrained Quadratic Programs (QCQPs) are an important class of optimization problems with diverse real-world applications. In this work, we propose a variational quantum algorithm for general QCQPs. By encoding the variables in the amplitude of a quantum state, the requirement for the qubit number scales logarithmically with the dimension of the variables, which makes our algorithm suitable for current quantum devices. Using the primal-dual interior-point method in classical optimization, we can deal with general quadratic constraints. Our numerical experiments on typical QCQP problems, including Max-Cut and optimal power flow problems, demonstrate better performance of our hybrid algorithm over classical counterparts.
Abstract Quadratically Constrained Quadratic Programs (QCQPs) are an important class of optimization problems with diverse real-world applications. In this work, we propose a variational quantum algorithm for general QCQPs. By encoding the variables in the amplitude of a quantum state, the requirement for the qubit number scales logarithmically with the dimension of the variables, which makes our algorithm suitable for current quantum devices. Using the primal-dual interior-point method in classical optimization, we can deal with general quadratic constraints. Our numerical experiments on typical QCQP problems, including Max-Cut and optimal power flow problems, demonstrate better performance of our hybrid algorithm over classical counterparts.
Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks, including solving optimization problems. Nonetheless, optimization problems with constraints may not have been handled in a disciplined fashion thus far. To address this gap, this work proposes a hybrid quantum-classical algorithmic paradigm termed the variational quantum eigensolver with constraints (VQEC) that extends the celebrated VQE to handle optimization with constraints. As with the standard VQE, the vector of optimization variables is captured by the state of a variational quantum circuit (VQC). To deal with constraints, VQEC optimizes a Lagrangian function classically over both the VQC parameters as well as the dual variables associated with constraints. To comply with the quantum setup, variables are updated via a perturbed primal-dual method leveraging the parameter shift rule. Among a wide gamut of potential applications, we showcase how VQEC can approximately solve quadratically constrained binary optimization problems, find stochastic binary policies satisfying quadratic constraints on the average and in probability, and solve large-scale linear programs over the probability simplex. Under an assumption on the error for the VQC to approximate an arbitrary probability mass function, we provide bounds on the optimality gap attained by a VQC. Numerical tests on a quantum simulator investigate the effect of various parameters and corroborate that VQEC can generate high-quality solutions.
Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks. Nonetheless, enforcing constraints in a disciplined fashion has been largely unexplored. To address this gap, this work proposes a hybrid quantum-classical algorithmic paradigm termed VQEC that extends the celebrated VQE to handle optimization with constraints. As with the standard VQE, the vector of optimization variables is captured by the state of a variational quantum circuit (VQC). To deal with constraints, VQEC optimizes a Lagrangian function classically over both the VQC parameters as well as the dual variables associated with constraints. To comply with the quantum setup, variables are updated via a perturbed primal-dual method leveraging the parameter shift rule. Among a wide gamut of potential applications, we showcase how VQEC can approximately solve quadratically-constrained binary optimization (QCBO) problems, find stochastic binary policies satisfying quadratic constraints on the average and in probability, and solve large-scale linear programs (LP) over the probability simplex. Under an assumption on the error for the VQC to approximate an arbitrary probability mass function (PMF), we provide bounds on the optimality gap attained by a VQC. Numerical tests on a quantum simulator investigate the effect of various parameters and corroborate that VQEC can generate high-quality solutions.
Conic programs arising in physics, quantum information, machine learning, and engineering are often defined over sparse graphs. Although such problems can be solved in polynomial time using classical interior-point solvers, the computational complexity scales unfavorably with graph size. We propose a variational quantum paradigm for solving conic programs, including quadratically constrained quadratic programs and semidefinite programs. We encode primal variables via the state of a parameterized quantum circuit (PQC) and dual variables via the probability mass function associated with a second PQC. The Lagrangian function can thus be expressed as scaled expectations of quantum observables. We pursue approximately stationary points of the Lagrangian by minimizing/maximizing the Lagrangian over the parameters of the first/second PQC. This is accomplished in a hybrid fashion: gradients are estimated using the two PQCs, while their parameters are updated classically using a primal-dual method. We propose permuting primal variables so that related observables have a banded form, enabling efficient measurement. We provide a complexity analysis that is useful to determine which problem types may enjoy quantum advantage. The framework is applied to the AC OPF problem, a large-scale optimization problem central to electric power system operation. Numerical tests on the IEEE 57-node system using PennyLane's simulator show that the proposed doubly variational quantum framework can find high-quality OPF solutions. While this demonstration does not yield a quantum speedup, the results serve as a proof-of-concept and highlight challenges toward practical quantum advantage. Although showcased for OPF, the framework has broader scope, including conic programs with many variables and constraints, problems defined over sparse graphs, and training quantum machine learning models to satisfy constraints.
Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.
Quantum computing provides alternative algorithmic approaches to solve computationally challenging problems and has shown potential advantages compared to classical methods for specific problem classes. This thesis explores variational quantum algorithms (VQAs) for solving the alternating current optimal power flow (AC OPF) problem and the AC power flow (PF) problem. Both tasks are fundamental to power system analysis, operation, and planning, but they become increasingly challenging as grid size and complexity grow. The first main contribution of the thesis introduces a variational quantum framework for solving the OPF problem, formulated as a nonconvex quadratically constrained quadratic program. The proposed method encodes primal and dual optimization variables using two parameterized quantum circuits (PQCs), allowing the OPF Lagrangian to be expressed as expectations over quantum observables. An OPF solution can be found by minimizing the Lagrangian over the parameters of the first PQC and maximizing it over the parameters of the second PQC. The proposed framework seeks saddle points of the Lagrangian in a hybrid fashion. The gradients of the Lagrangian are estimated using the two PQCs, and PQC parameters are updated classically using a primal-dual method. A key innovation is to permute the primal variables of the original problem, so the corresponding quantum observables adhere to a banded form that facilitates a novel qubit-efficient quantum measurement protocol. The second main contribution presents a quantum machine learning (QML) approach for learning AC PF solutions using a data-embedded PQC. The method first poses a single PF instance as a nonlinear least-squares problem over PQC parameters. Second, the PF specifications are embedded as features into another PQC, and the resultant QML model is trained to learn the PF mapping. Once presented with a new problem instance, the trained QML model can perform the prediction step efficiently in real-time operation. Third, a novel protocol is devised to efficiently measure PF observables by leveraging the graph structure of a power network. The proposed quantum AC PF/OPF framework sets the foundations for addressing more elaborate grid tasks via quantum computing. More broadly, the proposed quantum paradigms can be used to achieve safe QML as PQCs are trained to comply with data-dependent constraints.
Quantum algorithms offer a compelling new avenue for addressing difficult NP-complete optimization problems, such as the Generalized Assignment Problem (GAP). Given the operational constraints of contemporary Noisy Intermediate-Scale Quantum (NISQ) devices, hybrid quantum-classical approaches, specifically Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE), promises to be effective approaches to solve real-world optimization problems. This paper proposes an approach, named VQGAP, designed to efficiently solve the GAP by optimizing quantum resources and reducing the required parametrized quantum circuit width with respect to standard VQE. The main idea driving our proposal is to decouple the qubits of ansatz circuits from the binary variables of the General Assignment Problem, by providing encoding/decoding functions transforming the solutions generated by ansatze in the limited quantum space in feasible solutions in the problem variables space, by exploiting the constraints of the problem. Preliminary results, obtained through both noiseless and noisy simulations, indicate that VQGAP exhibits performance and behavior very similar to VQE, while effectively reducing the number of qubits and circuit depth.