Combinatorial optimization is one of the key candidates in the race for practical quantum advantage. In this work, we introduce a new family of quantum-enhanced optimizers and demonstrate how quantum machine learning models known as quantum generative models can find lower minima than those found by means of stand-alone state-of-the-art classical solvers. We present two new quantum-enhanced optimization strategies. The first scheme leverages data points evaluated during the optimization search from any quantum or classical optimizer. In this scheme, we show how our quantum generative model boosts the performance of classical solvers in hard-to-solve instances where the classical solver is not capable of making progress as a stand-alone strategy. The second quantum optimization strategy works as a stand-alone solver. Here we show its superior performance when the goal is to find the best minimum within the least number of cost function evaluations. Under this setting, we benchmark our quantum-enhanced optimization strategies against several solvers, including Bayesian optimizers which are known to be one of the best competing solvers in such tasks. To illustrate our findings, these benchmarks are performed in the context of the portfolio optimization problem by constructing instances from the S&P 500 stock market index. We show that our quantum-inspired generative models based on tensor networks generalize to unseen candidates with lower cost function values than any of the candidates seen by the classical solvers. This is the first demonstration of the generalization capabilities of quantum generative models that brings real value in the context of an industrial-scale application.
Combinatorial optimization is one of the key candidates in the race for practical quantum advantage. In this work, we introduce a new family of quantum-enhanced optimizers and demonstrate how quantum machine learning models known as quantum generative models can find lower minima than those found by means of stand-alone state-of-the-art classical solvers. We present two new quantum-enhanced optimization strategies. The first scheme leverages data points evaluated during the optimization search from any quantum or classical optimizer. In this scheme, we show how our quantum generative model boosts the performance of classical solvers in hard-to-solve instances where the classical solver is not capable of making progress as a stand-alone strategy. The second quantum optimization strategy works as a stand-alone solver. Here we show its superior performance when the goal is to find the best minimum within the least number of cost function evaluations. Under this setting, we benchmark our quantum-enhanced optimization strategies against several solvers, including Bayesian optimizers which are known to be one of the best competing solvers in such tasks. To illustrate our findings, these benchmarks are performed in the context of the portfolio optimization problem by constructing instances from the S&P 500 stock market index. We show that our quantum-inspired generative models based on tensor networks generalize to unseen candidates with lower cost function values than any of the candidates seen by the classical solvers. This is the first demonstration of the generalization capabilities of quantum generative models that brings real value in the context of an industrial-scale application.
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.
Abstract Devising an efficient exploration of the search space is one of the key challenges in the design of combinatorial optimization algorithms. Here, we introduce the Generator-Enhanced Optimization (GEO) strategy: a framework that leverages any generative model (classical, quantum, or quantum-inspired) to solve optimization problems. We focus on a quantum-inspired version of GEO relying on tensor-network Born machines, and referred to hereafter as TN-GEO. To illustrate our results, we run these benchmarks in the context of the canonical cardinality-constrained portfolio optimization problem by constructing instances from the S&P 500 and several other financial stock indexes, and demonstrate how the generalization capabilities of these quantum-inspired generative models can provide real value in the context of an industrial application. We also comprehensively compare state-of-the-art algorithms and show that TN-GEO is among the best; a remarkable outcome given the solvers used in the comparison have been fine-tuned for decades in this real-world industrial application. Also, a promising step toward a practical advantage with quantum-inspired models and, subsequently, with quantum generative models
Abstract Constrained combinatorial 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 some heuristic solvers, these are typically addressed by introducing certain Lagrange multipliers in the cost function, by relaxing them in some way, or worse yet, by generating many samples and only keeping valid ones, which leads to very expensive and inefficient searches. In this work, we encode arbitrary integer-valued equality constraints of the form A x ⃗ = b ⃗ , directly into U(1) symmetric tensor networks (TNs) and leverage their applicability as quantum-inspired generative models to assist in the search of solutions to combinatorial optimization problems within the generator-enhanced optimization framework of Alcazar et al (2021 arXiv: 2101.06250 ). This allows us to exploit the generalization capabilities of TN generative models while constraining them so that they only output valid samples. Our constrained TN generative model efficiently captures the constraints by reducing number of parameters and computational costs. We find that at tasks with constraints given by arbitrary equalities, symmetric matrix product states outperform their standard unconstrained counterparts at finding novel and better solutions to combinatorial optimization problems.
As the quantum computing community gravitates towards understanding the practical benefits of quantum computers, having a clear definition and evaluation scheme for assessing practical quantum advantage in the context of specific applications is paramount. Generative modeling, for example, is a widely accepted natural use case for quantum computers, and yet has lacked a concrete approach for quantifying success of quantum models over classical ones. In this work, we construct a simple and unambiguous approach to probe practical quantum advantage for generative modeling by measuring the algorithm's generalization performance. Using the sample-based approach proposed here, any generative model, from state-of-the-art classical generative models such as generative adversarial networks (GANs) to quantum models such as quantum circuit born machines, can be evaluated under the same conditions on a concrete well-defined framework. In contrast to other sample-based metrics for probing practical generalization, we leverage constrained optimization problems (e.g., cardinality-constrained problems) and use these discrete datasets to define specific metrics capable of unambiguously measuring the quality of the samples and the model's generalization capabilities for generating data beyond the training set, but still within the valid solution space. Additionally, our metrics can diagnose trainability issues such as mode collapse and overfitting, as we illustrate when comparing GANs to quantum-inspired models built out of tensor networks. Our simulation results show that our quantum-inspired models have up to a 68 times enhancement in generating unseen unique and valid samples compared to the GANs explored here, and a ratio of 61:2 for generating samples with better quality than those observed in the training set. We foresee these metrics as valuable tools for rigorously defining practical quantum advantage in the domain of generative modeling, where finding a winning model remains an ongoing challenge as new architectures are developed.
Abstract Generative modeling has seen a rising interest in both classical and quantum machine learning, and it represents a promising candidate to obtain a practical quantum advantage in the near term. In this study, we build over an existing framework for evaluating the generalization performance of generative models, and we establish the first quantitative comparative race towards practical quantum advantage (PQA) between classical and quantum generative models, namely Quantum Circuit Born Machines (QCBMs), Transformers (TFs), Recurrent Neural Networks (RNNs), Variational Autoencoders (VAEs), and Wasserstein Generative Adversarial Networks (WGANs). After defining four types of PQAs scenarios, we focus on what we refer to as potential PQA, aiming to compare quantum models with the best-known classical algorithms for the task at hand. We let the models race on a well-defined and application-relevant competition setting, where we illustrate and demonstrate our framework on 20 variables (qubits) generative modeling task. Our results suggest that QCBMs are more efficient in the data-limited regime than the other state-of-the-art classical generative models. Such a feature is highly desirable in a wide range of real-world applications where the available data is scarce.
Although several models have been proposed towards assisting machine learning (ML) tasks with quantum computers, a direct comparison of the expressive power and efficiency of classical versus quantum models for datasets originating from real-world applications is one of the key milestones towards a quantum ready era. Here, we take a first step towards addressing this challenge by performing a comparison of the widely used classical ML models known as restricted Boltzmann machines (RBMs), against a recently proposed quantum model, now known as quantum circuit Born machines (QCBMs). Both models address the same hard tasks in unsupervised generative modeling, with QCBMs exploiting the probabilistic nature of quantum mechanics and a candidate for near-term quantum computers, as experimentally demonstrated in three different quantum hardware architectures to date. To address the question of the performance of the quantum model on real-world classical data sets, we construct scenarios from a probabilistic version out of the well-known portfolio optimization problem in finance, by using time-series pricing data from asset subsets of the S&P500 stock market index. It is remarkable to find that, under the same number of resources in terms of parameters for both classical and quantum models, the quantum models seem to have superior performance on typical instances when compared with the canonical training of the RBMs. Our simulations are grounded on a hardware efficient realization of the QCBMs on ion-trap quantum computers, by using their native gate sets, and therefore readily implementable in near-term quantum devices.