Quantum Speedup for the Maximum Cut Problem

Weng-Long Chang, Renata Wong, Wen-Yu Chung +3

Given an undirected, unweighted graph with $n$ vertices and $m$ edges, the maximum cut problem is to find a partition of the $n$ vertices into disjoint subsets $V_1$ and $V_2$ such…