Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Understand

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications.

• To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost.
• With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers.
• Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables.