Comparison of the AQO and the QAOA for the vertex coloring problem

Abstract

We benchmark the time resources needed to execute the adiabatic quantum optimization (AQO), and to run the Quantum Approximate Optimization Algorithm (QAOA), for the vertex coloring problem. This is done via a numerical simulation of 20 Erd˝os-R´eny random graphs for different cases ranging from 8 to 21 qubits. With this comparison, we explore two of the most important algorithms of the analog and gate-based quantum computing paradigms, respectively. We apply the canonical implementation for both algorithms, so their initial Hamiltonian is the same, the one with the typical sum of Pauli-X matrices. In this line, we consider linear scheduling time for the AQO. For final adiabatic time T = 100 ns, the AQO achieves an overlap with the degenerate solutions over 0.9 in all cases. Meanwhile, the QAOA using the Powell classical optimizer, 5 layers and thousands of iterations has an overlap around 0.5 for the 8 qubits case and below 0.25 for the other cases. So, our results for the given task and idealized conditions indicate that the AQO significantly outperforms the QAOA in terms of time and success probability