On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms

Using the prototypically hard MAX-3-XORSAT problem class, we explore the practical mechanisms for exact and approximate hardness, for both classical and quantum algorithms. We conclude that while both tasks are classically difficult for essentially the same reason, in the quantum case the mechanisms are distinct. We qualitatively identify why traditional methods (e.g. high depth QAOA) are not reliably good approximation algorithms. We propose a new method, called spectral folding, that does not suffer from these issues, and study it analytically and numerically. We show that, for random hypergraphs including extremal planted solution instances (where the ground state satisfies a much higher fraction of constraints than in truly random problems), if we define the energy to be $E = N_{unsat}-N_{sat}$, then spectral folding will return states with energy $E leq A E_{GS}$ in polynomial time, where conservatively, $A simeq 0.6$. We benchmark variations of spectral folding for random approximation-hard (planted partial solution) instances in simulation; our results support this prediction. We do not claim that this guarantee holds for all possible hypergraphs. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.