Gaussian Processes are used in many applications to model spatial phenomena. Within this context, a key issue is to decide the set of locations where to take measurements so as to obtain a better approximation of the underlying function. Current state of the art techniques select such set to minimize the posterior variance of the Gaussian process. We explore the feasibility of solving this problem by proposing a novel Quadratic Unconstrained Binary Optimization (QUBO) model. In recent years this QUBO formulation has gained increasing attention since it represents the input for the specialized quantum annealer D-Wave machines. Hence, our contribution takes an important first step towards the sampling optimization of Gaussian processes in the context of quantum computation. Results of our empirical evaluation shows that the optimum of the QUBO objective function we derived represents a good solution for the above mentioned problem. In fact we are able to obtain comparable and in some cases better results than the widely used submodular technique.
Gaussian Processes are used in many applications to model spatial phenomena. Within this context, a key issue is to decide the set of locations where to take measurements so as to obtain a better approximation of the underlying function. Current state of the art techniques select such set to minimize the posterior variance of the Gaussian process. We explore the feasibility of solving this problem by proposing a novel Quadratic Unconstrained Binary Optimization (QUBO) model. In recent years this QUBO formulation has gained increasing attention since it represents the input for the specialized quantum annealer D-Wave machines. Hence, our contribution takes an important first step towards the sampling optimization of Gaussian processes in the context of quantum computation. Results of our empirical evaluation shows that the optimum of the QUBO objective function we derived represents a good solution for the above mentioned problem. In fact we are able to obtain comparable and in some cases better results than the widely used submodular technique.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.
Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
In this note, we describe an experiment on portfolio optimization using the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The dataset we use is taken from a real-world problem for which a classical solution is currently deployed and used in production. In this work, carried out in a collaboration between the Raiffeisen Bank International (RBI) and Reply, we derive a QUBO formulation, which we solve using various methods: two D-Wave hybrid solvers, that combine the employment of a quantum annealer together with classical methods, and a purely classical algorithm. Particular focus is given to the implementation of the constraint that requires the resulting portfolio’s variance to be below a specified threshold, whose representation in an Ising model is not straightforward. We find satisfactory results, consistent with the global optimum obtained by the exact classical strategy. However, since the tuning of QUBO parameters is crucial for the optimization, we investigate a hybrid method that allows for automatic tuning.
Abstract In this note, we describe an experiment on portfolio optimization using the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The dataset we use is taken from a real-world problem for which a classical solution is currently deployed and used in production. In this work, carried out in a collaboration between the Raiffeisen Bank International (RBI) and Reply, we derive a QUBO formulation, which we solve using various methods: two D-Wave hybrid solvers, that combine the employment of a quantum annealer together with classical methods, and a purely classical algorithm. Particular focus is given to the implementation of the constraint that requires the resulting portfolio’s variance to be below a specified threshold, whose representation in an Ising model is not straightforward. We find satisfactory results, consistent with the global optimum obtained by the exact classical strategy. However, since the tuning of QUBO parameters is crucial for the optimization, we investigate a hybrid method that allows for automatic tuning.