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.

基于 VQEC 算法模型，采用量子变分法和经典算法结合的方式进行带约束的优化，通过量子模拟器进行数值测试验证和参数优化，展示了其在近似解决复杂优化问题方面的优势。