English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the power of local algorithms for approximately solving Max$k$XOR, a generalization of two constraint satisfaction problems previouslystudied 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. Oninstances with either random signs (parities) or no overlapping clauses and$D+1$ clauses per variable, we calculate the expected satisfying fraction ofthe depth-1 QAOA from Farhi et al [arXiv:1411.4028] and compare with ageneralization of the local threshold algorithm from Hirvonen et al[arXiv:1402.2543]. Notably, the quantum algorithm outperforms the thresholdalgorithm for $k > 4$.  On the other hand, we highlight potential difficulties for the QAOA toachieve computational quantum advantage on this problem. We first compute atight upper bound on the maximum satisfying fraction of nearly all large randomregular Max $k$XOR instances by numerically calculating the ground state energydensity $P(k)$ of a mean-field $k$-spin glass [arXiv:1606.02365]. The upperbound grows with $k$ much faster than the performance of both one-localalgorithms. We also identify a new obstruction result for low-depth quantumcircuits (including the QAOA) when $k=3$, generalizing a result of Bravyi et al[arXiv:1910.08980] when $k=2$. We conjecture that a similar obstruction existsfor all $k$.

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