Speaker
Description
Combinatorial optimization problems (CO) have a strong impact on a wide range of disciplines such as finance, machine learning, logistics, etc. In addition to finding a solution with minimum cost, problems of high relevance involve a number of constraints that the solution must satisfy. Variational quantum algorithms (VQA) have emerged as promising candidates for solving these problems in the noisy intermediate-scale quantum stage [1]. However, the constraints are often complex enough to make their efficient mapping to quantum hardware difficult or even infeasible. An alternative standard approach is to transform the optimization problem to include these constraints as penalty terms, but this method involves additional hyperparameters and has several shortcomings [2].
Our work introduces the Multi-Objective Variational Constrained Optimizer (MOVCO), a new method for solving CO with challenging constraints [3]. MOVCO combines the quantum variational framework with a genetic multi-objective optimization to simultaneously optimize the projection of the variational wave function onto the subspace of solutions satisfying all constraints, and the energy of the feasible solutions. This procedure allows the algorithm to progressively sample states within the in-constraints space, while optimizing the energy of these states. We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem. We introduce a novel mathematical formulation for this problem, and compare the performance of MOVCO versus a penalty-based optimization. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima that do not satisfy any of the mandatory constraints.
References
[1] M.Cerezo et al., Nature Reviews Physics, 3 (2021).
[2] Andrew Lucas, Front.Phys., 2 (2014).
[3] Pablo Díez-Valle et al., arxiv preprint 2302:04196 (2023).
