Paper

Bounds on approximating Max \\(k\\)XOR with quantum and classical local algorithms

Hadfield, Stuart, Marwaha, Kunal

2022

Overview

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\\). On the other hand, we highlight potential difficulties for the QAOA to achieve computational quantum advantage on this problem. We first compute a tight upper bound on the maximum satisfying fraction of nearly all large random regular Max \\(k\\)XOR instances by numerically calculating the ground state energy density \\(P(k)\\) of a mean-field \\(k\\)-spin glass [arXiv:1606.02365]. The upper bound grows with \\(k\\) much faster than the performance of both one-local algorithms. We also identify a new obstruction result for low-depth quantum circuits (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 exists for all \\(k\\).

• Publisher: Cornell University Library, arXiv.org
• Subject: Algorithms / Flux density / Mathematical analysis / Spin glasses / Upper bounds