Max-Cut QAOA Cost Hamiltonian Compilation for Unweighted Graphs Using Minimum Global Controls and Qubit Bit Flips
Saber Dinpazhouh · Rice Research Repository (Rice University) · 2025
We study an operation compilation problem, associated with the hybrid quantum-classical algorithm, QAOA, for the max-cut problem on trapped-ion quantum computers. As opposed to the standard $CNOT$ and $R_z$ gate compilation of the cost Hamiltonian for QAOA, here the goal is to compile it to global coupling operations and individual qubit bit flips. Rajakumar et al have proposed this compilation and showed such a compilation exists for any graph. To mitigate operation error a short sequence of operations is desired. In essence, the problem is a low-rank semi-discrete matrix decomposition for the adjacency matrix of a given graph. The lowest possible rank for this decomposition is known as the graph coupling number, $gc(G)$, where $G$ is the input graph. They gave a combinatorial construction, named union of stars, with the rank of at most $3n-2$ for any unweighted graph with n vertices. They gave an $\mathcal{O}(m)$ construction for weighted graphs as well. Here we focus solely on the unweighted graphs. We extract important theoretical properties of the problem. Utilizing these properties we prove the order-optimality of the union of stars algorithm for unweighted graphs by introducing a family of graphs with a lower bound of n - 1 on their gc number. Additionally, we decrease the theoretical upper bound from $3n - 2$ to $2.5n + 2$ for any unweighted graph with n vertices. For specific graph families like cliques, perfect matching graphs, paths, and cycles, we find tighter bounds. Additionally, we propose a compact mixed integer program (MIP) which is competitive against their MIP formulation which has exponential size in the input graph. We also discover a beautiful connection of the problem with the Hadamard matrices.