Optimizing ansatz design in QAOA for Max-Cut

A QAOA finds good approximate solutions to a combinatorial optimization problem. For a graph G=(V, E), |V|=n, |E|=m, a depth p QAOA for Max-Cut requires 2mp CNOT gates. CNOT being 100x more error-prone than single-qubit gates, we propose two hardware-independent methods to reduce the number of CNOT gates in the first iteration of a QAOA circuit for Max-Cut while retaining functional equivalence. First, we utilize Edge Coloring of the graph to minimize the depth and eliminate at most n/2 CNOT gates. Next, we employ Depth First Search (DFS) on the input graph to eliminate n-1 CNOT gates, but the depth of the circuit increases moderately. We derive analytically the criteria for which the reduction in CNOT gates overshadows this increase in depth, leading to an overall lower error probability. All existing IBM Quantum Hardware satisfy this criterion. Finally, we propose an O(\Delta.n^2) greedy algorithm, \Delta being the maximum degree of the graph, that finds a spanning tree of lower height, thus reducing the overall depth of the circuit while retaining the elimination of n-1 CNOT gates. We show that this algorithm achieves ~ 84.8% reduction in depth from the DFS method. Probable methods to scale this for higher p and for specific hardware topologies are under study.