Combinatorial Optimization: From Classical to Quantum 

Abstract:  From "quantum-inspired" complementary metal–oxide–semiconductor annealers to universal quantum computers, recent advances in these emerging technologies open the discussions of finding practical applications that can utilize such hardware. One of the most promising target applications is combinatorial optimization.

We first look at the Ising optimization model, or equivalently, quadratic unconstrained binary optimization model, a unified mathematical framework many special-purpose hardware for optimization aim to solve. We focus on problems larger than the current hardware size and advocate using a local search framework to create a sequence of sub-problems that can be solved with hardware of limited size.  We name this framework QUBO local search (QUBO-LS). In addition, we categorize QUBO-LS into two types: constrained QUBO local search (C-QUBO-LS) and unconstrained QUBO local search (U-QUBO-LS). In particular, our U-QUBO-LS addresses the limitations of the QUBO framework and demonstrates efficient use of the hardware by formulating the local search sub-problems into QUBOs that use fewer binary variables and more tailored to the original combinatorial optimization problems. Our U-QUBO-LS can be easily generalized to different combinatorial optimization problems, and we give models for local search techniques for the traveling salesman problem (TSP), graph partitioning (GP), quadratic assignment problem (QAP), and minimum 2-sum problem (M2sP) on IPUs as examples.

Next, we focus on combinatorial optimization on near-term universal quantum computers, which is a promising path to demonstrating quantum advantage. However, the capabilities of these devices are constrained by high noise or error rates. We propose an iterative Layer VQE (L-VQE) approach, inspired by the Variational Quantum Eigensolver (VQE). We present a large-scale numerical study, simulating circuits with up to 40 qubits and 352 parameters, that demonstrates the potential of the proposed approach. We evaluate quantum optimization heuristics on the problem of detecting multiple communities in networks, for which we introduce a novel qubit-frugal formulation. We numerically compare L-VQE with Quantum Approximate Optimization Algorithm (QAOA) and demonstrate that QAOA achieves lower approximation ratios while requiring significantly deeper circuits. We show that L-VQE is more robust to finite sampling errors and has a higher chance of finding the solution as compared with standard VQE approaches. Our simulation results show that L-VQE performs well under realistic hardware noise.

Finally, we propose to find other applications that utilize the Ising optimization model, finding novel formulations for different problems, and use the special-purpose hardware for optimization to achieve acceleration or better quality of the solution. We also propose to investigate further and improve the quantum approximate optimization algorithm. We propose using different strategies to reduce the quantum resources the algorithm uses and make it more possible to execute on near-term noisy quantum devices.