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

Abstract

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$.

21+4 pages, 6 figures, code online at https://nbviewer.jupyter.org/github/marwahaha/QuAIL-2021/blob/main/maxkxor.ipynb and https://nbviewer.jupyter.org/github/marwahaha/QuAIL-2021/blob/main/parisi.ipynb

References in corpus (6)

• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Algorithmic Thresholds in Mean Field Spin Glasses
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs

Cited by in corpus (13)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Challenges and Opportunities in Quantum Optimization
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Analytical Framework for Quantum Alternating Operator Ansätze
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Synergies Between Operations Research and Quantum Information Science
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems