  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.
