An Approach for Combinatorial Optimization on Noisy Quantum Computers

Combinatorial optimization on near-term quantum devices is a promising path to demonstrating quantum advantage. However, the capabilities of these devices are constrained by high noise levels and limited error-mitigation. In this paper, we propose an iterative Layer-VQE (L-VQE) approach, inspired by Variational Quantum Eigensolver. 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 to QAOA, and demonstrate that QAOA achieves lower approximation ratios while requiring significantly deeper circuits. We show that L-VQE is more robust to sampling noise and has a higher chance of finding the solution, as compared to standard approaches. Our simulation results show that L-VQE performs well under realistic hardware noise.