Towards Max-Cut QAOA with Trapped Ion Crystals

Applications of near-term quantum computing hardware like the quantum approximate optimization algorithm (QAOA) motivate a desire to map application-specific coupling graphs to the native coupling graph between physical qubits. We show that a pairwise all-to-all entangling operator naturally realized with trapped ion crystals can be leveraged to produce the cost function for any Max-Cut graph of interest. We describe a novel 'union-of-stars' construction method and compare the required resources to Max-Cut QAOA constructions on other quantum hardware. Finally, we present initial progress towards realizing this scheme in the laboratory.