A Walkthrough of Qiskit’s New Optimization Module
A new module will boost research, development, and benchmarking of quantum optimization algorithms for near-term quantum computers
By Stefan Woerner
Optimization
Optimization problems arise in all areas of business and science: from healthcare logistics, to DNA sequence alignment, to balancing electricity networks. In many relevant cases, finding the optimal solution for a problem is intractable. This is particularly so for combinatorial optimization problems, such as the aforementioned examples, where the number of possible solutions grows exponentially with the problem size. Thus, we often have to rely on approximations or heuristics to find reasonable solutions. Hence, there is significant potential for further improvement, which could lead to higher quality, lower risk, and reduced resource requirements for many applications. Therefore, tremendous effort is put toward improving and developing new optimization algorithms to speed up computations and improve solution quality.
Quantum Optimization
A growing number of quantum optimization algorithms have been proposed. Some — usually assuming fault-tolerant quantum computers — have proven speed-ups over classical optimization algorithms. Others — possibly applicable already on near-term devices — are promising heuristics with the potential to outperform classical approximations. Such algorithms have already been demonstrated on real quantum devices for small illustrative problems, such as protein folding, portfolio optimization, and transaction settlement. These examples provide only a tiny outlook on the vast number of applications where quantum optimization may have an enormous impact in the future once quantum devices are available at the required scale.
The following subheadings provide a link to the corresponding tutorials in Qiskit.
Quantum Optimization with Qiskit
Today, we announce the release of a new optimization module in Qiskit. This combines best practices from classical optimization with state-of-the-art quantum algorithms to enable rapid prototyping, support education, and boost cutting-edge research. The new module is a first of its kind and has been developed by IBM Quantum researchers as well as contributors from our open source community, with special acknowledgement to our IBM Quantum Network collaborators at JPMorgan Chase.
“This release of Qiskit comes with a new, user-friendly optimization module, and we are pleased to contribute a method for addressing Constrained Binary Polynomial Optimization problems, based on Grover Adaptive Search. The modular design and the standardized components of Qiskit made the integration of the method (in the context of QUBOs) quite straightforward. The collaboration with our IBM Quantum partners continues to be fruitful.” –Austin Gilliam and Constantin Gonciulea, JPMorgan Chase
The Qiskit Optimization module covers everything from high-level modelling of optimization problems with automatic conversion of problems to different required representations, to a suite of easy-to-use quantum optimization algorithms that are ready to run on classical simulators as well as on real quantum devices. It is designed for classical optimization researchers and practitioners as well as for quantum algorithms researchers and allows a jump start to develop and work with new algorithms. Here, we take advantage of Qiskit’s circuit library.
With this release, the Qiskit Optimization module enables easy, efficient modelling of optimization problems using DOcplex — IBM Decision Optimization CPLEX modeling. A uniform interface as well as automatic conversion between different problem representations allows users to solve problems using a large set of algorithms, from variational quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), to Grover Adaptive Search, leveraging fundamental quantum algorithms provided by Qiskit. Furthermore, the modular design allows it to be easily extended and facilitates rapid development and testing of new algorithms. Compatible classical optimizers are also provided for testing, validation, and benchmarking
Quadratic Programs
Qiskit supports Quadratically Constrained Quadratic Programs — for simplicity we refer to them just as Quadratic Programs — with binary, integer, and continuous variables, as well as equality and inequality constraints. This class of optimization problems has a vast amount of relevant applications, while still being efficiently representable by sparse matrices and vectors. This class covers some very interesting sub-classes, from Convex Continuous Quadratic Programs, which can be solved efficiently by classical optimization algorithms, to Quadratic Unconstrained Binary Optimization (QUBO) problems, which cover many NP-complete, i.e., classically intractable, problems.
Problem Converters
While the provided representation of optimization problems is rather generic, optimization algorithms usually require problems to satisfy certain criteria to be applicable. For instance, some algorithms can only be applied to QUBOs, but not to Quadratic Programs in general. Thus, Qiskit provides converters to automatically map optimization problems to different formats whenever possible. This includes, for example, the efficient encoding of integer variables as binary variables or penalizing linear equality constraints in the objective function. This significantly extends the applicability of the available quantum optimization algorithms and allows the efficient modelling of interesting applications.
(Recursive) Minimum Eigen Optimizer
Solving a QUBO is equivalent to finding a ground state of a corresponding Ising Hamiltonian and many optimization algorithms are based on this fact. Actually, (approximately) computing ground states is important in many applications, such as quantum chemistry or physics. Thus, Qiskit provides a range of Minimum Eigensolvers to compute ground states, such as the Variational Quantum Eigensolver (VQE) and QAOA. To leverage these fundamental algorithms, the Qiskit optimization module provides the Minimum Eigen Optimizer. The Minimum Eigen Optimizer translates a given suitable Quadratic Program to a Hamiltonian, by applying all necessary conversions, calls a given Minimum Eigensolver, and returns the optimization results. This allows us to exploit the extensive research for computing ground states in an optimization context, without any translation overhead, e.g. using alternative aggregation functions within the optimization.
A potential limitation of variational algorithms is the increase of circuit depth with respect to the problem size. This may be prohibitive to achieve a quantum advantage on near-term devices. However, as proposed in a recent research article for QAOA, this may be overcome using a recursive optimization scheme: Recursive QAOA. In Qiskit, this concept is generalized to the Recursive Minimum Eigen Optimizer, which can be combined with the Minimum Eigen Optimizer, and thus, with every Minimum Eigensolver provided by Qiskit. This recursive optimization scheme may help to lower the required depth of the quantum circuits involved, and thus, speed-up the journey towards quantum advantage for optimization.
Grover Optimizer
Although most quantum algorithms for QUBOs are related to finding ground states of a corresponding Hamiltonian, this is not the only possibility. Our collaborators at JPMorgan Chase developed an efficient way to translate QUBOs to quantum oracles, which enables optimization based on Grover Search, with a quadratic speed-up over brute force search. Given the unified design, it is straight-forward to solve a given QUBO either using the Hamiltonian formalism or the Grover Optimizer, without having to change the model.
ADMM Optimizer
Although many relevant problems can be formulated as QUBOs, there are also lots of problems where this is not possible. Some applications contain budget, capacity, or resource limitations, which are usually modeled as inequality constraints, and thus, not compatible with QUBOs. Other applications require both, continuous and discrete, variables, which again, cannot be modeled as part of a QUBO. To approach such problems, Qiskit provides the ADMM Optimizer. The Alternating Direction Method of Multipliers (ADMM) allows the decomposition of certain Mixed Integer Programs (MIPs) into a sequence of QUBOs and convex continuous quadratic programs. This heuristic takes a QUBO optimizer as well as a convex continuous optimizer, calls both to solve the constructed sub-problems, and iteratively approximates the solution to the original MIP.
Classical Optimizers
Qiskit also provides three classical optimizers for validation, testing, benchmarking, and also as sub-routines, e.g., within the ADMM Optimizer. A first optimizer wraps IBM ILOG® CPLEX®, a state-of-the-art classical solver for (convex) Quadratic and Linear Programs. The two other optimizers wrap SciPy’s COBYLA and SLSQP, respectively, as alternatives to CPLEX for continuous constrained optimization.
How to get started
Qiskit’s optimization module is the first of its kind and allows for classically simulating the algorithms as well as testing them on real quantum devices, including IBM’s quantum systems available today to the public. Tutorials on how to model your own optimization problems and on how to use the different optimizers to solve them can be found here. This release is a milestone on the path to quantum advantage for optimization, which eventually could be impacting us in about any application area imaginable.
Here’s an example of how to solve a quadratic problem with a quantum optimization algorithm:
Qiskit will continuously grow to include new exciting research results and new classes of optimization problems and algorithms. Furthermore, new and enhanced Qiskit application modules will be released in the coming months, so stay tuned!
Acknowledgments
A special thanks to the core contributors of this first release of Qiskit’s optimization module (in alphabetical order): Anton Dekusar, Julien Gacon, Claudio Gambella, Austin Gilliam, Constantin Gonciulea, Donny Greenberg, Takashi Imamichi, Jakub Mareček, Manoel Marques, Atsushi Matsuo, Andrea Simonetto, and Steve Wood.
