We live in a world of dramatic change. Companies and societies are trying to tackle increasingly complex issues, and they are turning their attention to quantum technologies. Although it is expected to take some time before we see full-fledged quantum computers that utilize quantum phenomena, Toshiba is already working on quantum-inspired optimization technologies. We are applying our own in-house combinatorial optimization technologies for producing optimal results from massive numbers of options, providing them in the form of the quantum-inspired “SQBM+” optimization solution. This solution uses existing computers to produce highly accurate approximate solutions in short amounts of time. In this running feature, we will explain quantum-inspired optimization technologies.
In Part 1, we explained two methods in quantum computers (the gate method and the Ising machine method) and the positioning and structure of the quantum-inspired optimization technologies for them. In Part 2, we explained bifurcation, which is an important element of these technologies, along with how processing is accelerated and improved, and we provided an overview of the technologies. In Part 3, we will focus on combinatorial optimization problems.

In Part 1, we explained that the methods in quantum computers can be broadly divided into two types: the gate method and the Ising machine method. “Gate-based computers” are envisioned for general purpose applications, while “Ising machines” are specially tailored for solving combinatorial optimization problems.

But what is “combinatorial optimization”? Let’s delve into the world of optimization.

Optimization means “putting a phenomenon or system into the most suitable state for achieving specific objectives.” Let’s consider an example from the transport field: the optimization of a vehicle’s driving route.

Let us imagine that there are multiple vehicles driving toward different respective destinations. Each driver wants to reach their own destination in the shortest amount of time. If every vehicle drives along the shortest route, the vehicles will converge on certain roads and intersections, causing traffic jams. This will ultimately delay their arrival at their destinations. If several vehicles instead drive down routes that are not the shortest routes, this could reduce the amount of traffic congestion and result in shorter average arrival times.

So what routes should each vehicle take? Let us try to minimize the number of vehicles that choose not to drive the shortest routes.

Using a mathematical model to determine the optimal solutions to social problems and operation issues, such as searching for optimal results under specific conditions (constraints), is known as “mathematical optimization.”

In mathematical optimization, (1) the problem is expressed in the form of a mathematical model (mathematical modeling), (2) an “objective function” is defined so that the problem can be mathematically handled (formulation), and then (3) the input values that produce the smallest or largest objective function outputs are determined (minimization/maximization) (Fig. 1).

Mathematical optimization procedure

(1) Mathematical modeling
The problem is abstracted or simplified and represented in formula or graph form so that it can be handled mathematically.

(2) Formulation
In the mathematical model, a grading scale that indicates which states are desirable states is defined and variables that express the potential choices are selected. An objective function is developed to match up inputs, which are decided by these variables, and outputs, which indicate the evaluation of the results of those inputs. The constraints that apply to those inputs are also decided.

(3) Minimization/maximization
The input values that produce the largest and smallest outputs when applied to the objective function are determined, within the boundaries set by the constraints on the variables. These are the mathematical optimization results.

For the traffic example mentioned above, the procedure would be as follows.

(1) The flow of vehicles is graphed.

(2) As a measure of output desirability, a factor such as “traffic congestion” is chosen for investigation. The combinations of routes that can be taken by each vehicle are set as variables. A formula is chosen for calculating the degree of traffic network congestion for each combination of selected routes. This is the objective function. Constraints are then decided. For example, a constraint could be that automobiles that choose routes other than the shortest route must account for 1% or fewer of all the automobiles.

(3) The input value (combination of routes selected by the vehicles) that produces the smallest objective function (congestion) output is determined.

There are various types of optimization problems, such as linear programming problems and quadratic programming problems. They can be categorized by (a) the type of objective function, (b) whether or not there are constraints, and (c) the types of variables in the (2) formulation and (3) minimization/maximization steps above.

For example, when the objective function is expressed linearly, the problem is called a linear programming problem. When the objective function is a quadratic equation and the constraint is linear, the problem is called a quadratic programming problem. Within linear programming problems, when the values of variables are only integers, such as -2, -1, 0, 1, or 2, the process is called integer programming. When variables include both integers and so-called real numbers that correspond to continuous values on a number line, the process is called mixed integer programming (Fig. 2).

Combinatorial optimization is applied to discrete variable combinations. For example, a Hamiltonian path problem determines if there is a route that can connect all of the peaks in a graph in a single uninterrupted line. A knapsack problem is used to maximize the value of multiple products that can be placed into a container with weight or size constraints (a knapsack). A job-shop scheduling problem is used to optimize manufacturing processes.

Combinatorial optimization problems appear in all kinds of places in the real world, such as searching for which route that passes through several sightseeing spots would allow them to be visited in the shortest period of time. In the transportation example, if the number of potential routes to be taken by each vehicle is limited to two, the input to the objective function becomes a discrete combination of two choices for each vehicle, so the problem is a combinatorial optimization problem.

In combinatorial optimization, the number of possible inputs is limited, so a brute force approach can be applied to produce results: each input candidate can be fed into the objective function to perform calculations and the results can be compared to find the input value for which the objective function produces the smallest output value. However, when there is a larger number of variables, the number of input value candidates increases exponentially, so using the brute force approach to produce an answer within a limited amount of time is not practical.

For example, in the traffic example, if there are 1,000 vehicles driving within the area, and each vehicle has two potential routes it can follow, the number of input values for the objective function becomes 2¹⁰⁰⁰. This represents an order of more than 10³⁰⁰. There are only 10⁸⁰ atoms in the entire universe, which shows just how truly massive this 2¹⁰⁰⁰ is. For a number of combinations this large, even the fastest existing computers would not be able to examine every single pattern.

That is why combinatorial optimization problems require a different approach; one that is more efficient than brute force. Various different methods have been tried, and highly efficient algorithms have been developed for solving specific problems. However, many combinatorial optimization problems are in extremely difficult classes of problems -- so-called “NP-hard” and “NP-complete”* problems. It is believed that there are no efficient general-purpose methods for accurately determining optimal solutions to these problems.

* “NP-hard” and “NP-complete”: These are classes of computing difficulty for problems solved using computers. The classification is based on computational complexity theory. It is not believed that there are any methods for efficiently solving problems which are NP-hard (that is, which have non-deterministic polynomial-time hardness) or which are NP-complete (that is, which are non-deterministic polynomial-time complete) using modern computers.

In the real world, in many cases there is no need to rigorously determine the precise optimal solution. Instead, it is often sufficient to find input patterns that produce low evaluation function values at the practical level (suboptimal solutions). For situations such as these, algorithms have been proposed for efficiently solving problems without brute forcing them, although the results of these algorithms are not theoretically guaranteed. SQBM+ is one of those solvers*.

* Solver: A software library used to solve mathematical problems.

Many Ising machines used to solve combinatorial optimization problems provide interfaces for solving a specific type of combinatorial optimization problem: a QUBO* problem.

* Quadratic Unconstrained Binary Optimization

QUBO is a type of pattern within combinatorial optimization, and QUBO interfaces do not apply to all combinatorial optimization problems. Because of that, many Ising machines are based on QUBO interfaces but deal with general combinatorial optimization problems by using measures such as those shown below (Fig. 3).

(1) Dealing with objective functions other than quadratic functions

The objective functions of combinatorial optimization problems cannot solve problems such as cubic or higher polynomial equations using QUBO interfaces, which are meant for quadratic functions. To solve these problems, the number of variables can be increased to rewrite higher polynomial equations as quadratic equations, which are solved using QUBO. There are solvers which use this approach to provide interfaces called PUBO (Polynomial Unconstrained Boolean Optimization) interfaces that extend QUBO interfaces.

The SB Algorithm (Simulated Bifurcation Algorithm) used by SQBM+ is not limited to quadratic objective functions in the first place. Therefore, depending on the problem, it can directly handle cubic or higher polynomial equations, without converting the higher-order polynomial equation into a quadratic equation.

(2) Dealing with constraints

In many cases, combinatorial optimization problems have constraints. For example, in the traffic example, the requirement that “automobiles that choose routes other than the shortest route must account for 1% or fewer of all the automobiles” is a constraint.

When there are constraints, the problems cannot be solved with a QUBO interface, which presupposes that there are no constraints. To deal with this, methods such as the penalty method are used. With the penalty method, first a “function C” is developed which outputs 0 when the constraint is met and outputs a value larger than 0 when the constraint is not met. Next, “parameter k,” which adjusts the balance between the constraint and the objective function, is used to create “F'(=F+kC),” the sum of the original objective function F and kC. F' is set as a new objective function. If parameter k is set appropriately, the new objective function F' can be minimized to minimize objective function F while making C equal to 0. This means that the original objective function F can be minimized while satisfying the constraint, converting the problem into a constraint-free combinatorial optimization problem which can be solved using QUBO.

(3) Support for variables other than binary (0 or 1) variables

QUBO uses binary (0 or 1) variables, so it cannot be used for integer programming problems which have integer variables. To solve problems like this, the integers can be converted into binary form and then each digit in the binary string can be treated as an independent binary variable, so the problem can be reformulated in a form that can be solved using QUBO. This approach can also be used to solve problems with decimals.

Solving many real-world problems requires simultaneous handling of continuous values, not just binary or integer value variables. These problems can also be solved by applying various techniques to the SB Algorithm. One method is to perform hybrid processing, in which the binary portion is handled by SQBM+ and the continuous variable portion is handled using a conventional method other than SQBM+. In general, Ising machines can solve QUBO problems, but they do not excel at other problem patterns, so research has been carried out regarding combining Ising machines and conventional mathematical optimization technologies to produce hybrid algorithms that solve various types of problems with a high level of efficiency.

Research is being conducted regarding solving various problems using QUBO, and a wealth of related experience and know-how has been accrued. However, the reality is that applying the QUBO interface to new problems still involves a great deal of difficulty.

Nonetheless, if programs are written using the QUBO interface, when ultra-high performance quantum computers become a reality in the future, it may be possible to run the programs on these new computers as-is. This has the potential to greatly improve performance, making the concept an attractive one. Solving these different problems now, though, requires an interface that is easier to use.

SQBM+ provides not only a QUBO interface, but also other specialized interfaces for solving other problems such as maximum satisfiability problems, travelling salesman problems, and shift optimization problems. These solvers can be used to solve combinatorial optimization problems without requiring familiarity with QUBO.

Recently, progress has been made in middleware layers for using Ising machines. Solvers can be leveraged more efficiently if one can skillfully use this middleware.

In this part, focused on optimization, we explained what optimization is and how combinatorial optimization problems can be solved. In Part 4, we will introduce examples of actual problems solved using SQBM+.

• Quantum-Inspired Optimization Solutions “SQBM+”