Towards optimal circuit construction for the quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) is used to approximately solve combinatorial optimization (CO) problems. In the algorithm, an operator known as the cost Hamiltonian $C$ is used to encode the details of the CO problem via quantum gates. The parameters of the algorithm are then optimized with respect to the expected value of $C$. In this work, we study how modifying the gate implementation aspect of $C$ (while calculating the expected value with the original $C$) can affect the output of QAOA. Specifically, we solve the MaxCut problem of a graph $G$ in with three types of changes to $C$: using a randomly generated $C$, using a random subgraph of $G$ to generate $C$, and a special case where we choose a subgraph of $G$ that has triangles removed. We derive an expected value formula using this modified $C$ and show numerically that in some cases this modification performs better than normal QAOA.