Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond

Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu +1

We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph…