Quantum enhanced greedy solver for optimization problems

The quantum-classical algorithm systematically outperforms its classical counterpart, signaling a quantum enhancement with respect to its guaranteed output quality. Moreover, we observe an absolute performance comparable with the guarantees for a state-of-the-art semi-definite programming method.