  A canonical feature of the constraint satisfaction problems in NP is
approximation hardness, where in the worst case, finding sufficient-quality
approximate solutions is exponentially hard for all known methods.
Fundamentally, the lack of any guided local minimum escape method ensures both
exact and approximate classical approximation hardness, but the equivalent
mechanism(s) for quantum algorithms are poorly understood. For algorithms based
on Hamiltonian time evolution, we explore this question through the
prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms
for quantum exact and approximation hardness are fundamentally distinct. We
review known results from the literature, and identify mechanisms that make
conventional quantum methods (such as Adiabatic Quantum Computing) weak
approximation algorithms in the worst case. We construct a family of spectrally
filtered quantum algorithms that escape these issues, and develop analytical
theories for their performance. We show that, for random hypergraphs in the
approximation-hard regime, if we define the energy to be $E =
N_{\mathrm{unsat}}-N_{\mathrm{sat}}$, spectrally filtered quantum optimization
will return states with $E \leq q_m E_{\mathrm{GS}}$ (where $E_{\rm GS}$ is the
ground state energy) in sub-quadratic time, where conservatively, $q_m \simeq
0.59$. This is in contrast to $q_m \to 0$ for the hardest instances with
classical searches. We test all of these claims with extensive numerical
simulations. We do not claim that this approximation guarantee holds for all
possible hypergraphs, though our algorithm's mechanism can likely generalize
widely. These results suggest that quantum computers are more powerful for
approximate optimization than had been previously assumed.
