Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
arXiv:2302.04196 · doi:10.1088/2058-9565/ace474
Abstract
Combinatorial optimization problems are ubiquitous in industry. 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 have emerged as promising candidates for solving these problems in the noisy intermediate-scale quantum stage. 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 does not ensure that the constraints are satisfied due to the existence of local minima. In this paper, we introduce a new method for solving combinatorial optimization problems with challenging constraints using variational quantum algorithms. We propose the Multi-Objective Variational Constrained Optimizer (MOVCO) to classically update the variational parameters by a multiobjective optimization performed by a genetic algorithm. This optimization allows the algorithm to progressively sample only 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.
arXiv comment19 pages, 9 figures + appendix (4 pages, 2 figures)
References in corpus (39)
- Quantum Computing in the NISQ era and beyond
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- Efficient classical simulation of slightly entangled quantum computations
- pymoo: Multi-objective Optimization in Python
- Barren plateaus in quantum neural network training landscapes
- A Quantum Approximate Optimization Algorithm
- Noisy intermediate-scale quantum (NISQ) algorithms
- Parameterized quantum circuits as machine learning models
- Elucidating Reaction Mechanisms on Quantum Computers
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Towards Practical Quantum Variational Algorithms
- Quantum optimization using variational algorithms on near-term quantum devices
- Variational ansatz-based quantum simulation of imaginary time evolution
- Generalized Unitary Coupled Cluster Wavefunctions for Quantum Computation
- Variational quantum algorithms for nonlinear problems
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers
- Quantum computing enhanced computational catalysis
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
- Improving Variational Quantum Optimization using CVaR
- Resource-Efficient Quantum Algorithm for Protein Folding
- Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
- Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
- Benchmarking the Quantum Approximate Optimization Algorithm
- A case study of variational quantum algorithms for a job shop scheduling problem
- Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
- Penalty methods for variational quantum eigensolver
- Quantum variational optimization: The role of entanglement and problem hardness
- Quantum Image Segmentation Based on Grayscale Morphology
- Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
- Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations
- Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization
- A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem
- Forbidden subspaces for level-1 QAOA and IQP circuits
- Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver