New pre-print “Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction”
Optimization is one of the areas where quantum computing is expected to change our computational capabilities in a disruptive way. Most industrially relevant combinatorial optimization problems are however too large to fit on current or foreseeable quantum processors.
The new preprint, by Mathias Schmid, Naeimeh Mohseni, and Michael J. Hartmann, offers a solution. We propose a divide and conquer approach that divides the problem into subproblems, each of which can fit on the available quantum processor. After using a quantum algorithm to find all solution candidates for each subproblem, we form a new, reduced problem from the solution candidates for all subproblems. This procedure can be iterated until the global optimum is found by solving the remaining reduced problem in one go of the quantum algorithm.
There are two important features in our approach: it can handle ubiquitous frustration, and the reduction is tuneable.