Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree

Abstract

We consider constraint satisfaction problems of bounded degree, with a good notion of "typicality", e.g. the negation of the variables in each constraint is taken independently at random. Using the quantum approximate optimization algorithm (QAOA), we show that $\mu +\Omega (1/\sqrt{D})$ fraction of the constraints can be satisfied for typical instances, with the assignment efficiently produced by QAOA. We do so by showing that the averaged fraction of constraints being satisfied is $\mu +\Omega (1/\sqrt{D})$, with small variance. Here $\mu$ is the fraction that would be satisfied by a uniformly random assignment, and $D$ is the number of constraints that each variable can appear. CSPs with typicality include Max-$k$XOR and Max-$k$SAT. We point out how it can be applied to determine the typical ground-state energy of some local Hamiltonians. We also give a similar result for instances with "no overlapping constraints", using the quantum algorithm. We sketch how the classical algorithm might achieve some partial result.

18 pages

References in corpus (3)

• A Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Extremal eigenvalues of local Hamiltonians

Cited by in corpus (14)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• qTorch: The Quantum Tensor Contraction Handler
• Analytical Framework for Quantum Alternating Operator Ansätze
• Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Evaluation of Parameterized Quantum Circuits with Cross-Resonance Pulse-Driven Entanglers
• Quantum computing through the lens of control: A tutorial introduction
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• QForte: an efficient state simulator and quantum algorithms library for molecular electronic structure
• Crosstalk-Based Parameterized Quantum Circuit Approximation
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers