Approximate solution of MaxCut with low-depth Clifford circuits*

It has been conjectured that near-term quantum computers might offer a speedup in solving combinatorial optimization problems. Much work has been done exploring the extent to which this goal can be achieved via variational quantum algorithms, without very conclusive answers. A side product of this effort has been the construction of quantum-inspired algorithms. Improved or novel classical algorithms which exploit special structures of the problems under study unveiled by their quantum counterparts.  In this work we focus on the MaxCut problem and inspired by the solution circuits obtained with an adaptive variant of the quantum approximate optimization algorithm, we introduce a new quantum-inspired approximation algorithm, ADAPT-Clifford, for this problem. This algorithm is polynomial in the input both in time and space with worst case complexities O(N⁶) and O(N²), respectively. We implemented this algorithm and study its performance on different families of graphs. For positive edge weights we provide copious evidence that, up to hundreds of nodes, our algorithm produces a better approximate solution than the best classical algorithm, that of Goemans and Williamson. Our results then suggest a more resource-centric approach to the search for quantum speedup in solution of combinatorial optimization problems.