  The Quantum Approximate Optimization Algorithm (QAOA) is a promising
candidate algorithm for demonstrating quantum advantage in optimization using
near-term quantum computers. However, QAOA has high requirements on gate
fidelity due to the need to encode the objective function in the phase
separating operator, requiring a large number of gates that potentially do not
match the hardware connectivity. Using the MaxCut problem as the target, we
demonstrate numerically that an easier way to implement an alternative phase
operator can be used in lieu of the phase operator encoding the objective
function, as long as the ground state is the same. We observe that if the
ground state energy is not preserved, the approximation ratio obtained by QAOA
with such phase separating operator is likely to decrease. Moreover, we show
that a better alignment of the low energy subspace of the alternative operator
leads to better performance. Leveraging these observations, we propose a
sparsification strategy that reduces the resource requirements of QAOA. We also
compare our sparsification strategy with some other classical graph
sparsification methods, and demonstrate the efficacy of our approach.
