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

Abstract

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.

References in corpus (15)

• Quantum Mechanics helps in searching for a needle in a haystack
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Quantum annealing with more than one hundred qubits
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Quantum Optimization of Fully-Connected Spin Glasses
• Practical optimization for hybrid quantum-classical algorithms
• MAX 2-SAT with up to 108 qubits

Cited by in corpus (5)

• Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
• Towards Arbitrary QUBO Optimization: Analysis of Classical and Quantum-Activated Feedforward Neural Networks