An effective method for reducing function optimization problems from continuous variables to QUBO on the example of synchronous inversion of seismic data
Nickolay V Maletin, M. Tokarev, Dmitry V Minaev, Nadezhda A Borshchevskaia
Abstract The paper provides a brief overview of the current state of development of quantum, hybrid and quantum-inspired annealers and the problems that can be solved with their help. We propose a method for reducing high-degree polynomial optimization problems from a large number of continuous variables to quadratic unconstrained binary optimization (QUBO) problems, developed by the authors and not previously encountered in the literature. The QUBO formulation of the 1D problem of synchronous model-based inversion of seismic data, obtained through this method, is presented. Evaluations are carried out that demonstrate a significantly higher efficiency of the introduced technique in comparison with the standard one, as well as the possibility of solving the 1D problem of synchronous model-based inversion of industrial-scale seismic data (containing ∼1000 time steps) on the latest models of the D-Wave hybrid annealer.
Abstract The paper provides a brief overview of the current state of development of quantum, hybrid and quantum-inspired annealers and the problems that can be solved with their help. We propose a method for reducing high-degree polynomial optimization problems from a large number of continuous variables to quadratic unconstrained binary optimization (QUBO) problems, developed by the authors and not previously encountered in the literature. The QUBO formulation of the 1D problem of synchronous model-based inversion of seismic data, obtained through this method, is presented. Evaluations are carried out that demonstrate a significantly higher efficiency of the introduced technique in comparison with the standard one, as well as the possibility of solving the 1D problem of synchronous model-based inversion of industrial-scale seismic data (containing ∼1000 time steps) on the latest models of the D-Wave hybrid annealer.
Abstract This work demonstrates the fundamental possibility of solving quite large-scale problems of seismic data inversion on modern hybrid (quantum-classical) and quantum-inspired annealers using the example of a one-dimensional problem for a horizontally layered model of the medium in the acoustic approximation. The optimization problem for the residual function of observed and model data is decomposed into three problems: the optimization problem for a simpler function of the same dimension, the problem of finding the minimum of a one-dimensional function, and the problem of calculating the terms of a simple recurrent series. Then, the optimization problem for a simpler function is transformed into a quadratic unconstrained binary optimization problem of such a dimension that its solution can be calculated on modern annealers.
Abstract One of the promising areas for the future application of quantum computers is problems that are solved using stochastic modeling methods. One of these problems is the problem of synchronous inversion of seismic data in the presence of multimodal information on the elasticity characteristics of geological rocks. This paper analyzes the possibility of solving this problem using quantum annealing. Its reduction to the QUBO task is demonstrated. An assessment is carried out demonstrating the fundamental possibility of solving industrial-scale 1D problems on the latest models of the D-Wave hybrid quantum-classical annealer. In conclusion, an idea is briefly discussed, which, if successfully implemented, may make it possible to solve many 1D problems at once on such an annealer.
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.
Quantum annealing is a recent advancement in the field of optimization metaheuristics. Quantum annealers such as the D-Wave machines are primarily designed for solving discrete optimization problems. Solving nonlinear continuous optimization problems is also a very challenging task, in particular when nonconvex functions and multiple local optima are involved; nevertheless, convex problems can be solved efficiently using standard classical methods. It has not been explored in sufficient detail how quantum annealing could help in solving continuous optimization problems. In this work, we develop a prototype quantum-inspired solver for nonlinear continuous optimization problems. The solver is hybrid, as it has two pathways - classical and quantum-inspired. Given a continuous optimization problem via the web-based graphical interface that enables users to define and edit optimization problems, our solver computes a nonconvexity index for the problem, which determines the solution pathway. Problems with low nonconvexity indices are sent through the classical pathway and solved by standard separable programming techniques, while the others are transformed into mixed integer linear programming (MILP) problems via separable reformulations, which are restated as quadratic unconstrained binary optimization (QUBO) problems - the problem format compatible for quantum annealers, and eventually sent through the quantum pathway using D-Wave’s Neal sampler.
Quantum annealing is a metaheuristic method aimed at finding the global minimum of a pseudo-Boolean quadratic function. To solve a problem by a quantum annealer, it must be restated as a QUBO (quadratic unconstrained binary optimization) problem, the standard format acceptable to an annealer. However, there are many natural problems that turn out be of cubic or higher order, yet promising solutions can be obtained for many instances using quantum annealers, after converting to the QUBO format, using order reduction criteria. Accordingly, quadratization becomes a crucial preprocessing step in order to make use of present-day quantum annealing hardware that relies on coupling technology, which can only process interactions of at most degree two. A critical challenge is that quadratization methods often require many additional variables, degrading the performance of the annealers. A number of algorithmic and heuristic quadratization techniques have been proposed and used for annealing in the literature, affecting the performance of the annealers differently. We examine a number of such quadratization techniques, focusing on their efficiency, compactness, and applicability. We analyze the approaches motivated by diverse goals and highlight the transition from foundational approaches to more recent compact approaches. An evaluation of the current usage of different quadratization methods in the literature is carried out at the end of the survey. Further, we comment on the limitations on usage and show possible opportunities to enhance the performance of annealers.
This study demonstrates the application of quantum computing based quantum annealing to seismic traveltime inversion, a critical approach for inverting highly accurate velocity models. The seismic inversion problem is first converted into a Quadratic Unconstrained Binary Optimization problem, which the quantum annealer is specifically designed to solve. We then solve the problem via quantum annealing method. The inversion is applied on a synthetic velocity model, presenting a carbon storage scenario at depths of 1000-1300 m. As an application example, we also show the capacity of quantum computing to handle complex, noisy data environments. This work highlights the emerging potential of quantum computing in geophysical applications, providing a foundation for future developments in high-precision seismic imaging.