  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. This technique can be applied to any QUBO instance and leads to
either an all-classical or a hybrid quantum-classical approach. When quantum
heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used,
our proposal leads to a double advantage: a substantial reduction of quantum
resources, specifically an average of ~42% fewer qubits to solve MaxCut on
random 3-regular graphs, together with an improvement in the quality of the
approximate solutions reached.
