Bounds on approximating Max $k$XOR with quantum and classical local algorithms

Understand

We consider the power of local algorithms for approximately solving Max $k$XOR, a generalization of two constraint satisfaction problems previously studied with classical and quantum algorithms (MaxCut and Max E3LIN2).

• In Max $k$XOR each constraint is the XOR of exactly $k$ variables and a parity bit.
• On instances with either random signs (parities) or no overlapping clauses and $D+1$ clauses per variable, we calculate the expected satisfying fraction of the depth-1 QAOA from Farhi et al [arXiv:1411.4028] and compare with a generalization of the local threshold algorithm from Hirvonen et al [arXiv:1402.2543].
• Notably, the quantum algorithm outperforms the threshold algorithm for $k > 4$.