Multiobjective variational quantum optimization for constrained problems: an application to Cash Management

• URL: http://arxiv.org/abs/2302.04196v1
• Date: Wed, 8 Feb 2023 17:09:20 GMT
• Title: Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• Authors: Pablo D\'iez-Valle, Jorge Luis-Hita, Senaida Hern\'andez-Santana, Fernando Mart\'inez-Garc\'ia, \'Alvaro D\'iaz-Fern\'andez, Eva Andr\'es, Juan Jos\'e Garc\'ia-Ripoll, Escol\'astico S\'anchez-Mart\'inez, Diego Porras
• Abstract summary: We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms. We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
• Score: 45.82374977939355
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  This paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints. The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect.
  arXiv  Detail & Related papers  (2023-05-14T03:49:10Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization [7.541345730271882]
  In general, such constraints cannot be easily encoded in the circuit, and the quantum circuit measurement outcomes are not guaranteed to respect the constraints. We propose a new approach for solving constrained optimization problems with unimplement, easy-to-constrained quantum ansatze. We implement our method in QVoice, a Python package that interfaces with Qiskit for quick prototyping in simulators and on quantum hardware.
  arXiv  Detail & Related papers  (2022-11-13T20:58:00Z)
• Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
  We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer.
  arXiv  Detail & Related papers  (2022-09-29T18:00:40Z)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device. We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
  arXiv  Detail & Related papers  (2022-09-07T18:01:01Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Comparing Classical-Quantum Portfolio Optimization with Enhanced Constraints [0.0]
  We show how to add fundamental analysis to the portfolio optimization problem, adding in asset-specific and global constraints based on chosen balance sheet metrics. We analyze the current state-of-the-art algorithms for solving such a problem using D-Wave's Quantum Processor and compare the quality of the solutions obtained to commercially-available optimization software.
  arXiv  Detail & Related papers  (2022-03-09T17:46:32Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.