Combining Quantum-Classical Optimization at Mathlabs

The complexity of human systems and the detail of the questions we would like to answer is ever increasing. We want to discover the most nuanced solution to ever larger systems and make the best decision possible to move forward and do better than our competitors.

As part of Math Labs’ mission to help companies optimise their decision making using an increasing array of signals generated from world data, we have been continuously working at building a set of powerful inhouse tools for ourselves and our clients to transform these signals into optimal choices.

Across domains & industries there are decisions that must be made over large systems considering many local and global factors — where currently simplifications and unnecessary assumptions are made that reduce the effectiveness of the chosen solutions. Whether it involves creating a dynamic portfolio of companies that readjusts itself fast, or calculating the optimum logistics distribution pattern, or even selecting the right subset of thousands of features that go into a commercial machine learning model. A powerful optimization approach can give that required edge over competitive solutions.

Today, many technical giants and start-ups have started building a plethora of quantum or dedicated/efficient classical solvers that could address some of the problems above — but these are still too cumbersome for businesses to use.

Math Labs for its own inhouse use of combinatorial optimization — has developed a bridge between the business ask and the complexity of these quantum solvers. It has built and has been continually enhancing its own framework for analysing, checking, and solving combinatorial problems using classical, quantum and hybrid solvers.

The framework assists a user through the pathway of building the formal QUBO problem, simplifying the system, identifying the best solution method, and finally performing analysis on the output.

What is a QUBO — Quadratic Unconstrained Binary Optimization

The field of combinatorial optimization is concerned with setting many yes/no binary decisions and each solution set of decisions yields a corresponding objective function value, like a cost or profit value, that is to be optimized.

In recent years, the QUBO model has resulted in a powerful approach that has been applied to a rich variety of these NP-hard combinatorial optimization problems.

The term Unconstrained in the QUBO definition refers to the fact that QUBOs allow the computation to satisfy all the constraints but will not rigorously insist that all the constraints MUST be solved.

Briefly, the cost function for a QUBO problem can be expressed in compact form: 𝑓(𝑥) =∑ 𝑥𝑖. 𝑄𝑖,𝑗.𝑥𝑗

Where n is the number of binary yes/no decisions to be made, 𝑄𝑖,𝑗 are set values that define the interaction between the {𝑖, 𝑗} binary interaction which encodes the actual problem to solve and 𝑥 = (𝑥1, 𝑥2, ⋯, 𝑥𝑛) is the vector of binary decision variables that is chosen when optimising the cost function. The Q-matrix is an (𝑛×𝑛) square symmetric.

What is the QUBO Solution Pathway

To solve many of these problems quadratic unconstrained binary optimization (QUBO) formulations can be created and allow for highly detailed specialised solutions to be quickly created over standard approaches that are either simplified or involve a lot of human time.

Solving these combinatorial problems involves:

1. Formalising the problem into a QUBO system with all the constraints and options encoded.
2. Tailoring and balancing all the terms to make the system easier to solve and be particular to your needs.
3. Potentially using heuristics to simplify system to focus on the more difficult parts for the main solve.
4. Solving the system using a classical, quantum or hybrid approaches.
5. Processing the solution, checking the solutions, and estimating the quality of the solves.

Classical, Quantum or Hybrid Solvers

There are a variety of heuristic methods, classical solvers (in software and hardware), quantum solvers using quantum annealing as well as hybrid approaches. All the different methods have their own abilities and limitations that can affect the quality of the solution and depending on the problem type different solver approaches will be better suited.

Via an analysis of the QUBO formalism, the study of the heuristic effect, and testing the different solver methods we can determine the most suited solver to use for the situation and for future use. This allows us to know that the solution methods have been selected so that they are optimised to solving of the problem given your time and cost constraints.

Tailoring and Analysing

There can be many extra constraints or conditions that can be particular to each problem where the user wants to tune the problem to meet their needs, and this can be a technical issue balancing the number of varied conditions needed to be encoded into the QUBO system. To aide this we have pre-built several conditions into QUBO form and methods to automate the balancing of the terms given the users preferences.

Further analysis on the output solutions is useful to know how the system is performing. For certain systems it is not possible to guarantee the optimum solution is achieved and in fact knowing many good options can be preferable for further analysis. To this end we have built systems to check if constraints have been met in the potential solutions and perform analysis on the solution distribution to inform the user on the effectiveness of the solve.

Conclusion & Impact

As modern systems are growing in complexity, with margins getting smaller the need for quicker and more efficient, nuanced decision making is more important across businesses than ever.

The strength of the QUBO formalism is its ability to encode many different decision-making factors into the optimization problem to achieve more optimal solutions. This allows us the ability to approach larger more complex problems than before with speed.

The issue that still arises is the difficulty for businesses to approach these problems and how for the practitioner and enterprise it can be a daunting task. Thus, Math Labs’ tools allow the user to tailor, tune and understand the formation of the QUBO model for the problem. It can perform analysis on the QUBO and determine the best solvers, whether they are classical, quantum or hybrid, to use to satisfy the business time-cost constraints. Further, it studies and checks the solutions to estimate how successful the solve has been and that any constraints have been met.

The overall aim is to enable these methods to be introduced to more problems, bring better, quicker solutions than were possible before to optimise more parts of the business where possible.