  We develop new approximate compilation schemes that significantly reduce the
expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for
solving the Max-Cut problem. Our main focus is on compilation with trapped-ion
simulators using Pauli-$X$ operations and all-to-all Ising Hamiltonian
$H_\text{Ising}$ evolution generated by Molmer-Sorensen or optical dipole force
interactions, though some of our results also apply to standard gate-based
compilations. Our results are based on principles of graph sparsification and
decomposition; the former reduces the number of edges in a graph while
maintaining its cut structure, while the latter breaks a weighted graph into a
small number of unweighted graphs. Though these techniques have been used as
heuristics in various hybrid quantum algorithms, there have been no guarantees
on their performance, to the best of our knowledge. This work provides the
first provable guarantees using sparsification and decomposition to improve
quantum noise resilience and reduce quantum circuit complexity.
  For quantum hardware that uses edge-by-edge QAOA compilations, sparsification
leads to a direct reduction in circuit complexity. For trapped-ion quantum
simulators implementing all-to-all $H_\text{Ising}$ pulses, we show that for a
$(1-\epsilon)$ factor loss in the Max-Cut approximation ($\epsilon>0)$, our
compilations improve the (worst-case) number of $H_\text{Ising}$ pulses from
$O(n^2)$ to $O(n\log(n/\epsilon))$ and the (worst-case) number of Pauli-$X$ bit
flips from $O(n^2)$ to $O\left(\frac{n\log(n/\epsilon)}{\epsilon^2}\right)$ for
$n$-node graphs. We demonstrate significant reductions in noise are obtained in
our new compilation approaches using theory and numerical calculations for
trapped-ion hardware. We anticipate these approximate compilation techniques
will be useful tools in a variety of future quantum computing experiments.
