GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models

• URL: http://arxiv.org/abs/2101.06250v2
• Date: Thu, 30 Jun 2022 17:58:26 GMT
• Title: GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models
• Authors: Javier Alcazar, Mohammad Ghazi Vakili, Can B. Kalayci, Alejandro Perdomo-Ortiz
• Abstract summary: We introduce a new framework that leverages machine learning models known as generative models to solve optimization problems. We focus on a quantum-inspired version of GEO relying on tensor-network Born machines. We show its superior performance when the goal is to find the best minimum given a fixed budget for the number of function calls.
• Score: 62.997667081978825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a new framework that leverages machine learning models known as generative models to solve optimization problems. Our Generator-Enhanced Optimization (GEO) strategy is flexible to adopt any generative model, from quantum to quantum-inspired or classical, such as Generative Adversarial Networks, Variational Autoencoders, or Quantum Circuit Born Machines, to name a few. Here, we focus on a quantum-inspired version of GEO relying on tensor-network Born machines and referred to hereafter as TN-GEO. We present two prominent strategies for using TN-GEO. The first uses data points previously evaluated by any quantum or classical optimizer, and we show how TN-GEO improves the performance of the classical solver as a standalone strategy in hard-to-solve instances. The second strategy uses TN-GEO as a standalone solver, i.e., when no previous observations are available. Here, we show its superior performance when the goal is to find the best minimum given a fixed budget for the number of function calls. This might be ideal in situations where the cost function evaluation can be very expensive. To illustrate our results, we run these benchmarks in the context of the portfolio optimization problem by constructing instances from the S\&P 500 and several other financial stock indexes. We also comprehensively compare state-of-the-art algorithms in a generalized version of the portfolio optimization problem. The results show that TN-GEO is among the best compared to these state-of-the-art algorithms; a remarkable outcome given the solvers used in the comparison have been fine-tuned for decades in this real-world industrial application. We see this as an important step toward a practical advantage with quantum-inspired models and, subsequently, with quantum generative models.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization [12.016449555335976]
  We propose an open-source benchmark suite MaxCut-Bench dedicated to the NP-hard Maximum Cut problem in both its weighted and unweighted variants. We use the benchmark in an attempt to systematically corroborate or reproduce the results of several, popular learning-based approaches. Our results show that several of the learneds fail to outperform a naive greedy algorithm, and that only one of them consistently outperforms Tabu Search.
  arXiv  Detail & Related papers  (2024-06-14T19:44:23Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  We show that a model-free stage-based Q-learning algorithm can enjoy the same optimality in the $H$ dependence as model-based algorithms. Our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions.
  arXiv  Detail & Related papers  (2023-08-17T08:34:58Z)
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models [62.997667081978825]
  We build over a proposed framework for evaluating the generalization performance of generative models. We establish the first comparative race towards practical quantum advantage (PQA) between classical and quantum generative models. Our results suggest that QCBMs are more efficient in the data-limited regime than the other state-of-the-art classical generative models.
  arXiv  Detail & Related papers  (2023-03-27T22:48:28Z)
• 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)
• 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)
• Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection [1.9182522142368683]
  We introduce a variational quantum algorithm to solve unconstrained black box binary problems. This is in contrast to the typical setting of quantum algorithms for optimization. We show that the quantum method produces competitive and in certain aspects even better performance than traditional feature selection techniques.
  arXiv  Detail & Related papers  (2022-05-06T07:02:15Z)
• Generalization Metrics for Practical Quantum Advantage in Generative Models [68.8204255655161]
  Generative modeling is a widely accepted natural use case for quantum computers. We construct a simple and unambiguous approach to probe practical quantum advantage for generative modeling by measuring the algorithm's generalization performance. Our simulation results show that our quantum-inspired models have up to a $68 times$ enhancement in generating unseen unique and valid samples.
  arXiv  Detail & Related papers  (2022-01-21T16:35:35Z)

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.